Architecture for managing query friendly hierarchical values

• US 6,279,007 B1
• Filed: 11/30/1998
• Issued: 08/21/2001
• Est. Priority Date: 11/30/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Uppala, Radha Krishna
• Primary Examiner(s): Black, Thomas
• Assistant Examiner(s): LE, UYEN T
• Application Number:
  US09/201,239
• Time in Patent Office: 995 Days
• Field of Search: 707/100, 707/101, 707/1-6, 707/10, 707/103, 707/104
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

An architecture for managing query friendly hierarchical values contains a data structure having node value entries for node values that make up the hierarchical values, hierarchical value entries for the hierarchical values expressed in terms of node value identifiers found in the node value entries, and hierarchy parent entries for parent-child pairs of hierarchy values. A node value entry contains a node value, a node hash value generated from the node value by a first hashing algorithm, and the node value identifier. The node hash value defines the node value entry in which the corresponding node value is stored. The hierarchical value entry contains a hierarchical value represented by the node value identifiers that correspond to the node values that make up the hierarchical value. The hierarchical value entry also contains a hierarchical value hash value derived from the node value identifier representation of the hierarchical value using a second hashing algorithm and a hierarchical value identifier. The hierarchical value hash defines the hierarchical value entry in which the corresponding hierarchical value is stored. A hierarchy parent entry contains the hierarchical value identifier for the parent hierarchical value and the hierarchical value identifier for the child hierarchical value. The hierarchy parent entry also contains a depth value representing the distance in nodes between the parent hierarchical value and the node in the child hierarchical value that is furthest from the parent.

Claims

1. A computer-readable medium having stored thereon a data structure for managing hierarchical values having multiple nodes, the data structure comprising:

a plurality of node value entries, each node value entry comprising

a node value data field containing data representing a unique node value,

a node hash value data field functioning to identify the node value entry and derived from the node value data field using a first hashing algorithm, and

a node value identifier data field functioning to identify the node value in the node value data field; and

a plurality of hierarchy value entries, each hierarchy value entry comprising

a hierarchical value data field derived from each node value identifier that identifies the node value entry corresponding to each node value in a unique hierarchical value,

a hierarchical value hash value data field functioning to identify the hierarchy value entry and derived from the hierarchical value data field using a second hashing algorithm, and

a hierarchical value identifier data field functioning to identify the hierarchical value in the hierarchical value data field.

2. The computer-readable medium of claim 1, wherein the data structure further comprises:

a plurality of hierarchy parent entries, each hierarchy parent entry comprising

a parent hierarchical value identifier data field containing the hierarchical value identifier that identifies a parent hierarchical value,

a child hierarchical value identifier data field containing the hierarchical value identifier the identifies a child hierarchical value dependent upon the parent hierarchical value, and

a depth value data field containing data representing a distance in nodes between the parent hierarchical value and the node in the child hierarchical value furthest from the parent hierarchical value.

3. The computer-readable medium of claim 1, wherein the node value is in a first format and the node value identifier is in a second format.

4. The computer-readable medium of claim 3, wherein the first hashing algorithm is optimized for data in the first format and the second hashing algorithm is optimized for data in the second format.

5. The computer-readable medium of claim 1, wherein the node value and the node value identifier are in a single format.

6. The computer-readable medium of claim 5, wherein the first and second hashing algorithms are a single algorithm optimized for data in the single format.

7. The computer-readable medium of claim 1, wherein the hierarchical value data field is derived from the node value identifiers corresponding to the node value in the hierarchical value by concatenating the node identifiers.

8. A computer-readable medium having computer-executable instructions to cause a computer to perform acts comprising:

locating an entry in a node value data structure to store a unique node value by processing the node value through a first hashing algorithm;

storing the node value, a node hash value generated by the first hashing algorithm, and a unique node identifier in the entry located by the first hashing algorithm;

locating an entry in a hierarchy value data structure to store a unique hierarchical value by converting the hierarchical value from a first format to the node identifiers corresponding to the node values of the hierarchical value and processing the node identifiers through a second hashing algorithm; and

storing the node identifiers corresponding to the node value of the hierarchical value, a hierarchical value hash value generated by the second hashing algorithm, and a unique hierarchical value identifier in the entry located by the second hashing algorithm.

9. The computer-readable medium of claim 8, wherein the computer-executable instructions cause the computer to perform further acts comprising:

locating an entry in the hierarchy value data structure containing a unique hierarchical value by converting the hierarchical value from the first format to the node identifiers corresponding to the node values of the hierarchical value and processing the node identifiers through the second hashing algorithm; and

outputting the hierarchical value identifier of the entry located by the second hashing algorithm if the node identifiers in the entry match the node identifiers of the hierarchical value.

10. The computer-readable medium of claim 8, wherein the computer-executable instructions cause the computer to perform further acts comprising:

outputting the node identifiers in a entry in the hierarchical value data structure if the hierarchical value identifier in the entry matches a input hierarchical value identifier.

11. The computer-readable medium of claim 8, wherein the computer-executable instructions cause the computer to perform further acts comprising:

storing an entry in a hierarchy parent data structure for a parent-child hierarchy value pair containing the hierarchical value identifiers for the parent and the child hierarchy values, and a depth value representing a distance between the parent and the child.

12. The computer-readable medium of claim 11, wherein the computer-executable instructions cause the computer to perform further acts comprising:

outputting a child hierarchical value identifier if the depth value in the entry for the child hierarchical value satisfies a selection criteria.

13. The computer-readable medium of claim 8, wherein the acts are performed in the order recited.

14. A computerized system comprising:

a processing unit coupled to a memory and a computer-readable medium through a system bus;

computer-executable instructions stored upon the computer-readable medium that cause the processing unit to create, on the computer-readable medium, a node value data structure storing a node hash value generated using a first hashing algorithm and a hierarchy value data structure derived from the node value data structure using a second hashing algorithm; and

further computer-executable instructions that cause the processing unit to extract, from the node value data structure, at least one node identifier based on a first selection criteria, and to extract, from the hierarchy value data structure, a hierarchy value identifier using the at least one node identifier.

15. The computerized system of claim 14, wherein:

the computer-executable instructions further cause the processing unit to create, on the computer-readable medium, a hierarchy parent data structure derived from the hierarchy value data structure; and

the further computer-readable instructions further cause the processing unit to extract, from the hierarchy parent data structure, a child hierarchy value identifier using the hierarchy value identifier.

16. The computerized system of claim 15, wherein the further computer-readable instructions further cause the processing unit to extract, from the hierarchy parent data structure, a child hierarchy value identifier using a second selection criteria.

17. The computerized system of claim 16, wherein the further computer-readable instructions further cause the processing unit to return the child hierarchy value identifier when the child hierarchy value identifier extracted using the hierarchy value identifier is the same as a child hierarchy value identifier extracted using the second selection criteria.

18. The computerized system of claim 16, wherein the first selection criteria is a hierarchical value and the second selection criteria is a distance from a parent node identified by the hierarchical value to a child node.

19. The computerized system of claim 14, wherein the node value data structure is created from a plurality of node values using a hashing algorithm.

20. The computerized system of claim 14, wherein the hierarchy value data structure is derived from the node value data structure using a hashing algorithm.

21. The computerized system of claim 14, wherein the node value data structure is created from a plurality of node values using a first hashing algorithm and the hierarchy value data structure is derived from the node value data structure using a second hashing algorithm.