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 depth 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.
- 1.P. K. Agarwal, L. Arge, J. Erickson, P. G. Franciosa, and J. S. Vitter, "Efficient searching with linear constraints," Proceedings of the ACM Symposium on Principles of Database Systems, pp. 169-177, 1998.]] Google ScholarDigital Library
- 2.K. S. Beyer, J. Goldstein, R. Ramakrishnan, U. Shaft, "When is nearest neighbor meaningful," Proceedings of International Conference on Database Theory, pp. 217- 235, 1999.]] Google ScholarDigital Library
- 3.S. Berchtold, C. Bohm, and H. P. Kriegel, "The Pyramid-technique: towards breaking the curse of dimensionality," Proceedings of the A CM Symposium on Management of Data, pp. 142-153, 1998.]] Google ScholarDigital Library
- 4.T. M. Chan, "Fixed-dimensional linear programming queries made easy," Proceedings of the ACM Symposium on Computational Geometry, pp. 284-290, 1996.]] Google ScholarDigital Library
- 5.Y. C. Chang, L. Bergman, J. R. Smith, and C. S. Li, "Efficient multidimensional indexing structure for linear maximization queries," Proceedings of Multimedia Storage and Archiving Systems, Boston, MA 1999.]]Google Scholar
- 6.A. Das, S. R. Lele, G. E. Glass, T. Shields, and J. A. Patz, "Spatial modeling of vector abundance using generalized linear mixed models: application to Lyme disease," submitted to Biometrics for publication.]]Google Scholar
- 7.G. B. Dantzig, Linear programming and extensions, Princeton University Press, Princeton, NJ, 1963.]]Google ScholarDigital Library
- 8.R. Fagin, "Fuzzy queries in multimedia database systems, " Proceedings of the A CM Symposium on Principles of Database Systems, pp. 1-10, 1998.]] Google ScholarDigital Library
- 9.S. C. Fang and S. Puthenpura, Linear optimization and extentions, Prentice-Hall, Inc., Englewood Cliffs, NJ, 1993.]] Google ScholarDigital Library
- 10.J. Goldstein, R. Ramakrishnan, U. Shaft, and J. Yu, "Processing queries by linear constraints," Proceedings o} the A CM Symposium on Principles o} Database Systems, pp. 257-267, 1997.]] Google ScholarDigital Library
- 11.J. Matousek and O. Schwarzkopf, "Linear optimization queries," Proceedings o} the A CM Symposium on Computational Geometry, pp. 16-25, 1992.]] Google ScholarDigital Library
- 12.F. P. Preparata and M. I. Shamos, Computational geometry: an introduction, Springer Verlag, 1991.]] Google ScholarDigital Library
- 13.R. Seidel, "Linear programming and convex hulls made easy," Proceedings o} the A CM Symposium on Computational Geometry, pp. 211-215, 1990.]] Google ScholarDigital Library
Index Terms
- The onion technique: indexing for linear optimization queries
Recommendations
The onion technique: indexing for linear optimization queries
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. ...
The Onion-Tree: Quick Indexing of Complex Data in the Main Memory
ADBIS '09: Proceedings of the 13th East European Conference on Advances in Databases and Information SystemsSearching for elements in a dataset that are similar to a given query element is a core problem in applications that use complex data, and has been carried out aided by a metric access method (MAM). A growing number of these applications require indices ...
Comments