Indexing and searching JSON objects

• US 8,260,784 B2
• Filed: 02/13/2009
• Issued: 09/04/2012
• Est. Priority Date: 02/13/2009
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Beyer, Kevin Scott, Rao, Jun, Shekita, Eugene J
• Primary Examiner(s): Ehichioya, Fred I
• Assistant Examiner(s): Mobin, Hasanul
• Application Number:
  US12/371,005
• Publication Number:
  US 20100211572A1
• Time in Patent Office: 1,299 Days
• Field of Search: None
• US Class Current: 707/742
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Disclosed is a method of encoding JavaScript Object Notation (JSON) documents in an inverted index, wherein a tree representation of a JSON document is first generated, and, next, the JSON document is shredded into a list of <value, path, type, jdewey> tuples for each atom node, n, in the tree, where value is a label associated with n, path is a concatenation of node labels associated with ancestors of n, type is a description of a type of value, and jdewey of n is a partial Dewey code of its closest ancestor array node, if one exists, or empty, otherwise. Lastly, an inverted index is built using <path, type, value> as index term, and jdewey as payload. A method is also described to search the inverted index.

Claims

1. A method of encoding JavaScript Object Notation (JSON) documents in an inverted index, said method comprising:

generating a tree representation of a JSON document;

shredding said JSON document into a list of <

value, path, type, jdewey>

tuples for each atom node, n, in said tree, where value is a label associated with n, path is a concatenation of node labels associated with ancestors of n, starting from a root of said tree, type is a description of a type of value, and jdewey of n is a partial Dewey code of its closest ancestor array node when an ancestor array node exists and jdewey of n is empty when no closest ancestor array node exists; and

building an inverted index using <

path, type, value>

as index term, and jdewey as payload, said inverted index is organized as a list of ordered index terms, with each term in said list of ordered index terms pointing to a posting list, and each post is a <

d, plist>

pair, wherein d is the document ID and plist is an ordered list of positions within said JSON document and jdewey is stored in payload of each position.

2. The method of claim 1, wherein said list of tuples are losslessly encoded.

3. The method of claim 1, wherein said method of generating a tree representation further comprises the steps of:

creating an artificial root node labeled “

I”

; and

reviewing top level of said JSON document and adding any of or a combination of the following nodes;

a child atom node corresponding to atomic values, a child field node corresponding to object fields, and a child array node corresponding to array elements.

4. The method of claim 1, wherein said method comprises the step of searching said inverted index and outputting matching JSON documents from said searching step, said searching further comprising a first phase identifies potential matching JSON documents using the index without accessing said payload and a second phase computes the exact matching JSON documents using said payload.

5. The method of claim 1, wherein said method comprises the step of searching said inverted index, said searching step further comprising the steps of:

receiving a search query and constructing a parse tree from said received search query;

generating a first evaluation tree from said constructed parse tree to indentify a set of candidate JSON documents that match said search query;

generating a second evaluation tree from said constructed parse tree to identify a subset of said set of candidate JSON documents that exactly match said search query; and

evaluating said received search query based on said parse tree, first evaluation tree, and second evaluation tree, and outputting results of said evaluation.

6. The method of claim 5, wherein said first evaluation tree is generated based on removing array nodes in said constructed parse tree.

7. The method of claim 5, wherein said second evaluation tree is generated based on removing field and root nodes in said constructed parse tree.

8. The method of claim 5, wherein generation of said second evaluation tree is skipped for a predetermined type of query, and outputted results are based on evaluating said parse tree and said first evaluation tree.

9. An article of manufacture having non-transitory computer usable medium storing computer readable program code implementing a computer-based method of encoding JavaScript Object Notation (JSON) documents in an inverted index, said medium comprising:

computer readable program code generating a tree representation of a JSON document;

computer readable program code shredding said JSON document into a list of <

value, path, type, jdewey>

tuples for each atom node, n, in said tree, where value is a label associated with n, path is a concatenation of node labels associated with ancestors of n, starting from a root of said tree, type is a description of a type of value, and jdewey of n is a partial Dewey code comprising a Dewey code of its closest ancestor array node when an ancestor array node exists and jdewev of n is empty when no closest ancestor array node exists; and

computer readable program code building an inverted index using <

path, type, value>

as index term, and jdewey as payload, said inverted index is organized as a list of ordered index terms, with each term in said list of ordered index terms pointing to a posting list, and each post is a <

d, plist>

pair, wherein d is the document ID and plist is an ordered list of positions within said JSON document and jdewey is stored in payload of each position.

10. The article of manufacture of claim 9, wherein said list of tuples are losslessly encoded.

11. The article of manufacture of claim 9, wherein said medium further comprises:

computer readable program code creating an artificial root node labeled “

/”

; and

computer readable program code reviewing top level of said JSON document and adding any of or a combination of the following nodes;

a child atom node corresponding to atomic values, a child field node corresponding to object fields, and a child array node corresponding to array elements.

12. The article of manufacture of claim 9, wherein said medium further comprises computer readable program code searching said inverted index and outputting matching JSON documents from said searching step, said searching further comprising a first phase identifies potential matching JSON documents using the index without accessing said payload and a second phase computes the exact matching JSON documents using said payload.

13. The article of manufacture of claim 9, wherein said medium further:

computer readable program code receiving a search query and constructing a parse tree from said received search query;

computer readable program code generating a first evaluation tree from said constructed parse tree to indentify a set of candidate JSON documents that match said search query;

computer readable program code generating a second evaluation tree from said constructed parse tree to identify a subset of said set of candidate JSON documents that exactly match said search query; and

computer readable program code evaluating said received search query based on said parse tree, first evaluation tree, and second evaluation tree, and outputting results of said evaluation.

14. The article of manufacture of claim 13, wherein said first evaluation tree is generated based on removing array nodes in said constructed parse tree.

15. The article of manufacture of claim 13, wherein said second evaluation tree is generated based on removing field and root nodes in said constructed parse tree.

16. The article of manufacture of claim 13, wherein generation of said second evaluation tree is skipped for a predetermined type of query, and outputted results are based on evaluating said parse tree and said first evaluation tree.