Searching a Data Structure

• US 20170091244A1
• Filed: 09/24/2015
• Published: 03/30/2017
• Est. Priority Date: 09/24/2015
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Romanovskiy, Alexey
• Application Number:
  US14/864,492
• Publication Number:
  US 20170091244A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

A data structure is formed of at least one sequence of nodes having a plurality of elementary links, each elementary link being a directional edge from a respective node in the sequence to the next adjacent node in the sequence. Based one or more predicates, a distance along each elementary link for each of the one or more predicates is computed, and stored in the data structure in association with that elementary link. The distance along that elementary link is computed for that predicate by applying that predicate to the node to which that elementary link is directed, and is zero-valued unless that node satisfies that predicate.

Claims

1. A computer comprising:

an access module configured to access a data structure, wherein the data structure is formed of at least one sequence of nodes having a plurality of elementary links, each elementary link being a directional edge from a respective node in the sequence to the next adjacent node in the sequence; and

a distance computation module configured to compute, based one or more predicates, a distance along each elementary link for each of the one or more predicates, and store it in the data structure in association with that elementary link, wherein the distance along that elementary link is computed for that predicate by applying that predicate to the node to which that elementary link is directed, and is zero-valued unless that node satisfies that predicate.

2. A computer according to claim 1, wherein the one or more predicates are a plural number of predicates, whereby the distance computation module is configured to compute for each elementary link a distance vector along that link having that number of components, each component being the distance along that elementary link computed for a different one of the predicates.

3. A computer according to claim 1 for performing an index lookup on a data structure, the computer further comprising:

an index search input configured to receive a target index for a target predicate of the one the or more predicates; and

an index search module configured to use the distance along at least one of the elementary links computed for the target predicate to locate a target node in the sequence that has an index for the target predicate that matches the target index, the index of each node in the sequence for the target predicate being a sum of the distance(s) for the target predicate along the elementary link(s) from a reference node in the sequence to that node.

4. A computer according to claim 2, comprising a cross-index lookup module configured to perform a cross-index lookup for the target node by:

determining, based on said locating of the target node by the index search module, the index of the target node for a different one of the predicates.

5. A computer according to claim 4, comprising a user interface controller configured to:

control a display to display at least the target node, and

in response to a mode switch signal, control the display to display at least a set of one or more of the nodes that satisfy the different predicate, the set being selected by the user interface controller based on the cross-index lookup.

6. A computer according to claim 1 for performing a value lookup on a data structure, comprising:

a value search input configured to receive a target node value;

a value search module configured to locate a target node in the sequence that matches the target node value by comparing node values of nodes in the sequence to the target node value; and

a reverse-index lookup module configured perform a reverse-index lookup for the target node by;

determining, based on said locating of the target node by the value search module, an index of the target node for one of the predicates using the distance along at least one of the elementary links computed for said predicate, the index of each node in the sequence for said predicate being a sum of the distance(s) for said predicate along the elementary link(s) from a reference node in the sequence to that node.

7. A computer according to claim 3, wherein the search module is configured to locate the target node by implementing the following operations:

locating an earlier node in the sequence that has an index for the target predicate that is less than the target index,

determining that the index of the earlier node is less than the target index, and

in response to said determination, performing an explore algorithm for the earlier node by;

(i) generating a sum of the earlier node'"'"'s index with the distance for the target predicate along the elementary link from the earlier node to the next adjacent node in the sequence, and (ii) if the sum is less than the target index, repeating the explore algorithm for the next adjacent node in the sequence, whereby the explore algorithm is performed repeatedly until the target node is located.

8. A computer according to claim 1, wherein the sequence has higher-level links in addition to the elementary links, each of the higher-level links being a directional edge from a respective node in the sequence to a respective later node in the sequence, there being one or more of the elementary links between its respective node and its respective later node, wherein each of the elementary links has a lowest link level and each of the higher-level links has a link level above the lowest link level, the computer comprising:

a distance aggregation module configured compute a distance along each of the higher-level links for each predicate, and store it in the data structure in association with that link, the distance along that higher-level link being computed for that predicate by summing the distance(s) for that predicate along one or more lower-level links between that higher-level link'"'"'s respective node and its respective later node, the one or more lower level-links having a link level immediately below the link level of that higher-level link.

