SAQR: An efficient scheme for similarity-aware query refinement

Abdullah Albarrak, Mohamed A. Sharaf, Xiaofang Zhou

Research output: Contribution to journalConference articlepeer-review

3 Citations (Scopus)


Query refinement techniques enable database systems to automatically adjust a submitted query so that its result satisfies some specified constraints. While current techniques are fairly successful in generating refined queries based on cardinality constraints, they are rather oblivious to the (dis)similarity between the input query and its corresponding refined version. Meanwhile, enforcing a similarity-aware query refinement is a rather challenging task as it would require an exhaustive examination of the large space of possible query refinements. To address this challenge, we propose a novel scheme for efficient Similarity-aware Query Refinement (SAQR). SAQR aims to balance the tradeoff between satisfying the cardinality and similarity constraints imposed on the refined query so that to maximize its overall benefit to the user. To achieve that goal, SAQR implements efficient strategies to minimize the costs incurred in exploring the available search space. In particular, SAQR utilizes both similarity-based and cardinality-based pruning techniques to bound the search space and quickly find a refined query that meets the user expectations. Our experimental evaluation shows the scalability exhibited by SAQR under various workload settings, and the significant benefits it provides.

Original languageEnglish
Pages (from-to)110-125
Number of pages16
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8421 LNCS
Issue numberPART 1
Publication statusPublished - 2014
Externally publishedYes
Event19th International Conference on Database Systems for Advanced Applications, DASFAA 2014 - Bali, Indonesia
Duration: Apr 21 2014Apr 24 2014

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'SAQR: An efficient scheme for similarity-aware query refinement'. Together they form a unique fingerprint.

Cite this