Single versus Multiple Sorting in All Pairs Similarity Search


Yasuo Tabei JST Minato ERATO Project, Takeaki Uno National Institute Japan, Masashi Sugiyama Tokyo Institute Technology, Koji Tsuda National Institute Advanced Industrial Science Technology ;
Proceedings of 2nd Asian Conference on Machine Learning, PMLR 13:145-160, 2010.


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.

Related Material