Database Paper Browser

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
3201
Venue
SIGMOD
Year
2000
Pagerank
0.00023463938
Overall Rank
430 | 97.02%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 47 of 47 citing papers.

Rank Citing Paper Year Venue Pagerank
465 PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries 2001 SIGMOD 0.00022455702
749 An Optimal and Progressive Algorithm for Skyline Queries 2003 SIGMOD 0.00017228334
1,072 Regret-Minimizing Representative Databases 2010 VLDB 0.00014270817
1,262 RankSQL: Query Algebra and Optimization for Relational Top-k Queries 2005 SIGMOD 0.00012986539
1,597 Designing Fair Ranking Schemes 2019 SIGMOD 0.00011209846
1,784 Continuous Monitoring of Top-k Queries over Sliding Windows 2006 SIGMOD 0.00010567363
2,393 Rank-aware Query Optimization 2004 SIGMOD 8.9016542e-05
2,478 Computing k-Regret Minimizing Sets 2014 VLDB 8.6927744e-05
2,615 Interactive Regret Minimization 2012 SIGMOD 8.4473503e-05
2,933 Answering Top-k Queries Using Views 2006 VLDB 7.8679669e-05
2,976 Processing a Large Number of Continuous Preference Top-k Queries 2012 SIGMOD 7.789303e-05
3,014 Ranking with Uncertain Scoring Functions: Semantics and Sensitivity Measures 2011 SIGMOD 7.70946e-05
3,095 Answering Why-not Questions on Reverse Top-k Queries 2015 VLDB 7.5692859e-05
3,463 Towards Robust Indexing for Ranked Queries 2006 VLDB 7.069675e-05
3,665 Ad-hoc Top-k Query Answering for Data Streams 2007 VLDB 6.8633354e-05
4,711 Answering Top-k Queries with Multi-Dimensional Selections: The Ranking Cube Approach 2006 VLDB 5.9790683e-05
5,095 Branch-and-Bound Algorithm for Reverse Top-k Queries 2013 SIGMOD 5.7021328e-05
5,116 Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative 2017 SIGMOD 5.6830089e-05
5,255 Efficient k-Regret Query Algorithm with Restriction-free Bound for any Dimensionality 2018 SIGMOD 5.6013035e-05
5,299 Efficient Approximation of Optimization Queries Under Parametric Aggregation Constraints 2003 VLDB 5.5796719e-05
5,555 On Obtaining Stable Rankings 2019 VLDB 5.4386174e-05
5,904 k-Regret Queries with Nonlinear Utilities 2015 VLDB 5.2790141e-05
5,962 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 5.2536266e-05
6,203 Maximum Rank Query 2015 VLDB 5.1590738e-05
6,222 Reverse k-Ranks Query 2014 VLDB 5.1503175e-05
6,387 Exact Processing of Uncertain Top-k Queries in Multi-criteria Settings 2018 VLDB 5.0851965e-05
6,632 Global Immutable Region Computation 2014 SIGMOD 4.984576e-05
6,816 RRR: Rank-Regret Representative 2019 SIGMOD 4.9173197e-05
7,002 Marrying Top-k with Skyline Queries: Relaxing the Preference Input while Producing Output of Controllable Size 2021 SIGMOD 4.8670742e-05
7,135 Anytime Measures for Top-k Algorithms 2007 VLDB 4.8221884e-05
7,190 Database Support for Matching: Limitations and Opportunities 2006 SIGMOD 4.8051876e-05
7,276 Efficient and Generic Evaluation of Ranked Queries 2011 SIGMOD 4.7798595e-05
7,559 Strongly Truthful Interactive Regret Minimization 2019 SIGMOD 4.7107487e-05
7,750 Computing Immutable Regions for Subspace Top-k Queries 2013 VLDB 4.6607023e-05
8,584 Geometric Approaches for Top-k Queries 2017 VLDB 4.4914121e-05
8,825 Determining the Impact Regions of Competing Options in Preference Space 2017 SIGMOD 4.4415078e-05
8,877 Creating Top Ranking Options in the Continuous Option and Preference Space 2019 VLDB 4.4302563e-05
8,889 A General Framework for Modeling and Processing Optimization Queries 2007 VLDB 4.4278238e-05
9,453 Towards Indexing Functions: Answering Scalar Product Queries 2014 SIGMOD 4.339214e-05
9,774 On m-Impact Regions and Standing Top-k Influence Problems 2021 SIGMOD 4.2856106e-05
10,986 Directional Queries: Making Top-k Queries More Effective in Discovering Relevant Results 2024 SIGMOD 4.1945683e-05
11,367 tau-LevelIndex: Towards Efficient Query Processing in Continuous Preference Space 2022 SIGMOD 4.1945683e-05
11,655 Top-k Queries over Digital Traces 2019 SIGMOD 4.1945683e-05
11,883 Query Reranking As A Service 2016 VLDB 4.1945683e-05
12,135 Answering Top-k Queries Over a Mixture of Attractive and Repulsive Dimensions 2012 VLDB 4.1945683e-05
12,167 FIFO Indexes for Decomposable Problems 2011 PODS 4.1945683e-05
12,351 A Fair Assignment Algorithm for Multiple Preference Queries 2009 VLDB 4.1945683e-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
169 Fuzzy Queries in Multimedia Database Systems 1998 PODS 0.00038895438
931 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.00015238406
1,172 Processing Queries By Linear Constraints 1997 PODS 0.00013505441
1,502 Efficient Searching with Linear Constraints (Extended Abstract) 1998 PODS 0.00011643406
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
1,172 Processing Queries By Linear Constraints 1997 PODS 0.00013505441
5,299 Efficient Approximation of Optimization Queries Under Parametric Aggregation Constraints 2003 VLDB 5.5796719e-05
3,991 Beyond Simple Aggregates: Indexing for Summary Queries 2011 PODS 6.5553055e-05
931 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.00015238406
8,895 Fast and Adaptive Indexing of Multi-Dimensional Observational Data 2016 VLDB 4.427268e-05
9,453 Towards Indexing Functions: Answering Scalar Product Queries 2014 SIGMOD 4.339214e-05
2,003 Indexing for Data Models with Constraints and Classes (Extended Abstract) 1993 PODS 9.8126082e-05
7,005 Indexing the Edges – A simple and yet efficient approach to high-dimensional indexing 2000 PODS 4.8654221e-05
8,889 A General Framework for Modeling and Processing Optimization Queries 2007 VLDB 4.4278238e-05
3,463 Towards Robust Indexing for Ranked Queries 2006 VLDB 7.069675e-05