Show description

We pop from the heap another θ − 1 − x elements, identify the new top element of the heap, let it be r¨, and directly skip to the first element s¨ ≥ r¨ in every token list (we can identify such elements using binary search on the respective lists). 1 All-Match Selection Queries 303 to the heap, and repeat. An important observation here is that an element that was popped from the heap might end up subsequently being re-inserted to the heap, if it happens to be equal to the top element of the heap after the θ − 1 total removals.

L(λvm )} be the m lists corresponding to the query tokens. t. λvi ∈ s. The simplest algorithm for evaluating the similarity between the query and all the strings in lists Lv , is to perform a multiway merge of the string identifiers in Lv , to compute all intersections v ∩ s. This will directly yield the Weighted Intersection similarity. Whether we compute the weighted intersection on sequences, frequency-sets or sets depends on whether the initial construction of the inverted index was done on sequences, frequency-sets, or sets.

Let N k be the k-th smallest similarity score in heap H. t. N (s, v) ≥ N k , hence the algorithm can stop inserting new strings in M . The algorithm can also evict from M strings whose best-case similarity is smaller than N k , as both N k and the best-case similarity of strings in M keep getting tighter. After the frontier condition has been met, the algorithm needs to simply complete the partial similarity scores of strings already in M in order to determine the final top-k answers. The important question is how to seed the algorithm with a good set of k initial candidates.