Efficient multidimensional indexing structure for linear maximization queries

Yuan-Chi Chang; Lawrence D. Bergman; John R. Smith; Chung-Sheng Li

doi:10.1117/12.360440

24 August 1999 Efficient multidimensional indexing structure for linear maximization queries

Yuan-Chi Chang, Lawrence D. Bergman, John R. Smith, Chung-Sheng Li

Proceedings Volume 3846, Multimedia Storage and Archiving Systems IV; (1999) https://doi.org/10.1117/12.360440
Event: Photonics East '99, 1999, Boston, MA, United States

Abstract

Linear optimization queries appear in many application domains in the form of ranked lists subject to a linear criterion. Surveys such as top 50 colleges, best 20 towns to live and ten most costly cities ar often based on linearly weighted factors. The importance of linear modeling to information analysis and retrieval thus cannot be overemphasized. Limiting returned results to the extreme cases is an effective way to filter the overwhelmingly large amount of unprocessed data. This paper discusses the construction, maintenance and utilization of a multidimensional indexing structure for processing linear optimization queries. The proposed indexing structure enables fast query processing and has minimal storage overhead. Experimental result demonstrated that proposed indexing achieves significant performance gain with speedup like 100 times faster than linear scan to retrieve top 100 records out of a million. In this structure, a data record is indexed by its depth in a layered convex hull. Convex hull is the boundary of the smallest convex region contain a given set of points in a metric space. It is long known from linear programming theory that linear maximum and minimum always happen at some vertex of the convex hull. We applied this simple fact to build a multi-layered convex structure, which enables highly efficient query retrieval for any dynamically issued linear optimization criteria.

Citation Download Citation

Yuan-Chi Chang, Lawrence D. Bergman, John R. Smith, and Chung-Sheng Li "Efficient multidimensional indexing structure for linear maximization queries", Proc. SPIE 3846, Multimedia Storage and Archiving Systems IV, (24 August 1999); https://doi.org/10.1117/12.360440

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available