Hyperspace index

• US 8,176,052 B2
• Filed: 03/02/2007
• Issued: 05/08/2012
• Est. Priority Date: 03/03/2006
• Status: Active Grant

• Current Assignee: Perfect Search Corporation
• Original Assignee: Perfect Search Corporation
• Inventors: Millett, Ronald P., Higgins, John C., Inouye, Dillion
• Primary Examiner(s): Vo, Tim T
• Assistant Examiner(s): Fan, Shiow-Jy
• Application Number:
  US12/281,262
• Publication Number:
  US 20090307184A1
• Time in Patent Office: 1,894 Days
• Field of Search: 707/999.002, 707/999.003, 707/999.005, 707/690, 707/741, 707/803, 707/713, 707/715, 707/999.006, 707/E17.002, 707/E17.017, 707/E17.053, 707/696
• US Class Current: 707/741
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

Hyperspace index data structure. 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 binary bits or groups of small parameter pattern keyed records. Each binary bit or parameter pattern keyed record corresponds to an identifier corresponding to a parameter pattern. If the bit or 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 data 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.

Claims

1. In a computing environment, a computer storage device storing a hyperspace index for indexing identifiers, 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 hyperspace index comprising:

a top level index representing a set of parameter patterns that may appear in one or more data sources front ended by the hyperspace index, each parameter pattern in the set of parameter patterns mapping to an identifier and wherein at least some of the parameter patterns map to the same identifier as another parameter pattern, wherein the top level index comprises a plurality of binary bits, wherein each binary bit corresponds to one of the identifiers, wherein a binary bit being set indicates that at least one of the parameter patterns that map to the identifier is present in the one or more data sources;

a plurality of lower level indexes, each lower level index comprising;

an index hierarchically below another index in the hierarchy, wherein each lower level index represents a subset of the parameter patterns represented by the other index above the lower level index in the hierarchy, each parameter pattern represented by the lower level index mapping to an identifier and wherein the lower level index comprises a plurality of binary bits, wherein each binary bit corresponds to one of the identifiers, wherein a binary bit being set indicates that one or more of the parameter patterns represented by the lower level index that map to the identifier is present in the one or more data sources.

2. The computer storage device of claim 1, wherein identifiers are derived from a calculated hash of a corresponding parameter pattern.

3. The computer storage device of claim 1, wherein the identifiers in each lower level index and the identifiers in the top level abbreviated index are derived using the same algorithm.

4. The computer storage device of claim 1, wherein parameter patterns comprise search specifiers.

5. The computer storage device of claim 4, wherein the search specifiers comprise Boolean combinations of search terms.

6. The computer storage device of claim 4, wherein the search specifiers comprise at least one of a question or an answer.

7. The computer storage device of claim 1, wherein the parameter patterns further comprise ranking information combined with search specifiers.

8. The computer storage device of claim 7, wherein the ranking information includes personalized ranking through customized criteria.

9. The computer storage device of claim 1, wherein the parameter patterns include an ordering according to a priority.

10. The computer storage device of claim 1, wherein the parameter patterns further comprise ranking information combined with search terms, wherein the ranking information includes at least one of user preference ranking, job appropriate ranking, profession appropriate ranking, linguistic appropriate ranking, stylistic appropriate ranking, and ranking based on previous searches.

11. The computer storage device of claim 1, wherein the indexes are organized into hierarchical threads according to a ranking such that referencing of the data hyperspace index for identifier entries can be accomplished by following higher ranked hierarchical threads first.

12. The computer storage device of claim 11, wherein the indexes are organized such that indexes beyond a given threshold are not relevant.

13. The computer storage device of claim 1, wherein the lower level indexes are sized with a selected granularity to set a level of search resolution.

14. The computer storage device of claim 1, wherein which parameter patterns are included in a subset of parameter patterns represented by each lower level index is based on characteristics of objects represented in the lower level index.

15. The computer storage device of claim 1, wherein the identifiers in each index comprise a number of bits from a hash of the corresponding parameter pattern.

16. The computer storage device of claim 15, wherein the identifiers in a lower level index comprise a lesser number of bits from the hash of the corresponding parameter pattern than the number of bits from the hash of the corresponding parameter used for the identifiers in an index hierarchically above the lower level index.

17. The computer storage device of claim 1, wherein at least some of the identifiers in a particular index include a frequency pointer that indicates the number of indicators for the parameter pattern in indexes hierarchically below the particular index.

18. The computer storage device of claim 1, wherein at least some of the identifiers in a particular index include one or more child index pointers that indicate which lower level indexes below the particular index include one or more identifiers for the corresponding parameter pattern.

19. The computer storage device of claim 1, wherein at least some of the identifiers in a particular index a short circuit pointer which allows for lower level indexes to be bypassed such that a search can be focused to a particular location or record of a data space.

20. The computer storage device of claim 1, wherein the top level index and the plurality of lower level indexes are a combination of abbreviated indexes, indexes of small records accessed by an identifier number as a key, and full text indexes.

21. The computer storage device of claim 1, wherein lower level indexes at the bottom of the hierarchy comprise at least one of records or documents ordered from high to low relevance in the fields.

22. The computer storage device of claim 21, wherein relevance is determined by at least one of general reliability or relevance, or static reliability or relevance.

23. The computer storage device of claim 1, wherein lower level indexes at the bottom of the hierarchy are distributed according to relevance in proportions across a set of multiple clusters of servers.

24. 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 for indexing identifiers into 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:

creating, in the at least one computer storage device, a top level index comprising a plurality of identifiers for representing a set of parameter patterns that may appear in one or more data sources front ended by the hyperspace index, wherein the top level index comprises a plurality of binary bits, each bit being associated with an identifier, creating the top level index including;

for each parameter pattern in the set of parameter patterns, mapping the parameter pattern to an identifier and wherein at least some of the parameter patterns map to the same identifier as another parameter pattern; and

for each identifier that a parameter pattern was mapped to, setting the corresponding binary bit in the top level index such that a binary bit being set indicates that at least one of the parameter patterns that map to the identifier may be present in the one or more data sources; and

creating, in the at least one computer storage device, a plurality of lower level indexes, each lower level index comprising an index hierarchically below another index in the hierarchy, each lower level index comprising a plurality of identifiers for representing a subset of the parameter patterns represented by the other index above the lower level index in the hierarchy, wherein each lower level index comprises a plurality of binary bits, each bit being associated with an identifier, creating each lower level index comprising;

for each parameter pattern in the subset of parameter patterns, mapping the parameter pattern to an identifier; and

for each identifier that a parameter pattern was mapped to, setting the corresponding binary bit in the lower level index such that a binary bit being set indicates that one or more of the parameter patterns represented by the lower level index that map to the identifier is present in the one or more data sources.

25. The method of claim 24, wherein mapping the parameter pattern to an identifier comprises creating a hash of the parameter pattern and using a portion of the hash as the identifier for the pattern parameter.

26. The method of claim 24, wherein one of the parameter patterns is a parameter pattern for a data object, the method further comprising:

including additional identifiers for additional parameter patterns for the data object in the top level index and one or more of the lower level indexes.

27. The method of claim 26, further comprising allocating memory for the top level index and the one or more of the lower level indexes based on the number of data objects, the number of parameter patterns for each data object, and one or more multipliers.

28. The method of claim 27, wherein allocating memory is done for each index individually based on the number of data objects, the number of parameter patterns for each data object, and a multiplier, for each index.

29. The method of claim 24, further comprising organizing a hierarchical arrangement of indexes by priority.