Document - Selecting sketches for similarity search

2018

Conference article Open Access

Selecting sketches for similarity search

Mic V., Novak D., Vadicamo L., Zezula P.

Similarity Search Bit string sketches

Techniques of the Hamming embedding, producing bit string sketches, have been recently successfully applied to speed up similarity search. Sketches are usually compared by the Hamming distance, and applied to filter out non-relevant objects during the query evaluation. As several sketching techniques exist and each can produce sketches with different lengths, it is hard to select a proper configuration for a particular dataset. We assume that the (dis)similarity of objects is expressed by an arbitrary metric function, and we propose a way to efficiently estimate the quality of sketches using just a small sample set of data. Our approach is based on a probabilistic analysis of sketches which describes how separated are objects after projection to the Hamming space.

Source: ADBIS 2018 - 22nd European Conference on Advances in Databases and Information Systems, pp. 127–141, Budapest, Ungheria, 2-5 September 2018

Metrics

Back to previous page

Cite as

BibTeX entry

@inproceedings{oai:it.cnr:prodotti:403042,
	title = {Selecting sketches for similarity search},
	author = {Mic V. and Novak D. and Vadicamo L. and Zezula P.},
	doi = {10.1007/978-3-319-98398-1_9},
	booktitle = {ADBIS 2018 -  22nd European Conference on Advances in Databases and Information Systems, pp. 127–141, Budapest, Ungheria, 2-5 September 2018},
	year = {2018}
}