Informační systém Masarykovy univerzity 

PPP-Codes for Large-Scale Similarity Searching

česky | in English

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, 27 s. ISBN 978-3-662-49213-0. doi:10.1007/978-3-662-49214-7_2.
Další formáty:   BibTeX LaTeX RIS
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
Originální jazyk angličtina
Typ výsledku Článek ve sborníku
Obor Informatika
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"
WWW 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 0302-9743
Doi http://dx.doi.org/10.1007/978-3-662-49214-7_2
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ěnil Změnil: RNDr. Pavel Šmerk, Ph.D., učo 3880. Změněno: 27. 4. 2017 09:39.
Anotace
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 VaVNázev: Centrum pro multi-modální interpretaci dat velkého rozsahu
Investor: Grantová agentura ČR, Projekty na podporu excelence v základním výzkumu
VytisknoutZobrazeno: 23. 10. 2017 06:04

Relevantní odkazy 


Nahoru | Aktuální datum a čas: 23. 10. 2017 06:04, 43. (lichý) týden

Kontakty: istech(zavináč/atsign)fi(tečka/dot)muni(tečka/dot)cz, studijní odd., správci práv, is-technici, e-technici, IT podpora | Použití cookies | Více o Informačním systému