PPP-Codes for Large-Scale Similarity Searching

Investor logo

Warning

This publication doesn't include Faculty of Sports Studies. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

NOVÁK David ZEZULA Pavel

Year of publication 2016
Type Article in Proceedings
Conference Transactions on Large-Scale Data- and Knowledge-Centered Systems XXIV
MU Faculty or unit

Faculty of Informatics

Citation
Web publisher link
Doi http://dx.doi.org/10.1007/978-3-662-49214-7_2
Field Informatics
Keywords similarity search; pivot permutations; approximate search; kNN search
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info