Method and system for forming, storing and using sets of data values

• US 6,460,046 B1
• Filed: 06/01/1999
• Issued: 10/01/2002
• Est. Priority Date: 06/01/1999
• Status: Expired due to Fees

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navigation Technologies Corp. (Nokia Corporation)
• Inventors: Meek, James A.
• Primary Examiner(s): Coby, Frantz
• Application Number:
  US09/323,339
• Time in Patent Office: 1,218 Days
• Field of Search: 707/102, 707/100, 707/101, 707/103, 707/104, 701/200, 701/208, 701/211, 358/133, 382/56
• US Class Current: 707/741
• CPC Class Codes: G01C 21/387 Organisation of map data, e.g. version management or database structures
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: Y10S 707/919 Geographic
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A data construction for storing data efficiently and a method for forming and using the data construction is disclosed. The method comprises representing a set of actual data values from an original source of data with an alternative representation. One or more parameters of a formula are determined to approximate the set of actual data values in the original source of data. For each actual data value in the original source of data, the difference between the actual data value and the value predicted therefor by the formula is determined. The difference for each actual data value is stored in a data construction on the medium along with the one or more parameters. The alternative representation preserves the information content of the actual data values from the original source of data while reducing the storage requirements for storing the information on a medium.

Claims

1. A method of providing for a compact representation of data in a database used by a computer-based system comprising:

determining at least one parameter value by which a predefined formula approximates a first set of actual data values contained in said database; and

using a computer program to store an alternative representation of said first set of actual data values in a data construction to form a compact representation of said database, wherein said alternative representation comprises a difference between each actual data value in said first set and a value predicted therefor by said predefined formula.

2. The method of claim 1 further comprising the step of:

storing said data construction on a computer-readable medium.

3. The method of claim 1 further comprising the step of:

storing a group descriptor array with said alternative representation, wherein said group descriptor array contains a plurality of parameter values including a plurality of base values and at least one multiplier value.

4. The method of claim 1 further comprising the step of:

storing a group descriptor array with said alternative representation, wherein said group descriptor array contains a plurality of parameter values including a plurality of base values and a plurality of multiplier values, wherein each multiplier value of said plurality of multiplier values is associated with a respective one base value of said plurality of base values.

5. The method of claim 1 further comprising the step of:

storing an alternative representation of a second set of actual data values in said data construction, wherein said alternative representation of said second set of actual data values is associated with said alternative representation of said first set of actual data values in said data construction.

6. The method of claim 1 wherein said predefined formula comprises a linear relationship.

7. The method of claim 6 wherein said at least one parameter value comprises a multiplier, wherein said multiplier predicts an amount by which each succeeding data value in said first set of actual data values changes according to said linear relationship.

8. The method of claim 6 wherein said at least one parameter value comprises a base value, wherein said base value comprises a minimum actual value of all values in said first set.

9. A geographic database comprising an index including data values that are alternative representations of actual data values, wherein said data values in said index are formed according to the method of claim 1.

10. The geographic database of claim 9 wherein said index associates geographic record ID'"'"'s with locations on a storage medium at which data associated with said geographic record ID'"'"'s is located.

11. A geographic database stored on a computer-readable medium, comprising:

geographic data values that are alternative representations of actual data values, wherein said data values are formed according to the method of claim 1.

12. A data construction in a database stored on a computer-readable physical storage medium comprising:

at least one parameter by which a formula predicts each value of a plurality of actual data values in an original source of data in a database; and

for each actual data value of said plurality of actual data values, an alternative representation value therefor stored in a compact representation of the database, wherein said alternative representation value comprises a difference by which said actual value in said plurality of actual data values differs from a value predicted therefor according to said formula.

13. The invention of claim 12 wherein said plurality of actual data values are record ID'"'"'s.

14. The invention of claim 12 further comprising:

an identification of a base value, wherein said base value is equal to a smallest value of said plurality of actual data values in said original source of data.

15. The invention of claim 12 further comprising:

an identification of a base value, wherein said base value is selected so that each difference by which an actual data value differs from the value predicted therefor by said formula has the same sign.

16. The invention of claim 12 further comprising:

an identification of a base value, wherein said base value is selected so that a range of positive differences is approximately equal to a range of negative differences.

17. The invention of claim 12 wherein said at least one parameter comprises:

at least one base value; and

at least one multiplier value by which each succeeding data value in said first set of actual data values is approximated by said formula.

18. The invention of claim 12 further comprising:

a plurality of base values, wherein each base value of said plurality of base values is associated with a separate respective one of a plurality of groups of actual data values formed from said plurality of actual data values in the original source of data, and wherein each base value.

19. The invention of claim 18 further comprising:

a plurality of multipliers, wherein each multiplier of said plurality of multipliers is associated with a separate respective one of said plurality of groups, and wherein each multiplier is a value that approximates an amount for the group by which each succeeding actual value in the group changes relative to an immediately preceding actual value.

20. The invention of claim 12 wherein said at least one parameter comprises a multiplier that predicts an amount by which each actual value in said plurality of actual data values changes relative to an immediately preceding actual value.

21. The invention of claim 12 wherein said at least one parameter comprises:

at least one base value, wherein said at least one base value is selected so that each difference by which an actual data value differs from the value predicted therefor by said formula has the same sign; and

a multiplier that predicts an amount by which each actual data value in said plurality of actual data values changes relative to an immediately preceding actual data value.

22. A method of using a data construction in a database used by a program executed on a computer platform, the method comprising the steps of:

reading at least one parameter from a header of the data construction;

using said parameter with a predetermined formula to determine a prediction of each of a plurality of actual data values;

reading a plurality of differences contained in said data construction; and

for each difference of said plurality of differences contained in said data construction, adding the difference to the prediction obtained by using said formula to thereby obtain the actual data value represented thereby in said database.