Operations on multi-level nested data structure

• US 8,078,645 B2
• Filed: 07/09/2008
• Issued: 12/13/2011
• Est. Priority Date: 07/09/2008
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Singh, Vikash
• Primary Examiner(s): Coby, Frantz
• Application Number:
  US12/170,025
• Publication Number:
  US 20100011013A1
• Time in Patent Office: 1,252 Days
• Field of Search: 707/802, 707/803
• US Class Current: 707/802
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/258 Data format conversion from or to a database

Abstract

Multiple sets of data are obtained from different sources. Each data set is represented using a different format having a different syntax and organized in a multi-level nested data structure. Each data set is reformatted into a standardized table format using a depth-first recursive algorithm without relying on the syntax schema of the original format of the data set. Various operations are performed on the tables corresponding to the data sets, including but not limited to joining multiple tables, grouping selected rows of a table, ranking rows of a table, adding or deleting fields from selected rows of a table, etc. Optionally, inferred namespace and text normalization are utilized for selected table operations. One or more templates are provided for converting the data set of a table to a format that may be presented to a user.

Claims

1. A method implemented on a machine having at least one processor, storage, and communication platform, comprising:

traversing through a data stream containing a plurality of name-value pairs organized in a multi-level nested data structure; and

for each name-value pair encountered in the multi-level nested data structure,

if the name-value pair is located at two levels outside an innermost level, then constructing a new table as a current table corresponding to the name-value pair,

if the name-value pair is located at one level outside the innermost level, then constructing a new row within the current table as a current row corresponding to the name-value pair, and

if the name-value pair is located at the innermost level, then adding the name-value pair to the current row of the current table as a field.

2. A method as recited in claim 1, wherein the multi-level nested data structure is represented as a hierarchical tree structure, such that a leaf node of the tree structure corresponds to a name-value pair located at the innermost level, a parent node of a leaf node corresponds to a name-value pair located at one level outside the innermost level, and a grandparent node of a leaf node corresponds to a name-value pair located at two levels outside the innermost level.

3. A method as recited in claim 1, wherein the data stream complies with XML syntax specification.

4. A method as recited in claim 3, wherein a name-value pair corresponds to an XML element having a start tag, an end tag, and data enclosed by the start tag and the end tag, such that the name in the name-value pair corresponds to the tag name of the XML element and the value in the name-value pair corresponds to the data enclosed by the start tag and the end tag of the XML element.

5. A method as recited in claim 3, further comprising:

ignoring data contained in the data stream that is not an XML element.

6. A method as recited in claim 1, wherein the data stream complies with JSON syntax specification.

7. A method as recited in claim 6, wherein a name-value pair corresponds to a pair of data separated by a colon (“

;

”

), such that the name in the name-value pair corresponds to the data located on the left side of the colon and the value in the name-value pair corresponds to the data located on the right side of the colon.

8. A method as recited in claim 1, wherein traversing through the data stream employs a depth-first recursive algorithm.

9. A method as recited in claim 1, further comprising:

for each name-value pair encountered that is located at two levels outside the innermost level, determining a total size of data nested within the name-value pair; and

selecting the table corresponding to the name-value pair located at two levels outside the innermost level that has the largest total size of data nested within the name-value pair.

10. A method as recited in claim 1, further comprising:

discarding each name-value pair encountered that is located at more than two levels outside the innermost level.

11. A method implemented on a machine having at least one processor, storage, and communication platform, comprising:

traversing through a plurality of data elements organized in a multi-level nested data structure and represented using a predefined syntax, wherein each data element includes a name portion and a value portion; and

for each data element encountered in the multi-level nested data structure, if the data element is located at two levels outside an innermost level, then constructing a new table as a current table corresponding to the data element,

if the data element is located at one level outside the innermost level, then constructing a new row within the current table as a current row corresponding to the data element, and

if the data element is located at the innermost level, then adding the data element to the current row of the current table as a field, wherein the field has a name corresponding to the name portion of the data element and a value corresponding to the value portion of the data element.

12. A method as recited in claim 11, wherein traversing through the plurality of data elements does not rely on a schema of the syntax used to represent the data elements.

13. A method as recited in claim 11, further comprising:

for each data element encountered that is located at two levels outside the innermost level, determining a total size of data nested within the data element; and

selecting the table corresponding to the data element located at two levels outside the innermost level that has the largest total size of data nested within the name-value pair.

14. A method as recited in claim 11, further comprising:

discarding each data element encountered that is located at more than two levels outside the innermost level.

15. A method as recited in claim 11, wherein the value portion of each data element that is located not at the innermost level is another data element.

16. A tangible non-transitory machine-readable medium having information stored thereon, wherein the information, when read by a machine, causes the machine to perform the following:

traversing through a data stream containing a plurality of name-value pairs organized in a multi-level nested data structure; and

for each name-value pair encountered in the multi-level nested data structure,

if the name-value pair is located at two levels outside an innermost level, then constructing a new table as a current table corresponding to the name-value pair,

if the name-value pair is located at one level outside the innermost level, then constructing a new row within the current table as a current row corresponding to the name-value pair, and

if the name-value pair is located at the innermost level, then adding the name-value pair to the current row of the current table as a field.

17. The medium of claim 16, wherein the data stream is represented using a predefined syntax, and traversing through the data stream does not rely on a schema of the predefined syntax.

18. The medium of claim 16, wherein the information that, when read by the machine, causes the machine to perform traversing through the data stream includes a depth-first recursive algorithm that determines whether and where a name-value pair is placed in a table according to a location of the name-value pair within the data structure.