PPP-Codes for Large-Scale Similarity Searching

D 2016

PPP-Codes for Large-Scale Similarity Searching

NOVÁK, David a Pavel ZEZULA

Základní údaje

Originální název

PPP-Codes for Large-Scale Similarity Searching

Autoři

NOVÁK, David (203 Česká republika, garant, domácí) a Pavel ZEZULA (203 Česká republika, domácí)

Vydání

Berlin Heidelberg, Transactions on Large-Scale Data- and Knowledge-Centered Systems XXIV, od s. 61-87, 27 s. 2016

Nakladatel

Springer

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

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

Forma vydání

tištěná verze "print"

Odkazy

publisher link

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/16:00087959

Organizační jednotka

Fakulta informatiky

ISBN

978-3-662-49213-0

ISSN

DOI

http://dx.doi.org/10.1007/978-3-662-49214-7_2

UT WoS

000452460000002

Klíčová slova anglicky

similarity search; pivot permutations; approximate search; kNN search

Štítky

DISA, similarity search

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 14. 5. 2020 15:34, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

Many current applications need to organize data with respect to mutual similarity between data objects. A typical general strategy to retrieve objects similar to a given sample is to access and then refine a candidate set of objects. We propose an indexing and search technique that can significantly reduce the candidate set size by combination of several space partitionings. Specifically, we propose a mapping of objects from a generic metric space onto main memory codes using several pivot spaces; our search algorithm first ranks objects within each pivot space and then aggregates these rankings producing a candidate set reduced by two orders of magnitude while keeping the same answer quality. Our approach is designed to well exploit contemporary HW: (1) larger main memories allow us to use rich and fast index, (2) multi-core CPUs well suit our parallel search algorithm, and (3) SSD disks without mechanical seeks enable efficient selective retrieval of candidate objects. The gain of the significant candidate set reduction is paid by the overhead of the candidate ranking algorithm and thus our approach is more advantageous for datasets with expensive candidate set refinement, i.e. large data objects or expensive similarity function. On real-life datasets, the search time speedup achieved by our approach is by factor of two to five.

Návaznosti

GBP103/12/G084, projekt VaV

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

Investor: Grantová agentura ČR, Centrum pro multi-modální interpretaci dat velkého rozsahu

Citovat

NOVÁK, David a Pavel ZEZULA. PPP-Codes for Large-Scale Similarity Searching. In Abdelkader Hameurlain, Josef Küng, Roland Wagner, Hendrik Decker, Lenka Lhotska, Sebastian Link. Transactions on Large-Scale Data- and Knowledge-Centered Systems XXIV. Berlin Heidelberg: Springer, 2016, s. 61-87. ISBN 978-3-662-49213-0. Dostupné z: https://dx.doi.org/10.1007/978-3-662-49214-7_2.

@inproceedings{1346582,
   author = {Novák, David and Zezula, Pavel},
   address = {Berlin Heidelberg},
   booktitle = {Transactions on Large-Scale Data- and Knowledge-Centered Systems XXIV},
   doi = {http://dx.doi.org/10.1007/978-3-662-49214-7_2},
   editor = {Abdelkader Hameurlain, Josef Küng, Roland Wagner, Hendrik Decker, Lenka Lhotska, Sebastian Link},
   keywords = {similarity search; pivot permutations; approximate search; kNN search},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Berlin Heidelberg},
   isbn = {978-3-662-49213-0},
   pages = {61-87},
   publisher = {Springer},
   title = {PPP-Codes for Large-Scale Similarity Searching},
   url = {http://link.springer.com/chapter/10.1007/978-3-662-49214-7_2},
   year = {2016}
}

TY  - JOUR
ID  - 1346582
AU  - Novák, David - Zezula, Pavel
PY  - 2016
TI  - PPP-Codes for Large-Scale Similarity Searching
PB  - Springer
CY  - Berlin Heidelberg
SN  - 9783662492130
KW  - similarity search
KW  - pivot permutations
KW  - approximate search
KW  - kNN search
UR  - http://link.springer.com/chapter/10.1007/978-3-662-49214-7_2
L2  - http://link.springer.com/chapter/10.1007/978-3-662-49214-7_2
N2  - Many current applications need to organize data with respect to mutual similarity between data objects. A typical general strategy to retrieve objects similar to a given sample is to access and then refine a candidate set of objects. We propose an indexing and search technique that can significantly reduce the candidate set size by combination of several space partitionings. Specifically, we propose a mapping of objects from a generic metric space onto main memory codes using several pivot spaces; our search algorithm first ranks objects within each pivot space and then aggregates these rankings producing a candidate set reduced by two orders of magnitude while keeping the same answer quality. Our approach is designed to well exploit contemporary HW: (1) larger main memories allow us to use rich and fast index, (2) multi-core CPUs well suit our parallel search algorithm, and (3) SSD disks without mechanical seeks enable efficient selective retrieval of candidate objects. The gain of the significant candidate set reduction is paid by the overhead of the candidate ranking algorithm and thus our approach is more advantageous for datasets with expensive candidate set refinement, i.e. large data objects or expensive similarity function. On real-life datasets, the search time speedup achieved by our approach is by factor of two to five.
ER  -

NOVÁK, David a Pavel ZEZULA. PPP-Codes for Large-Scale Similarity Searching. In Abdelkader Hameurlain, Josef Küng, Roland Wagner, Hendrik Decker, Lenka Lhotska, Sebastian Link. \textit{Transactions on Large-Scale Data- and Knowledge-Centered Systems XXIV}. Berlin Heidelberg: Springer, 2016, s.~61-87. ISBN~978-3-662-49213-0. Dostupné z: https://dx.doi.org/10.1007/978-3-662-49214-7\_{}2.

Podrobný výpis o publikaci