Managing Storage of Data for Range-Based Searching

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.

1 . A method including:
 receiving a value of a numerical attribute of a record stored in a data structure;   generating a numerical range that includes the value of the numerical attribute; and   storing, in an index associated with the data structure, an entry 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 corresponding to a value of an attribute of the record different from the numerical attribute, and the second index key corresponding to the generated numerical range.   
     
     
         2 . The method of  claim 1 , wherein the value of the numerical attribute is represented by a time stamp, and the numerical range defines a range of time. 
     
     
         3 . The method of  claim 2 , wherein generating the numerical range includes determining a first value in time units that separates a time corresponding to the time stamp from a predetermined point in time. 
     
     
         4 . The method of  claim 3 , wherein the numerical range is a time range of a predetermined time duration, and generating the numerical range includes dividing the first value by the predetermined time duration to provide a quotient that represents the numerical range. 
     
     
         5 . The method of  claim 1 , wherein the entry further 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 first record and the second record include values of the numerical attribute represented by different time stamps. 
     
     
         7 . The method of  claim 5 , further including receiving a query that requests the retrieval of records that are associated with the first index key and that are associated with a time between a first time and a second time. 
     
     
         8 . The method of  claim 7 , further including generating respective numerical ranges for the first time and the second time. 
     
     
         9 . The method of  claim 8 , wherein generating the respective numerical ranges includes:
 determining a second value in time units that separates the first time from a second predetermined point in time; and   determining a third value in time units that separates the second time from the second predetermined point in time.   
     
     
         10 . The method of  claim 9 , wherein generating the respective numerical ranges includes:
 dividing the second value by the 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 , further including identifying entries within the index that include the first index key, and that include a second index key that corresponds to a numerical range that is equal to the numerical range for the first time or the numerical range for the second time or that is between the respective numerical ranges for the first time and the second time. 
     
     
         12 . A computer-readable storage medium storing a computer program that includes instructions for causing a computing system to:
 receive a value of a numerical attribute of a record stored in a data structure;   generate a numerical range that includes the value of the numerical attribute; and   store, in an index associated with the data structure, an entry 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 corresponding to a value of an attribute of the record different from the numerical attribute, and the second index key corresponding to the generated numerical range.   
     
     
         13 . A computing system including:
 an input device or port configured to receive a value of a numerical attribute of a record stored in a data structure; and   at least one processor configured to:
 generate a numerical range that includes the value of the numerical attribute; and 
 store, in an index associated with the data structure, an entry 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 corresponding to a value of an attribute of the record different from the numerical attribute, and the second index key corresponding to the generated numerical range. 
   
     
     
         14 . A computing system including:
 means for receiving a value of a numerical attribute of a record stored in a data structure; and   means for indexing the record, the indexing including:
 generating a numerical range that includes the value of the numerical attribute; and 
 storing, in an index associated with the data structure, an entry 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 corresponding to a value of an attribute of the record different from the numerical attribute, and the second index key corresponding to the generated numerical range.