Back
#
Complexity of Adaptive Spatial Indexing for Robust Distributed Data

An MSCS Thesis

by

Matthew Vincent Mahoney

Jan. 1998

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

## Abstract

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 log^{2} log n);
update, O(log^{2} n log^{2} log n),
provided that the number of dimensions
is fixed or grows no faster than O(log n).

## Download

47 pages
Matt Mahoney, mmahoney@cs.fit.edu