A Hashed Schema for Similarity Search in Metric Spaces

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F00%3A00002859" target="_blank" >RIV/00216224:14330/00:00002859 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

A Hashed Schema for Similarity Search in Metric Spaces

Popis výsledku v původním jazyce

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 aimsat 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.

Název v anglickém jazyce

A Hashed Schema for Similarity Search in Metric Spaces

Popis výsledku anglicky

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 aimsat 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.

Druh

D - Stať ve sborníku

CEP obor

BD - Teorie informace

OECD FORD obor

—

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2000

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the First DELOS Network of Excellence Workshop on "Information Seeking, Searching and Querying in Digital Libraries"

ISBN

ERCIM-01-W01

ISSN

—

e-ISSN

—

Počet stran výsledku

5

Strana od-do

—

Název nakladatele

ERCIM

Místo vydání

Zurich

Místo konání akce

—

Datum konání akce

—

Typ akce podle státní příslušnosti

—

Kód UT WoS článku

—