There are a number of data structures in the literature that solve the dynamic orthogonal range search problem in polylogarithmic time (say, range trees). My understanding is that these structures typically don’t perform well in practice due to the high constant factors involved.
On the flipside, there’s the R-tree, which solves orthogonal range searches quickly in practice on the types of inputs typically encountered. However, it doesn’t have a nice known upper bound on the cost of searches.
Are there any data structures known that represent the “best of both worlds” in the sense that they have nice provable polylogarithmic bounds on their query costs and run quickly in practice?
Thanks!
