|
|
|
     |
                                     |
Return to Spatial and Nearest Neighbor Queries
2, multiple accesses of the same node, large space overhead). In this paper we develop BBS (branch-and-bound skyline), a progressive algorithm also based on nearest neighbor search, which is IO optimal, i.e., it performs a single access only to those R-tree nodes that may contain skyline points. Furthermore, it does not retrieve duplicates and its space overhead is significantly smaller than that of NN. Finally, BBS is simple to implement and can be efficiently applied to a variety of alternative skyline queries. An analytical and experimental comparison shows that BBS outperforms NN (usually by orders of magnitude) under all problem instances.
@inproceedings {DBLP:conf/sigmod/PapadiasTFS03, author = {Dimitris Papadias and Yufei Tao and Greg Fu and Bernhard Seeger}, booktitle = {SIGMOD Conference}, title = {An Optimal and Progressive Algorithm for Skyline Queries.}, pages = {467-478}, year = {2003}, url = {db/conf/sigmod/sigmod2003.html#PapadiasTFS03}, ee = {http://www.acm.org/sigmod/sigmod03/eproceedings/papers/r17p04.pdf}, crossref = {conf/sigmod/2003}, bibsource = {DBLP, http://dblp.uni-trier.de} }  ©2004 Association for Computing Machinery |
