Compact and succinct data structures for multidimensional orthogonal range searching

摘要

We introduce compact and succinct representations of a d-dimensional point set for any constant d ≥ 3 supporting orthogonal range searching. Our first data structure uses dn lgn + o(nlgn) bits, where n denotes the number of points in P, and supporting reporting queries in O((n~((d-2)/d) + occ)lgn/lglgn) time, and counting queries in O(n~((d-2)/d) lgn/lglgn) time, where occ denotes the number of point to report, which is faster than known algorithms. Our second data structure uses dnlgU - nlgn + o(nlgn) bits, where U is the size of the universe, which asymptotically matches the information-theoretic lower bound. The query time complexity is worse than the first one, but the algorithm runs fast in practical database search.