Efficient Peer-to-Peer Namespace Searches
Efficient Peer-to-Peer Namespace Searches
Files
Publication or External Link
Date
2004-04-19
Authors
Gopalakrishnan, Vijay
Bhattacharjee, Bobby
Chawathe, Sudarshan
Keleher, Pete
Advisor
Citation
DRUM DOI
Abstract
In this paper we describe new methods for efficient and exact search
(keyword and full-text) in distributed namespaces. Our methods can be
used in conjunction with existing distributed lookup schemes, such as
Distributed Hash Tables, and distributed directories. We describe how
indexes for implementing distributed searches can be efficiently
created, located, and stored. We describe techniques for creating
approximate indexes that can be used to bound the space requirement at
individual hosts; such techniques are particularly useful for full-text
searches that may require a very large number of individual indexes to
be created and maintained.
Our methods use a new distributed data structure called the view tree.
View trees can be used to efficiently cache and locate results from
prior queries. We describe how view trees are created, and maintained.
We present experimental results, using large namespaces and realistic
data, showing that the techniques introduced in this paper can reduce
search overheads (both network and processing costs) by more than an
order of magnitude.
(UMIACS-TR-2004-13)