Range query estimation with data skewness for top-k retrieval

Top-k querying can significantly improve the performance of web-based business intelligence applications such as price comparison and product recommendation systems. Top-k retrieval involves finding a limited number of records in a relational database that are most similar to user-specified attribute-value pairs. This paper extends the cost-based query-mapping method for top-k retrieval by incorporating data skewness in range estimation. Experiments on real world and synthetic multi-attribute data sets show that incorporating data skewness provides a robust performance across different types of data sets, query sets, distance functions, and histograms. (C) 2013 Elsevier B.V. All rights reserved.