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
3202
Venue
SIGMOD
Year
2000
Pagerank
0.0002349868
Overall Rank
428 | 97.03%
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
464 PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries 2001 SIGMOD 0.00022476798
746 An Optimal and Progressive Algorithm for Skyline Queries 2003 SIGMOD 0.00017212135
1,070 Regret-Minimizing Representative Databases 2010 VLDB 0.00014274615
1,207 RankSQL: Query Algebra and Optimization for Relational Top-k Queries 2005 SIGMOD 0.0001327437
1,577 Designing Fair Ranking Schemes 2019 SIGMOD 0.00011276814
1,773 Continuous Monitoring of Top-k Queries over Sliding Windows 2006 SIGMOD 0.00010600438
2,249 Rank-aware Query Optimization 2004 SIGMOD 9.1956569e-05
2,477 Computing k-Regret Minimizing Sets 2014 VLDB 8.6907684e-05
2,621 Interactive Regret Minimization 2012 SIGMOD 8.4408945e-05
2,936 Answering Top-k Queries Using Views 2006 VLDB 7.8579393e-05
2,967 Processing a Large Number of Continuous Preference Top-k Queries 2012 SIGMOD 7.7975455e-05
3,015 Ranking with Uncertain Scoring Functions: Semantics and Sensitivity Measures 2011 SIGMOD 7.7079141e-05
3,100 Answering Why-not Questions on Reverse Top-k Queries 2015 VLDB 7.5625111e-05
3,447 Towards Robust Indexing for Ranked Queries 2006 VLDB 7.082382e-05
3,665 Ad-hoc Top-k Query Answering for Data Streams 2007 VLDB 6.8631567e-05
4,718 Answering Top-k Queries with Multi-Dimensional Selections: The Ranking Cube Approach 2006 VLDB 5.9664602e-05
5,074 Branch-and-Bound Algorithm for Reverse Top-k Queries 2013 SIGMOD 5.7113169e-05
5,113 Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative 2017 SIGMOD 5.6827696e-05
5,259 Efficient k-Regret Query Algorithm with Restriction-free Bound for any Dimensionality 2018 SIGMOD 5.5972902e-05
5,285 Efficient Approximation of Optimization Queries Under Parametric Aggregation Constraints 2003 VLDB 5.583298e-05
5,558 On Obtaining Stable Rankings 2019 VLDB 5.4375292e-05
5,906 k-Regret Queries with Nonlinear Utilities 2015 VLDB 5.274596e-05
5,963 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 5.2485815e-05
6,204 Maximum Rank Query 2015 VLDB 5.1547199e-05
6,219 Reverse k-Ranks Query 2014 VLDB 5.1458862e-05
6,378 Exact Processing of Uncertain Top-k Queries in Multi-criteria Settings 2018 VLDB 5.0844506e-05
6,632 Global Immutable Region Computation 2014 SIGMOD 4.9803909e-05
6,804 RRR: Rank-Regret Representative 2019 SIGMOD 4.917138e-05
6,988 Marrying Top-k with Skyline Queries: Relaxing the Preference Input while Producing Output of Controllable Size 2021 SIGMOD 4.8665394e-05
7,133 Anytime Measures for Top-k Algorithms 2007 VLDB 4.8175888e-05
7,170 Database Support for Matching: Limitations and Opportunities 2006 SIGMOD 4.807309e-05
7,273 Efficient and Generic Evaluation of Ranked Queries 2011 SIGMOD 4.775366e-05
7,541 Strongly Truthful Interactive Regret Minimization 2019 SIGMOD 4.7104726e-05
7,751 Computing Immutable Regions for Subspace Top-k Queries 2013 VLDB 4.6562296e-05
8,581 Geometric Approaches for Top-k Queries 2017 VLDB 4.4874332e-05
8,812 Creating Top Ranking Options in the Continuous Option and Preference Space 2019 VLDB 4.4397776e-05
8,823 Determining the Impact Regions of Competing Options in Preference Space 2017 SIGMOD 4.4372904e-05
8,890 A General Framework for Modeling and Processing Optimization Queries 2007 VLDB 4.4235206e-05
9,377 Towards Indexing Functions: Answering Scalar Product Queries 2014 SIGMOD 4.344689e-05
9,754 On m-Impact Regions and Standing Top-k Influence Problems 2021 SIGMOD 4.2856385e-05
10,989 Directional Queries: Making Top-k Queries More Effective in Discovering Relevant Results 2024 SIGMOD 4.1905499e-05
11,369 tau-LevelIndex: Towards Efficient Query Processing in Continuous Preference Space 2022 SIGMOD 4.1905499e-05
11,660 Top-k Queries over Digital Traces 2019 SIGMOD 4.1905499e-05
11,891 Query Reranking As A Service 2016 VLDB 4.1905499e-05
12,143 Answering Top-k Queries Over a Mixture of Attractive and Repulsive Dimensions 2012 VLDB 4.1905499e-05
12,175 FIFO Indexes for Decomposable Problems 2011 PODS 4.1905499e-05
12,359 A Fair Assignment Algorithm for Multiple Preference Queries 2009 VLDB 4.1905499e-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
171 Fuzzy Queries in Multimedia Database Systems 1998 PODS 0.00038843975
929 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.0001523035
1,171 Processing Queries By Linear Constraints 1997 PODS 0.00013507216
1,499 Efficient Searching with Linear Constraints (Extended Abstract) 1998 PODS 0.00011643887
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
1,171 Processing Queries By Linear Constraints 1997 PODS 0.00013507216
5,285 Efficient Approximation of Optimization Queries Under Parametric Aggregation Constraints 2003 VLDB 5.583298e-05
3,989 Beyond Simple Aggregates: Indexing for Summary Queries 2011 PODS 6.5545373e-05
929 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.0001523035
8,895 Fast and Adaptive Indexing of Multi-Dimensional Observational Data 2016 VLDB 4.423024e-05
9,377 Towards Indexing Functions: Answering Scalar Product Queries 2014 SIGMOD 4.344689e-05
2,010 Indexing for Data Models with Constraints and Classes (Extended Abstract) 1993 PODS 9.8046157e-05
7,006 Indexing the Edges – A simple and yet efficient approach to high-dimensional indexing 2000 PODS 4.8606861e-05
8,890 A General Framework for Modeling and Processing Optimization Queries 2007 VLDB 4.4235206e-05
3,447 Towards Robust Indexing for Ranked Queries 2006 VLDB 7.082382e-05