9. A computer according to claim 3, wherein one of the higher-level links is from a yet-earlier node in the sequence to the earlier node from which the target node is located, the earlier node being located from the yet-earlier node by summing the index of the yet-earlier node with the distance along the higher-level link from the yet-earlier node to the earlier node, thereby computing the index of the earlier node.

10. A computer according to claim 1, comprising:

an aggregate node generation module configured to generate one or more aggregate nodes, each of the aggregate nodes representing a respective group of the nodes in the sequence, and to insert each aggregate node at a respective position in the sequence with an elementary link to that aggregate node from the node immediately before its respective position, wherein the distance computation module is configured to compute a distance for each of the one or more predicates along that elementary link, wherein for at least one of the one or more predicates the computed distance along that elementary link is zero-valued unless at least one node in that respective group satisfies that predicate.

11. A computer according to claim 10, wherein the respective group represented by one of the aggregate nodes contains at least another of the aggregate nodes, wherein for at least one of the one or more predicates, the other aggregate node satisfies that predicate if and only if at least one node in the other aggregate node'"'"'s respective group satisfies that predicate.

12. A computer according to claim 10, wherein the group aggregation module is configured to store in association with each aggregate node a respective cardinality component for each of the one or more predicates, which indicates the number of nodes in its respective group that satisfy that predicate.

13. A computer according to claim 12, comprising a user interface controller configured to use the cardinality component for at least one of the aggregate nodes to generate display data for displaying, on a display, at least some of the nodes in its respective group.

14. A computer according to claim 1, wherein the one or more predicates are a plural number of predicates, wherein one of the predicates is a universal predicate that is satisfied by every node in the sequence.

15. A computer according to claim 1, wherein each link is embodied by a pointer to the node to which that link is directed, the pointer being stored in the node from which that link is directed;

and/or wherein the distance along that link computed for each predicate is stored in association with that pointer in;

the node from which that link is directed, or the node to which that link is directed.

16. A computer according to claim 1, wherein the distance computation module is implemented by a computer program configured to be executed by a processor of the computer, wherein the one or more predicates are a plural number of predicates, wherein the distances along the elementary links for a first and a second of the predicates are computed in parallel by separate threads of the computer program.

17. A computer according to claim 1, wherein the distance computation module is configured to:

compute the distances along the elementary links for a first of the one or more predicates by applying the first predicate to each of the nodes, and

compute the distances along the elementary links for a second predicate using (i) the distances computed for the first predicate, (ii) a known relationship between the first predicate and the second predicate and (iii) the second predicate, whereby in calculating the distances along the elementary links for the second predicate, the second predicate is applied to only some of the nodes in the sequence by the distance computation module.

18. A computer according to claim 3, comprising a user interface configured to use the located target node output to a user of the computer a display element representing the target node.

19. A computer-implemented method of optimising an electronically stored data structure for an index lookup, wherein the data structure is formed of at least one sequence of nodes having a plurality of elementary links, each elementary link being a directional edge from a respective node in the sequence to the next adjacent node in the sequence, the method comprising:

computing, based one or more predicates, a distance along each elementary link for each of the one or more predicates by applying that predicate to the node to which that elementary link is directed, wherein the distance is zero-valued unless that node satisfies that predicate; and

storing in the data structure, in association with each elementary link, the one or more distances along that link computed for the one or more predicates.

20. A computer program product comprising executable code stored on a computer-readable storage medium, the code configured when executed on a computer to perform the following operations:

accessing a data structure, wherein the data structure is formed of at least one sequence of nodes having a plurality of elementary links, each elementary link being a directional edge from a respective node in the sequence to the next adjacent node in the sequence;

computing, based one or more predicates, a distance along each elementary link for each of the one or more predicates by applying that predicate to the node to which that elementary link is directed, wherein the distance is zero-valued unless that node satisfies that predicate; and

storing in the data structure, in association with each elementary link, the one or more distances along that link computed for the one or more predicates.