The Onion Technique: Indexing for Linear Optimization Queries Yuan-Chi Chang, Lawrence D. Bergman, Vittorio Castelli, Chung-Sheng Li, Ming-Ling Lo, and John R. Smith   View Paper (PDF)   Return to Research Sessions Abstract This paper describes the Onion technique, a special indexing structure for linear optimization queries. Linear optimization queries ask for top-N records subject to the maximization or minimization of linearly weighted sum of record attribute values. Such query appears in many applications employing linear models and is an effective way to summarize representative cases, such as the top-50 ranked colleges. The Onion indexing is based on a geometric property of convex hull, which guarantees that the optimal value can always be found at one or more of its vertices. The Onion indexing makes use of this property to construct convex hulls in layers with outer layers enclosing inner layers geometrically. A data record is indexed by its layer number or equivalently its dept in the layered convex hull. Queries with linear weightings issued at run time are evaluated from the outmost layer inwards. We show experimentally that the Onion indexing achieves orders of magnitude speedup against sequential linear scan when N is small compared to the cardinality of the set. The Onion technique also enables progressive retrieval, which processes and returns ranked results in a progressive manner. Furthermore, the proposed indexing can be extended into a hierarchical organization of data to accommodate both global and local queries. References Note: References link to DBLP on the Web. [1] Pankaj K. Agarwal , Lars Arge , Jeff Erickson , Paolo Giulio Franciosa , Jeffrey Scott Vitter : Efficient Searching with Linear Constraints. PODS 1998 : 169-178 [2] Kevin S. Beyer , Jonathan Goldstein , Raghu Ramakrishnan , Uri Shaft : When Is ''Nearest Neighbor'' Meaningful? ICDT 1999 : 217-235 [3] Stefan Berchtold , Christian Böhm , Hans-Peter Kriegel : The Pyramid-Tree: Breaking the Curse of Dimensionality. SIGMOD Conference 1998 : 142-153 [4] Timothy M. Chan : Fixed-Dimensional Linear Programming Queries Made Easy. Symposium on Computational Geometry 1996 : 284-290 [5] ... [6] ... [7] ... [8] Ronald Fagin : Fuzzy Queries in Multimedia Database Systems. PODS 1998 : 1-10 [9] ... [10] Jonathan Goldstein , Raghu Ramakrishnan , Uri Shaft , Jie-Bing Yu : Processing Queries By Linear Constraints. PODS 1997 : 257-267 [11] Jirí Matousek , Otfried Schwarzkopf : Linear Optimization Queries. Symposium on Computational Geometry 1992 : 16-25 [12] ... [13] Raimund Seidel : Linear Programming and Convex Hulls Made Easy. Symposium on Computational Geometry 1990 : 211-215 BIBTEX @inproceedings{DBLP:conf/sigmod/ChangBCLLS00,   author    = {Yuan-Chi Chang and                 Lawrence D. Bergman and                 Vittorio Castelli and                 Chung-Sheng Li and                 Ming-Ling Lo and                 John R. Smith},    editor    = {Weidong Chen and                 Jeffrey F. Naughton and                 Philip A. Bernstein},    title     = {The Onion Technique: Indexing for Linear Optimization Queries},    booktitle = {Proceedings of the 2000 ACM SIGMOD International Conference on                 Management of Data, May 16-18, 2000, Dallas, Texas, USA},    journal   = {SIGMOD Record},    publisher = {ACM},    volume    = {29},    number    = {2},    year      = {2000},    isbn      = {1-58113-218-2},    pages     = {391-402},    crossref  = {DBLP:conf/sigmod/2000},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, DiSC'01 Copyright ©2002 ACM Inc.