Efficient Dynamic Range Searching using Data Replication

Given the lower bound of $\\Omega(n^{(d-1)/d})$ for range query time complexityon $n$ $d$-dimensional point data, we investigate whether little replicationcan improve the query and update times significantly. We propose linear-spaceindex structures that minimize the query and update times; the query time weachieve is $O(n^{\\epsilon})$ for any $\\epsilon >0$, and, the update time is$O(\\log n)$.