Query understanding pipeline

Patent metadata

Field	Value
Publication number	US-9747365-B2
Application number	US-201414339588-A
Country	US
Kind code	B2
Filing date	Jul 24, 2014
Priority date	Jun 30, 2014
Publication date	Aug 29, 2017
Grant date	Aug 29, 2017

Abstract

A method for performing a search includes receiving a search query having one or more query terms from a remote device and generating a collection of one or more analyzed tokens based on the search query. The analyzed token collection is indicative of at least a subset of the query term(s). The method includes inputting the analyzed token collection into different parsers that each parse the analyzed token collection and/or the search query according to a parsing operation specific to the parser and output a parsed query including a list of one or more parsed tokens. Each parsed token includes a string, and at least one parsed token of at least one of the parsed queries includes one or more properties of the string. The method further includes generating a retrieval query based on the parsed queries outputted by the parsers and generating search results based on the retrieval query.

First claim

What is claimed is:

1. A method comprising:
receiving, by a processing device, a search query from a remote device, wherein the search query includes one or more query terms;
generating, by the processing device, a collection of one or more analyzed tokens based on the search query, wherein the collection of one or more analyzed tokens indicates at least a subset of the one or more query terms;
analyzing, by the processing device, the collection of one or more analyzed tokens with a plurality of different parsers, wherein:
each parser of the plurality of different parsers is configured to (i) according to a parsing operation specific to the parser, parse at least one of (a) the collection of one or more analyzed tokens and (b) the search query and (ii) output parsed query that includes a list of one or more parsed tokens,
each of the parsed tokens includes a corresponding string, and
at least one parsed token of at least one of the parsed queries includes one or more properties of the corresponding string;

generating, by the processing device, a retrieval query based on the parsed queries output by the plurality of different parsers, wherein:
the retrieval query is a data structure that includes a plurality of retrieval leaf nodes, and
each retrieval leaf node of the plurality of retrieval leaf nodes stores at least one of (i) a property of a string from a respective one of the parsed tokens and (ii) the string from the respective one of the parsed tokens;

identifying, by the processing device, a consideration set of records based on the plurality of retrieval leaf nodes, wherein each record of the consideration set of records includes state data related to at least one of (i) a function of a corresponding application and (ii) a state of the corresponding application resulting from performing the function;
determining, by the processing device, for each record in the consideration set of records, a result score for the record, wherein the result score for the record is determined based on a matching between the retrieval leaf node and the state data of the record;
generating, by the processing device, search results based on a subset of the consideration set of records, wherein the subset is selected based on the result scores of the consideration set of records; and
providing, by the processing device, the search results to the remote device.

2. The method of claim 1 , wherein:
at least one of the parsed tokens of at least one of the parsed queries includes a confidence value; and
the confidence value indicates a level of confidence of a property of the string determined by the parser that generated the parsed token.

3. The method of claim 1 , wherein generating the retrieval query based on the parsed queries comprises:
generating an intent query based on the parsed queries, wherein:
the intent query is a tree data structure that includes a plurality of connected intent query nodes, and
the plurality of connected intent query nodes includes one or more intent query leaf nodes that each store a respective one of the parsed tokens; and

generating the retrieval query based on the intent query.

4. The method of claim 3 , wherein generating the retrieval query based on the intent query comprises:
for each intent query leaf node, generating a subtree of the retrieval query based on the intent query leaf node; and
connecting the generated subtrees of the retrieval query using higher level intermediate nodes, the higher level intermediate nodes each storing a logic operator.

5. The method of claim 4 , wherein generating the subtree for the intent query leaf node comprises:
determining whether the parsed token stored in the intent query leaf node includes one or more properties in addition to the string of the parsed token;
in response to the parsed token in the intent query leaf node including one or more properties:
creating a string retrieval leaf node;
storing the string of the parsed token in the string retrieval leaf node;
for each property in the parsed token stored in the intent query leaf node:
creating a property retrieval leaf node; and
storing the property of the parsed token in the property retrieval leaf node;

creating an intermediate level node to store a logic operator; and
connecting the string retrieval leaf node and each of the property retrieval leaf nodes with the intermediate level node; and

in response to the parsed token in the intent query leaf node not including one or more properties:
creating a string retrieval leaf node; and
storing the string of the parsed token in the string retrieval leaf node.

6. The method of claim 3 further comprising:
generating a scoring query based on the intent query and the search query, wherein the scoring query is nested data structure, and
determining the result scores of each record in the consideration set based on the scoring query.

7. The method of claim 1 , wherein, for each record of the consideration set of records, the state data stores one or more access mechanisms to access the functionality or the state of the application.

8. The method of claim 1 , wherein the plurality of different parsers includes a location parser that outputs location parsed tokens and a synonym parser that outputs synonym parsed tokens.

9. The method of claim 8 , wherein:
the location parsed tokens include a string identifying a known geographic location and one or more properties of the string, and
each property includes geographic coordinates corresponding to the geographic location and a confidence value that indicates a degree of likelihood that the analyzed tokens analyzed by the location parser are describing the known geographic location.

10. The method of claim 8 , wherein:
the synonym parsed tokens include a string defining one or more strings defined in the analyzed tokens and one or more properties, and
the one or more properties define a synonym of the string and a confidence value that indicates a degree of likelihood that the synonym is an acceptable substitute for the string.

11. The method of claim 1 further comprising generating a subtree in the retrieval query for each parsed token that has a property, wherein generating the subtree in the retrieval query for a first parsed token includes:
creating an intermediate level node to store a logic operator;
creating a string retrieval leaf node;
storing the corresponding string of the first parsed token in the string retrieval leaf node;
connecting the string retrieval leaf node with the intermediate level node; and
for each property in the first parsed token:
creating a property retrieval leaf node;
storing the property in the property retrieval leaf node; and
connecting the property retrieval leaf node with the intermediate level node.

12. A search engine comprising:
a storage device that stores a datastore, the datastore storing a plurality of records, wherein each record includes state data related to at least one of (i) a function of a corresponding application and (ii) a state of the corresponding application resulting from performing the function;
a processing device that executes computer readable instructions, the computer readable instructions, when executed by the processing device, causing the processing device to:
receive a search query from a remote device, wherein the search query includes one or more query terms;
generate a collection of one or more analyzed tokens based on the search query, wherein the collection of one or more analyzed tokens indicates at least a subset of the one or more query terms;
analyze the collection of one or more analyzed tokens with a plurality of dif

Assignees

• Quixey Inc

Inventors

• Singh Brahm Kiran
• Purcell Shawn

Classifications

• G06F16/3329 Primary

  Natural language query formulation · CPC title

• G06F17/30654 Primary

  Physics · mapped topic