Operations of multi-level nested data structure

• US 8,078,638 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/169,931
• Publication Number:
  US 20100010960A1
• Time in Patent Office: 1,252 Days
• Field of Search: 707/791, 707/802, 707/803, 707/809, 707/810, 707/811
• US Class Current: 707/791
• CPC Class Codes: G06F 16/2456 Join operations
• CPC Class Codes: G06F 16/258 Data format conversion from or to a database
• CPC Class Codes: G06F 16/9027 Trees

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:

accessing a first table corresponding to a first set of data, wherein the first set of data contains a first plurality of name-value pairs organized in a multi-level nested structure and represented using a first format with a first syntax, the first table has at least one row and each row has at least one field, and the first table corresponds to a name-value pair from the first set of data that is located at two levels outside an innermost level, each row of the first table corresponds to a name-value pair nested immediately within the name-value pair corresponding to the first table, and each field of a row corresponds to a name-value pair nested immediately within the name-value pair corresponding to the row;

accessing at least a second table corresponding to a second set of data, wherein the second set of data contains a second plurality of name-value pairs organized in a multi-level nested structure and represented using a second format with a second syntax, the second table has at least one row and each row has at least one field, and the second table corresponds to a name-value pair from the second set of data that is located at two levels outside an innermost level, each row of the second table corresponds to a name-value pair nested immediately within the name-value pair corresponding to the second table, and each field of a row corresponds to a name-value pair nested immediately within the name-value pair corresponding to the row;

joining at least the first table and the second table according to a join predicate to obtain a third table, such that a row from the first table and a row from the second table are combined to form a row in the third table if the row from the first table and the row from the second table both satisfy the join predicate; and

automatically resolving any namespace conflict when joining the first table and the second table, such that if a field from a first row from the first table and a field from a second row from the second table have the same name and the first row and the second row are to be combined, then the field from the first row is automatically qualified with a name of the first table and the field from the second row is automatically qualified with a name of the second table.

4. A method as recited in claim 1, wherein the join predicate is expressed as a conditional function.

2. A method as recited in 1, further comprising:

converting the first set of data into the first table; and

converting the second set of data into the second table, wherein the first set of data and the second set of data are converted into the first table and the second table respectively without relying on any schema for the first syntax and the second syntax.

3. A method as recited in 1, wherein the first table and the second table are joined without any namespace qualification.

5. A method as recited in 1, further comprising:

grouping selected rows from the third table according to a group predicate, such that all the rows from the third table that satisfy the group predicate are grouped into a single row.

6. A method as recited in 5, further comprising:

grouping selected rows from the third table further according to a field grouping scheme, such that duplicate fields from the selected rows are replaced with a single field having a value calculated according to the field grouping scheme.

7. A method as recited in 1, further comprising:

ranking the rows from the third table according to a rank predicate.

8. A method as recited in 1, further comprising:

presenting the third table based on a template.

9. A system, comprising:

at least one storage device; and

at least one processor coupled to the at least one storage device, the at least one processor configured for performing;

(i) a reformat operation that receives as input a data set having a plurality of data elements organized in a multi-level nested data structure and returns as output a first table, wherein the first table has at least one row and each row has at least one field, the first table corresponds to a data element that is located at two levels outside an innermost level, each row of the first table corresponds to a data element nested immediately within the data element corresponding to the first table, and each field of a row corresponds to a data element nested immediately within the data element corresponding to the row; and

(ii) a join operation that receives as input a second table, a third table, and a join predicate and returns as output a fourth table, such that a row from the second table and a row from the third table are combined to form a row in the fourth table if the row from the second table and the row from the third table both satisfy the join predicate,

wherein

when performing the join operation, the at least one processor automatically resolves any namespace conflict when joining the second table and the third table, such that if a field from a first row from the second table and a field from a second row from the third table have the same name and the first row and the second row are to be combined, then the field from the first row is automatically qualified with a name of the second table and the field from the second row is automatically qualified with a name of the third table.

10. The system of claim 9, wherein the input data set is represented using a format having a predefined syntax, and the reformat operation does not rely on a schema of the predefined syntax.

11. The system of claim 9, wherein the at least one processor is further configured for performing:

a group operation that receives as input a fifth table and a group predicate and returns as output a sixth table, such that selected rows from the fifth table that satisfy the group predicate are grouped into a single row in the sixth table.

12. The system of claim 9, wherein the at least one processor is further configured for performing:

a rank operation that receives as input a seventh table and a rank condition and returns as output a eight table, such that the rows in the seventh table are ranked according to the rank condition.

13. The system of claim 9, wherein the at least one processor is further configured for performing:

a text normalization operation that receives as input a first alpha-numerical string and returns as output a second alpha-numerical string, where all the alphabets in the first alphanumerical string are converted to either lower or upper case and all the trivial words and extra white spaces in the first alpha-numerical string are discarded.

14. The system of claim 9, wherein the at least one storage device is configured for storing:

at least one template that complies with a predefined syntax for presenting a table to a user.

15. 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:

access a first table corresponding to a first set of data, wherein the first set of data contains a first plurality of name-value pairs organized in a multi-level nested structure and represented using a first format with a first syntax, the first table has at least one row and each row has at least one field, and the first table corresponds to a name-value pair from the first set of data that is located at two levels outside an innermost level, each row of the first table corresponds to a name-value pair nested immediately within the name-value pair corresponding to the first table, and each field of a row corresponds to a name-value pair nested immediately within the name-value pair corresponding to the row;

access at least a second table corresponding to a second set of data, wherein the second set of data contains a second plurality of name-value pairs organized in a multi-level nested structure and represented using a second format with a second syntax, the second table has at least one row and each row has at least one field, and the second table corresponds to a name-value pair from the second set of data that is located at two levels outside the innermost level, each row of the second table corresponds to a name-value pair nested immediately within the name-value pair corresponding to the second table, and each field of a row corresponds to a name-value pair nested immediately within the name-value pair corresponding to the row;

join at least the first table and the second table according to a join predicate to obtain a third table, such that a row from the first table and a row from the second table are combined to form a row in the third table if the row from the first table and the row from the second table both satisfy the join predicate; and

automatically resolve any namespace conflict when joining the first table and the second table, such that if a field from a first row from the first table and a field from a second row from the second table have the same name and the first row and the second row are to be combined, then the field from the first row is automatically qualified with a name of the first table and the field from the second row is automatically qualified with a name of the second table.

16. The medium of claim 15, wherein the information, when read by the machine, causes the machine to further perform the following:

convert the first set of data into the first table; and

convert the second set of data into the second table, wherein the first set of data and the second set of data are converted into the first table and the second table respectively without relying on any schema for the first syntax and the second syntax.

17. The medium of claim 15, wherein the first table and the second table are joined without any namespace qualification.