Hyperspace Index

• US 20090307184A1
• Filed: 03/02/2007
• Published: 12/10/2009
• 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, Dillon K.
• Granted Patent: US 8,176,052 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 data structure for indexing identifiers, wherein the identifiers correspond to parameter patterns, and wherein the presence of an identifier in the data structure indicates that the corresponding parameter pattern may be present in a set of parameter patterns, and wherein absence of the indicator in the data structure can be used to indicate that the corresponding parameter pattern is not present in the set of parameter patterns, the data structure comprising:

a first field, wherein the first field comprises a first plurality of binary bits, each binary bit corresponding to a possible identifier corresponding to a parameter pattern from among a first set of parameter patterns, and wherein when the bit is set, the identifier is included in the first field; and

one or more additional fields hierarchically below the first data field, wherein each of the additional fields comprises at least one of identifiers for a subset of the first set of parameter patterns represented by identifiers in the first field, identifiers for a parameter pattern related to one or more of the parameter patterns in the first set of parameter patterns or a subset of parameter patterns or related parameter patterns represented by one of the other one or more additional fields hierarchically above the field including the identifiers, wherein the absence of an identifier corresponding to a parameter pattern for a particular field indicates that the parameter pattern is not represented by an indicator in fields hierarchically below the field irrespective of the presence of identifiers corresponding to the parameter pattern being present fields hierarchically above the field not including an identifier corresponding to the parameter pattern, and wherein 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 in the set of parameter patterns.

2. The data structure of claim 1, wherein identifiers are derived from a calculated hash of a corresponding parameter pattern.

3. The data structure of claim 1, wherein location information of an identifier for parameter pattern in the first field can be preserved in hierarchically lower fields by deriving identifiers for the parameter pattern in the lower fields using the same method that was used to derive the identifier for the parameter pattern in the first field.

4. The data structure of claim 1, wherein parameter patterns comprise search specifiers.

5. The data structure of claim 4, wherein the search specifiers comprise Boolean combinations of search terms.

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

7. The data structure of claim 1, wherein the parameter patterns further comprise ranking information combined with search specifiers,

8. The data structure of claim 7, wherein the ranking information includes personalized ranking through customized criteria.

9. The data structure of claim 1, wherein the parameter patterns include an ordering according to a priority.

10. The data structure 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 data structure of claim 1, wherein fields are organized into hierarchical threads according to a ranking such that referencing of the data structure for identifier entries can be accomplished by following higher ranked hierarchical threads first.

12. The data structure of claim 11, wherein fields are organized such that fields beyond are given threshold are not relevant.

13. The data structure of claim 1, wherein the one or more additional fields are sized with a selected granularity to set a level of search resolution.

14. The data structure of claim 1, wherein the subsets of parameter patterns or associated parameter patterns are sub-divided into fields according to characteristics of objects represented in the field.

15. The data structure of claim 1, wherein each possible identifier corresponding to a parameter pattern corresponds to a binary representation of the parameter pattern such that the first field comprises a full text index.

16. The data structure of claim 1, wherein a possible identifier corresponding to a parameter pattern corresponds to a unique identifier or substantially unique identifier of the parameter pattern.

17. The data structure of claim 1, wherein the possible identifier comprises a frequency pointer that include an indication of the frequency of indicators for the parameter pattern in lower portions of an index.

18. The data structure of claim 1, wherein the possible identifier comprises one or more child index pointers pointing to portions of an index that may contain identifiers for the parameter pattern.

19. The data structure of claim 1, wherein the possible identifier comprises a short circuit pointer which allows for lower level fields to be bypassed such that a search can be focused to a particular location or record of a data space.

20. The data structure of claim 1, wherein the first field and the one or more fields hierarchically below the first field are a combination of abbreviated indexes, indexes of small records accessed by an identifier number as a key and full text indexes.

21. The data structure of claim 1, the data structure comprising fields at a lowest hierarchical level, and wherein the fields at the lowest hierarchical level comprise at least one of records or documents ordered from high to low relevance in the fields.

22. The data structure of claim 21, wherein relevance is determined by at least one of general reliability or relevance, or static reliability or relevance.

23. The data structure of claim 1, the data structure comprising fields at a lowest hierarchical level, and wherein the fields at the lowest hierarchical level are distributed according to relevance in proportions across a set of multiple clusters of servers.

24. In a computing environment, a method for indexing identifiers into a data structure, wherein the identifiers correspond to parameter patterns, and wherein the presence of an identifier in the data structure indicates that the corresponding parameter pattern may be present in a set of parameter patterns, and wherein absence of the indicator in the data structure can be used to indicate that the corresponding parameter pattern is not present in the set of parameter patterns, the method comprising:

including a first field identifier for a first parameter in a first field, wherein the first field comprises a first plurality of binary bits, each binary bit corresponding to a possible identifier corresponding to a parameter pattern from among a first set of parameter patterns, and wherein when the bit is set, the identifier is included in the first field; and

including one or more lower field identifiers for the first parameter pattern or a parameter pattern related to the first parameter pattern in one or more additional fields hierarchically below the first data field, wherein each of the additional fields comprises at least one of identifiers for a subset of the first set of parameter patterns represented by identifiers in the first field, identifiers for a parameter pattern related to one or more of the parameter patterns in the first set of parameter patterns or a subset of parameter patterns or related parameter patterns represented by one of the other one or more additional fields hierarchically above the field including the identifiers.

25. The method of claim 24, further comprising generating a hash code for the parameter pattern, and wherein the first field identifier and the one or more lower field identifiers are derived from the generated hash code.

26. The method of claim 24, wherein the first parameter pattern 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 first field; and

