Report ID
1997-13
Report Authors
K. V. Ravi Kanth and Ambuj K. Singh
Report Date
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.
Document
1997-13.ps278.16 KB