System and method for query auto-completion using a data structure with trie and ternary query nodes

• US 9,659,109 B2
• Filed: 05/28/2014
• Issued: 05/23/2017
• Est. Priority Date: 05/27/2014
• Status: Active Grant

• Current Assignee: Walmart Apollo, LLC (WalMart Inc.)
• Original Assignee: Wal-Mart Stores Texas LLC (WalMart Inc.)
• Inventors: Hiwale, Rohit, Goel, Vishwas
• Primary Examiner(s): Mahmoudi, Tony
• Assistant Examiner(s): Le, Michael
• Application Number:
  US14/289,495
• Publication Number:
  US 20150347436A1
• Time in Patent Office: 1,091 Days
• Field of Search: 707706
• CPC Class Codes: G06F 16/90324 using system suggestions

Abstract

A method of providing predictive search query recommendations for a search query. The method can be implemented via execution of computer instructions configured to run at one or more processing modules and configured to be stored at one or more non-transitory memory storage modules. The method can include receiving the search query from a user. The method also can include determining the predictive search query recommendations for the search query using a tree data structure. At least one top layer of the tree data structure can include at least one trie query node and bottom layers of the tree data structure can include ternary tree query nodes. The method further can include sending the predictive search query recommendations to the user. Other embodiments of related systems and methods are also disclosed.

Claims

1. A method of providing predictive search query recommendations for a search query, the method being implemented via execution of computer instructions configured to run at one or more processing modules and configured to be stored at one or more non-transitory memory storage modules, the method comprising:

receiving the search query from a user;

determining the predictive search query recommendations for the search query using a tree data structure, wherein at least one top layer of the tree data structure comprise at least one trie query node, and wherein bottom layers of the tree data structure comprise ternary tree query nodes; and

sending the predictive search query recommendations to the user,

wherein;

the at least one top layer of the tree data structure having the at least one trie query node are at least three layers at a top of the tree data structure;

the tree data structure comprises query nodes and solution nodes;

the query nodes comprise the at least one trie query node and the ternary tree query nodes;

each of the solution nodes is a leaf node of the tree data structure, is a child of a ternary tree query node within the ternary tree query nodes, and comprises a predictive query solution and a score;

each of the ternary tree query nodes comprises a subtree score that is equal to a highest score of any of the solution nodes in a subtree that is rooted at the ternary tree query node; and

determining the predictive search query recommendations comprises;

determining an ending-character query node from among the query nodes based on the search query; and

if the ending-character query node is one of the ternary tree query nodes;

determining a subset of the solution nodes having scores that are in a group of highest scores in any of the solution nodes that are in an ending-character subtree that is rooted at the ending-character query node; and

using the predictive query solutions of the solution nodes in the subset of the solution nodes as the predictive search query recommendations.

2. The method of claim 1, wherein:

receiving the search query from the user comprises receiving a partial search query from the user prior to the user performing an action indicating entry of a complete search query that includes the partial search query.

3. The method of claim 1, wherein:

the predictive search query recommendations include one or more suggested queries that have a prefix string that is different than the search query.

4. The method of claim 1, wherein:

receiving the search query from the user comprises receiving the search query from the user such that the search query includes one or more typographic or orthographic errors; and

sending the predictive search query recommendations to the user comprises sending the predictive search query recommendations to the user such that the predictive search query recommendations include one or more corrections of the one or more typographic or orthographic errors.

5. The method of claim 1, wherein:

the at least one top layer of the tree data structure having the at least one trie query node are three to five layers at the top of the tree data structure.

6. The method of claim 1, wherein:

each of the at least one trie query node comprises one or more results lists;

and

determining the predictive search query recommendations further comprises;

if the ending-character query node is one of the at least one trie query node, using one of the one or more results lists of the one of the at least one trie query node as the predictive search query recommendations.

7. The method of claim 1, wherein:

determining the subset of the solution nodes comprises;

determining a highest solution node from among the solution nodes in the ending-character subtree, such that the score of the highest solution node is higher than any other of the scores of the solution nodes in the ending-character subtree.

8. The method of claim 7, wherein:

determining the highest solution node comprises;

traversing the ending-character subtree from the ending-character query node to the highest solution node by repeatedly branching from a parent query node of the query nodes to a top child query node of the query nodes, wherein the subtree score of the top child query node is equal to the subtree score of the parent query node.

9. The method of claim 7, wherein:

determining the highest solution node comprises;

storing a reference to a next-highest-branch query node of the query nodes, wherein the next-highest-branch query node is a query node of the query nodes in the ending-character subtree, the next-highest-branch query node is a child node of one of the query nodes traversed when determining the highest solution node, and the subtree score of the next-highest-branch query node is a next-highest score than the score of the highest solution node; and

