Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
Locality Sensitive Hashing at Lyst
Search
Maciej Kula
July 24, 2015
Programming
0
1.2k
Locality Sensitive Hashing at Lyst
Description of the intuition behind locality sensitive hashing and its application at Lyst.
Maciej Kula
July 24, 2015
Tweet
Share
More Decks by Maciej Kula
See All by Maciej Kula
Implicit and Explicit Recommender Systems
maciejkula
0
2.6k
Binary Embeddings For Efficient Ranking
maciejkula
0
630
Rust for Python Native Extensions
maciejkula
0
450
Hybrid Recommender Systems at PyData Amsterdam 2016
maciejkula
5
2.6k
Recommendations under sparsity
maciejkula
1
330
Metadata Embeddings for User and Item Cold-start Recommendations
maciejkula
2
850
Other Decks in Programming
See All in Programming
Perl 5 OOP機構30年史 - Perl 5's OOP Mechanism over the past 30 years
moznion
0
320
Ruby Parser progress report 2024
yui_knk
2
230
事業フェーズの変化に対応する 開発生産性向上のゼロイチ
masaygggg
0
200
オートマトン学習しろ / Do automata learning
makenowjust
3
130
Scala におけるコンパイラエラーとの付き合い方
chencmd
2
430
Architecture Decision Record (ADR)
nearme_tech
PRO
1
690
Debugging: All you need to know (for simultaneous interpreting)
jmatsu
2
800
状態管理ライブラリZustandの導入から運用まで
k1tikurisu
3
470
Desafios e Lições Aprendidas na Migração de Monólitos para Microsserviços em Java
jessilyneh
2
150
いつか使える ObjectSpace / Maybe useful ObjectSpace
euglena1215
2
140
connect-go で面倒くささと戦う / 2024-08-27 #newmo_layerx_go
izumin5210
2
650
Boost Performance and Developer Productivity with Jakarta EE 11
ivargrimstad
0
490
Featured
See All Featured
How STYLIGHT went responsive
nonsquared
93
5.1k
Refactoring Trust on Your Teams (GOTO; Chicago 2020)
rmw
29
2.6k
Let's Do A Bunch of Simple Stuff to Make Websites Faster
chriscoyier
502
140k
Unsuck your backbone
ammeep
667
57k
Bash Introduction
62gerente
608
210k
Distributed Sagas: A Protocol for Coordinating Microservices
caitiem20
326
21k
The Invisible Side of Design
smashingmag
296
50k
Atom: Resistance is Futile
akmur
261
25k
Save Time (by Creating Custom Rails Generators)
garrettdimon
PRO
24
610
Web development in the modern age
philhawksworth
205
10k
実際に使うSQLの書き方 徹底解説 / pgcon21j-tutorial
soudai
166
48k
The Language of Interfaces
destraynor
153
23k
Transcript
Speeding up search with locality sensitive hashing. by Maciej Kula
Hi, I’m Maciej Kula. @maciej_kula
We collect the world of fashion into a customisable shopping
experience.
Given a point, find other points close to it. Nearest
neighbour search… 4
None
At Lyst we use it for… 1.) Image Search 2.)
Recommendations 6
Convert image to points in space (vectors) & use nearest
neighbour search to get similar images. 1. Image Search (-0.3, 2.1, 0.5)
Super useful for deduplication & search.
Convert products and users to points in space & use
nearest neighbour search to get related products for the user. 2. Recommendations user = (-0.3, 2.1, 0.5) product = (5.2, 0.3, -0.5)
Great, but…
11 80 million We have images
12 9 million We have products
Exhaustive nearest neighbour search is too slow.
Locality sensitive hashing to the rescue! Use a hash table.
Pick a hash function that puts similar points in the same bucket. Only search within the bucket.
We use Random Projection Forests
Partition by splitting on random vectors
Partition by splitting on random vectors
Partition by splitting on random vectors
Partition by splitting on random vectors
Partition by splitting on random vectors
Points to note Keep splitting until the nodes are small
enough. Median splits give nicely balanced trees. Build a forest of trees.
Why do we need a forest? Some partitions split the
true neighbourhood of a point. Because partitions are random, other trees will not repeat the error. Build more trees to trade off query speed for precision.
LSH in Python annoy, Python wrapper for C++ code. LSHForest,
part of scikit-learn FLANN, an auto-tuning ANN index
But… LSHForest is slow. FLANN is a pain to deploy.
annoy is great, but can’t add points to an existing index.
So we wrote our own.
github.com/lyst/rpforest pip install rpforest
rpforest Quite fast. Allows adding new items to the index.
Does not require us to store points in memory.
We use it in conjunction with PostgreSQL Send the query
point to the ANN index. Get ANN row ids back Plug them into postgres for filtering Final scoring done in postgres using C extensions.
Side note: postgres is awesome. Arrays & custom functions in
C
Gives us a fast and reliable ANN service 100x speed-up
with 0.6 10-NN precision Allows us to serve real-time results All on top of a real database.
thank you @maciej_kula