Dominant Graph: An Efficient Indexing Structure to Answer Top-K Queries
- 1 April 2008
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636382,p. 536-545
Abstract
Given a record set D and a query score function F, a top-k query returns k records from D, whose values of function F on their attributes are the highest. In this paper, we investigate the intrinsic connection between top-k queries and dominant relationship between records, and based on which, we propose an efficient layer-based indexing structure, Dominant Graph (DG), to improve the query efficiency. Specifically, DG is built offline to express the dominant relationship between records and top-k query is implemented as a graph traversal problem, i.e. Traveler algorithm. We prove theoretically that the size of search space (that is the number of retrieved records from the record set to answer top-k query) in our basic algorithm is directly related to the cardinality of skyline points in the record set (see Theorem 3.2). Based on the cost analysis, we propose the optimization technique, pseudo record, to improve the search efficiency. In order to handle the top-k query in the high dimension record set, we also propose N-Way Traveler algorithm. Finally, extensive experiments demonstrate that our proposed methods have significant improvement over its counterparts, including both classical and state art of top-k algorithms. For example, the search space in our algorithm is less than 1/5 of that in AppRI (Xin et al., 2006), one of state art of top-k algorithms. Furthermore, our method can support any aggregate monotone query function.Keywords
This publication has 13 references indexed in Scilit:
- Top-k Query Processing in Uncertain Databases2007
- Efficient Aggregation of Ranked Inputs2006
- Robust Cardinality and Cost Estimation for Skyline Operator2006
- RankSQL2005
- Efficient Processing of Ranked Queries with Sweeping SelectionLecture Notes in Computer Science, 2005
- Supporting Top-k Join Queries in Relational Databases2003
- Top- k selection queries over relational databasesACM Transactions on Database Systems, 2002
- Optimal aggregation algorithms for middleware2001
- Query processing issues in image (multimedia) databases1999
- The quickhull algorithm for convex hullsACM Transactions on Mathematical Software, 1996