determining the subset of the solution nodes comprises;

determining a next-highest solution node of the solution nodes from among a next-highest-branch subtree that is rooted at the next-highest-branch query node.

10. The method of claim 9, wherein:

determining the next-highest solution node comprises;

traversing the next-highest-branch subtree from the next-highest-branch query node to the next-highest solution node by repeatedly branching from a parent query node of the query nodes to a top child query node of the query nodes, wherein the subtree score of the top child query node is equal to the subtree score of the next-highest-branch query node.

11. The method of claim 1, wherein:

the score of each of the solution nodes is based on a relevance of the predictive query solution of the solution node.

12. The method of claim 1, wherein:

the tree data structure is pre-computed prior to receiving the search query from the user.

13. The method of claim 1, wherein:

the tree data structure is pre-cached prior to receiving the search query from the user.

14. A system for providing predictive search query recommendations for a search query, the system comprising:

one or more processing modules; and

one or more non-transitory memory storage modules storing computing instructions configured to run on the one or more processing modules and perform;

receiving the search query from a user;

determining the predictive search query recommendations for the search query using a tree data structure, wherein at least one top layer of the tree data structure comprise at least one trie query node, and wherein bottom layers of the tree data structure comprise ternary tree query nodes; and

sending the predictive search query recommendations to the user,

wherein;

the at least one top layer of the tree data structure having the at least one trie query node are at least three layers at a top of the tree data structure;

the tree data structure comprises query nodes and solution nodes;

the query nodes comprise the at least one trie query node and the ternary tree query nodes;

each of the solution nodes is a leaf node of the tree data structure, is a child of a ternary tree query node within the ternary tree query nodes, and comprises a predictive query solution and a score;

each of the ternary tree query nodes comprises a subtree score that is equal to a highest score of any of the solution nodes in a subtree that is rooted at the ternary tree query node; and

determining the predictive search query recommendations comprises;

determining an ending-character query node from among the query nodes based on the search query; and

if the ending-character query node is one of the ternary tree query nodes;

determining a subset of the solution nodes having scores that are in a group of highest scores in any of the solution nodes that are in an ending-character subtree that is rooted at the ending-character query node; and

using the predictive query solutions of the solution nodes in the subset of the solution nodes as the predictive search query recommendations.

15. The system of claim 14, wherein the computing instructions are further configured such that:

receiving the search query from the user comprises receiving the search query from the user such that the search query includes one or more typographic or orthographic errors; and

sending the predictive search query recommendations to the user comprises sending the predictive search query recommendations to the user such that the predictive search query recommendations include corrections of the typographic or orthographic errors.

16. The system of claim 14, wherein the computing instructions are further configured such that:

each of the at least one trie query node comprises one or more results lists;

and

determining the predictive search query recommendations further comprises;

if the ending-character query node is one of the at least one trie query node, using one of the one or more results lists of the one of the at least one trie query node as the predictive search query recommendations.

17. The system of claim 14, wherein the computing instructions are further configured such that:

determining the subset of the solution nodes comprises;

determining a highest solution node from among the solution nodes in the ending-character subtree, wherein the score of the highest solution node is higher than any other of the scores of the solution nodes in the ending-character subtree.

18. The system of claim 17, wherein the computing instructions are further configured such that:

determining the highest solution node comprises;

traversing the ending-character subtree from the ending-character query node to the highest solution node by repeatedly branching from a parent query node of the query nodes to a top child query node of the query nodes, wherein the subtree score of the top child query node is equal to the subtree score of the parent query node.

19. The system of claim 17, wherein the computing instructions are further configured such that:

determining the highest solution node comprises;

storing a reference to a next-highest-branch query node of the query nodes, wherein the next-highest-branch query node is a query node of the query nodes in the ending-character subtree, the next-highest-branch query node is a child node of one of the query nodes traversed when determining the highest solution node, and the subtree score of the next-highest-branch query node is a next-highest score than the score of the highest solution node; and

determining the subset of the solution nodes comprises;

determining a next-highest solution node of the solution nodes from among a next-highest-branch subtree that is rooted at the next-highest-branch query node.

20. The system of claim 19, wherein the computing instructions are further configured such that:

determining the next-highest solution node comprises;

traversing the next-highest-branch subtree from the next-highest-branch query node to the next-highest solution node by repeatedly branching from a parent query node of the query nodes to a top child query node of the query nodes, wherein the subtree score of the top child query node is equal to the subtree score of the next-highest-branch query node.