D 2011

Stabilizing the Recall in Similarity Search

KYSELÁK, Martin, David NOVÁK and Pavel ZEZULA

Basic information

Original name

Stabilizing the Recall in Similarity Search

Name in Czech

Stabilizace kvality v podobnost

Authors

KYSELÁK, Martin (203 Czech Republic, guarantor, belonging to the institution), David NOVÁK (203 Czech Republic, belonging to the institution) and Pavel ZEZULA (203 Czech Republic, belonging to the institution)

Edition

New York, Fourth International Conference on Similarity Search and Applications, SISAP 2011, p. 59-66, 8 pp. 2011

Publisher

ACM Press

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Italy

Confidentiality degree

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

Publication form

printed version "print"

RIV identification code

RIV/00216224:14330/11:00073202

Organization unit

Faculty of Informatics

ISBN

978-1-4503-0795-6

DOI

Keywords in English

locality-sensitive hashing; metric space; similarity search; recall; stability;

Tags

Tags

International impact, Reviewed
Změněno: 1/4/2015 09:00, RNDr. Pavel Šmerk, Ph.D.

Abstract

V originále

The recent techniques for approximate similarity search focus on optimizing answer precision/recall and they typically improve the average of these measures over a set of sample queries. However, according to our observation, the recall for particular indexes and queries can fluctuate considerably. In order to stabilize the recall, we propose a query-evaluation model that exploits several variants of the search index. This approach is applicable to a signicant subset of current approximate methods with a focus on techniques based purely on metric postulates. Applying this approach to the M-Index structure, we perform extensive measurements on large datasets and we show that this approach has a positive impact on the recall stability and it suppresses the most unsatisfactory cases. Further, the results indicate that the proposed approach can also increase the general average recall for given overall search costs.

Links

GAP103/10/0886, research and development project
Name: Vizuální vyhledávání obrázků na Webu (Acronym: VisualWeb)
Investor: Czech Science Foundation, Content-based Image Retrieval on the Web Scale
GA201/09/0683, research and development project
Name: Vyhledávání v rozsáhlých multimediálních databázích
Investor: Czech Science Foundation, Similarity Searching in Very Large Multimedia Databases
GPP202/10/P220, research and development project
Name: Podobnostní vyhledávání s konstantní škálovatelností (Acronym: SIM-SCALE)
Investor: Czech Science Foundation
VF20102014004, research and development project
Name: Multimediální analýza (Acronym: Multimediální analýza)
Investor: Ministry of the Interior of the CR