Compressed representation of a data base that permits AD HOC querying

• US 5,946,692 A
• Filed: 05/08/1997
• Issued: 08/31/1999
• Est. Priority Date: 05/08/1997
• Status: Expired due to Term

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Faloutsos, Christos N., Jagadish, Hosagrahar Visvesvaraya, Korn, Philip Russell
• Primary Examiner(s): Kulik, Paul V.
• Assistant Examiner(s): ROBINSON, GRETA LEE
• Application Number:
  US08/848,454
• Time in Patent Office: 845 Days
• Field of Search: 707/101, 707/100, 707/104, 707/2, 707/1
• 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: G06F 18/2135 based on approximation criteria, e.g. principal component analysis
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A method and system for compressing a data base that permits queries on the compressed representation of the data base. Another feature is that an approximation of the values of the data base are derivable directly from the compressed representation of the data base. Yet another feature is correction of poor approximations of the reconstructed data. Still another feature is the capability of performing aggregate queries of the compressed representation of the data base.

Claims

1. A data base system comprising:

a compressed representation of a data base, said data base having cells containing values and said compressed representation having a property that at least approximations of said value of said cells of said data base are derivable directly from said compressed representation, said property particularly comprising the property of lossy compressed representation; and

a query engine for responding to a query requesting at least said value of a given cell by deriving at least an approximation of said value of said given cell directly from said compressed representation.

2. The data base system set forth in claim 1 wherein:

time required to derive said value of said given cell is substantially constant with respect to size of said data base.

3. The data base system set forth in claim 1 wherein:

said query comprises an aggregate query whose result is a function of a set of said values of said given cells.

4. The data base system set forth in claim 1 further comprises:

correction information which when accessed by a cell'"'"'s location, returns information for correcting said cell'"'"'s value;

correction means for correcting said errors of said approximation of said values of said cells stored in said table; and

when querying said compressed representation, determining for said information whether error correction is necessary, and using said correction means to make said correction.

5. The data base system set forth in claim 1 wherein:

said compressed representation is accomplished by a clustering method.

6. The data base system set forth in claim 1 wherein:

said compressed representation is accomplished by a spectral method.

7. The data base system set forth in claim 1 wherein:

said compressed representation is accomplished by computing a singular value decomposition of said data base.

8. The data base system set forth in claim 1 further comprises:

said data base from which said compressed representation is made.

9. The data base system set forth in claim 1 further comprises:

correction information which when accessed by a cell'"'"'s location, returns information for correcting said cell'"'"'s value.

10. The data base system set forth in claim 9 further comprises:

correction means for correcting said errors of said approximations of said values of said cells stored in said correction information.

11. The data base system set forth in claim 10 wherein:

said correction information contains correct values for said cells having an error greater than a predetermined amount.

12. The data base system set forth in claim 11 wherein:

said correction information contains deltas, said deltas representing the difference between said value of said cell and said approximation of said value.

13. The data base system set forth in claim 12 further comprises:

a hash table for storing said correction information.

39. The data base system of claim 1, said compressed representation being accomplished based on an input parameter.

40. The data base system of claim 39, said input parameter for determining a maximum percentage of storage space utilized after compression.

41. The data base system of claim 40, said compressed representation being accomplished based upon said determined maximum percentage of storage space for minimizing a total reconstruction error.

14. A method of querying a data base to obtain values of cells therein comprising the steps of:

making a compressed representation of said data base, said data base representation having a property that at least approximations of said values of said cells of said data base are derivable directly from said compressed representation, said compressed representation being lossy; and

after said compressed representation has been made, querying said compressed representation using a query engine for responding to a query requesting at least said value of said cells by deriving at least said approximation of said value of said given cell directly from said compressed representation.

15. The method set forth in claim 14 wherein:

in said step of making said compressed representation, said compressed representation further has a property that at least said approximation of said value of a cell may be further obtained from said compressed representation in a time which is substantially constant with respect to size of said data base.

16. The method set forth in claim 14 wherein said compressed representation is lossy and the method further comprises the steps of:

when making said compressed representation, determining from correction information for each cell whether said approximation of said value of said cell has an error;

when said approximation has such said error, making said error correcting entry for said cell associated with said compressed representation; and

