A practical approach for efficiently answering top-k relational queries
Authors: Ayanso, Anteneh; Goes, Paulo B.; Mehta, Kumar
Journal: Decision Support Systems (2007)
DOI: 10.1016/j.dss.2007.04.005
An increasing number of application areas now rely on obtaining the “best matches” to a given query as opposed to exact matches sought by traditional transactions. This type of exploratory querying (also called top-k querying) can significantly improve the performance of web-based applications such as consumer reviews, price comparisons and recommendations for products/ services. Due to the lack of support for specialized indexes and/or data structures in relational database management systems (RDBMSs), recent research has focused on utilizing summary statistics (histograms) maintained by RDBMSs for translating the top-k request into a traditional range query. Because the RDBMS query engines are already optimized for execution of range queries, such approach has both practical as well as efficiency advantages. In this paper, we review the strengths and weaknesses of common histogram construction techniques with regard to their structural characteristics, accuracy in approximating the true distribution of the underlying data, and implications for top-k retrieval. We also present our top-k retrieval strategy (Query-Level Optimal Cost Strategy — QLOCS) and demonstrate its “histogram-…