Abstract
Optimal Dynamic Range Searching in Non-replicating Index Structures
by: K. V. Ravi Kanth and Ambuj K. Singh
Abstract:
We consider the problem of dynamic range searching in tree structures that donot replicate data. We propose a new dynamic structure, called the {\\emO-tree\\/}, that achieves a query time complexity of $O(n^{(d-1)/d})$ on $n$$d$-dimensional points and an amortized insertion/deletion time complexity of$O(\\log n)$. We show that this structur e is optimal when data is notreplicated. In addition to optimal query and insertion/deletion times, theO-tree also supports exact match queries in worst-case logarithmic time.
Keywords:
Range Searching, divided k-d trees, Dynamic indexing
Date:
July 1997
Document: 1997-13
