Complexity of Adaptive Spatial Indexing for Robust Distributed Data

An MSCS Thesis
Matthew Vincent Mahoney
Jan. 1998

Thesis Advisor: Philip K. Chan, Ph.D.


A spatial index suitable for implementation of a multidimensionally keyed database (such as text retrieval system) in an unreliable, decentralized, distributed environment is shown to have complexity comparable to the Internet's Domain Name Service and better than USENET or Web search engines. The index is a graph mapped into Euclidean space with high smoothness, a property allowing efficient backtrack-free directed search techniques such as hill climbing. Updates are tested using random search, then edges are adaptively added to bypass local minima, network congestion, and hardware failures. Protocols are described. Empirical average case complexity for n data items are: storage, O(n log n); query, O(log n log2 log n); update, O(log2 n log2 log n), provided that the number of dimensions is fixed or grows no faster than O(log n).


47 pages

Matt Mahoney,