DBScholar

Back to papers

An Optimal and Progressive Algorithm for Skyline Queries

Summary: BBS: a branch-and-bound progressive skyline algorithm using NN search; IO-optimal with a single R-tree access and no duplicates. Analysis and experiments show BBS outperforms NN by orders of magnitude across distributions and supports multiple skyline queries. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h8b59d3eb0935065f
Venue
SIGMOD
Year
2003
Pagerank
0.00015338893
Overall Rank
638 | 95.72%
DOI
10.1145/872757.872814

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{papadias_sigmod03,
        title = {{An Optimal and Progressive Algorithm for Skyline Queries}},
        author = {Papadias, Dimitris and Tao, Yufei and Fu, Greg and Seeger, Bernhard},
        series = {{SIGMOD} '03},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/872757.872814},
        url = {https://dl.acm.org/doi/10.1145/872757.872814},
        year = {2003}
}

Incoming Citations (Sorted by Pagerank)

Showing 32 of 32 citing papers.

Rank Citing Paper Year Venue Pagerank
817 Finding k-Dominant Skylines in High Dimensional Space 2006 SIGMOD 0.00013672764
1,124 Probabilistic Skylines on Uncertain Data 2007 VLDB 0.00011927351
1,213 Maximal Vector Computation in Large Data Sets 2005 VLDB 0.00011512468
1,394 Efficient Computation of the Skyline Cube 2005 VLDB 0.00010796403
1,643 Relaxing Join and Selection Queries 2006 VLDB 0.00010006399
1,892 Efficient Computation of Reverse Skyline Queries 2007 VLDB 9.4166991e-05
2,357 Catching the Best Views of Skyline: A Semantic Approach Based on Decisive Subspaces 2005 VLDB 8.5820096e-05
2,491 Efficient Skyline Computation over Low-Cardinality Domains 2007 VLDB 8.3921786e-05
2,566 Stratified Computation of Skylines with Partially-Ordered Domains 2005 SIGMOD 8.288424e-05
2,786 DADA: A Data Cube for Dominant Relationship Analysis 2006 SIGMOD 8.0165674e-05
2,996 Multi-objective Query Processing for Database Systems 2004 VLDB 7.7697801e-05
3,192 Monochromatic and Bichromatic Reverse Skyline Search over Uncertain Databases 2008 SIGMOD 7.5512396e-05
3,318 Skyline Community Search in Multi-valued Networks 2018 SIGMOD 7.4324312e-05
3,340 Refreshing the Sky: The Compressed Skycube with Efficient Support for Frequent Updates 2006 SIGMOD 7.4080086e-05
4,252 Primitives for Workload Summarization and Implications for SQL 2003 VLDB 6.7015609e-05
4,705 Context-Sensitive Ranking 2006 SIGMOD 6.4591302e-05
5,072 ProgXe: Progressive Result Generation Framework for Multi-Criteria Decision Support Queries 2010 SIGMOD 6.2870709e-05
5,548 Efficient Skyline Querying with Variable User Preferences on Nominal Attributes 2008 VLDB 6.0882467e-05
6,012 Call to Order: A Hierarchical Browsing Approach to Eliciting Users' Preference 2010 SIGMOD 5.9143092e-05
6,579 Parallel Computation of Skyline and Reverse Skyline Queries Using MapReduce 2013 VLDB 5.7446105e-05
6,601 Efficient Parallel Skyline Processing using Hyperplane Projections 2011 SIGMOD 5.7397409e-05
6,745 Categorical Skylines for Streaming Data 2008 SIGMOD 5.6908052e-05
8,479 Skyline Operator on Anti-correlated Distributions 2013 VLDB 5.3332727e-05
8,547 Discovering the Skyline of Web Databases 2016 VLDB 5.3171862e-05
9,499 QSkycube: Efficient Skycube Computation Using Point-Based Space Partitioning 2011 VLDB 5.1708619e-05
9,543 FHL-Cube: Multi-Constraint Shortest Path Querying with Flexible Combination of Constraints 2022 VLDB 5.1614165e-05
11,541 Directional Queries: Making Top-k Queries More Effective in Discovering Relevant Results 2024 SIGMOD 4.9793485e-05
12,420 Processing of Probabilistic Skyline Queries Using MapReduce 2015 VLDB 4.9793485e-05
12,565 eSkyline: Processing Skyline Queries over Encrypted Data 2013 VLDB 4.9793485e-05
12,691 ZINC: Efficient Indexing for Skyline Computation 2011 VLDB 4.9793485e-05
12,788 Minimizing the Communication Cost for Continuous Skyline Maintenance 2009 SIGMOD 4.9793485e-05
12,962 On Dominating Your Neighborhood Profitably 2007 VLDB 4.9793485e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0011405675
28 Nearest Neighbor Queries 1995 SIGMOD 0.00051312804
256 Efficient Progressive Skyline Computation 2001 VLDB 0.00022981799
313 Shooting Stars in the Sky: An Online Algorithm for Skyline Queries 2002 VLDB 0.00021311041
342 The Onion Technique: Indexing for Linear Optimization Queries 2000 SIGMOD 0.00020530255
412 Fuzzy Queries in Multimedia Database Systems 1998 PODS 0.00018694414
418 PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries 2001 SIGMOD 0.00018617842
507 Supporting Incremental Join Queries on Ranked Inputs 2001 VLDB 0.00017101297
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 12,962 On Dominating Your Neighborhood Profitably 2007 VLDB
2 3,340 Refreshing the Sky: The Compressed Skycube with Efficient Support for Frequent Updates 2006 SIGMOD
3 5,590 Scalable Skyline Computation Using Object-based Space Partitioning 2009 SIGMOD
4 576 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD
5 5,144 On Finding Skylines in External Memory 2011 PODS
6 3,478 Approaching the Skyline in Z Order 2007 VLDB
7 2,740 The Spatial Skyline Queries 2006 VLDB
8 2,566 Stratified Computation of Skylines with Partially-Ordered Domains 2005 SIGMOD
9 256 Efficient Progressive Skyline Computation 2001 VLDB
10 1,892 Efficient Computation of Reverse Skyline Queries 2007 VLDB