UNDERSTANDING TABLES FOR SEARCH

• US 20150379057A1
• Filed: 10/02/2014
• Published: 12/31/2015
• Est. Priority Date: 06/30/2014
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wang, Zhongyuan, Chen, Zhimin, Chakrabarti, Kaushik, Finnigan, James P., Narasayya, Vivek R., Chaudhuri, Surajit, Ganjam, Kris, Zoryn, Kanstantsyn
• Granted Patent: US 9,734,181 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 subject column candidates, each subject column candidate being a candidate for a subject column of the table, each subject column candidate including a plurality of values;

for each subject column candidate;

identifying occurrences of any value from among the plurality of values being paired with one or more column names across a plurality of other tables; and

calculating a score for the subject candidate column based on the identified occurrences, the calculated score indicating a likelihood of the candidate column being a subject column; and

selecting at least one of the subject column candidates as a subject column of the table in accordance with the calculated scores.

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

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

4. The method of claim 1, wherein selecting a specified number of columns from the table as subject column candidates comprises selecting a specified number of columns from the table as subject column candidates 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 subject column candidates a specified number of columns from a relational table.

6. The method of claim 1, wherein selecting a specified number of columns from the table as subject column candidates a specified number of columns from a web table.

7. The method of claim 1, wherein identifying occurrences of any value from among the plurality of values being paired with one or more column names across a plurality of other tables comprises identifying occurrences of any value from among the plurality of values being paired with one or more column names across a plurality of web tables.

8. The method of claim 1, wherein selecting at least one of the subject column candidates as a subject column of the table comprises selecting a plurality of the subject column candidates as a subject column of the table.

9. At a computer system the 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 Lanauge (HTML)<

th>

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

thead>

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 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 claim 9, further comprising increasing confidence in selecting the row of the table as the column header by 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 the computer system, a method for detecting a column header for table including one or more rows, the method comprising:

constructing a set of candidate column names for the table;

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.

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; and

one or more computer storage media having stored thereon computer executable instructions representing a subject column detector, the subject column detector for detecting one or more subject columns of a table, the subject column detector configured to;

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

for each subject column candidate;

identify occurrences of any value from among the plurality of values being paired with one or more column names across a plurality of other tables; and

calculate a score for the subject candidate column based on the identified occurrences, the calculated score indicating a likelihood of the candidate column being a subject column; and

select at least one of the subject column candidates as a subject column of the table in accordance with the calculated scores.

22. The system of claim 21, wherein the subject column detector being configured to select a specified number of columns from the table as subject column candidates comprises the subject column detector being configured to select a specified number of leftmost columns of the table as subject column candidates.

23. The system of claim 21, wherein the subject column detector being configured to select a specified number of columns from the table as subject column candidates comprises the subject column detector being configured to select a specified number of columns from the table as subject column candidates based on the distinctness of cell values in the specified number of columns.

24. The system of claim 21, wherein the subject column detector being configured to identify occurrences of any value from among the plurality of values being paired with one or more column names across a plurality of other tables comprises the subject column detector being configured to identify occurrences of any value from among the plurality of values being paired with one or more column names across a plurality of web tables.

25. The system of claim 21, wherein the subject column detector being configured to select at least one of the subject column candidates as a subject column of the table comprises the subject column detector being configured to select a plurality of the subject column candidates as a subject column of the table.

26. A system, the system comprising:

one or more processors;

system memory; and

one or more computer storage media having stored thereon computer executable instructions representing a column header detector, the subject column detector for detecting one or more subject columns of a table, the subject column detector configured to;

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 subject column detector configured 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 subject column detector being configured to construct a set of candidate column names for the table comprises the subject column detector being configured 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 subject column detector configured to increase confidence in selecting the row of the table as the column header by inferring 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; and

one or more computer storage media having stored thereon computer executable instructions representing a column header detector, the subject column detector for detecting one or more subject columns of a table, the subject column detector configured to;

construct a set of candidate column names for the table;

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.

31. The system of claim 30, wherein the subject column detector being configured to infer that a column included in the set of candidate column names is a hypernym of the cell values contained in the column comprise the subject column detector configured to 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 subject column detector being configured 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 comprise wherein the subject column detector being configured 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 subject column detector being configured 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.