← AI HoodmanNo. 013 · Retrieval

Approximate Nearest Neighbor Search

How do you cluster a billion videos?

01of 06
Use the arrows, swipe or the arrow keys to turn the slides. Click a slide to read it page by page.
  1. Slide 1 of 6: You need to split 1 billion video embeddings into 100,000 groups, so search only checks a few. ? 1 billion videos 100,000 groups How do you cluster a billion videos into groups?
  2. Slide 2 of 6: The key idea: K-means clustering. 1 Drop K centers at random. 3 Each center moves to the average of its dots. 2 Each dot joins its nearest center. 4 Repeat until the centers stop moving. Videos that are close together end up in the same group.
  3. Slide 3 of 6: At a billion videos: Train on a sample. 1 Randomly pick 1% (10 million) 2 Run k-means on the sample 3 Assign all 1 billion to the nearest center How many groups? About 4 × √ N, where N = number of videos. This is how FAISS (Facebook AI Similarity Search) builds its index. k-means on all 1 billion is too slow, and a random sample learns the same map.
  4. Slide 4 of 6: The catch: The best match can sit across the border. Group B Best match Group A Group D Search 1 group: missed Search 3 groups: found Groups have hard borders, but similarity doesn't.
  5. Slide 5 of 6: The fix: Search the closest few groups. True best matches found (%) Search time (relative) 90% 95% 99% 25x 70% 3x 1x 5.5x 10 50 100 500 0.01% 0.05% 0.1% 0.5% Groups searched (out of 100,000) Start around 0.1% of groups. Raise it until you find ~95% of the true best matches. More groups searched means better matches, but slower search.
  6. Slide 6 of 6: Takeaway: Cluster once, offline. Search the nearest clusters, online.

Keep reading

Approximate Nearest Neighbor Search · 1 / 6
  1. Slide 1 of 6: You need to split 1 billion video embeddings into 100,000 groups, so search only checks a few. ? 1 billion videos 100,000 groups How do you cluster a billion videos into groups?
  2. Slide 2 of 6: The key idea: K-means clustering. 1 Drop K centers at random. 3 Each center moves to the average of its dots. 2 Each dot joins its nearest center. 4 Repeat until the centers stop moving. Videos that are close together end up in the same group.
  3. Slide 3 of 6: At a billion videos: Train on a sample. 1 Randomly pick 1% (10 million) 2 Run k-means on the sample 3 Assign all 1 billion to the nearest center How many groups? About 4 × √ N, where N = number of videos. This is how FAISS (Facebook AI Similarity Search) builds its index. k-means on all 1 billion is too slow, and a random sample learns the same map.
  4. Slide 4 of 6: The catch: The best match can sit across the border. Group B Best match Group A Group D Search 1 group: missed Search 3 groups: found Groups have hard borders, but similarity doesn't.
  5. Slide 5 of 6: The fix: Search the closest few groups. True best matches found (%) Search time (relative) 90% 95% 99% 25x 70% 3x 1x 5.5x 10 50 100 500 0.01% 0.05% 0.1% 0.5% Groups searched (out of 100,000) Start around 0.1% of groups. Raise it until you find ~95% of the true best matches. More groups searched means better matches, but slower search.
  6. Slide 6 of 6: Takeaway: Cluster once, offline. Search the nearest clusters, online.