when querying said compressed representation, determining from said correction information whether error correction is necessary, and if correction is necessary, using said error correcting entry to make said correction.

17. The method set forth in claim 14 wherein:

in the step of making a compressed representation, said compressed representation is made using a clustering method.

18. The method set forth in claim 14 wherein:

in the step of making a compressed representation, said compressed representation is made using a spectral method.

19. The method set forth in claim 14 wherein:

in the step of making a compressed representation, said compressed representation is made by computing a singular value decomposition of said data base.

20. The method set forth in claim 16 wherein:

in the step of making a compressed representation, said compressed representation is made by computing a singular value decomposition of said data base.

21. The method set forth in claim 19 wherein:

said singular value decomposition is computed in two passes over said data base including,

representing said data base as a column to column similarity matrix by constructing said column to column similarity matrix, tracking a partial sum of each said value of said column to column similarity matrix, reading a row of said database at a time, multiplying and adding every combination of elements in that said row to an appropriate element of said column to column similarity matrix;

storing said column to column similarity matrix in memory;

computing eigenvectors of said column to column similarity matrix;

computing eigenvalues of said column to column similarity matrix;

computing a second matrix by multiplying said eigenvectors, an inverse of said eigenvalue and said database represented as a matrix, whereby said compressed representation of said database is derived.

22. The method set forth in claim 20 wherein:

said singular value decomposition is computed in two passes over said data base including,

representing said data base as a column to column similarity matrix by constructing said column to column similarity matrix, tracking a partial sum of each said value of said column to column similarity matrix, reading a row of said database at a time, multiplying and adding every combination of elements in that said row to an appropriate element of said column to column similarity matrix;

storing said column to column similarity matrix in memory;

computing eigenvectors of said column to column similarity matrix;

computing eigenvalues of said column to column similarity matrix;

computing a second matrix by multiplying said eigenvectors, an inverse of said eigenvalue and said database represented as a matrix, whereby said compressed representation of said database is derived.

42. The method of claim 14, said step of making a compressed representation being based on an input parameter.

43. The method of claim 42, said input parameter for determining a maximum percentage of storage space utilized after compression.

44. The method of claim 43, further comprising the step of:

based on said input parameter, determining a minimum total reconstruction error for said compressed representation.

23. A data base system comprising:

a compressed representation of a data base, said data base having cells containing values and said compressed representation having a property that at least approximations of said value of said cells of said data base are derivable directly from said compressed representation;

a query engine for responding to a query requesting at least said value of a given cell by deriving at least an approximation of said value of said given cell directly from said compressed representation;

correction information which when accessed by a cell'"'"'s location, returns information for correcting said cell'"'"'s value; and

correction means for correcting said errors of said approximations of said values of said cells stored in said information.

24. A data base system comprising:

a compressed representation of a data base, said data base having cells containing values and said compressed representation having a property that at least approximations of said value of said cells of said data base are derivable directly from said compressed representation; and

a query engine for responding to an aggregate query whose result is a function of a set of said values from said given cells of said data base by deriving said set of values directly from said compressed representation, said result of said aggregate query being an approximation of a correct result of said aggregate query.

25. The data base system set forth in claim 24 further comprises:

correction information which when accessed by a cell'"'"'s location, returns information for correcting said cell'"'"'s value.

26. The data base system set forth in claim 25 further comprises:

correction means for using said correction information to correct errors in said approximation.

27. The data base system set forth in claim 26 wherein:

said correction information contains said values of said cells having an error greater than a predetermined amount.

28. The data base system set forth in claim 27 wherein:

said correction information contains deltas, said deltas represent the difference between said value of said cell and said approximation of said value.

29. The data base system set forth in claim 28 further comprises:

a hash table for storing said correction information.

30. A method of querying a data base to obtain values of cells therein comprising the steps of:

making a compressed representation of said data base, said data base representation having a property that at least approximations of said values of said cells of said data base are derivable directly from said compressed representation;

after said compressed representation has been made, querying said compressed representation using a query engine for responding to a query requesting at least said value of said cells by deriving at least said approximation of said given cell directly from said compressed representation;

when making said compressed representation, determining for each cell whether said approximation of said value of said cell has an error greater than a predetermined amount;

