Similarity search initialization

• US 8,972,415 B2
• Filed: 04/30/2012
• Issued: 03/03/2015
• Est. Priority Date: 04/30/2012
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Viswanathan, Krishnamurthy, Gupta, Chetan Kumar, Al Mueen, Abdullah
• Primary Examiner(s): Truong, Dennis
• Application Number:
  US13/460,015
• Publication Number:
  US 20130290350A1
• Time in Patent Office: 1,037 Days
• Field of Search: 707/749, 707/706, 707/711, 707/780, 707/797, 715/236, 715/210, 715/700
• US Class Current: 707/749
• CPC Class Codes: G06F 16/90335 Query processing

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.

Claims

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.

2. A similarity search initialization system of claim 1, further comprising a suffix tree generator to generate the suffix tree from a concatenation of the target string and the query string.

3. The similarity search initialization system of claim 2, wherein the selected leaf is a sibling leaf of a leaf of the suffix tree, the leaf representing the query string suffix, and wherein the candidate substring is a substring of the target string that begins at a location in the target string given by the selected leaf minus a difference between a length of the query string and a length of the query string suffix.

4. The similarity search initialization system of claim 3, wherein the selected leaf is a left-most sibling leaf of the leaf representing the query string suffix.

5. The similarity search initialization system of claim 1, wherein the target sequence is a time sequence.

6. The similarity search initialization system of claim 1, wherein the distance module is to determine the distance between the query and each subsequence of a plurality of subsequences of the target sequence corresponding to a respective one of a plurality of candidate substrings, each candidate substring comprising a different prefix of a plurality of prefixes associated with a corresponding plurality of selected leaves produced by the leaf selector with respect to a plurality of different query string suffixes, and wherein the determined distance used as the initial upper bound is a minimum of the determined distances.

7. The similarity search initialization system claim 1, further comprising a string quantizer to convert the target sequence into the target string and to convert the query into the query string, the target string and the query string each comprising a different termination symbol, wherein the termination symbols are not present in a finite symbol alphabet of the string quantizer.

8. A non-transient computer readable medium storing instructions that, when executed by a processor, implement the similarity search initialization system of claim 1, the instructions comprising:

instructions that implement the leaf selector to select a leaf of a suffix tree; and

instructions that implement the distance module to determine a distance between the query and the subsequence of the target sequence.

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.

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.

11. The method of similarity search initialization of claim 10, further comprising:

generating the suffix tree from a concatenation of the target string and the query string,

wherein the selected leaf is a sibling leaf of a leaf of the suffix tree, the leaf representing the query string suffix, and wherein the candidate substring is a substring that begins at a location in the target string given by the selected leaf minus a difference between a length of the query string and a length of the query string suffix.

12. The method of similarity search initialization of claim 10, wherein execution of the distance operator determines the distance between the query and each subsequence of a plurality of subsequences of the target sequence corresponding to respective ones of a plurality of candidate substrings, each candidate substring comprising a different prefix of a plurality of prefixes associated with a corresponding plurality of different query string suffixes, and wherein the determined distance used as the initial upper bound is a minimum of the determined distances.

13. The method of similarity search initialization of claim 10, further comprising:

quantizing the target sequence to produce the target string, the target string comprising a first termination symbol that is not represented in a finite symbol alphabet used in quantizing; and

quantizing the query to produce the query string, the query string comprising a second termination symbol that is not in the finite symbol alphabet used in quantizing, the second termination symbol being different from the first termination symbol,

wherein the target sequence is a time sequence.

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.

15. A similarity search initialization system comprising the non-transient computer readable medium of claim 14, the search initialization system further comprising:

a processor to execute the instructions encoded on the non-transient computer readable medium; and

a memory to store the suffix tree and the determined distance,

wherein the string used in generating the suffix tree comprises a concatenation of the target string and the query string, and wherein the instructions that implement identifying the longest prefix comprise instructions that implement selecting a leaf of the sub-tree rooted at the sibling of a leaf representing the query string suffix, and wherein the candidate substring is a substring starting at a location in the target string given by the sibling leaf minus a difference between the query string length and a length of the query string suffix.