Share Email Print

Proceedings Paper

Efficient multidimensional indexing structure for linear maximization queries
Author(s): Yuan-Chi Chang; Lawrence D. Bergman; John R. Smith; Chung-Sheng Li
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper 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.

Paper Details

Date Published: 24 August 1999
PDF: 11 pages
Proc. SPIE 3846, Multimedia Storage and Archiving Systems IV, (24 August 1999); doi: 10.1117/12.360440
Show Author Affiliations
Yuan-Chi Chang, IBM Thomas J. Watson Research Ctr. (United States)
Lawrence D. Bergman, IBM Thomas J. Watson Research Ctr. (United States)
John R. Smith, IBM Thomas J. Watson Research Ctr. (United States)
Chung-Sheng Li, IBM Thomas J. Watson Research Ctr. (United States)

Published in SPIE Proceedings Vol. 3846:
Multimedia Storage and Archiving Systems IV
Sethuraman Panchanathan; Shih-Fu Chang; C.-C. Jay Kuo, Editor(s)

© SPIE. Terms of Use
Back to Top