when said approximation has such said error, making said error correcting entry for said cell in correction information associated with said compressed representation; and

when querying said compressed representation, determining from said correction information whether error correction is necessary, and if correction is necessary, using said error correcting entry to make said correction.

31. The method set forth in claim 30 wherein said error correcting entry is accomplished by computing singular value decomposition delta.

32. A method of aggregate querying a data base system to obtain a set of values of cells therein comprising the steps of:

making a compressed representation of said data base, said data base representation having a property that said set of values of said cells of said data base are derivable directly from said compressed representation; and

after said compressed representation has been made, aggregate querying said compressed representation using a query engine for responding to an aggregate query requesting at least said set value of said cells by deriving said given cells directly from said compressed representation, said response to said aggregate query being an approximation of a correct aggregate query response.

33. The method set forth in claim 32 wherein said compressed representation is lossy and the method further comprises the steps of:

when making said compressed representation, determining for each cell whether said set of value of said cells has an error greater than a predetermined amount;

when said cells has such said error, making said error correcting entry for said cells in correction information associated with said compressed representation; and

when querying said compressed representation, determining from said correction information whether error correction is necessary, and if correction is necessary, using said error correcting entry to make said correction.

34. A memory device characterized in that:

said memory device contains a compressed representation of a data base, said compressed representation having a property that at least approximations of said value of said cells of said data base are directly derivable from said compressed representation, said property particularly comprising the property of lossy compressed representation.

35. The memory device set forth in claim 34 further comprises:

correction information which when accessed by a cell'"'"'s location, returns information for correcting said cell'"'"'s value.

36. A data base system comprising:

a compressed representation of a data base, said data base having cells containing values and said compressed representation having a property that at least approximations of said value of said cells of said data base are derivable directly from said compressed representation; and

a query engine for responding to a query requesting at least said value of a given cell by deriving at least an approximation of said value of said given cell directly from said compressed representation,

said compressed representation being accomplished by one of a clustering method, a spectral method, or by computing a singular value decomposition of said data base.

37. A method of querying a data base to obtain values of cells therein comprising the steps of:

making a compressed representation of said data base, said data base representation having a property that at least approximations of said values of said cells of said data base are derivable directly from said compressed representation;

after said compressed representation has been made, querying said compressed representation using a query engine for responding to a query requesting at least said value of said cells by deriving at least said approximation of said value of said given cell directly from said compressed representation; and

in said step of making said compressed representation, said compressed representation further having a property that at least said approximation of said value of a cell may be further obtained from said compressed representation in a time which is substantially constant with respect to size of said data base.

38. A data base system comprising:

a compressed representation of a data base, said data base having cells containing values and said compressed representation having a property that at least approximations of said value of said cells of said data base are derivable directly from said compressed representation;

a query engine for responding to an aggregate query whose result is a function of a set of said values from said given cells of said data base by deriving said set of values directly from said compressed representation; and

correction information which, when accessed according to a cell'"'"'s location, returns information for correcting said cell'"'"'s value.

45. A memory device characterized in that, said memory device contains code which, when executed in a computer, performs the steps of:

making a compressed representation of said data base, said data base representation having a property that at least approximations of said values of said cells of said data base are derivable directly from said compressed representation, said compressed representation is lossy; and

after said compressed representation has been made, querying said compressed representation using a query engine for responding to a query requesting at least said value of said cells by deriving at least said approximation of said value of said given cell directly from said compressed representation.

46. A memory device characterized in that, said memory device contains code which, when executed in a computer, performs the steps of:

making a compressed representation of said data base, said data base representation having a property that at least approximations of said values of said cells of said data base are derivable directly from said compressed representation;

after said compressed representation has been made, querying said compressed representation using a query engine for responding to a query requesting at least said value of said cells by deriving at least said approximation of said given cell directly from said compressed representation;

when making said compressed representation, determining for each cell whether said approximation of said value of said cell has an error greater than a predetermined amount;

when said approximation has such said error, making said error correcting entry for said cell in correction information associated with said compressed representation; and

when querying said compressed representation, determining from said correction information whether error correction is necessary, and if correction is necessary, using said error correcting entry to make said correction.