Compact N-tree: an indexing structure for distance range queries

Mobile query processing is, currently, a very active research field. Range and nearest neighbor queries are commonly used in spatiotemporal databases and location based services (LBS). In this paper, we focus on finding nearest neighbors of a query point within a certain distance range. We propose a new indexing structure CN-tree, Compact N-tree, based on a recent indexing technique called N-tree. CN-tree joins efficiency of N-tree´s data partitioning scheme to pertinent objects´ approximation with minimal bounding rectangles of R-trees which are reported to be the best performing for range search. We show how we use the approximation in constructing CN-tree and, then, how this index can support range queries efficiently by minimizing computation of distances and avoiding overlapping of minimal bounding rectangles. The experimental results through the comparison with the well know R*-tree, show that the proposed CN-tree widely outperforms R*-tree as an in-memory index and it presents competitive performances when used as an in-disk index.