We consider the problem of multi-dimensional orthogonal range searching in linear space for any d dimensions. The kd-tree achieves O(n~((d-1)/d)) query time for range counting, which is optimal among bounding-box tree structures, and it has been considered to be the best complexity bound in practice for four decades, while the non-overlapping krange achieves O(n~ε) query time in theory. Several twodimensional data structures have better query times than the kd-tree, but have never been generalized to higher dimensions in linear space. In this paper, we propose a new succinct data structure, called the KDW-tree, which requires less space partitioning than the kd-tree and achieves O(n~((d-2)/d) log n) time for range counting. This is the first succinct data structure that has a lower time complexity than the kd-tree in arbitrary dimensions. In experiments, our data structure significantly outperformed the kd-tree using linear space both for range counting and sum queries in low dimensions for high selectivity.
展开▼
