Efficient multidimensional indexing structure for linear maximization queries

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 are 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 results 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 containing 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.