3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.