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
3263
Venue
SIGMOD
Year
2000
Pagerank
0.0002089582
Overall Rank
333 | 97.72%
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
407 PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries 2001 SIGMOD 0.00019021441
623 An Optimal and Progressive Algorithm for Skyline Queries 2003 SIGMOD 0.00015684963
973 RankSQL: Query Algebra and Optimization for Relational Top-k Queries 2005 SIGMOD 0.00012874284
1,072 Regret-Minimizing Representative Databases 2010 VLDB 0.0001230281
1,513 Continuous Monitoring of Top-k Queries over Sliding Windows 2006 SIGMOD 0.00010530872
1,597 Designing Fair Ranking Schemes 2019 SIGMOD 0.00010246472
1,759 Rank-aware Query Optimization 2004 SIGMOD 9.8160244e-05
2,063 Computing k-Regret Minimizing Sets 2014 VLDB 9.2399169e-05
2,427 Processing a Large Number of Continuous Preference Top-k Queries 2012 SIGMOD 8.5915976e-05
2,491 Interactive Regret Minimization 2012 SIGMOD 8.5086491e-05
2,525 Answering Top-k Queries Using Views 2006 VLDB 8.4653166e-05
2,571 Ranking with Uncertain Scoring Functions: Semantics and Sensitivity Measures 2011 SIGMOD 8.4029939e-05
2,895 Answering Why-not Questions on Reverse Top-k Queries 2015 VLDB 7.9829449e-05
3,007 Towards Robust Indexing for Ranked Queries 2006 VLDB 7.8583548e-05
3,317 Ad-hoc Top-k Query Answering for Data Streams 2007 VLDB 7.5251856e-05
4,514 Branch-and-Bound Algorithm for Reverse Top-k Queries 2013 SIGMOD 6.6500719e-05
4,587 Answering Top-k Queries with Multi-Dimensional Selections: The Ranking Cube Approach 2006 VLDB 6.6170389e-05
4,727 Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative 2017 SIGMOD 6.5362946e-05
4,939 Efficient k-Regret Query Algorithm with Restriction-free Bound for any Dimensionality 2018 SIGMOD 6.4336325e-05
5,164 Efficient Approximation of Optimization Queries Under Parametric Aggregation Constraints 2003 VLDB 6.3372067e-05
5,465 On Obtaining Stable Rankings 2019 VLDB 6.2075408e-05
5,593 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 6.1552328e-05
5,654 k-Regret Queries with Nonlinear Utilities 2015 VLDB 6.1330869e-05
5,796 Reverse k-Ranks Query 2014 VLDB 6.0859929e-05
6,052 Exact Processing of Uncertain Top-k Queries in Multi-criteria Settings 2018 VLDB 5.9941393e-05
6,249 Maximum Rank Query 2015 VLDB 5.9418925e-05
6,592 RRR: Rank-Regret Representative 2019 SIGMOD 5.830041e-05
6,636 Marrying Top-k with Skyline Queries: Relaxing the Preference Input while Producing Output of Controllable Size 2021 SIGMOD 5.8172769e-05
6,830 Global Immutable Region Computation 2014 SIGMOD 5.759977e-05
7,185 Anytime Measures for Top-k Algorithms 2007 VLDB 5.6779179e-05
7,299 Efficient and Generic Evaluation of Ranked Queries 2011 SIGMOD 5.6513289e-05
7,305 Strongly Truthful Interactive Regret Minimization 2019 SIGMOD 5.6501646e-05
7,584 Database Support for Matching: Limitations and Opportunities 2006 SIGMOD 5.5913983e-05
7,806 Computing Immutable Regions for Subspace Top-k Queries 2013 VLDB 5.5407909e-05
8,665 Geometric Approaches for Top-k Queries 2017 VLDB 5.3884685e-05
8,825 Creating Top Ranking Options in the Continuous Option and Preference Space 2019 VLDB 5.3616725e-05
9,010 Determining the Impact Regions of Competing Options in Preference Space 2017 SIGMOD 5.3333957e-05
9,115 A General Framework for Modeling and Processing Optimization Queries 2007 VLDB 5.3215443e-05
9,525 Towards Indexing Functions: Answering Scalar Product Queries 2014 SIGMOD 5.2555551e-05
9,900 On m-Impact Regions and Standing Top-k Influence Problems 2021 SIGMOD 5.1997534e-05
11,199 Directional Queries: Making Top-k Queries More Effective in Discovering Relevant Results 2024 SIGMOD 5.093636e-05
11,565 tau-LevelIndex: Towards Efficient Query Processing in Continuous Preference Space 2022 SIGMOD 5.093636e-05
11,850 Top-k Queries over Digital Traces 2019 SIGMOD 5.093636e-05
12,083 Query Reranking As A Service 2016 VLDB 5.093636e-05
12,331 Answering Top-k Queries Over a Mixture of Attractive and Repulsive Dimensions 2012 VLDB 5.093636e-05
12,363 FIFO Indexes for Decomposable Problems 2011 PODS 5.093636e-05
12,544 A Fair Assignment Algorithm for Multiple Preference Queries 2009 VLDB 5.093636e-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
402 Fuzzy Queries in Multimedia Database Systems 1998 PODS 0.00019072958
864 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.00013522522
1,219 Processing Queries By Linear Constraints 1997 PODS 0.00011620957
1,561 Efficient Searching with Linear Constraints (Extended Abstract) 1998 PODS 0.00010361147
Previous Page 1 / 1 Next

Semantically Similar Papers