Efficient Skyline and Top-k Retrieval in Subspaces
Authors:
- 25 June 2007
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 19 (8) , 1072-1088
Abstract
Skyline and top-k queries are two popular operations for preference retrieval. In practice, applications that require these operations usually provide numerous candidate attributes, whereas, depending on their interests, users may issue queries regarding different subsets of the dimensions. The existing algorithms are inadequate for subspace skyline/top-k search because they have at least one of the following defects: 1) they require scanning the entire database at least once, 2) they are optimized for one subspace but incur significant overhead for other subspaces, or 3) they demand expensive maintenance cost or space consumption. In this paper, we propose a technique SUBSKY, which settles both types of queries by using purely relational technologies. The core of SUBSKY is a transformation that converts multidimensional data to one-dimensional (1D) values. These values are indexed by a simple B-tree, which allows us to answer subspace queries by accessing a fraction of the database. SUBSKY entails low maintenance overhead, which equals the cost of updating a traditional B-tree. Extensive experiments with real data confirm that our technique outperforms alternative solutions significantly in both efficiency and scalability.Keywords
This publication has 25 references indexed in Scilit:
- Branch-and-bound processing of ranked queriesInformation Systems, 2007
- Finding k-dominant skylines in high dimensional space2006
- Skyline Queries Against Mobile Lightweight Devices in MANETs2006
- Skyline with presorting2004
- Algorithms and applications for answering ranked queries using ranked viewsThe VLDB Journal, 2004
- Skyline Cardinality for Relational Processing2004
- Shooting Stars in the Sky2002
- The onion techniqueACM SIGMOD Record, 2000
- Distance browsing in spatial databasesACM Transactions on Database Systems, 1999
- Combining fuzzy information from multiple systems (extended abstract)1996