Query and index over documents

• US 9,208,254 B2
• Filed: 12/10/2012
• Issued: 12/08/2015
• Est. Priority Date: 12/10/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Zhang, Li, Budiu, Mihai, Yu, Yuan, Plotkin, Gordon D.
• Primary Examiner(s): Cao, Phuong Thao
• Application Number:
  US13/709,064
• Publication Number:
  US 20140164388A1
• Time in Patent Office: 1,093 Days
• Field of Search: 707/742, 707/797, 707/798, 707/E17.008
• US Class Current: 1/1
• CPC Class Codes: G06F 16/322 Trees
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: Y10S 707/956 Hierarchical

Abstract

A document index is generated from a set of documents and is used to identify documents that match one or more queries. A tree is generated for each document with a node corresponding to each object of the document. The nodes of the generated trees are merged or combined to generate the document index, which is itself a tree. In addition, an inverted index is generated for each node of the index that identifies the tree(s) that the node originated from. When a query is received, the query is first executed against the document index tree: during the execution, proper set operations are applied to the inverted indices associated with the nodes matched by the query. The resulted set identifies the documents that may match the query. The query is then executed on the identified documents.

Claims

1. A method comprising:

receiving a plurality of documents by a computing device, wherein each document comprises a plurality of objects;

for each document, generating a graph representing the document by the computing device, wherein each graph comprises a node corresponding to each object of the represented document;

generating a document index by merging the generated graphs by the computing device, wherein each node in the document index includes identifiers of one or more graphs that include the node, and wherein the document index comprises a graph;

generating a matrix from the document index by the computing device;

receiving a query by the computing device;

generating a matrix from the received query by the computing device;

generating one or more matrix operations from the received query by the computing device;

identifying one or more documents of the plurality of documents that are responsive to the query using the matrix generated from the document index, the matrix generated from the received query, and the one or more matrix operations by the computing device;

running the query on the identified one or more documents to generate a subset of the identified one or more documents by the computing device; and

providing the subset of the one or more identified documents in response to the query by the computing device.

2. The method of claim 1, wherein the identified one or more documents includes document fragments.

3. The method of claim 1, wherein the generated graphs comprise trees.

4. The method of claim 1, wherein the received query comprises a plurality of sub-queries, wherein generating the one or more matrix operations comprises generating a matrix operation from each sub-query of the plurality of sub-queries, and further comprising:

identifying one or more documents of the plurality of documents that are responsive to the received query by evaluating the generated matrix from each sub-query of the received query, the generated matrix from the document index, and the generated matrix operation from each sub-query.

5. The method of claim 1, wherein the identifiers of the one or more graphs comprises an inverted index.

6. A method comprising:

receiving a document index by a computing device, wherein the document index comprises a plurality of nodes, each node includes identifiers of one or more graphs of a plurality of graphs, each graph represents a document of a plurality of documents, and wherein the document index comprises a graph;

generating a matrix from the received document index by the computing device;

receiving a query by the computing device, wherein the query comprises a plurality of sub-queries;

for each sub-query;

generating a matrix from the sub-query by the computing device;

generating a matrix operation from the sub-query;

determining nodes in the document index that match the sub-query by evaluating the matrix generated from the sub-query, the matrix operation generated from the sub-query, and the matrix generated from the document index by the computing device; and

for each determined node that matches the sub-query, determining the one or more graphs identified by the identifiers of the determined node by the computing device;

determining a union of the determined one or more graphs for each sub-query by the computing device;

identifying documents that are represented by the graphs of the determined union of the determined one or more graphs by the computing device;

running the query on the identified documents to generate a subset of the identified documents; and

providing the subset of the identified documents in response to the query by the computing device.

7. The method of claim 6, wherein the plurality of documents are one or more of JavaScript Object Notation (JSON) documents, and XML documents.

8. The method of claim 6, wherein the identified documents include document fragments.

9. The method of claim 6, wherein the received document index is generated by merging the plurality of graphs.

10. The method of claim 6, wherein the identifiers of one or more graphs of the plurality of graphs comprise inverted indexes.

11. A system comprising:

a computing device;

an index engine configured to generate a document index from a plurality documents, wherein the document index includes a plurality of nodes, each node identifies one or more documents of the plurality of documents, and wherein the document index comprises a graph; and

a query engine configured to;

generate a matrix from the document index;

receive a query;

generate one or more matrix operations from the received query;

generate a matrix from the received query;

identify one or more documents of the plurality of documents that are responsive to the query by evaluating the matrix generated from the document index, the matrix generated from the received query, and the one or more matrix operations;

run the query on the identified one or more documents to generate a subset of the identified one or more documents; and

provide the subset of the identified one or more documents in response to the query.

12. The system of claim 11, wherein the index engine configured to generate a document index from a plurality documents comprises the index engine configured to:

for each document, generate a graph representing the document, wherein each graph comprises a node corresponding to an object of the document; and

generate the document index by merging the nodes of the generated graphs, wherein each node in the document index includes identifiers of one or more graphs that include the node.

13. The system of claim 12, wherein the graphs comprise trees.

14. The system of claim 11, wherein the plurality of documents are one or more of JavaScript Object Notation (JSON) documents, and XML documents.

15. The system of claim 11, wherein the identified one or more documents include document fragments.