Abstract
Efficient Dynamic Range Searching using Data Replication
by: K. V. Ravi Kanth and Ambuj K. Singh
Abstract:
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)$.
Keywords:
Range Searching, Dynamization techniques, Global Rebuilding
Date:
July 1997
Document: 1997-12
