Method and server for predicting a query-completion suggestion for a partial user-entered query

1. A method of training a machine learning algorithm (MLA) for determining a query-completion suggestion for a partial user-entered query, the partial user-entered query being part of a potential user query, the method executable by a server, the method comprising:

receiving, by the server, a plurality of past user queries;

parsing, by the server, the plurality of past user queries into a plurality of n-grams, each one of the plurality of n-grams being associated with at least one respective past user query and respective n-gram features, the n-gram features being indicative of a pair-based co-occurrence of n-grams from each possible pair of n-grams of the plurality of n-grams in the plurality of past user queries; and

for a given n-gram of a given past user query:

selecting, by the server, a plurality of candidate n-grams from the plurality of n-grams based on the pair-based co-occurrence of each one of the plurality of n-grams and the given n-gram in the plurality of past user queries;

generating, by the server, respective feature vectors for the given n-gram and the plurality of candidate n-grams based on the respective n-gram features;

generating, by the server, a training set for the given n-gram comprising an input portion and a label portion,

the input portion being based on a group of n-grams and the respective feature vectors, the group of n-grams comprising (i) the plurality of candidate n-grams and (ii) the given n-gram,

the label portion being based on the given past user query and the group of n-grams, the label portion being representative of a group-based co-occurrence of the group of n-grams in the given past user query, the group-based co-occurrence being indicative of a sub-group of candidate n-grams that co-occurs together with the given n-gram in the given past user query, and

training, by the server, the MLA based on the training set to determine, during its in-use phase, a predicted group-based co-occurrence of an in-use group of n-grams including a plurality of in-use candidate n-grams and at least one in-use n-gram in the potential user query, the predicted group-based co-occurrence being dependent on the at least one in-use n-gram and each in-use candidate n-gram in the plurality of in-use candidate n-grams, the predicted group-based co-occurrence being indicative of a sub-group of in-use candidate n-grams amongst the plurality of in-use candidate n-grams that are likely to co-occur together with the at least one in-use n-gram in the potential user query, the at least one in-use n-gram being the partial user-entered query, the predicted group-based co-occurrence for determining the sub-group of in-use candidate n-grams to be used as the respective query-completion suggestion.

2. The method of claim 1 , wherein the method comprises:

determining, by the server, the n-gram features to be associated with each one of the plurality of n-grams based on the plurality of n-grams and the plurality of past user queries.

3. The method of claim 1 , wherein the selecting the plurality of candidate n-grams from the plurality of n-grams comprises selecting, by the server, only n-grams from the plurality of n-grams that co-occurred with the given n-gram in the plurality of past user queries.

4. The method of claim 1 , wherein the selecting the plurality of candidate n-grams from the plurality of n-grams comprises:

ranking, by the server, at least some of the plurality of n-grams based on the pair-based co-occurrence of each one of the plurality of n-grams and the given n-gram in the plurality of past user queries; and

selecting, by the server, top ranked n-grams from the at least some of the plurality of n-grams as the plurality of candidate n-grams.

5. The method of claim 1 , wherein one of the plurality of n-grams co-occurred with the given n-gram in one of the plurality of past user queries when the one of the plurality of n-grams is either one of:

a preceding n-gram to the given n-gram in the one of the plurality of past user queries, and

a following n-gram to the given n-gram in the one of the plurality of past user queries.

6. The method of claim 5 , wherein:

the preceding n-gram is an immediately preceding n-gram; and

the following n-gram is an immediately following n-gram.

7. The method of claim 1 , wherein the n-gram features of the given n-gram are indicative of the pair-based co-occurrence of each one of the plurality of n-grams and the given n-gram in the plurality of past user queries.

8. The method of claim 1 , wherein the method further comprises:

receiving, by the server, the partial user-entered query;

parsing, by the server, the partial user-entered query into the at least one in-use n-gram, the at least one in-use n-gram being associated with respective n-gram features;

selecting, by the server, the plurality of in-use candidate n-grams from the plurality of n-grams based on the pair-based co-occurrence of each one of the plurality of n-grams with the at least one in-use n-gram in the plurality of past user queries;

generating, by the server, respective feature vectors for the at least one in-use n-gram and the plurality of in-use candidate n-grams based on the respective n-gram features; and

determining, by the server executing the MLA, the predicted group-based co-occurrence of the in-use group of n-grams including the plurality of in-use candidate n-grams and the at least one in-use n-gram, the determining the predicted group-based co-occurrence being dependent on the at least one in-use n-gram and each in-use candidate n-gram in the plurality of in-use candidate n-grams.

9. The method of claim 8 , wherein the method further comprises:

ranking, by the server, the plurality of in-use candidate n-grams based on the predicted group-based co-occurrence.

10. The method of claim 9 , wherein the method further comprises:

