Full Citation

Title: Efficient Skyline and Top-k Retrieval in Subspaces

Citation Type: Miscellaneous

Publication Year: 2007

ISBN:

ISSN:

DOI: 10.1109/TKDE.2007.1051

NSFID:

PMCID:

PMID:

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.

Url: http://ieeexplore.ieee.org/document/4262537/

User Submitted?: No

Authors: Tao, Yufei; Xiao, Xiaokui; Pei, Jian

Publisher: IEEE Educational Activities Department

Data Collections: IPUMS USA

Topics: Population Data Science

Countries: United States