Patent Document ID: 8972415
Application ID: 13460015

Base Claim:
1. A similarity search initialization system comprising: a leaf selector implemented by a processor to select a leaf of a suffix tree generated from a target string representing a target sequence, the selected leaf being associated with a prefix in the suffix tree having a longest match to a suffix of a query string representing a query; and a distance module to determine a distance between the query and a subsequence of the target sequence that is represented by a candidate substring of the target string, the candidate substring comprising the prefix associated with the selected leaf, wherein the determined distance is to provide an initial upper bound in a similarity search of the target sequence using the query.

---

Claim 9:
9. A similarity search system comprising the similarity search initialization system of claim 1 , the similarity search system further comprising a similarity search engine to determine a distance between the query and the subsequence of the target sequence, the similarity search engine employing the initial upper bound provided by the similarity search initialization system to implement early abandonment during a distance determination of a similarity search.