Publication details
Similarity Grid for Searching in Metric Spaces
| Basic information | |
|---|---|
| Original title: | Similarity Grid for Searching in Metric Spaces |
| Authors: | Michal Batko, Claudio Gennaro, Pavel Zezula |
| Further information | |
|---|---|
| Citation: | BATKO, Michal  - GENNARO, Claudio - ZEZULA, Pavel. Similarity Grid for Searching in Metric Spaces. In Peer-to-Peer, Grid, and Service-Orientation in Digital Library Architectures: 6th Thematic Workshop of the EU Network of Excellence DELOS. Revised Selected Papers. LNCS 3664. Berlin : Springer-Verlag Heidelberg, 2005. ISBN 3-540-28711-6, pp. 25-44. 24.6.2004, Cagliari. |
| Original language: | English |
| Field: | Computer hardware and software |
| Type: | Article in Proceedings |
| Keywords: | distributed data; scalable structures; similarity search; metric space |
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 structure also scales well with respect to the growing volume of retrieved data. Moreover, a small 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.
Related projects:
