Single Versus Multiple Sorting in All Pairs Similarity Search
Abstract
To save memory and improve speed, vectorial data such as images and signals are often represented as strings of discrete symbols (i.e., sketches). Chariker (2002) proposed a fast approximate method for finding neighbor pairs of strings by sorting and scanning with a small window. This method, which we shall call 'single sorting', is applied to locality sensitive codes and prevalently used in speed-demanding web-related applications. To improve on single sorting, we propose a novel method that employs blockwise masked sorting. Our method can dramatically reduce the number of candidate pairs which have to be verified by distance calculation in exchange with an increased amount of sorting operations. So it is especially attractive for high dimensional dense data, where distance calculation is expensive. Empirical results show the efficiency of our method in comparison to single sorting and recent fast nearest neighbor methods.
Cite
Text
Tabei et al. "Single Versus Multiple Sorting in All Pairs Similarity Search." Proceedings of 2nd Asian Conference on Machine Learning, 2010.Markdown
[Tabei et al. "Single Versus Multiple Sorting in All Pairs Similarity Search." Proceedings of 2nd Asian Conference on Machine Learning, 2010.](https://mlanthology.org/acml/2010/tabei2010acml-single/)BibTeX
@inproceedings{tabei2010acml-single,
title = {{Single Versus Multiple Sorting in All Pairs Similarity Search}},
author = {Tabei, Yasuo and Uno, Takeaki and Sugiyama, Masashi and Tsuda, Koji},
booktitle = {Proceedings of 2nd Asian Conference on Machine Learning},
year = {2010},
pages = {145-160},
volume = {13},
url = {https://mlanthology.org/acml/2010/tabei2010acml-single/}
}