home search a-z help
University of Cambridge Computer Laboratory
Thursday Mar 23rd, 2006 - 4:30pm
Computer Laboratory > Research > Systems Research Group > NetOS > Seminars > Thursday Mar 23rd, 2006 - 4:30pm

Spatial Indexing in Structured Overlays

Eric Yu-En Lu

Motivated by the need for scalable solutions for large scale search engines, there has been much interest for spatial queries in large scale overlays. Unstructured overlays approaches, poses no constraints on where the data should be, work primarily on efficient flooding techniques. In contrast, structured overlays give data unique addresses that complex queries may require expensive query plan to evaluate.

In light of this observation, we propose content distance addressing that associates spatial proximity with overlay proximity. Therefore, spatial queries such as nearest neighbor and range queries reduces to flooding in a designated region on the overlay, subject to the range specified.

In this talk, we evaluate this idea on both keyword based datasets (FreeDB) and vector space based datasets (TREC). We show that our scheme gives good load-balancing using no run-time adaptations and exhibits efficient query performance.