DBScholar

Back to papers

The Onion Technique: Indexing for Linear Optimization Queries

Summary: Introduces Onion indexing, a layered convex-hull based index for linear optimization queries (top-N under linear weights). Queries are evaluated from outer hulls inward, enabling progressive retrieval and orders-of-magnitude speedups over scans for small N; supports hierarchical/global-local data organization. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h85e9f47d8c95f675
Venue
SIGMOD
Year
2000
Pagerank
0.00020530255
Overall Rank
342 | 97.71%
DOI
10.1145/342009.335433

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{chang_sigmod00,
        title = {{The Onion Technique: Indexing for Linear Optimization Queries}},
        author = {Chang, Yuan-Chi and Bergman, Lawrence and Castelli, Vittorio and Li, Chung-Sheng and Lo, Ming-Ling and Smith, John R.},
        series = {{SIGMOD} '00},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/342009.335433},
        url = {https://dl.acm.org/doi/10.1145/342009.335433},
        year = {2000}
}

Incoming Citations (Sorted by Pagerank)

Showing 47 of 47 citing papers.

Rank Citing Paper Year Venue Pagerank
418 PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries 2001 SIGMOD 0.00018617842
638 An Optimal and Progressive Algorithm for Skyline Queries 2003 SIGMOD 0.00015338893
961 RankSQL: Query Algebra and Optimization for Relational Top-k Queries 2005 SIGMOD 0.0001282305
1,087 Regret-Minimizing Representative Databases 2010 VLDB 0.00012097722
1,379 Designing Fair Ranking Schemes 2019 SIGMOD 0.0001086418
1,439 Continuous Monitoring of Top-k Queries over Sliding Windows 2006 SIGMOD 0.00010642846
1,773 Rank-aware Query Optimization 2004 SIGMOD 9.6719067e-05
2,105 Computing k-Regret Minimizing Sets 2014 VLDB 9.0330207e-05
2,485 Processing a Large Number of Continuous Preference Top-k Queries 2012 SIGMOD 8.3993865e-05
2,545 Interactive Regret Minimization 2012 SIGMOD 8.3178501e-05
2,561 Answering Top-k Queries Using Views 2006 VLDB 8.2977193e-05
2,620 Ranking with Uncertain Scoring Functions: Semantics and Sensitivity Measures 2011 SIGMOD 8.2168186e-05
2,955 Answering Why-not Questions on Reverse Top-k Queries 2015 VLDB 7.8102237e-05
3,068 Towards Robust Indexing for Ranked Queries 2006 VLDB 7.6867401e-05
3,379 Ad-hoc Top-k Query Answering for Data Streams 2007 VLDB 7.3568458e-05
4,614 Branch-and-Bound Algorithm for Reverse Top-k Queries 2013 SIGMOD 6.5014577e-05
4,648 Answering Top-k Queries with Multi-Dimensional Selections: The Ranking Cube Approach 2006 VLDB 6.4867043e-05
4,831 Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative 2017 SIGMOD 6.3897334e-05
5,068 Efficient k-Regret Query Algorithm with Restriction-free Bound for any Dimensionality 2018 SIGMOD 6.2893698e-05
5,269 Efficient Approximation of Optimization Queries Under Parametric Aggregation Constraints 2003 VLDB 6.2014805e-05
5,482 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 6.111411e-05
5,610 On Obtaining Stable Rankings 2019 VLDB 6.0686149e-05
5,786 k-Regret Queries with Nonlinear Utilities 2015 VLDB 5.9954861e-05
5,913 Reverse k-Ranks Query 2014 VLDB 5.9500931e-05
6,176 Exact Processing of Uncertain Top-k Queries in Multi-criteria Settings 2018 VLDB 5.8609559e-05
6,378 Maximum Rank Query 2015 VLDB 5.8086918e-05
6,716 RRR: Rank-Regret Representative 2019 SIGMOD 5.6993087e-05
6,756 Marrying Top-k with Skyline Queries: Relaxing the Preference Input while Producing Output of Controllable Size 2021 SIGMOD 5.6900378e-05
6,971 Global Immutable Region Computation 2014 SIGMOD 5.6308579e-05
7,327 Anytime Measures for Top-k Algorithms 2007 VLDB 5.5512161e-05
7,394 Efficient and Generic Evaluation of Ranked Queries 2011 SIGMOD 5.5370795e-05
7,452 Strongly Truthful Interactive Regret Minimization 2019 SIGMOD 5.5235226e-05
7,727 Database Support for Matching: Limitations and Opportunities 2006 SIGMOD 5.4659695e-05
7,961 Computing Immutable Regions for Subspace Top-k Queries 2013 VLDB 5.4167814e-05
8,801 Geometric Approaches for Top-k Queries 2017 VLDB 5.2735579e-05
8,993 Creating Top Ranking Options in the Continuous Option and Preference Space 2019 VLDB 5.2419215e-05
9,172 Determining the Impact Regions of Competing Options in Preference Space 2017 SIGMOD 5.2140475e-05
9,288 A General Framework for Modeling and Processing Optimization Queries 2007 VLDB 5.2021887e-05
9,702 Towards Indexing Functions: Answering Scalar Product Queries 2014 SIGMOD 5.1381851e-05
10,086 On m-Impact Regions and Standing Top-k Influence Problems 2021 SIGMOD 5.0830849e-05
11,541 Directional Queries: Making Top-k Queries More Effective in Discovering Relevant Results 2024 SIGMOD 4.9793485e-05
11,874 tau-LevelIndex: Towards Efficient Query Processing in Continuous Preference Space 2022 SIGMOD 4.9793485e-05
12,150 Top-k Queries over Digital Traces 2019 SIGMOD 4.9793485e-05
12,376 Query Reranking As A Service 2016 VLDB 4.9793485e-05
12,622 Answering Top-k Queries Over a Mixture of Attractive and Repulsive Dimensions 2012 VLDB 4.9793485e-05
12,654 FIFO Indexes for Decomposable Problems 2011 PODS 4.9793485e-05
12,834 A Fair Assignment Algorithm for Multiple Preference Queries 2009 VLDB 4.9793485e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank Cited Paper Year Venue Pagerank
412 Fuzzy Queries in Multimedia Database Systems 1998 PODS 0.00018694414
886 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.0001325914
1,237 Processing Queries By Linear Constraints 1997 PODS 0.00011396286
1,589 Efficient Searching with Linear Constraints (Extended Abstract) 1998 PODS 0.00010139591
Previous Page 1 / 1 Next

Semantically Similar Papers