Indexing the edges - a simple and yet efficient approach to high-dimensional indexing

Abstract

In this paper, we propose a new tunable index scheme, called iMinMax(θ), that maps points in high dimensional spaces to single dimension values determined by their maximum or minimum values among all dimensions. By varying the tuning `knob' θ, we can obtain different family of iMinMax structures that are optimized for different distributions of data sets. For a d-dimensional space, a range query need to be transformed into d subqueries. However, some of these subqueries can be pruned away without evaluation, further enhancing the efficiency of the scheme. Experimental results show that iMinMax(θ) can outperform the more complex Pyramid technique by a wide margin.