Self-compacting pattern indexer: storing, indexing and accessing information in a graph-like data structure

• US 8,065,293 B2
• Filed: 10/24/2007
• Issued: 11/22/2011
• Est. Priority Date: 10/24/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Meeder, Brendan, Cole, Jeffrey, Thompson, R. Donald III, Mukerjee, Kunal
• Primary Examiner(s): Coby; Frantz
• Application Number:
  US11/923,430
• Publication Number:
  US 20090112905A1
• Time in Patent Office: 1,490 Days
• Field of Search: 707/798, 707/711, 707/696, 707739-746, 707/802
• US Class Current: 707/711
• CPC Class Codes: G06F 16/322 Trees

Abstract

An indexing system uses a graph-like data structure that clusters features indexes together. The minimum atomic value in the data structure is represented as a leaf node which is either a single feature index or a sequence of two or more feature indexes when a minimum sequence length is imposed. Root nodes are formed as clustered collections of leaf nodes and/or other root nodes. Context nodes are formed from root nodes that are associated with content that is being indexed. Links between a root node and other nodes each include a sequence order value that is used to maintain the sequencing order for feature indexes relative to the root node. The collection of nodes forms a graph-like data structure, where each context node is indexed according to the sequenced pattern of feature indexes. Clusters can be split, merged, and promoted to increase the efficiency in searching the data structure.

Claims

1. A computing device that is arranged to manage a quantum indexed graph data structure, the computing device comprising:

a processing unit that is arranged to execute instructions to manage the quantum indexed graph data structure; and

a system memory that is arranged to store the instructions for execution by the processing unit, wherein the executable instructions are arranged for;

extracting a first ordered set of atomic values from a sequence that is associated with a new content;

creating a new context node for the quantum indexed graph data structure;

associating the new context node with all of the new content;

wherein the new context node stores all of the new content that is included in different nodes at a hierarchical level below the new context node;

wherein the new context node serves as an index for the new content;

identifying common nodes in the quantum indexed graph data structure, wherein each common node includes a second ordered set of atomic values that match at least a portion of the first ordered set of atomic values;

linking the new context node to all identified common nodes;

wherein the identified common nodes are at a hierarchical level below the new context node;

creating new leaf nodes for any portion of the first ordered set of atomic values that are not identified with common nodes;

linking the new context node to all new leaf nodes;

wherein the new leaf nodes are at a hierarchical level below the new context node;

assigning sequence order values to all links from the new context node based on the first ordered set of atomic values; and

adding the new context node to the quantum indexed graph data structure such that the content is indexed according to the first ordered set of atomic values.

2. The computing device of claim 1, wherein the executable instructions for extracting the first ordered set of atomic values further comprises:

identifying a set of feature indexes in the sequence, and assigning each atomic value in the first ordered set to a corresponding feature index from the set of feature indexes in the sequence.

3. The computing device of claim 1, wherein the executable instructions for extracting the first ordered set of atomic values further comprises:

identifying a set of feature indexes in the sequence, and grouping adjacent portions feature indexes from the set of feature indexes according to their order in the sequence based on a minimum sequence length associated with a smallest atomic value.

4. The computing device of claim 1, wherein the executable instructions for creating new leaf nodes further comprises:

selecting a group of sequentially ordered feature indexes according to a minimum sequence length associated with a smallest atomic value, and forming a leaf node with the group of sequentially ordered feature indexes.

5. The computing device of claim 1, wherein the executable instructions for identifying common nodes in the quantum indexed graph data structure further comprises:

selecting a candidate node in the quantum indexed graph data structure, identifying the second ordered set of atomic values for the selected candidate node, determining if the second ordered set of atomic values occur within the first ordered set of atomic values, and identifying the selected candidate node as a common node when the second ordered set of atomic values occur within the first ordered set of atomic values.

6. The computing device of claim 1, the executable instructions further comprising:

locating a cluster of common nodes for the identified common nodes that share a common root node, and splitting the cluster of common nodes from the common root node.

7. The computing device of claim 6, the executable instructions for splitting the cluster of common nodes further comprising:

creating a new root node for the cluster of common nodes, linking the new root node to each corresponding node from the cluster of common nodes, updating sequence order values for each link to each corresponding node from the cluster of common nodes, and linking the common root node to the new root node, and updating the sequence order values for the common root node.

8. The computing device of claim 1, the executable instructions further comprising:

tracking a corresponding frequency of each corresponding context node, and promoting each context node that has a corresponding frequency of use that exceeds a threshold.

9. The computing device of claim 1, the executable instructions further comprising:

querying the quantum indexed graph data structure with a search term, traversing the graph data structure to locate candidate context nodes, comparing each candidate context node to the search term, and identifying a possible sequence match when at least one of the atomic values associated with the candidate context node matches at least one atomic value associated with the search term.

10. The computing device of claim 9, the executable instructions further comprising retrieving the content associated with the candidate context node that is identified as a sequence match.

