Istituto di Scienza e Tecnologie dell'Informazione     
Gennaro C., Savino P., Zezula P. A hashed schema for similarity search in metric spaces. In: Information Seeking, Searching and Querying in Digital Libraries. First DELOS Network of Excellence Workshop (Zurich, Switzerland, 11-12 December 2000). Proceedings, pp. 83 - 88. Ercim, 2000.
A novel access structure for similarity search in metric data, called Similarity Hashing (SH), is proposed. Its multi-level hash structure of separable buckets on each level supports easy insertion and bounded search costs, because at most one bucket needs to be accessed at each level for range queries up to a pre-de ned value of search radius. At the same time, the number of distance computations is always signi cantly reduced by use of pre-computed distances obtained at insertion time. Buckets of static les can be arranged in such a way that the I/O costs never exceed the costs to scan a compressed sequential file. Experimental results demonstrate that the performance of SH is superior to the available tree-based structures. Contrary to tree organizations, the SH structure is suitable for distributed and parallel implementations.
Subject Similarity search
H.3.3 Information Search and Retrieval

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