Searching using query graphs
A device can receive a search query. The search query can relate to a geographic location. The device can process the search query to parse the search query into a plurality of strings. The plurality of strings can include text. The device can determine that one or more strings, of the plurality of strings, satisfy a condition. The device can generate, using the plurality of strings, a query graph that includes a plurality of paths relating to the condition. The query graph can further include a plurality of nodes leading to and/or included in the plurality of paths, and a plurality of transitions between the plurality of nodes. The device can perform one or more actions relating to the query graph to obtain, from a data structure, one or more search results that correspond to the search query.
1. A device, comprising:
one or more memories; and
one or more processors, communicatively coupled to the one or more memories, to:
receive a search query,
the search query relating to a geographic location;
process the search query to parse the search query into a plurality of strings,
the plurality of strings including text;
determine that one or more strings, of the plurality of strings, satisfy a condition,
wherein the one or more processors, when determining that the one or more strings satisfy the condition, are to determine that the one or more strings render the search query ambiguous;
generate, using the plurality of strings, a query graph that includes a plurality of paths relating to the condition,
the query graph being a directed acyclic graph and including:
a plurality of nodes leading to and/or included in the plurality of paths,
each node, of the plurality of nodes, corresponding to a category of data, of a plurality of categories of data, in a data structure, and
a plurality of transitions between the plurality of nodes wherein each transition, of the plurality of transitions, is associated with at least one letter or a word, and
wherein a transition, of the plurality of transitions, is associated with adding a letter to the one or more strings in a subsequent node of the query graph such that the subsequent node resolves the ambiguous search query; and
perform one or more actions relating to the query graph to obtain, from the data structure, one or more search results that correspond to the search query.
2. The device of claim 1 , where the one or more processors, when processing the search query to parse the search query into the plurality of strings, are to process the search query to parse the search query into the plurality of strings based on one or more delimiters.
3. The device of claim 2 , where the one or more delimiters include a space character or a comma.
4. The device of claim 1 , where the one or more processors, when determining that the one or more strings satisfy the condition, are to determine that the one or more strings are substitutable with one or more other strings.
5. The device of claim 1 , where the one or more processors, when determining that the one or more strings satisfy the condition, are to determine that the one or more strings are optional.
6. The device of claim 1 , where the plurality of categories of data include a street name category of data and one or more geographic region name categories of data.
7. The device of claim 1 , where the one or more processors, when performing the one or more actions, are to utilize the query graph to guide a search process to obtain the one or more search results.
8. A non-transitory computer-readable medium storing instructions, the instructions comprising:
one or more instructions that, when executed by one or more processors, cause the one or more processors to:
receive a search query,
the search query relating to a geographic location;
process the search query to parse the search query into a plurality of strings,
the plurality of strings including text;
determine that one or more strings, of the plurality of strings, satisfy a condition,
wherein the one or more instructions that cause the one or more processors to determine that the one or more strings satisfy the condition cause the one or more processors to determine that the one or more strings render the search query ambiguous;
generate, using the plurality of strings, a query graph that includes a plurality of paths relating to the condition,
the query graph being a directed acyclic graph, and further including:
a plurality of nodes leading to and/or included in the plurality of paths,
each node, of the plurality of nodes, corresponding to a category of data, of a plurality of categories of data, in a data structure, and
a plurality of transitions between the plurality of nodes,
wherein each transition, of the plurality of transitions, is associated with at least one letter or a word, and
wherein a transition, of the plurality of transitions, is associated with adding a letter to the one or more strings in a subsequent node of the query graph such that the subsequent node resolves the ambiguous search query; and
perform one or more actions relating to the query graph to obtain, from the data structure, one or more search results that correspond to the search query.
9. The non-transitory computer-readable medium of claim 8 , where the one or more instructions, that cause the one or more processors to receive the search query, cause the one or more processors to receive the search query based on one or more selections by a user of a client device.
10. The non-transitory computer-readable medium of claim 8 , where the one or more instructions, that cause the one or more processors to perform the one or more actions, cause the one or more processors to:
utilize the query graph to guide a search process to obtain the one or more search results.
11. The non-transitory computer-readable medium of claim 8 , where a first node, of the plurality of nodes, contains a first portion of a string, of the one or more strings, and where a second node, of the plurality of nodes, contains a second portion of the string.
12. The non-transitory computer-readable medium of claim 11 , where a third node, of the plurality of nodes, contains a string that is not included in the plurality of strings.
13. The non-transitory computer-readable medium of claim 12 , where the first node leads to a first path, of the plurality of paths, and a second path, of the plurality of paths, where the second path is different than the first path, where the second node is included in the first path, and where the third node is included in the second path.
14. The non-transitory computer-readable medium of claim 8 , where the plurality of transitions include:
a token transition between a first node, of the plurality of nodes, that contains a first string, of the plurality of strings, that includes one or more letters of a first word and a second node, of the plurality of nodes, that contains a second string, of the plurality of strings, that includes one or more letters of a second word different than the first word.
15. A method, comprising:
receiving, by a device, a search query,
the search query relating to a geographic location;
processing, by the device, the search query to parse the search query into a plurality of strings,
the plurality of strings including text;
determining, by the device, that one or more strings, of the plurality of strings, satisfy a condition,
wherein determining that the one or more strings satisfy the condition includes determining that the one or more strings render the search query ambiguous;
generating, by the device and using the plurality of strings, a query graph that includes a plurality of paths relating to the condition,
the query graph being a directed acyclic graph, and further including:
a plurality of nodes leading to and/or included in the plurality of paths,
each node, of the plurality of nodes, corresponding to a category of data, of a plurality of categories of data, in a data structure, and
a plurality of transitions between the plurality of nodes,
wherein each transition, of the plurality of transitions, is associated with at least one letter or a word, and
wherein a transition, of the plurality of transitions, is associated with adding a letter to the one or more strings in a subsequent node of the query graph such that the subsequent node resolves the ambiguous search query; and
performing, by the device, one or more actions relating to the query graph to obtain, from the data structure, one or more search results that correspond to the search query.
16. The method of claim 15 , where the plurality of nodes includes a root node at which traversal of the query graph begins, and one or more terminal nodes.
17. The method of claim 15 , where generating the query graph includes associating one or more constraints with one or more nodes of the plurality of nodes.
18. The method of claim 15 , where generating the query graph includes associating cost information with one or more nodes of the plurality of nodes.
19. The method of claim 18 , where the cost information indicates a measure of quality of results that will be obtained from traversal of the one or more nodes.
20. The method of claim 15 , where performing the one or more actions includes performing a search using a priority queue.