11. The computing device of claim 9, the executable instructions further comprising maintaining a corresponding counter for each context node, incrementing the corresponding counter for the candidate context node when a sequence match is identified, and promoting the candidate context node when the corresponding counter exceeds a threshold.

12. The computing device of claim 9, the executable instructions further comprising applying a heuristic scoring process to the possible sequence match, wherein each possible sequence match has a heuristic score indicative of a likelihood of a match between the candidate context node and the query term, and sorting the possible sequence matches based on the heuristic score.

13. The computing device of claim 12, the executable instructions for applying the heuristic scoring process further comprising calculating the heuristic score (heuristic_score) for each possible sequence match from the length of the match (MatchLength) and the number of overlaps from other matches (Overlaps), wherein heuristic_score=2^{MaxLength −}

2^Overlaps.

14. The computing device of claim 12, the executable instructions further comprising applying a noise filter process to modify the heuristic score for each possible sequence match.

15. The computing device of claim 14, the executable instructions for applying the noise filter process further comprising:

subtracting a noise floor value from the heuristic score, wherein the noise floor value for the possible sequence match corresponds to;

[4(m−

1)(n−

1)]/[S²(1−

4/S)], where m is the length of the query term, n is the number of indexed feature sets, and S is the size of the set of atomic values.

16. The computing device of claim 1, the executable instructions further comprising querying the quantum indexed graph data structure with a search term, hashed-tree traversing the graph data structure to locate candidate context nodes, comparing each candidate context node to at least a portion of the search term, and identifying possible sequence matches when at least one of the atomic values associated with the candidate context node matches at least one atomic value associated with the search term.

17. The computing device of claim 16, the executable instructions for hashed-tree traversing the graph data structure further comprising:

selecting at least one atomic value associated with the search term, shifting the selected at least one atomic value by a hashing shift amount, and exclusive ORing the shifted atomic value with an old hash code to generate a new code, and determining whether the new code is already occupied.

18. The computing device of claim 17, the executable instructions further comprising calculating a re-probe code by offsetting the new code when collisions are detected with the new code.

19. A computer implemented method for managing a quantum indexed graph data structure, the method comprising:

extracting a first ordered set of atomic values from a sequence of feature indexes that is associated with a new content;

creating a new context node for the quantum indexed graph data structure;

associating the new context node with the new content;

wherein the new context node stores all of the new content that is included in different nodes at a hierarchical level below the new context node;

wherein the new context node serves as an index for the new content;

identifying common nodes in the quantum indexed graph data structure, wherein each common node includes a second ordered set of atomic values that match at least a portion of the first ordered set of atomic values;

linking the new context node to all identified common nodes;

wherein the identified common nodes are at a hierarchical level below the new context node;

creating new leaf nodes for any portion of the first ordered set of atomic values that are not identified with common nodes;

linking the new context node to all new leaf nodes;

wherein the new leaf nodes are at a hierarchical level below the new context node;

assigning sequence order values to all links from the new context node based on the first ordered set of atomic values; and

adding the new context node to the quantum indexed graph data structure such that the content is indexed according to the first ordered set of atomic values.

20. The computer implemented method of claim 19, wherein each feature index is either a numerical index or a symbolic name that is mapped to a characteristic feature of the content.

21. The computer implemented method of claim 20, wherein each feature index is a numerical index that is mapped to one member of a group of acoustic phonemes that represent human speech.

22. The computer implemented method of claim 20, wherein the content corresponds to at least one member of the group comprising:

a digitally encoded audio signal, a digitally encoded video signal, a digitally encoded photographic image, and a file.

23. The computing implemented method of claim 20, wherein extracting a first ordered set of atomic values further comprises grouping adjacent portions of feature indexes from the sequence of feature indexes according to their order in the sequence based on a minimum sequence length associated with a smallest atomic value.

24. The computing implemented method of claim 21, further comprising locating a cluster of common nodes for the identified common nodes that share a common root node, and splitting the cluster of common nodes from the common root node.

25. A tangible computer-readable medium having computer-executable instructions for managing a quantum-indexed graph data structure, comprising:

extracting a first ordered set of atomic values from a sequence of feature indexes that is associated with a new content, where each atomic value corresponds to one or more feature indexes that occur in sequence based on a minimum sequence length;

creating a new context node for the quantum indexed graph data structure;

associating the new context node with the new content;

wherein the new context node includes all of the new content that is included in different nodes at a hierarchical level below the new context node;

wherein the new context node serves as an index for the new content;

identifying common nodes in the quantum indexed graph data structure, wherein each common node includes a second ordered set of atomic values that match at least a portion of the first ordered set of atomic values;

linking the new context node to all identified common nodes;

wherein the identified common nodes are at a hierarchical level below the new context node;

creating new leaf nodes for any portion of the first ordered set of atomic values that are not identified with common nodes;

linking the new context node to all new leaf nodes;

wherein the new leaf nodes are at a hierarchical level below the new context node;

assigning sequence order values to all links from the new context node based on the first ordered set of atomic values; and

adding the new context node to the quantum indexed graph data structure such that the content is indexed according to the first ordered set of atomic values.