determining, by the server, the sub-group of in-use candidate n-gram to be used as the respective query-completion suggestion based on the predicted group-based co-occurrence.

11. The method of claim 1 , wherein the given n-gram is at least one of:

a letter-based n-gram;

a phoneme-based n-gram;

a syllable-based n-gram; and

a word-based n-gram.

12. A server comprising at least one processor, and

memory storing executable instructions, which, when executed by the at least one processor, cause the server to:

receive a plurality of past user queries;

parse the plurality of past user queries into a plurality of n-grams, each one of the plurality of n-grams being associated with at least one respective past user query and respective n-gram features, the n-gram features being indicative of a pair-based co-occurrence of n-grams from each possible pair of n-grams of the plurality of n-grams in the plurality of past user queries; and

for a given n-gram of a given past user query:

select a plurality of candidate n-grams from the plurality of n-grams based on the pair-based co-occurrence of each one of the plurality of n-grams and the given n-gram in the plurality of past user queries;

generate respective feature vectors for the given n-gram and the plurality of candidate n-grams based on the respective n-gram features;

generate a training set for the given n-gram comprising an input portion and a label portion,

the input portion being based on a group of n-grams and the respective feature vectors, the group of n-grams comprising (i) the plurality of candidate n-grams and (ii) the given n-gram,

the label portion being based on the given past user query and the group of n-grams, the label portion being representative of a group-based co-occurrence of the group of n-grams in the given past user query, the group-based co-occurrence being indicative of a sub-group of candidate n-grams that co-occurs together with the given n-gram in the given past user query, and

train a machine learning algorithm (MLA) based on the training set to determine, during its in-use phase, a predicted group-based co-occurrence of an in-use group of n-grams including a plurality of in-use candidate n-grams and at least one in-use n-gram in a potential user query comprising a partial user-entered query, the predicted group-based co-occurrence being dependent on the at least one in-use n-gram and each in-use candidate n-gram in the plurality of in-use candidate n-grams, the predicted group-based co-occurrence being indicative of a sub-group of in-use candidate n-grams amongst the plurality of in-use candidate n-grams that are likely to co-occur together with the at least one in-use n-gram in the potential user query, the at least one in-use n-gram being the partial user-entered query, the predicted group-based co-occurrence for determining the sub-group of in-use candidate n-grams to be used as a respective query-completion suggestion.

13. The server of claim 12 , wherein the instructions cause the server to:

determine the n-gram features to be associated with each one of the plurality of n-grams based on the plurality of n-grams and the plurality of past user queries.

14. The server of claim 12 , wherein the instructions that cause the server to select the plurality of candidate n-grams from the plurality of n-grams comprise instructions that cause the server to select only n-grams from the plurality of n-grams that co-occurred with the given n-gram in the plurality of past user queries.

15. The server of claim 12 , wherein the instructions that cause the server to select the plurality of candidate n-grams from the plurality of n-grams comprise instructions that cause the server to:

rank at least some of the plurality of n-grams based on the pair-based co-occurrence of each one of the plurality of n-grams and the given n-gram in the plurality of past user queries; and

select top ranked n-grams from the at least some of the plurality of n-grams as the plurality of candidate n-grams.

16. The server of claim 12 , wherein one of the plurality of n-grams co-occurred with the given n-gram in one of the plurality of past user queries when the one of the plurality of n-grams is either one of:

a preceding n-gram to the given n-gram in the one of the plurality of past user queries, and

a following n-gram to the given n-gram in the one of the plurality of past user queries.

17. The server of claim 16 , wherein:

the preceding n-gram is an immediately preceding n-gram; and

the following n-gram is an immediately following n-gram.

18. The server of claim 12 , wherein the n-gram features of the given n-gram are indicative of the pair-based co-occurrence of each one of the plurality of n-grams and the given n-gram in the plurality of past user queries.

19. The server of claim 12 , wherein the instructions cause the server to:

receive the partial user-entered query;

parse the partial user-entered query into the at least one in-use n-gram, the at least one in-use n-gram being associated with respective n-gram features;

select the plurality of in-use candidate n-grams from the plurality of n-grams based on the pair-based co-occurrence of each one of the plurality of n-grams with the at least one in-use n-gram in the plurality of past user queries;

generate respective feature vectors for the at least one in-use n-gram and the plurality of in-use candidate n-grams based on the respective n-gram features; and

determine, by executing the MLA, the predicted group-based co-occurrence of the in-use group of n-grams including the plurality of in-use candidate n-grams and the at least one in-use n-gram, the server being configured to determine the predicted group-based co-occurrence being dependent on the at least one in-use n-gram and each in-use candidate n-gram in the plurality of in-use candidate n-grams.

20. The server of claim 19 , wherein the instructions cause the server to:

rank the plurality of in-use candidate n-grams based on the predicted group-based co-occurrence.