Article
Efficient Processing of Exact Top-k Queries over Disk-Resident Sorted Lists
VLDB Journal
Publication Type
Journal Article
Version
submittedVersion
Publication Date
6-2010
Abstract
The top-k query is employed in a wide range of applications to generate a ranked list of data that have the highest aggregate scores over certain attributes. As the pool of attributes for selection by individual queries may be large, the data are indexed with per-attribute sorted lists, and a threshold algorithm (TA) is applied on the lists involved in each query. The TA executes in two phases--find a cut-off threshold for the top-k result scores, then evaluate all the records that could score above the threshold. In this paper, we focus on exact top-k queries that involve monotonic linear scoring functions over disk-resident sorted lists. We introduce a model for estimating the depths to which each sorted list needs to be processed in the two phases, so that (most of) the required records can be fetched efficiently through sequential or batched I/Os. We also devise a mechanism to quickly rank the data that qualify for the query answer and to eliminate those that do not, in order to reduce the computation demand of the query processor. Extensive experiments with four different datasets confirm that our schemes achieve substantial performance speed-up of between two times and two orders of magnitude over existing TAs, at the expense of a memory overhead of 4.8 bits per attribute value. Moreover, our scheme is robust to different data distributions and query characteristics.
Identifier
10.1007/s00778-009-0174-x
Publisher
Springer Verlag
Creative Commons License
Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International
Additional URL
http://dx.doi.org/10.1007/s00778-009-0174-x
Citation Information
Hwee Hwa PANG, Xuhua DING and Baihua ZHENG. "Efficient Processing of Exact Top-k Queries over Disk-Resident Sorted Lists" VLDB Journal Vol. 19 Iss. 3 (2010) p. 437 - 456 ISSN: 1066-8888 Available at: http://works.bepress.com/hweehwa-pang/68/