Finding profiles similar to a given input required k-nearest-neighbour search over sparse TF-IDF term vectors. The initial approach used a Lucene search index with cosine distance ranking - this produced good results but took on the order of 10 seconds per query, which was too slow for interactive use.
BK-tree index
The solution was a custom BK-tree implementation written in Go. A BK-tree is a metric tree structure that supports efficient nearest-neighbour queries under any distance metric satisfying the triangle inequality. Here, distance was computed over sets of TF-IDF terms (sparse term sets), enabling fast approximate matching without needing to compare every candidate.
Index structure
Indexing ran offline as a nightly batch job. Each indexed record (user profile or content item) was represented by its top-10 TF-IDF terms. To keep tree sizes manageable, a separate BK-tree was built per keyword: for each keyword, all records with that keyword in their top-10 terms were selected and a tree was built over their full sparse term vectors. Trees were serialised to binary gob format and stored on S3.
Query execution
At query time:
- The three highest-weighted keywords from the input vector (or manually entered) were selected.
- The corresponding BK-trees were fetched from S3 and deserialised.
- A k-nearest-neighbour search was run independently on each tree.
- Results from all three trees were merged and re-ranked against the original input vector.
This approach reduced query latency from ~10 seconds (Lucene + cosine distance) to tens-to-hundreds of milliseconds - fast enough for interactive search with the infrastructure budget available.