Managing storage of data for range-based searching

Patent metadata

Field	Value
Publication number	US-9811570-B2
Application number	US-201213543339-A
Country	US
Kind code	B2
Filing date	Jul 6, 2012
Priority date	Jul 8, 2011
Publication date	Nov 7, 2017
Grant date	Nov 7, 2017

Abstract

In general, a value of a numerical attribute of a record stored in a data structure is received. A numerical range is generated that includes the value of the numerical attribute. An entry is stored, in an index associated with the data structure, that specifies a location of the record within the data structure and that includes a first index key and a second index key. The first index key corresponds to a value of an attribute of the record different from the numerical attribute, and the second index key corresponds to the generated numerical range.

First claim

What is claimed is:

1. A method for managing storage of data including:
for each of multiple records stored in a data structure, assigning an identifier that represents a range of values based on an attribute of the record, the range being specific to the record, in which assigning an identifier for a particular record includes:
determining a value based on a difference between a value of the attribute of the particular record and a first reference value, and
determining the identifier that represents the range of values for the particular record based on a relationship between the value based on the difference and a second reference value; and

storing entries in an index associated with the data structure, each entry specifying a location of a corresponding record within the data structure, the storing including, for each entry:
storing a first index key in the entry, in which the first index key is indicative of the identifier that represents the range of values for the corresponding record, and
storing a second index key in the entry, the second index key based on a value stored in the corresponding record,
wherein the index is sorted by both (i) the first index key indicative of the identifier that represents the range of values and (ii) the second index key.

2. The method of claim 1 , wherein the attribute is represented by a time stamp, and the range of values corresponds to a range of time.

3. The method of claim 2 , wherein the first reference value corresponds to a time stamp from a predetermined point in time, and wherein determining a value based on the difference between the value of the attribute of the particular record and the first reference value includes:
determining a first value in time units that separates a time corresponding to the time stamp from the predetermined point in time.

4. The method of claim 3 , wherein the second reference value corresponds to a predetermined time duration, and wherein determining the identifier that represents the range of values includes:
dividing the first value by the predetermined time duration to provide a quotient that represents the range of values.

5. The method of claim 1 , wherein each entry specifies a location, within the data structure, of a second record that is associated with the first index key and the second index key.

6. The method of claim 5 , wherein the record is a first record, and wherein the attribute of the first record and the attribute of the second record are each represented by a different time stamp.

7. The method of claim 5 , including:
receiving a query that requests the retrieval of records that are associated with the second index key and that are associated with a time between a first time and a second time.

8. The method of claim 7 , including:
assigning first and second identifiers that represent respective ranges of values for the first time and the second time.

9. The method of claim 8 , wherein assigning the first and second identifiers that represent the respective ranges of values includes:
determining a second value in time units based on a separation between the first time and a second predetermined point in time; and
determining a third value in time units based on a separation between the second time and the second predetermined point in time.

10. The method of claim 9 , wherein assigning the first and second identifiers that represent the respective ranges of values includes:
dividing the second value by a predetermined time duration to provide a quotient that represents a numerical range for the first time; and
dividing the third value by the predetermined time duration to provide a quotient that represents a numerical range for the second time.

11. The method of claim 10 , including:
identifying one or more entries within the index that include the second index key, and that include a first index key that corresponds to the range of values for the first time or the range of values for the second time or that is between the respective ranges of values for the first time and the second time.

12. The method of claim 1 , wherein the entries are sorted in the index primarily by the first index key indicative of the identifier that represents the range of values.

13. The method of claim 1 , wherein the entries are sorted in the index primarily by the second index key.

14. The method of claim 1 , wherein the attribute has a value that satisfies the range of values.

15. The method of claim 14 , wherein the value of the attribute is within the range of values.

16. The method of claim 1 , wherein determining the identifier that represents the range of values comprises dividing the value based on the difference by the second reference value to provide a quotient that represents the range of values.

17. A non-transitory computer-readable storage medium storing a computer program for managing the storage of data, the computer program including instructions for causing a computing system to:
for each of multiple records stored in a data structure, assigning an identifier that represents a range of values based on an attribute of the record, the range being specific to the record, in which assigning an identifier for a particular record includes:
determining a value based on a difference between a value of the attribute of the particular record and a first reference value, and
determining the identifier that represents the range of values for the particular record based on a relationship between the value based on the difference and a second reference value; and

store entries in an index associated with the data structure, each entry specifying a location of a corresponding record within the data structure, the storing including, for each entry:
storing a first index key in the entry, in which the first index key is indicative of the identifier that represents the range of values for the corresponding record, and
storing a second index key in the entry, the second index key based on a value stored in the corresponding record,
wherein the index is sorted by both (i) the first index key indicative of the identifier that represents the range of values and (ii) the second index key.

18. The non-transitory computer-readable storage medium of claim 17 , wherein the attribute is represented by a time stamp, and the range of values corresponds to a range of time.

19. The non-transitory computer-readable storage medium of claim 18 , wherein the first reference value corresponds to a time stamp from a predetermined point in time, and wherein determining a value based on the difference between the value of the attribute of the particular record and the first reference value includes:
determining a first value in time units that separates a time corresponding to the time stamp from the predetermined point in time.

20. The non-transitory computer-readable storage medium of claim 19 , wherein the second reference value corresponds to a predetermined time duration, and wherein determining the identifier that represents the range of values includes:
dividing the first value by the predetermined time duration to provide a quotient that represents the range of values.

21. The non-transitory computer-readable storage medium of claim 17 , wherein each entry specifies a location, within the data structure, of a second record that is associated with the first index key and the second index key.

22. The non-transitory computer-readable storage medium of claim 21 , wherein the

Assignees

• Stanfill Craig W
• Ab Initio Technology Llc

Inventors

• Stanfill Craig W

Classifications

• G06F16/2477 Primary

  Temporal data queries · CPC title

• G06F16/213

  with details for schema evolution support · CPC title

• G06F16/2322

  using timestamps · CPC title

• G06F16/2474

  Sequence data queries, e.g. querying versioned data · CPC title

• G06F17/30548

  Physics · mapped topic