Approximate query processing using wavelets

• US 6,760,724 B1
• Filed: 07/24/2000
• Issued: 07/06/2004
• Est. Priority Date: 07/24/2000
• Status: Expired due to Term

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Rastogi, Rajeev, Garofalakis, Minos N., Chakrabarti, Kaushik, Shim, Kyuseok
• Primary Examiner(s): Rones, Charles
• Assistant Examiner(s): Mahmoudi, Hassan
• Application Number:
  US09/624,115
• Time in Patent Office: 1,443 Days
• Field of Search: 707/1, 707/4, 707/102, 707/104.1, 382/283, 382/232, 382/149, 382/100, 382/248, 382/224, 382/279, 382/128, 382/132, 704/9, 375/240.03, 375/240.11, 700/17, 386/46
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method for querying electronic data. The query method comprises creating wavelet-coefficient synopses of the electronic data and then querying the synopses in the wavelet-coefficient domain to obtain a wavelet-coefficient query result. The wavelet-coefficient query result is then rendered to provide an approximate result.

Claims

1. A computer implemented method for querying electronic data to generate approximate answers to queries comprising the steps of:

generating multi-dimensional wavelet-coefficient synopses of at least one relational array;

querying said multi-dimensional wavelet-coefficient synopses of said at least one relational array to obtain a wavelet-coefficient result; and

deriving an approximate result from said wavelet-coefficient result.

2. The method of claim 1, wherein said generating step comprises:

decomposing said at least one relational array into multi-dimensional wavelet-coefficients; and

retaining a portion of said multi-dimensional wavelet-coefficients which exceed a predefined threshold to produce said multi-dimensional wavelet-coefficient synopses.

3. The method of claim 2, wherein said decomposing step comprises:

decomposing said at least one relational array into multi-dimensional Haar wavelet-coefficients.

4. The method of claim 3, wherein said decomposing step is performed in a single pass over said at least one relational array.

5. The method of claim 1, wherein said wavelet-coefficient synopses are multi-dimensional Haar wavelet-coefficient synopses.

6. The method of claim 5, wherein said generating step comprises:

decomposing said at least one relational array into a plurality of sub-arrays;

recursively computing multi-dimensional Haar wavelet-coefficients for each of said plurality of sub-arrays; and

composing the recursively computed multi-dimensional Haar wavelet-coefficients for said plurality of sub-arrays into said multi-dimensional Haar wavelet-coefficient synopses.

7. The method of claim 1, wherein said querying step is performed directly on said wavelet-coefficient synopses of said at least one relational array.

8. The method of claim 7, wherein said querying step comprises using query processing algorithms that operate directly on said wavelet coefficient synopses.

9. The method of claim 8, wherein the input and output of each of said query processing algorithms are sets of wavelet coefficients.

10. The method of claim 1, wherein said deriving step comprises rendering said approximate result from said wavelet-coefficient result.

11. The method of claim 10, wherein said approximate result is in relational form.

12. The method of claim 1, wherein said querying step comprises at least the step of performing aggregate and non-aggregate SQL operations directly on said wavelet-coefficient synopses of said at least one relational array in the wavelet coefficient domain.

13. A computer implemented query method for querying electronic data comprising the steps of:

generating multi-dimensional wavelet-coefficient synopses of relational data;

querying said multi-dimensional wavelet-coefficient synopses to obtain a wavelet-coefficient result; and

expanding said wavelet-coefficient result into an approximate relational result.

14. The method of claim 13, wherein said generating step comprises computing said wavelet-coefficient synopses in a single pass over said relational data.

15. The method of claim 14, wherein said wavelet-coefficient synopses are multi-dimensional Haar wavelet-coefficient synopses.

16. The method of claim 13, wherein said querying step comprises at least the step of performing aggregate and non-aggregate SQL operations directly on said wavelet-coefficient synopses of said at least one relational array in the wavelet coefficient domain.

17. A device for querying electronic data to generate approximate answers to queries comprising:

a processing unit having;

a first program for generating multi-dimensional wavelet-coefficient synopses of at least one relational array;

a second program for querying said wavelet-coefficient synopses of said at least one relational array to obtain a wavelet-coefficient result; and

a third program for deriving an approximate result from said wavelet-coefficient result; and

a processor for executing the programs; and

an output device for displaying said approximate result.

18. The system of claim 17, wherein said second program performs aggregate and non-aggregate SQL operations directly on said wavelet-coefficient synopses of said at least one relational array in the wavelet coefficient domain.