PROVIDING QUERY COMPLETIONS BASED ON DATA TUPLES

• US 20120185507A1
• Filed: 01/18/2011
• Published: 07/19/2012
• Est. Priority Date: 01/18/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Paparizos, Stelios, Gemmell, David James
• Granted Patent: US 10,691,679 B2
• Time in Patent Office: Days
• US Class Current: 707/774
• CPC Class Codes: G06F 16/2428 Query predicate definition using graphical user interfaces, including menus and forms G06F16/2423 takes precedence
• CPC Class Codes: G06F 16/243 Natural language query formulation

Abstract

Data, such as product data or airline flight data, is represented using structured data tuples, tables, or as data with related metadata and tags, and stored by a search engine. Partial queries are received by the search engine from a user and are used to generate a dialog between the search engine and the user. The dialog may include suggested query completions for the partial queries that correspond to a schema associated with the data tuples. The suggested query completions may be determined using attribute combinations of attributes and attribute values, or metadata and tags associated with the data tuples, including known synonyms and misspellings. The user may interact with the query completions in the dialog, and the search engine may revise the dialog and the query completions according to the interactions. A user may query data tuples without knowing the schema used by the underlying data structures.

Claims

1. A method comprising:

receiving first query data at computing device;

determining a first plurality of query completions based on the first query data and a set of attribute combinations associated with a plurality of data tuples by the computing device;

providing a subset of the first plurality of query completions by the computing device;

receiving second query data at the computing device;

determining a second plurality of query completions based on the first query data, the second query data, and the set of attribute combinations by the computing device; and

providing a subset of the second plurality of query completions by the computing device.

2. The method of claim 1, wherein the subset of the first plurality of query completions and the subset of the second plurality of query completions are provided in a dialog, and further comprising providing additional subsets of query completions in the dialog in response to additionally received query data.

3. The method of claim 1, wherein each of the plurality of data tuples comprises a plurality of attributes, and each attribute has one or more attribute values, and the set of attribute combinations comprises a mapping of the attributes and the attribute values to a plurality of query completions, and wherein determining the first plurality of query completions for the received query data based on the first query data and the set of attribute combinations comprises:

determining one or more attributes or attribute values that are partial matches of the first query data; and

determining the first plurality of query completions based on the mapping and the determined one or more attributes or attribute values that are partial matches.

4. The method of claim 1, further comprising selecting the subset of the first plurality of query completions.

5. The method of claim 4, wherein selecting the subset of the first plurality of query completions comprises selecting the subset of the first plurality of query completions using a query log of previously received queries.

6. The method of claim 4, wherein selecting the subset of the first plurality of query completions comprises selecting the subset of the first plurality of query completions using a diversity function.

7. The method of claim 4, wherein selecting the subset of the first plurality of query completions comprises selecting the subset of the first plurality of query completions according to a popularity associated with each of the plurality of query completions.

8. The method of claim 1, wherein the first plurality of query completions and the second plurality of query completions comprise concrete query completions and abstract query completions.

9. The method of claim 1, wherein at least one of the query completions of the first set of query completions includes a token, and the received second query data includes a value for the token.

10. A method comprising:

receiving a set of data tuples at a computing device, wherein each data tuple comprises a plurality of attributes and each attribute has one or more attribute values;

generating a set of attribute combinations based on the plurality of attributes and the corresponding one or more attribute values by the computing device;

receiving query data at the computing device;

determining a plurality of query completions for the query data using the set of attribute combinations by the computing device; and

providing a subset of the query completions by the computing device.

11. The method of claim 10, wherein the set of attribute combinations comprises a grammar.

12. The method of claim 11, wherein the grammar comprises a finite state transducer.

13. The method of claim 11, wherein the grammar comprises synonyms of the attributes and the attribute values.

14. The method of claim 11, wherein the grammar comprises misspellings of the attributes and the attribute values.

15. The method of claim 10, further comprising selecting the subset of the query completions.

16. The method of claim 15, wherein selecting the subset of the query completions comprises selecting the subset of the query completions using a query log of previously received queries.

17. The method of claim 15, wherein selecting the subset of the query completions comprises selecting the subset of the query completions using a diversity function.

18. A system comprising:

at least one computing device;

a grammar generator adapted to;

receive a set of data tuples, wherein each data tuple comprises a plurality of attributes and each attribute has one or more attribute values; and

generate a set of attribute combinations based on the plurality of attributes and the corresponding one or more attribute values; and

a query completion determiner adapted to;

receive query data;

determine a plurality of query completions for the query data using the set of query combinations; and

provide a subset of the determined one or more query completions.

19. The system of claim 18, wherein the set of attribute combinations comprises a mapping of attributes and attribute values to a plurality of query completions, and the query completion determiner is further adapted to:

determine one or more attributes or attribute values that are partial matches of the query data; and

determine the plurality of query completions based on the mapping and the determined one or more attribute or attribute values that are partial matches.

20. The system of claim 18, wherein the set of attribute combinations further comprises misspellings of the attributes and the attribute values.