Understanding tables for search

• US 9,734,181 B2
• Filed: 10/02/2014
• Issued: 08/15/2017
• Est. Priority Date: 06/30/2014
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Wang, Zhongyuan, Chakrabarti, Kaushik, Narasayya, Vivek R., Zoryn, Kanstantsyn, Finnigan, James P., Ganjam, Kris, Chen, Zhimin, Chaudhuri, Surajit
• Primary Examiner(s): MOSER, BRUCE M
• Application Number:
  US14/505,188
• Publication Number:
  US 20150379057A1
• Time in Patent Office: 1,048 Days
• Field of Search: None
• CPC Class Codes: G06F 16/211 Schema design and management
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 16/901 Indexing; Data structures therefor; Storage structures for retrieval from the web G06F16/951
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/955 using information identifiers, e.g. uniform resource locators [URL]

Abstract

The present invention extends to methods, systems, and computer program products for understanding tables for search. Aspects of the invention include identifying a subject column for a table, detecting a column header using other tables, and detecting a column header using a knowledge base. Implementations can be utilized in a structured data search system (SDSS) that indexes structured information, such as, tables in a relational database or html tables extracted from web pages. The SDSS allows users to search over the structured information (tables) using different mechanisms including keyword search and data finding data.

Claims

1. A method for detecting one or more subject columns of a table, the method comprising:

selecting a specified number of columns from the table as candidate subject columns, each candidate subject column being a candidate for a true subject column of the table, each candidate subject column including a plurality of values;

for each candidate subject column;

determining a co-occurrence for values in the candidate subject column, including determining how often values in the candidate subject column also occur in true subject columns in a plurality of other tables;

calculating a score for the candidate subject column based on the determined co-occurrence, the calculated score indicating a likelihood of the candidate subject column being a true subject column; and

classifying the candidate subject column as one of;

a true subject column of the table or a non-subject column of the table based on the calculated score for the candidate subject column.

2. The method of claim 1, wherein selecting a specified number of columns from the table as candidate subject columns comprises selecting a specified number of leftmost columns of the table as candidate subject columns.

3. The method of claim 2, wherein selecting a specified number of leftmost columns of the table as candidate subject columns comprises selecting a specified number of leftmost non-numeric columns of the table as candidate subject columns.

4. The method of claim 1, wherein selecting a specified number of columns from the table as candidate subject columns comprises selecting a specified number of columns from the table as candidate subject columns based on the distinctness of cell values in the specified number of columns.

5. The method of claim 1, wherein selecting a specified number of columns from the table as candidate subject columns comprises selecting a specified number of columns from one of:

a relational table or a web table.

6. The method of claim 1, wherein determining a co-occurrence for values in the candidate subject column comprises calculating a co-occurrence fraction for each value in the candidate subject column, the co-occurrence fraction indicative of how often the value occurs in true subject columns of the plurality of other tables relative to how often the value occurs overall in the plurality of other tables.

7. The method of claim 1, wherein calculating a score for the candidate subject column comprises calculating a score for the candidate subject column from a co-occurrence fraction for each value, the co-occurrence fraction indicative of how often the value occurs in true subject columns of the plurality of other tables relative to how often the value occurs overall in the plurality of other tables.

8. The method of claim 1, wherein calculating a score for the candidate subject column comprises calculating a score for the candidate subject column based on the occurrence of the values in a knowledge base.

9. At a computer system, a method for detecting a column header for a table including one or more rows, the method comprising:

constructing a set of candidate column names for the table from data defining the table;

for each candidate column name in the set of candidate column names;

calculating a candidate column name frequency for the candidate column name by identifying one or more other tables, from among a set of other tables, that also contain the candidate column name as a candidate column name; and

calculating a non-candidate column name frequency for the candidate column name by identifying a second one or more other tables, from among the set of other tables, that contain the candidate column name other than as a candidate column name; and

selecting a row of the table as a column header when at least a specified threshold of candidate column names contained in the row have a candidate column name frequency that is greater than a non-candidate column name frequency.

10. The method of claim 9, further comprising prior to constructing a set of candidate column names determining that the data defining the table does not expressly define a column header.

11. The method of claim 10, determining that the data defining the table does not expressly define a column header comprises determining that the data defining the table does not include a HyperText Markup Language (HTML) <

th>

tag and does not include a HyperText Markup Language (HTML)<

thread>

tag.

12. The method of claim 9, further comprising prior to constructing a set of candidate column names determining that the table lacks an expressly defined column header.

13. The method of claim 9, wherein constructing a set of candidate column names for the table comprises constructing a set of candidate column names for the table from column names included in the first row of the table.

14. The method of claim 9, wherein constructing a set of candidate column names for the table comprises constructing a set of candidate column names for a relational web table.

15. The method of claim 9, wherein selecting a row of the table as a column header comprises selecting the first row of the table as the column header.

16. The method of claim 9, further comprising inferring that at least one column of the selected row is a hypernym of the cell values contained in the at least one column.

17. At a computer system, a method for detecting a column header for a table including one or more rows, the method comprising:

constructing a set of candidate column names for the table;

for each candidate column name in the set of candidate column names;

calculating a candidate column name frequency for the candidate column name by identifying one or more other tables, from among a set of other tables, that also contain the candidate column name as a candidate column name;

inferring that a column included in the set of candidate column names is a hypernym of the cell values contained in the column based on the cell values contained in the column; and

selecting the row containing the column as a column header for the table based on the inference and the candidate column name frequencies for the candidate column names in the row.

18. The method of claim 17, wherein inferring that a column included in the set of candidate column names is a hypernym of the cell values contained in the column comprises inferring that a column included in the set of candidate column names is a hypernym of the cell values contained in the column through reference to a knowledge base.

