Abbreviated index
First Claim
1. In a computing environment, one or more computer readable storage media, the one or more computer readable storage media comprising:
- a pre-filter data structure for pre-indexing identifiers, wherein the identifiers represent searchable data elements or combinations of data elements in a data store and wherein an identifier being pre-indexed in the data structure indicates that the corresponding data element or combination of data elements may be present in the data store, and wherein absence of the identifier being indexed in the data structure can be used to indicate that the corresponding data element or combination of data elements is not present in the data store, such that when it is known that a data element or combination of data elements does not exist in the data store, expensive search and retrieval operations on the data store can be avoided, the data structure comprising;
a first field, wherein the first field comprises a first plurality of binary bits, each binary bit corresponding to an identifier,wherein a first particular bit in the first plurality of binary bits is set, and wherein the first particular bit corresponds to an identifier generated for a first data element that is stored in the data store, andwherein a second particular bit in the first plurality of binary bits is also set, wherein the second particular bit corresponds to an identifier generated for a first combination of data elements that is stored in the data store, the first combination of data elements including the first data element.
3 Assignments
0 Petitions
Accused Products
Abstract
Abbreviated index of parameter patterns. An abbreviated index includes indicators that a parameter pattern may be in a set of parameter patterns. To create the abbreviated index, indicators for overlapping parameter patterns of a given parameter pattern are placed in the index. Different patterns may have the same indicator, so the abbreviated index does not necessarily give an absolute indication of the presence of a parameter pattern in the set of parameter patterns, but rather may give an indication of the possible inclusion of a parameter pattern. The use of indicators for overlapping patterns can be used to increase confidence as to the existence of a given parameter pattern in the set of parameter patterns. The absence of an indicator for a parameter pattern or an overlapping parameter pattern will indicate with certainty that the parameter pattern is not present in the set of parameter patterns.
39 Citations
17 Claims
-
1. In a computing environment, one or more computer readable storage media, the one or more computer readable storage media comprising:
a pre-filter data structure for pre-indexing identifiers, wherein the identifiers represent searchable data elements or combinations of data elements in a data store and wherein an identifier being pre-indexed in the data structure indicates that the corresponding data element or combination of data elements may be present in the data store, and wherein absence of the identifier being indexed in the data structure can be used to indicate that the corresponding data element or combination of data elements is not present in the data store, such that when it is known that a data element or combination of data elements does not exist in the data store, expensive search and retrieval operations on the data store can be avoided, the data structure comprising; a first field, wherein the first field comprises a first plurality of binary bits, each binary bit corresponding to an identifier, wherein a first particular bit in the first plurality of binary bits is set, and wherein the first particular bit corresponds to an identifier generated for a first data element that is stored in the data store, and wherein a second particular bit in the first plurality of binary bits is also set, wherein the second particular bit corresponds to an identifier generated for a first combination of data elements that is stored in the data store, the first combination of data elements including the first data element. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
9. A computer implemented method of creating a gate-keeper data structure that can be used to evaluate the possible existence of a data element or combination of data elements in a collection of data elements that are stored in a data store and can be used to determine absolutely the absence of a data element or combination of data elements from the collection of data elements in the data store, so as to avoid expensive search and retrieval operations on the data store when it is known that the data element or combination of data elements is not included in the data store, the method comprising the following acts that are performed by a processor:
-
(a) accessing a collection of data elements that are stored in a data store; (b) generating identifiers for at least some of the data elements that are stored in the data store and for combinations of at least some of the data elements; (b) allocating a predetermined number of bits in a computer readable medium for a gate-keeper data structure, each of the bits in the gate-keeper data structure corresponding to an identifier; and (c) for each of the identifiers generated for the data elements and combinations of data elements, setting the corresponding bit in the gate-keeper data structure. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16)
-
-
17. A computer implemented method of determining if a full index should be searched for a data element or combination of data elements to determine if the data element or combination of data elements is stored in a set of data elements for which the full index exits, the method comprising the following acts that are performed by a processor:
-
receiving a search string, the search string comprising a plurality of data elements; for a first combination of data elements in the search string, generating an identifier, the first combination of data elements including one or more of the plurality of data elements in the search string; at a gatekeeper data structure front ending a full index, wherein the gate keeper data structure comprises a first field, wherein the first field comprises a first plurality of binary bits, each binary bit corresponding to an identifier, determining if a bit corresponding to the identifier generated for the first combination of data elements is set; for a second combination of data elements in the search string, generating an identifier, the second combination of data elements including at least one of the one or more data elements of the first combination; at the gate keeper data structure determining if a bit corresponding to the identifiers for the second combination of data elements is set; and as a result of determining that bits are set corresponding to the generated identifiers for the first and second combinations, performing at least one of searching the full index or returning a confidence rating to a user.
-
Specification