Abstract: Efficient index structures for fast approximate nearest neighbor queries are required in many applications such as recommendation systems. In high-dimensional spaces, many conventional methods suffer from excessive usage of memory and slow response times. We propose a method where multiple random projection trees are combined. We demonstrate by extensive experiments on a wide variety of data sets that the method is faster than existing partitioning tree or hashing based approaches, making it the fastest available technique on high accuracy levels.

Speaker: Teemu Roos

Affiliation: Associate Professor, Department of Computer Science, University of Helsinki

Place of Seminar: University of Helsinki

Hyvönen et al., “Fast Nearest Neighbor Search through Sparse Random Projections and Voting”, IEEE Big Data Conference 2016: [link]