Performance Study of Independent Anchor Spaces for Similarity
Searching

J 2014

Performance Study of Independent Anchor Spaces for Similarity Searching

NOVÁK, David and Pavel ZEZULA

Basic information

Original name

Performance Study of Independent Anchor Spaces for Similarity Searching

Authors

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

Edition

The Computer Journal, Oxford, UK, Oxford University Press, 2014, 0010-4620

Other information

Language

English

Type of outcome

Článek v odborném periodiku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

United Kingdom of Great Britain and Northern Ireland

Confidentiality degree

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

References:

publisher site

Impact factor

Impact factor: 0.787

RIV identification code

RIV/00216224:14330/14:00073219

Organization unit

Faculty of Informatics

DOI

http://dx.doi.org/10.1093/comjnl/bxt114

UT WoS

000344649500011

Keywords in English

similarity search; metric space; multi-index; efficiency; robustness

Abstract

V originále

This work targets the problem of search efficiency vs. answer quality of approximate metric-based similarity search. We especially focus on techniques based on recursive Voronoi-like partitioning or, from another perspective, on pivot permutations. These techniques use sets of reference objects (anchors/pivots) to partition the metric space into cells of close data items. Instead of refining the search space by enlarging the anchor set of a single index, we propose to divide a large pivot set into several subsets and build multiple indexes with independent space partitioning; at query time, the overall search costs are also divided among the separate indexes. Our thorough experimental study on three different real datasets uncovers drawbacks of excessive increase of a single pivot set size—such partitioning refinement can be counterproductive beyond a certain number of pivots. Our approach overcomes the root causes of this limitation and increases the answer quality while preserving the search costs. Further, we address the question of robustness of the answer quality, which can be significantly improved by utilization of independent anchor spaces.

Links

GBP103/12/G084, research and development project

Name: Centrum pro multi-modální interpretaci dat velkého rozsahu

Investor: Czech Science Foundation

VG20122015073, research and development project

Name: Efektivní vyhledávání v rozsáhlých biometrických datech (Acronym: EFBIO)

Investor: Ministry of the Interior of the CR

Citovat

NOVÁK, David and Pavel ZEZULA. Performance Study of Independent Anchor Spaces for Similarity Searching. The Computer Journal. Oxford, UK: Oxford University Press, 2014, vol. 57, No 11, p. 1741-1755. ISSN 0010-4620. Available from: https://dx.doi.org/10.1093/comjnl/bxt114.

@article{1180308,
   author = {Novák, David and Zezula, Pavel},
   article_location = {Oxford, UK},
   article_number = {11},
   doi = {http://dx.doi.org/10.1093/comjnl/bxt114},
   keywords = {similarity search; metric space; multi-index; efficiency; robustness},
   language = {eng},
   issn = {0010-4620},
   journal = {The Computer Journal},
   title = {Performance Study of Independent Anchor Spaces for Similarity Searching},
   url = {http://comjnl.oxfordjournals.org/content/57/11/1741},
   volume = {57},
   year = {2014}
}

TY  - JOUR
ID  - 1180308
AU  - Novák, David - Zezula, Pavel
PY  - 2014
TI  - Performance Study of Independent Anchor Spaces for Similarity Searching
JF  - The Computer Journal
VL  - 57
IS  - 11
SP  - 1741-1755
EP  - 1741-1755
PB  - Oxford University Press
SN  - 00104620
KW  - similarity search
KW  - metric space
KW  - multi-index
KW  - efficiency
KW  - robustness
UR  - http://comjnl.oxfordjournals.org/content/57/11/1741
L2  - http://comjnl.oxfordjournals.org/content/57/11/1741
N2  - This work targets the problem of search efficiency vs. answer quality of approximate metric-based similarity search. We especially focus on techniques based on recursive Voronoi-like partitioning or, from another perspective, on pivot permutations. These techniques use sets of reference objects (anchors/pivots) to partition the metric space into cells of close data items. Instead of refining the search space by enlarging the anchor set of a single index, we propose to divide a large pivot set into several subsets and build multiple indexes with independent space partitioning; at query time, the overall search costs are also divided among the separate indexes. Our thorough experimental study on three different real datasets uncovers drawbacks of excessive increase of a single pivot set size—such partitioning refinement can be counterproductive beyond a certain number of pivots. Our approach overcomes the root causes of this limitation and increases the answer quality while preserving the search costs. Further, we address the question of robustness of the answer quality, which can be significantly improved by utilization of independent anchor spaces.
ER  -

NOVÁK, David and Pavel ZEZULA. Performance Study of Independent Anchor Spaces for Similarity Searching. \textit{The Computer Journal}. Oxford, UK: Oxford University Press, 2014, vol.~57, No~11, p.~1741-1755. ISSN~0010-4620. Available from: https://dx.doi.org/10.1093/comjnl/bxt114.

Detailed Information on Publication Record