Efficient Storage and Retrieval of Posting Lists

• US 20090132521A1
• Filed: 08/29/2008
• Published: 05/21/2009
• Est. Priority Date: 08/31/2007
• Status: Active Grant

• Current Assignee: Zhigu Holdings Limited
• Original Assignee: Powerset (Microsoft Corporation)
• Inventors: O'Connor, Brendan, Thione, Giovanni Lorenzo, Pell, Barney, Walters, Chad, Biewald, Lukas
• Granted Patent: US 8,229,970 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/322 Trees
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

A role tree having nodes corresponding to semantic roles in a hierarchy is defined. A posting list is generated for each association of a term and a semantic role in the hierarchy. The posting lists are stored contiguously on a physical storage medium such that a subtree of the hierarchy of semantic roles can be loaded from the storage medium as a single contiguous block. The posting lists for a subtree of the hierarchy are retrieved by obtaining data identifying the beginning location on the physical storage medium of the posting lists for the term at the top of a desired subtree of the hierarchy and data identifying the length of the posting lists of the desired subtree of the hierarchy. A single contiguous block that includes the posting lists for the desired subtree of the hierarchy is then retrieved from the beginning location through the specified length.

Claims

1. A method for storing one or more posting lists on a physical storage medium, the method comprising storing a plurality of posting lists related to one another in a strict dominance hierarchy contiguously on the physical storage medium such that the posting lists in a subtree of the hierarchy can be loaded from the physical storage medium as a single contiguous block.

2. The method of claim 1, wherein the hierarchy comprises a hierarchy of semantic roles, one or more of the semantic roles being associated with a term.

3. The method of claim 2, further comprising generating a posting list for each association of a term and a semantic role, the posting list comprising data identifying one or more documents that include usage of the term in the associated semantic role, and wherein storing the plurality of posting lists comprises storing the posting lists contiguously on the physical storage medium such that the posting lists in a subtree of the hierarchy of semantic roles can be loaded from the physical storage medium as a single contiguous block.

4. The method of claim 3, further comprising storing data indicating a starting position for the posting list for each node in the role tree.

5. The method of claim 4, further comprising for each of the nodes of the role tree that are not leaf nodes, storing data indicating a total size of the posting lists under the node.

6. The method of claim 5, wherein the data indicating the total size of the posting lists under the node is stored in a lexicon.

7. The method of claim 6, wherein a natural language engine utilizes the posting lists in a semantic index.

8. A method for retrieving one or more posting lists stored on a physical storage medium such that the posting lists in a subtree of a hierarchy of semantic roles can be loaded from the physical storage medium as a single contiguous block, the method comprising:

retrieving data identifying a beginning location on the physical storage medium of the posting lists for a term at a top of a desired subtree of the hierarchy;

retrieving data identifying the length of posting lists of the desired subtree of the hierarchy; and

loading a single contiguous block from the beginning location through the length, the single contiguous block including the posting lists for the desired subtree of the hierarchy.

9. The method of claim 8, wherein the hierarchy comprises a role tree having nodes corresponding to the semantic roles.

10. The method of claim 9, wherein the data identifying the length of the desired subtree of the hierarchy is stored in a lexicon.

11. The method of claim 10, wherein the posting lists comprise data identifying one or more documents that include usage of a term in an associated semantic role.

12. The method of claim 11, wherein the posting lists have been stored on the physical storage medium by performing a pre-order depth-first traversal of the nodes of the role tree, and at each of the nodes, writing the posting list for a term associated with the semantic role corresponding the node to the physical storage medium.

13. The method of claim 12, wherein the nodes of the role tree are related to one another in a strict dominance relation.

14. The method of claim 8, wherein the data identifying the beginning location on the physical storage medium of the posting lists for the term at the top of the desired subtree of the hierarchy is stored in a lexicon.

15. A computer storage medium having computer executable instructions stored thereon which, when executed by a computer, cause the computer to:

associate one or more semantic roles defined by a hierarchy with a term;

generate a posting list for each association of a term and a semantic role, the posting list comprising data identifying one or more documents that include usage of the term in the associated semantic role; and

to

store the posting lists contiguously on a physical storage medium such that the posting lists in a subtree of the hierarchy can be loaded from the physical storage medium as a single contiguous block.

16. The computer storage medium of claim 15, comprising further computer executable instructions which, when executed by the computer, cause the computer to:

retrieve data identifying the beginning location on the physical storage medium of the posting lists for a term at a top of a desired subtree of the hierarchy;

retrieve data identifying the length of posting lists of the desired subtree of the hierarchy; and

load a single contiguous block from the beginning location through the length, the single contiguous block including the posting lists for the desired subtree of the hierarchy.

17. The computer storage medium of claim 16, wherein the hierarchy comprises a role tree having nodes corresponding to the semantic roles.

18. The computer storage medium of claim 17, wherein storing the posting lists contiguously on the physical storage medium comprises performing a pre-order depth-first traversal of the nodes of the role tree, and at each of the nodes, writing the posting list for a term associated with the semantic role corresponding the node to the physical storage medium.

19. The computer storage medium of claim 18, wherein the nodes of the role tree are related to one another in a strict dominance relation.

20. The computer storage medium of claim 19, having further computer executable instructions stored thereon which, when executed by the computer, will cause the computer to store data indicating a total size of the posting lists under the node for each of the nodes of the role tree.