PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Batko M., Gennaro C., Savino P., Zezula P. Scalable Similarity Search in Metric Spaces. In: DELOS Workshop on Digital Library Architectures: Peer-to-Peer, Grid, and Service-Orientation (S. Margherita di Pula (Cagliari), Italy, 24-25 June 2004).
 
 
Abstract
(English)
Similarity search in metric spaces represents an important paradigm for content-based retrieval of many applications. Existing centralized search structures can speed-up retrieval, but they do not scale up to large volume of data because the response time is linearly increasing with the size of the searched file. The proposed GHT* index is a scalable and distributed structure. By exploiting parallelism in a dynamic network of computers, the GHT* achieves practically constant search time for similarity range queries in data-sets of arbitrary size. The amount of replicated routing information on each server increases logarithmically. At the same time, the potential for interquery parallelism is increasing with the growing data-sets because the relative number of servers utilized by individual queries is decreasing. All these properties are verified by experiments on a prototype system using real-life data-sets.
Subject Similarity Search
Metric Space
Peer-to-Peer
Grid
H.3.3 Information Search and Retrieval
H.3.4 Systems and Software. Distributed systems


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional