SYSTEMS AND METHODS FOR COMPUTATION OF OPTIMAL DISTANCE BOUNDS ON COMPRESSED TIME-SERIES DATA

• US 20090204574A1
• Filed: 02/07/2008
• Published: 08/13/2009
• Est. Priority Date: 02/07/2008
• Status: Active Grant

• Current Assignee: International Business Machines SA (International Business Machines Corporation)
• Original Assignee: International Business Machines SA (International Business Machines Corporation)
• Inventors: Yu, Philip Shi-Lung, Vlachos, Michail
• Granted Patent: US 7,882,126 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2474 Sequence data queries, e.g. querying versioned data
• CPC Class Codes: G06F 2216/03 Data mining

Abstract

There are provided a method and a system for computation of optimal distance bounds on compressed time-series data. In a method for similarity search, the method includes the step of transforming sequence data into a compressed sequence represented by top-k coefficients of the sequence data and a sum of the energy of omitted coefficients of the sequence data. The method further includes the step of computing at least one of a lower bound and an upper bound on a distance range between a query sequence and the compressed sequence, given a first and a second constraint. The first constraint is that a sum of squares of the omitted coefficients is less than a sum of the energy of the omitted coefficients. The second constraint is that the energy of the omitted coefficients is less than the energy of a lowest energy one of the top-k coefficients.

Claims

1. A method for similarity search, comprising:

transforming sequence data into a compressed sequence represented by top-k coefficients of the sequence data and a sum of the energy of omitted coefficients of the sequence data; and

computing at least one of a lower bound and an upper bound on a distance range between a query sequence and the compressed sequence, given a first and a second constraint, the first constraint being a sum of squares of the omitted coefficients being less than a sum of the energy of the omitted coefficients, the second constraint being the energy of the omitted coefficients being less than the energy of a lowest energy one of the top-k coefficients.

2. The method of claim 1, wherein any of the lower bound and the upper bound is substantially identical to an actual distance between the query sequence and the compressed sequence subject to an amount of compression of at least the compressed sequence.

3. The method of claim 1, wherein the query sequence is compressed.

4. The method of claim 3, wherein any of the lower bound and the upper bound is substantially identical to an actual distance between the query sequence and the compressed sequence subject to an amount of compression of the query sequence and the compressed sequence.

5. The method of claim 1, wherein said computing step uses a linear distance function, and is unrestricted with respect to the linear distance function used.

6. The method of claim 1, wherein the linear distance function is Euclidean distance.

7. The method of claim 1, wherein said computing step uses a non-linear distance function that is capable of being bounded by a linear distance.

8. The method of claim 1, wherein the non-linear distance function is at least one of as Time-Warping and Longest Common Subsequence.

9. The method of claim 1, wherein the sequence data is transformed using an orthonormal transform.

10. The method of claim 9, wherein the orthonormal transform involves at least one of Fourier components, wavelet components, and principal components of the sequence data.

11. A computer readable medium comprising a computer readable program for similarity search, wherein the computer readable program when executed on a computer causes the computer to perform the steps of:

transforming sequence data into a compressed sequence represented by top-k coefficients of the sequence data and a sum of the energy of omitted coefficients of the sequence data; and

computing at least one of a lower bound and an upper bound on a distance range between a query sequence and the compressed sequence, given a first and a second constraint, the first constraint being a sum of squares of the omitted coefficients being less than a sum of the energy of the omitted coefficients, the second constraint being the energy of the omitted coefficients being less than the energy of a lowest energy one of the top-k coefficients.

12. The computer readable medium of claim 11, wherein any of the lower bound and the upper bound is substantially identical to an actual distance between the query sequence and the compressed sequence subject to an amount of compression of at least the compressed sequence.

13. The computer readable medium of claim 11, wherein the query sequence is compressed.

14. The computer readable medium of claim 13, wherein any of the lower bound and the upper bound is substantially identical to an actual distance between the query sequence and the compressed sequence subject to an amount of compression of the query sequence and the compressed sequence.

15. The computer readable medium of claim 11, wherein said computing step uses a linear distance function, and is unrestricted with respect to the linear distance function used.

16. The computer readable medium of claim 11, wherein the linear distance function is Euclidean distance.

17. The computer readable medium of claim 11, wherein said computing step uses a non-linear distance function that is capable of being bounded by a linear distance.

18. The computer readable medium of claim 11, wherein the non-linear distance function is at least one of as Time-Warping and Longest Common Subsequence.

19. The computer readable medium of claim 11, wherein the sequence data is transformed using an orthanormal transform.

20. The computer readable medium of claim 19, wherein the orthonormal transform involves at least one of Fourier components, wavelet components, and principal components of the sequence data.