ANSWERING WEB QUERIES USING STRUCTURED DATA SOURCES

• US 20110047171A1
• Filed: 08/24/2009
• Published: 02/24/2011
• 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.
• Granted Patent: US 8,832,133 B2
• Time in Patent Office: Days
• US Class Current: 707/760
• 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 modifying the query into an expression based on dictionary information, using the expression to access data in a structured data store, and returning search results including results obtained from the structured data store.

2. 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.

3. 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.

4. The method of claim 3 wherein the structured data store comprises a database table, wherein the subset of the 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.

5. 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.

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

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

8. The method of claim 1 further comprising, mining at least one query log 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.

9. The method of claim 8 further comprising generating patterns based on the query log and the structured data source.

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

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

12. In a computing environment, a system comprising, a structured data store, a set of dictionaries including token class data, and a query processing mechanism that receives an input web query and annotates the query into an annotated query based upon token classes, the query processing mechanism configured to use information to translate the annotated query into an evaluation expression, and to query the structured data store with the evaluation expression to obtain search results for the web query.

13. The system of claim 12 wherein the query processing mechanism finds a matching pattern and uses the matching pattern to determine which structured data store, of a plurality of available structured data stores, to query with the expression.

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

15. The system of claim 12 wherein the token classes include universal token classes, data driven token classes and modifier token classes.

16. The system of claim 15 wherein one or more select operations, filter operations, sort operations, or project operations operate on the 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.

17. The system of claim 12 wherein the evaluation 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.

18. The system of claim 12 wherein the structured data store comprises a database, an xml structure or a flat table.

19. One or more computer-readable media having computer-executable instructions, which when executed perform steps, comprising:

receiving an online web query;

annotating the query into tokens and token classes, including segmenting the query into parts, to find candidate patterns;

finding a matching pattern that matches the query from among the candidate patterns;

translating the query or the annotated query, based on the matching pattern, into an evaluation expression; and

accessing the data store with the evaluation expression to obtain search results for the online web query.

20. The one or more computer-readable media of claim 19 having further computer-executable instructions comprising, routing the evaluation to the structured data store based upon the matching pattern.