A Performance-guaranteed approximate range query algorithm for the ND-tree

Abstract

Range queries are a widely-used type of similarity queries that find all objects within a given distance from the query object. In this paper, we propose an approximate range query algorithm for the ND-tree, a multi-dimensional index for vectors with non-ordered discrete components. By sacrificing a little accuracy, approximate algorithms generally can greatly improve search performance. Our proposed approximate algorithm maintains a priority queue of tree nodes whose bounding rectangles (BR) intersect the query sphere. But it only accesses a user-specified portion of the queue. We propose a novel volume-based weighting scheme for the priority queue. The idea is that tree nodes whose BR has a larger intersection with the query sphere contain more result objects, thus should be accessed earlier. A closed-form formula is derived to calculate the volume of an intersection. Our experimental study using both synthetic and real data shows that the proposed algorithm can significantly improve query performance while maintaining high query accuracy.