Finding the top K most similar sets

Question

I have a database containing sets of words. So for example, I have a database that has:

{happy, birthday, to, you}
{how, are, you}
...

Given a query set, lets say {how, was your, birthday}, I want to find the top K sets in the database that is most similar to my query. Similarity metric used can be something like Jaccard's Index. Right now, I go through the database one by one and calculate the Jaccard Index and keep track of the top K scores found so far. I was wondering if there are any data structures or methods that would allow me to more efficiently find the top K scores. Right now it's a linear search. Thanks

Answer 1

Do you have any information about your data set? Is it sparse, will most similarities be zero? Is the total dictionary small? You could consider a inverted index. For example

word  query_id
W1    [1, 3, 6]
W2    [2, 5]
W3    [1, 3, 4]
W4    [2, 3, 4]
W5    [2, 3, 6]

query_id  query
1         W1 W3
2         W2 W4 W4
3         W1 W3 W4 W5
4         W3 W4
5         W2
6         W1 W5

Here W_i is a word, e.g. birthday and query_id is the id of the query in the database. e.g. {how, are, you} might have id 22. Now you get a query {W1 W3 W5}. Aggregate counts on the inverted index. W1 was seen in queries 1, 3, and 6. W3 in 1, 3, and 4, etc.

query_id  count
1         2
2         1
3         3
4         1
6         2

The count will the number of words in common with the incoming query, this is the numerator of the jaccard similarity. So, to find the top k you can start with the queries with the highest count. query_id 3 has the highest count and its similarity is 3/4.

If you have a massive database there are techniques like locality sensitive hashing which will basically reduce the search space into a small bucket. The incoming query gets hashed and lands in a bucket. You can then do a linear search with all the queries in this bucket to find the nearest k.