D 2000

A Hashed Schema for Similarity Search in Metric Spaces

ZEZULA, Pavel

Basic information

Original name

A Hashed Schema for Similarity Search in Metric Spaces

Authors

Edition

1. vyd. Zurich, Proceedings of the First DELOS Network of Excellence Workshop on "Information Seeking, Searching and Querying in Digital Libraries" p. 83-87, Wokshop series, 2000

Publisher

ERCIM

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10000 1. Natural Sciences

Country of publisher

Switzerland

Confidentiality degree

není předmětem státního či obchodního tajemství

RIV identification code

RIV/00216224:14330/00:00002859

Organization unit

Faculty of Informatics

ISBN

ERCIM-01-W01
Změněno: 19/2/2001 17:11, prof. Ing. Pavel Zezula, CSc.

Abstract

V originále

A hashing schema for similarity search in generic metric spaces is investigated, assuming that only distances for pairs of objects are known. Similarity Hashing partitions data objects in bounding regions without overlapping. The proposed structure aims at reducing both the I/O and the CPU search costs. Contrary to the traditional tree-based approaches, specific upper-bounds on the search cost can be determined and the data organized in such way that the I/O costs never exceed those needed for sequential scan. Though the current version is static, it can be modified for dynamic data; it is also suitable for parallel implementations. Insertion is fast, and once the computed distances in the search phase are reused to significantly reduce the number of distance computations, that is proportional to the CPU costs. Experiments with the current prototype provide very encouraging results, especially for small similarity ranges.

Links

MSM 143300004, plan (intention)
Name: Digitální knihovny
Investor: Ministry of Education, Youth and Sports of the CR, Digital libraries