# I/O-Efficient Similarity Join

arXiv: https://arxiv.org/abs/1507.00552 · HTML: https://mlsanity.com/paper/1507.00552/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jul 2015.

## Built on by (most cited first, 3 of 3)

- [DM algorithms in health industry](https://mlsanity.com/paper/2103.01888/) (2021)
- [Algoritmos de miner'ia de datos en la industria sanitaria](https://mlsanity.com/paper/2104.09395/) (2021)
- [Mathematical Models for Local Sensing Hashes](https://mlsanity.com/paper/2111.08344/) (2021)

## Abstract (arXiv)

We present an I/O-efficient algorithm for computing similarity joins based on locality-sensitive hashing (LSH). In contrast to the filtering methods commonly suggested our method has provable sub-quadratic dependency on the data size. Further, in contrast to straightforward implementations of known LSH-based algorithms on external memory, our approach is able to take significant advantage of the available internal memory: Whereas the time complexity of classical algorithms includes a factor of Nρ, where ρ is a parameter of the LSH used, the I/O complexity of our algorithm merely includes a factor (N/M)ρ, where N is the data size and M is the size of internal memory. Our algorithm is randomized and outputs the correct result with high probability. It is a simple, recursive, cache-oblivious procedure, and we believe that it will be useful also in other computational settings such as parallel computation.