19. The method of claim 18, wherein inferring that a column included in the set of candidate column names is a hypernym of the cell values contained in the column through reference to a knowledge base comprises extracting one or more concept attributes and one or more instance attributes from the knowledge base.

20. The method of claim 18, further comprising, prior to selecting the row containing the column as a column header for the table, determining for another column included in the set of candidate column names that the cell type of the column header and the cell type of other cells in the column differ.

21. A system, the system comprising:

one or more processors;

system memory coupled to the one or more hardware processors, the system memory storing instructions that are executable by the one or more hardware processors; and

the one or more hardware processors executing the instructions stored in the system memory to detect one or more subject columns of a table, including the following;

select a specified number of columns from the table as candidate subject columns, each candidate subject column being a candidate for a true subject column of the table, each candidate subject column including a plurality of values;

for each subject candidate column;

determine a co-occurrence for values in the candidate subject column, including determining how often values in the candidate subject column also occur in true subject columns in a plurality of other tables; and

calculate a score for the candidate subject column based on the determined co-occurrence, the calculated score indicating a likelihood of the candidate subject column being a true subject column; and

classify the candidate subject column as one of;

a true subject column of the table or a non-subject column of the table based on the calculated score for the candidate subject column.

22. The system of claim 21, wherein the one or more hardware processors executing the instructions stored in the system memory to select a specified number of columns from the table as candidate subject columns comprises the one or more hardware processors executing the instructions stored in the system memory to select a specified number of leftmost columns of the table as candidate subject columns.

23. The system of claim 21, wherein the one or more hardware processors executing the instructions stored in the system memory to select a specified number of columns from the table as candidate subject columns comprises the one or more hardware processors executing the instructions stored in the system memory to select a specified number of columns from the table as candidate subject columns based on the distinctness of cell values in the specified number of columns.

24. The system of claim 21, wherein the one or more hardware processors executing the instructions stored in the system memory to calculate a score for the candidate subject column comprises the one or more hardware processors executing the instructions stored in the system memory to calculate a score for the candidate subject column from a co-occurrence fraction for each value, the co-occurrence fraction indicative of how often the value occurs in true subject columns of the plurality of other tables relative to how often the value occurs overall in the plurality of other tables.

25. The system of claim 21, wherein the one or more hardware processors executing the instructions stored in the system memory to calculate a score for the candidate subject column comprises the one or more hardware processors executing the instructions stored in the system memory to calculate a score for the candidate subject column based on the occurrence of the values in a knowledge base.

26. A system, the system comprising:

one or more processors;

system memory coupled to the one or more hardware processors, the system memory storing instructions that are executable by the one or more hardware processors; and

the one or more hardware processors executing the instructions stored in the system memory to detect a column header for a table including one or more rows, including the following;

construct a set of candidate column names for the table from data defining the table;

for each candidate column name in the set of candidate column names;

calculate a candidate column name frequency for the candidate column name by identifying one or more other tables, from among a set of other tables, that also contain the candidate column name as a candidate column name; and

calculate a non-candidate column name frequency for the candidate column name by identifying a second one or more other tables, from among the set of other tables, that contain the candidate column name other than as a candidate column name; and

select a row of the table as a column header when at least a specified threshold of candidate column names contained in the row have a candidate column name frequency that is greater than a non-candidate column name frequency.

27. The system of claim 26, further comprising the one or more hardware processors executing the instructions stored in the system memory to, prior to constructing a set of candidate column names, determine that the table lacks an expressly defined column header.

28. The system of claim 26, wherein the one or more hardware processors executing the instructions stored in the system memory to construct a set of candidate column names for the table comprises the one or more hardware processors executing the instructions stored in the system memory to construct a set of candidate column names for the table from column names included in the first row of the table.

29. The system of claim 26, further comprising the one or more hardware processors executing the instructions stored in the system memory to infer that at least one column of the selected row is a hypernym of the cell values contained in the at least one column.

30. A system, the system comprising:

one or more processors;

system memory coupled to the one or more hardware processors, the system memory storing instructions that are executable by the one or more hardware processors; and

the one or more hardware processors executing the instructions stored in the system memory to detect a column header for a table including one or more rows, including the following;

construct a set of candidate column names for the table;

for each candidate column name in the set of candidate column names;

calculate a candidate column name frequency for the candidate column name by identifying one or more other tables, from among a set of other tables, that also contain the candidate column name as a candidate column name;

infer that a column included in the set of candidate column names is a hypernym of the cell values contained in the column based on the cell values contained in the column; and

select the row containing the column as a column header for the table based on the inference and the candidate column name frequencies for the candidate column names in the row.

31. The system of claim 30, wherein the one or more hardware processors executing the instructions stored in the system memory to infer that a column included in the set of candidate column names is a hypernym of the cell values contained in the column comprises the one or more hardware processors executing the instructions stored in the system memory to infer that a column included in the set of candidate column names is a hypernym of the cell values contained in the column through reference to a knowledge base.

32. The system of claim 30, wherein the one or more hardware processors executing the instructions stored in the system memory to infer that a column included in the set of candidate column names is a hypernym of the cell values contained in the column through reference to a knowledge base comprises the one or more hardware processors executing the instructions stored in the system memory to extract one or more concept attributes and one or more instance attributes from the knowledge base.

33. The system of claim 30, further comprising the one or more hardware processors executing the instructions stored in the system memory to, prior to selecting the row containing the column as a column header for the table, determine for another column included in the set of candidate column names that the cell type of the column header and the cell type of other cells in the column differ.