Answering web queries using structured data sources

• US 8,832,133 B2
• Filed: 08/24/2009
• Issued: 09/09/2014
• Est. Priority Date: 08/24/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Paparizos, Stelios, Ntoulas, Alexandros, Shafer, John C.
• Primary Examiner(s): AL HASHEMI, SANA A
• Application Number:
  US12/545,872
• Publication Number:
  US 20110047171A1
• Time in Patent Office: 1,842 Days
• Field of Search: 707/765, 707/791, 707/802, 707/828, 707/713, 707/736
• US Class Current: 707/765
• CPC Class Codes: G06F 16/2452 Query translation
• CPC Class Codes: G06F 16/252 between a Database Management System and a front-end application

Abstract

Described is answering online web queries from a structured data store, such as a products database. An online web search query is modified into an evaluation expression for accessing a structured data store (e.g., a database, XML file, a flat table) to find search results. A query is matched to a pattern, which is used to generate the expression, as well as determine to which structured data store the query is routed. Tokens (e.g., words) in the query are processed against a dictionary of token classes (sets of tokens) and patterns (sets of token classes) to annotate the query to map the query to the matching pattern. A translation process generates the expression based on translation hints that correspond to the matching pattern. Also described is offline mining of query logs to generate the dictionaries.

Claims

1. In a computing environment, a method comprising, processing an online web search query, including generating one or more patterns based upon dictionary information obtained from query logs in which the dictionary information comprises data indicating universal token classes, data driven token classes and modifier token classes, finding a matching pattern that matches the online web search query from among the one or more patterns, translating the online web search query based on the matching pattern into the evaluation expression, using the expression to access data in a structured data store, and returning search results including results obtained from the structured data store.

4. The method of claim 1 further comprising determining which structured data store of a plurality of structured data stores to use in accessing the data.

5. The method of claim 1 wherein modifying the query comprises annotating the query into one or more parts, and mapping at least one part to a subset of the set of structured data.

6. The method of claim 1 wherein the structured data store comprises a database table, wherein the subset of a set of structured data comprises a column of that table, and wherein using the expression to access the data comprises filtering data in the column.

7. The method of claim 1 wherein modifying the query comprises annotating the query into parts, including matching words of the query to tokens, annotating the query with token classes, finding candidate patterns, and mapping the tokens for each candidate pattern.

8. The method of claim 1 wherein using the expression to access data comprises matching a pattern to words in the online web search query.

9. The method of claim 1 further comprising, mining at least one of the query logs to obtain the dictionary information, or accessing structured data to obtain the dictionary information, or both mining at least one query log and accessing structured data to obtain the dictionary information.

17. The method of claim 8 further comprising using the pattern to determine which structured data store of a plurality of structured data stores to use in accessing the data.

18. The method of claim 9 further comprising generating the one or more patterns based on the structured data source.

19. The method of claim 18 further comprising compressing the patterns based on frequency or structural similarity, or both frequency and structural similarity, of words in query log.

20. The method of claim 18 further comprising using mapping rules for the pattern to obtain translation-related information for modifying the online web search query into the expression.

2. In a computing environment, a system comprising, a structured data store, dictionary information comprising a set of dictionaries, and a query processing mechanism configured to generate one or more patterns based upon dictionary information obtained from query logs, receive an input web query, segment the input web query into parts corresponding to token classes from the dictionary information to find candidate patterns, find a matching pattern that matches the input web query amongst the candidate patterns, use the matching pattern to translate the input web query into an expression, and to query the structured data store with the expression to return search results for the input web query including data accessed from the structured data store.

10. The system of claim 2, wherein the query processing mechanism is further configured to annotate the input web query based upon a token class.

11. The system of claim 2 wherein the query processing mechanism is further configured to find a matching pattern and use the matching pattern to determine which structured data store, of a plurality of available structured data stores, to query with the expression.

12. The system of claim 2 wherein the structured data store comprises a database of information related to commercial products.

13. The system of claim 2 wherein the set of dictionaries comprises data indicating universal token classes, data driven token classes and modifier token classes, wherein one or more select operations, filter operations, sort operations, or project operations operate on data driven tokens classes, the universal token classes or the modifiers, or any combination of the data driven tokens classes, the universal token classes or the modifiers.

14. The system of claim 2 wherein the expression includes one or more operations, including a select operation to select a column, an access operation to access a column from the structured data store, a filter operation to filter a column based upon an operand and a value condition so as to remove rows not satisfying the operand and value condition on entries of the column, or a sort operation to sort rows, or any combination of one or more select operations, access operations, filter operations, or sort operations.

3. At least one computer storage medium having computer-executable instructions stored thereon, which in response to execution by a computer, cause the computer to perform steps comprising:

generating one or more patterns based upon dictionary information obtained from query logs, annotating the online web query into tokens and token classes from the dictionary information, segmenting the online web query into parts to find candidate patterns, finding a matching pattern that matches the online web query from among the candidate patterns, modifying the online web query into an evaluation expression based on the matching pattern, using the matching pattern to determine which structured data store to route the evaluation expression, using the evaluation expression to access data in the structured data store, and returning search results including the data accessed from the structured data store.

15. The at least one computer storage medium of claim 3 having further computer-executable instructions, which in response to execution by the computer, cause the computer to perform further steps comprising:

translating the online web query, based on the matching pattern, into the evaluation expression, and accessing the data store with the evaluation expression to obtain the search results for the online web query.

16. The at least one computer storage medium of claim 3 having further computer-executable instructions, which in response to execution by the computer, cause the computer to perform further steps comprising:

routing the evaluation expression to the structured data store based upon the matching pattern.