including additional lower identifiers for the additional parameter patterns or related additional parameter patterns in the one or more additional fields hierarchically below the first data field.

27. The method of claim 26, further comprising allocating memory for the first field and the one or more additional fields hierarchically below the first data field 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 field individually based on the number of data objects, the number of parameter patterns for each data object, and a multiplier, for each field.

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

30. In a computing environment, a method of locating identifiers in an index, wherein the identifiers correspond to parameter patterns, and wherein the presence of an identifier in the data structure indicates that the corresponding parameter pattern may be present in a set of parameter patterns, and wherein absence of the indicator in the data structure can be used to indicate that the corresponding parameter pattern is not present in the set of parameter patterns, the method comprising:

referencing a first field for a first identifier corresponding to a first parameter pattern, wherein the first field comprises a first plurality of binary bits, each binary bit corresponding to a possible identifier corresponding to a parameter pattern from among a first set of parameter patterns, and wherein when the bit is set, the identifier is included in the first field; and

if the first identifier is in the first field, referencing one or more additional fields hierarchically below the first field for one or more identifiers corresponding to the parameter pattern or one or more related parameter patterns, wherein each of the additional fields comprises at least one of identifiers for a subset of the first set of parameter patterns represented by identifiers in the first field, identifiers for a parameter pattern related to one or more of the parameter patterns in the first set of parameter patterns or a subset of parameter patterns or related parameter patterns represented by one of the other one or more additional fields hierarchically above the field including the identifiers, wherein the absence of an identifier corresponding to a parameter pattern for a particular field indicates that the parameter pattern is not represented by an indicator in fields hierarchically below the field irrespective of the presence of identifiers corresponding to the parameter pattern being present fields hierarchically above the field not including an identifier corresponding to the parameter pattern, and wherein the absence of an identifier corresponding to a parameter pattern in at least one field of each of the hierarchical threads indicates that the parameter pattern is not present in the set of parameter patterns.

31. The method of claim 30, wherein referencing one or more additional fields hierarchically below the first data field for one or more identifiers corresponding to the parameter pattern or one or more related parameter patterns comprises referencing fields in a hierarchical thread, from higher levels in the thread to lower levels in the threads and stopping referencing fields in a thread when an identifier for a parameter pattern being referenced for does not appear in a field in the thread.

32. The method of claim 30, wherein referencing a first field for a first identifier corresponding to a first parameter pattern, comprises referencing parameter patterns for more relevant parameter patterns first.

33. The method of claim 32, wherein relevance is determined by at least one of linguistic analysis, date, or reliability of a document or record.

34. In a computing environment, a method of indexing parameter patterns for later search and retrieval, the method comprising:

operating on one or more parameter patterns to generate a identifier code for each parameter pattern;

sorting the identifier codes generated for the parameter patterns; and

correlating offsets with sorted identifier codes where each offset is correlated to one of a sorted identifier code, wherein the offset represents a portion of one or more identifier codes correlated to the offset, or to an indicator that indicates that a particular offset does not correspond to an identifier code for a parameter pattern.

35. The method of claim 34, wherein a given offset comprises a predetermined number of the most significant bits of an identifier code correlated to the given offset.

36. The method of claim 34, wherein sorting the identifier codes generated for the parameter patterns comprises sorting the identifier codes in an ascending order numerically.

37. The method of claim 34, wherein the indicator that indicates that a particular offset does not correspond to identifier code for a parameter pattern is a negative number.

38. The method of claim 34, wherein the indicator that indicates that a particular offset does not correspond to an identifier code for a parameter pattern includes an indicator for locating a next identifier code corresponding to a parameter pattern.

39. In a computing environment, a method of checking an index for entries, the method comprising:

operating on a parameter pattern to create a identifier code;

generating an offset from the identifier code;

comparing the offset to a set of correlated offsets wherein the set of correlated offsets are correlated with sorted identifier codes where each offset is correlated to one of;

a sorted identifier code, wherein the offset represents a portion of one or more pre-calculated identifier codes correlated to the offset, or to an indicator that indicates that a particular offset does not correspond to a pre-calculated identifier code for a parameter pattern;

if a correlated offset matches the offset, and the correlated offset is correlated to a portion of one or more pre-calculated identifier codes, then comparing the identifier code to at least one of the one or more pre-calculated identifier codes;

but

if a correlated offset matches the offset, and the correlated offset is correlated to an indicator that indicates that a particular offset does not correspond to a pre-calculated identifier code for a parameter pattern, then returning an indication that the parameter pattern is not included in a set of parameter patterns.

40. The method of claim 39, wherein comparing the identifier code to at least one of the one or more pre-calculated identifier codes comprises:

continuing comparing the identifier code to pre-calculated identifier codes until either the identifier code matches a pre-calculated identifier code, or until a compared pre-calculated identifier code is greater than the identifier code;

if the identifier code matches a pre-calculated identifier code, then returning an indication that the identifier code matches a pre-calculated identifier code;

but

if a compared pre-calculated identifier code is greater than the identifier code, then returning an indication that the parameter pattern is not included in a set of parameter patterns.

41. The method of claim 39, wherein generating an offset comprises selecting a predetermined number of the most significant bits of an identifier code correlated to the given offset.

42. In a computing environment, a data structure for indexing parameter patterns, the data structure comprising:

a first field, the first field comprising pre-calculated identifier codes for parameter patterns, wherein the pre-calculated identifier codes are sorted in the first field;

a second field, the second field comprising an enumeration of each of the pre-calculated identifier codes; and

a third field, the third field comprising one or more offsets, wherein each offset is correlated to one of the enumerations in the second field or to an indicator that indicates that a particular offset does not correspond to a identifier code for a parameter pattern.