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.00020520649
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.00018609134
638 An Optimal and Progressive Algorithm for Skyline Queries 2003 SIGMOD 0.00015331662
962 RankSQL: Query Algebra and Optimization for Relational Top-k Queries 2005 SIGMOD 0.00012818013
1,087 Regret-Minimizing Representative Databases 2010 VLDB 0.00012092041
1,379 Designing Fair Ranking Schemes 2019 SIGMOD 0.00010859038
1,441 Continuous Monitoring of Top-k Queries over Sliding Windows 2006 SIGMOD 0.00010638056
1,773 Rank-aware Query Optimization 2004 SIGMOD 9.6683429e-05
2,106 Computing k-Regret Minimizing Sets 2014 VLDB 9.0287481e-05
2,485 Processing a Large Number of Continuous Preference Top-k Queries 2012 SIGMOD 8.3954142e-05
2,545 Interactive Regret Minimization 2012 SIGMOD 8.3139128e-05
2,561 Answering Top-k Queries Using Views 2006 VLDB 8.2940439e-05
2,621 Ranking with Uncertain Scoring Functions: Semantics and Sensitivity Measures 2011 SIGMOD 8.2130891e-05
2,958 Answering Why-not Questions on Reverse Top-k Queries 2015 VLDB 7.80653e-05
3,070 Towards Robust Indexing for Ranked Queries 2006 VLDB 7.6831067e-05
3,380 Ad-hoc Top-k Query Answering for Data Streams 2007 VLDB 7.353368e-05
4,616 Branch-and-Bound Algorithm for Reverse Top-k Queries 2013 SIGMOD 6.4983802e-05
4,651 Answering Top-k Queries with Multi-Dimensional Selections: The Ranking Cube Approach 2006 VLDB 6.4836419e-05
4,833 Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative 2017 SIGMOD 6.3867086e-05
5,071 Efficient k-Regret Query Algorithm with Restriction-free Bound for any Dimensionality 2018 SIGMOD 6.2863925e-05
5,275 Efficient Approximation of Optimization Queries Under Parametric Aggregation Constraints 2003 VLDB 6.1985695e-05
5,487 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 6.1085184e-05
5,611 On Obtaining Stable Rankings 2019 VLDB 6.0657421e-05
5,788 k-Regret Queries with Nonlinear Utilities 2015 VLDB 5.9926479e-05
5,916 Reverse k-Ranks Query 2014 VLDB 5.9472799e-05
6,178 Exact Processing of Uncertain Top-k Queries in Multi-criteria Settings 2018 VLDB 5.8581814e-05
6,382 Maximum Rank Query 2015 VLDB 5.805942e-05
6,721 RRR: Rank-Regret Representative 2019 SIGMOD 5.6966108e-05
6,761 Marrying Top-k with Skyline Queries: Relaxing the Preference Input while Producing Output of Controllable Size 2021 SIGMOD 5.6873442e-05
6,972 Global Immutable Region Computation 2014 SIGMOD 5.6281923e-05
7,329 Anytime Measures for Top-k Algorithms 2007 VLDB 5.5485926e-05
7,396 Efficient and Generic Evaluation of Ranked Queries 2011 SIGMOD 5.5344583e-05
7,456 Strongly Truthful Interactive Regret Minimization 2019 SIGMOD 5.5209079e-05
7,733 Database Support for Matching: Limitations and Opportunities 2006 SIGMOD 5.4633844e-05
7,964 Computing Immutable Regions for Subspace Top-k Queries 2013 VLDB 5.4143673e-05
8,809 Geometric Approaches for Top-k Queries 2017 VLDB 5.2711392e-05
9,002 Creating Top Ranking Options in the Continuous Option and Preference Space 2019 VLDB 5.23944e-05
9,181 Determining the Impact Regions of Competing Options in Preference Space 2017 SIGMOD 5.2115802e-05
9,298 A General Framework for Modeling and Processing Optimization Queries 2007 VLDB 5.1997281e-05
9,707 Towards Indexing Functions: Answering Scalar Product Queries 2014 SIGMOD 5.1357527e-05
10,091 On m-Impact Regions and Standing Top-k Influence Problems 2021 SIGMOD 5.0806786e-05
11,547 Directional Queries: Making Top-k Queries More Effective in Discovering Relevant Results 2024 SIGMOD 4.9769913e-05
11,880 tau-LevelIndex: Towards Efficient Query Processing in Continuous Preference Space 2022 SIGMOD 4.9769913e-05
12,156 Top-k Queries over Digital Traces 2019 SIGMOD 4.9769913e-05
12,382 Query Reranking As A Service 2016 VLDB 4.9769913e-05
12,628 Answering Top-k Queries Over a Mixture of Attractive and Repulsive Dimensions 2012 VLDB 4.9769913e-05
12,660 FIFO Indexes for Decomposable Problems 2011 PODS 4.9769913e-05
12,840 A Fair Assignment Algorithm for Multiple Preference Queries 2009 VLDB 4.9769913e-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
413 Fuzzy Queries in Multimedia Database Systems 1998 PODS 0.00018686769
886 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.00013253709
1,239 Processing Queries By Linear Constraints 1997 PODS 0.00011391184
1,590 Efficient Searching with Linear Constraints (Extended Abstract) 1998 PODS 0.00010134811
Previous Page 1 / 1 Next

Semantically Similar Papers