Paper
24 August 1999 Efficient multidimensional indexing structure for linear maximization queries
Yuan-Chi Chang, Lawrence D. Bergman, John R. Smith, Chung-Sheng Li
Author Affiliations +
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.
© (1999) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
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
Lens.org Logo
CITATIONS
Cited by 2 scholarly publications.
Advertisement
Advertisement
RIGHTS & PERMISSIONS
Get copyright permission  Get copyright permission on Copyright Marketplace
KEYWORDS
Databases

Computer programming

Multimedia

Data modeling

Algorithm development

Analytical research

Chemical elements

RELATED CONTENT


Back to Top