Hyperspace index

Abstract

A data structure indexes identifiers corresponding to parameter patterns. The presence of an identifier in the data structure indicates that the corresponding parameter pattern may be present in a set of parameter patterns, while absence of the indicator can be used to indicate that the corresponding parameter pattern is not present. The data structure includes a first field which includes small parameter pattern records. Each parameter pattern record corresponds to an identifier corresponding to a parameter pattern. If the record corresponding to the identifier is set or present, the identifier is included in the first field. One or more additional fields are hierarchically below the first field. Each of the additional fields includes identifiers for a subset of information in the first field. The absence of an identifier corresponding to a parameter pattern at any level in all of the hierarchical threads indicates that the parameter pattern is not present.

1 . In a computing environment including at least one processor and at least one computer storage device, a method, performed by the at least one processor, of locating identifiers in a hyperspace index, wherein the identifiers correspond to parameter patterns, and wherein the presence of an identifier in the hyperspace index indicates that the corresponding parameter pattern may be present in a set of parameter patterns, and wherein absence of the indicator in the hyperspace index indicates that the corresponding parameter pattern is not present in the set of parameter patterns, the method comprising:
 referencing, within a hyperspace index stored in the at least one computer storage device, a top level index for a first small parameter pattern record corresponding to a first parameter pattern, wherein the top level index comprises a sorted list of small parameter pattern records, each small parameter pattern record representing at least one parameter pattern found in one or more data sources front ended by the hyperspace index;   determining that the top level index indicates that at least one parameter pattern represented by the first small parameter pattern record is present in the one or more data sources;   referencing one or more lower level indexes for a second small parameter pattern record corresponding to the first parameter pattern, wherein each lower level index comprises an index hierarchically below another index in the hierarchy, each lower level index comprising a sorted list of small parameter pattern records, each small parameter pattern record representing at least one parameter pattern found in one or more data sources front ended by the hyperspace index; and   determining that at least one of the one or more lower level indexes indicate that the first parameter pattern is not present in the one or more data sources.   
     
     
         2 . The method of  claim 1 , wherein the first small parameter pattern record is different than the second small parameter pattern record in each lower level index. 
     
     
         3 . The method of  claim 2 , wherein the first small parameter pattern record comprises a portion of a hash of the first parameter pattern, and wherein the second small parameter pattern record in each lower level index comprises a smaller portion of the hash of the first parameter pattern than the portion of the hash used in an index above the lower level index in the hierarchy. 
     
     
         4 . The method of  claim 1 , wherein referencing one or more lower level indexes comprises referencing a plurality of lower level indexes in a particular order, and stopping referencing lower level indexes when a referenced lower level index indicates that the first parameter pattern is not present in the one or more data sources. 
     
     
         5 . The method of  claim 1 , wherein referencing the top level or one or more lower level indexes, further comprises:
 accessing an offset data structure to determine an offset, within the sorted list of small parameter pattern records of the corresponding index, at which referencing of the index is to begin.   
     
     
         6 . The method of  claim 5 , wherein the offset correlation table comprises a plurality of search hash offsets that are each correlated with an index table entry. 
     
     
         7 . The method of  claim 5 , wherein an index table entry comprises a portion of a small parameter pattern record, and the plurality of index table entries comprise each unique portion of possible small parameter pattern records. 
     
     
         8 . The method of  claim 7 , wherein a portion comprises a first n bits of the small parameter pattern record. 
     
     
         9 . The method of  claim 6 , wherein a search hash offset comprises an offset within the index where small parameter pattern records corresponding to the correlated index table entry begin in the index, or an indicator that the index does not include any small parameter pattern records that correspond to the correlated index table entry. 
     
     
         10 . The method of  claim 9 , wherein the indicator is a negative number. 
     
     
         11 . The method of  claim 6 , further comprising:
 determining a search hash offset for the first small parameter pattern; and   referencing the index beginning at the search hash offset.   
     
     
         12 . The method of  claim 1 , wherein at least some of the small parameter pattern records in the top level index include one or more additional bits defining one or more characteristics of the small parameter pattern record within the hyperspace index. 
     
     
         13 . The method of  claim 12 , wherein one or more of the additional bits represent a frequency characteristic that defines the number of times the corresponding small parameter pattern record appears in indexes at lower levels of the hyperspace index. 
     
     
         14 . The method of  claim 12 , wherein one or more of the additional bits represent a child characteristic that defines whether the small parameter pattern record appears in indexes along one or both child paths in the hierarchy. 
     
     
         15 . The method of  claim 14 , wherein the one or more additional bits representing the child characteristic comprises a first bit representing a left path and a second bit representing a right path. 
     
     
         16 . The method of  claim 15 , further comprising:
 performing a logical AND on the first and second bits of at least two small parameter pattern records being referenced to determine a path where each of the at least two small parameter pattern records are present.   
     
     
         17 . The method of  claim 12 , wherein one or more of the additional bits comprise a short circuit characteristic that identities a particular lower level index where the first small parameter pattern record is found when the one or more data sources contain a single occurrence of the first parameter pattern such that any intervening lower level indexes between the referenced index and the particular lower level index can be bypassed. 
     
     
         18 . The method of  claim 17 , further comprising:
 removing the first small parameter pattern record from any intervening lower level indexes.   
     
     
         19 . One or more computer storage devices storing computer executable instructions which when executed perform a method of locating identifiers in a hyperspace index, wherein the identifiers correspond to parameter patterns, and wherein the presence of an identifier in the hyperspace index indicates that the corresponding parameter pattern may be present in a set of parameter patterns, and wherein absence of the indicator in the hyperspace index indicates that the corresponding parameter pattern is not present in the set of parameter patterns, the method comprising:
 referencing, within a hyperspace index stored in the at least one computer storage device, a top level index for a first small parameter pattern record corresponding to a first parameter pattern, wherein the top level index comprises a sorted list of small parameter pattern records, each small parameter pattern record representing at least one parameter pattern found in one or more data sources front ended by the hyperspace index;   determining that the top level index indicates that at least one parameter pattern represented by the first small parameter pattern record is present in the one or more data sources;   referencing one or more lower level indexes for a second small parameter pattern record corresponding to the first parameter pattern, wherein each lower level index comprises an index hierarchically below another index in the hierarchy, each lower level index comprising a sorted list of small parameter pattern records, each small parameter pattern record representing at least one parameter pattern found in one or more data sources front ended by the hyperspace index; and   determining that at least one of the one or more lower level indexes indicate that the first parameter pattern is not present in the one or more data sources.   
     
     
         20 . The one or more computer storage devices of  claim 19 , wherein referencing the top level or one or more lower level indexes, further comprises:
 accessing an offset data structure to determine an offset, within the sorted list of small parameter pattern records of the corresponding index, at which referencing of the index is to begin.