Erik Bernhardsson, CTO, Better Mortgage, NYC 2017
summary
Library Annoy builds a forest of random projection trees that returns approximate nearest neighbors much faster than brute force, e.g. a scan that took 2m34s becomes 470ms on a laptop, and increasing search work can reproduce exact results in 1–2s. Indexes are saved as a memory-mapped index so queries load instantly. Examples: 6 million food images embedded to 128 dimensions, MNIST pixels at 784 dims; more trees raise accuracy but slow queries.
AI-written summary · about
chapters (29)
- 0:00Intro
- 0:44What's nearest neighbor(s)
- 0:555 nearest neighbors
- 1:20But what's the point?
- 1:34MNIST example
- 2:12MNIST neighbors
- 4:28Nearest food pics
- 4:56Vector methods for text
- 5:38Represent documents and/or words as f-dimensional vector
- 6:27Vector methods for collaborative filtering
- 7:01CF vectors - examples
- 8:04Geospatial indexing
- 8:56Nearest neighbors the brute force way
- 9:31Using word2vec's brute force search
- 9:47Introducing Annoy
- 9:59mmap = best
- 10:56Using Annoy's search
- 11:52performance
- 12:28Start with the point set
- 13:16Side note: making trees small
- 13:28Binary tree
- 13:55Searching the tree
- 14:45Problemo
- 15:16Trick 1: Priority queue
- 16:34Annoy query structure
- 16:52Compute distances
- 20:33Improving the algorithm
- 21:13ann-benchmarks
- 22:21Current ANN trends
related talks
26mUsing Random Projections to Make Sense of High-Dimensional ...
24mSpeeding up search with locality sensitive hashing
32mRetrieval Augmentation and Semantic Search at Scale
37mLearned Indexes: a New Idea for Efficient Data Access #bbuzz
45mBehind the hype: managing billion-scale embeddings in Elasticsearch and OpenSearch
47mLatest innovations from Elasticsearch: Drive speed, scale & relevance (PRT266)
01h 09mVector Search: Ask Me Anything!
52mModern Problems Require Modern Solutions