|
|
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: they (i) require scanning the entire database at least once; (ii)
are optimized for one subspace but incur significant overhead for other
subspaces; (iii) demand expensive maintenance cost or space consumption.
In this paper, we propose a technique, SUBSKY, which settles both
types of queries using purely relational technologies. The core of SUBSKY
is a transformation that converts multidimensional data to 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.
|
|
