Similarity Search Initialization
First Claim
1. A similarity search initialization system comprising:
- a leaf selector 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.
2 Assignments
0 Petitions
Accused Products
Abstract
A similarity search initialization system includes a leaf selector to select a leaf of a suffix tree generated from a target string representing a target sequence. The selected leaf is associated with a prefix in the suffix tree having a longest match to a suffix of a query string representing a query. The system further includes a distance module to determine a distance between the query and a subsequence of the target sequence represented by a candidate substring of the target string. The candidate substring includes the prefix associated with the selected leaf. The determined distance is to provide an initial upper bound in a similarity search of the target sequence using the query.
-
Citations
15 Claims
-
1. A similarity search initialization system comprising:
-
a leaf selector 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A method of similarity search initialization, the method comprising:
-
selecting a leaf of a suffix tree generated from a target string representing a target sequence stored in a memory, 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 executing a distance operator using a processor, the distance operator to determine a distance between the query and a subsequence of the target sequence represented by a candidate substring of the target string, the candidate substring comprising the prefix associated with the selected leaf as a suffix, wherein the determined distance is an initial upper bound in a similarity search of the target sequence using the query. - View Dependent Claims (11, 12, 13)
-
-
14. A non-transient computer readable medium encoded with instructions that, when executed by a processor, implement a similarity search initialization comprising instructions that implement:
-
generating a suffix tree from a string comprising a target string representing a target sequence; identifying a longest prefix in the suffix tree that matches a suffix of a query string representing a query; and determining a distance between the query and a subsequence of the target sequence represented by a candidate substring of the target string, the candidate substring comprising the identified longest prefix as a suffix and having a length equal to the query string, wherein the determined distance provides an initial upper bound in a similarity search of the target sequence using the query. - View Dependent Claims (15)
-
Specification