Approximate template matching for natural language queries

1. A method for performing a search, the method comprising:

receiving an input query via a user input device, wherein the input query comprises a plurality of words;

identifying, from the plurality of words, a first word and a second word;

computing a first representation vector corresponding to a degree to which the first word matches a set of word features, and a second representation vector corresponding to a degree to which the second word matches the set of word features;

retrieving, from a database, a search query template relating to a search intent;

identifying, from a plurality of words of the search query template, a third word associated with a third representation vector corresponding to a degree to which the third word matches the set of word features;

identifying, from the plurality of words of the search query template, a fourth word associated with a fourth representation vector corresponding to a degree to which the fourth word matches the set of word features;

determining a similarity of the first representation vector with the third representation vector and a similarity of the second representation vector with the fourth representation vector;

selecting, based on the determined similarities, the search query template;

retrieving search results based on the selected search query template; and

generating for display the retrieved search results.

2. The method of claim 1 , wherein determining a similarity of the first representation vector with the third representation vector and a similarity of the second representation vector with the fourth representation vector comprises:

computing a first distance between the first representation vector and the third representation vector;

computing a second distance between the second representation vector and the fourth representation vector;

determining whether the first distance is less than a first threshold distance; and

determining whether the second distance is less than a second threshold distance.

3. The method of claim 2 , wherein computing the first distance between the first representation vector and the third representation vector comprises:

comparing a first value in the first representation vector with a corresponding second value in the second representation vector to determine whether the first value and the second value differ by less than a threshold value;

in response to determining that the values differ by less than the threshold value, leaving the distance unchanged; and

in response to determining that the values do not differ by less than the threshold value, computing a degree to which the values are dissimilar and incrementing the distance based on the degree to which the values are dissimilar.

4. The method of claim 2 , wherein computing the first distance between the first representation vector and the third representation vector is based on an orientation of the first representation vector with respect to the third representation vector in a vector space, such that the first distance is a measure of an angle between the first representation vector and the third representation vector.

5. The method of claim 1 , further comprising including one of the first word and the second word from the input query in the query to the database.

6. The method of claim 5 , further comprising:

identifying a part of speech associated with the first word; and

in response to determining that the first word is a subject of the input query, including the first word in the query to the database.

7. The method of claim 1 , further comprising:

comparing the first word to a list of stop words to determine whether the first word matches a stop word of the list of stop words; and

in response to determining that the first word matches the stop word:

selecting a third word of the input query; and

computing a fifth representation vector, wherein values of the first representation vector correspond to degrees to which the third word of the input query matches features of the set of word features.

8. The method of claim 2 , wherein the first distance is smaller than a third distance between the first representation vector and the fourth representation vector when the first word matches a meaning of the third word and does not match a meaning of the fourth word.

9. The method of claim 2 , wherein the search query template is a first search query template, and further comprising:

in response to determining that the first distance is greater than the first threshold distance:

retrieving a second search query template from the database, wherein the second search query template is associated with a fifth representation vector and a sixth representation vector having respective values corresponding to degrees to which a first word of the second search query template and a second word of the second search query template match features of the set of word features respectively; and

computing a third distance between the first representation vector and the fifth representation vector; and

in response to determining that the third distance is less than the first threshold distance, computing a fourth distance between the second representation vector and the sixth representation vector; and

in response to determining that the fourth distance is less than the second threshold, selecting the second search query template for retrieving the search results.

10. The method of claim 1 , wherein generating for display the retrieved search results further comprises:

retrieving a layout from the database associated with the search query template; and

generating for display the retrieved search results based on the layout.

11. A system comprising control circuitry configured to for performing a search, wherein the control circuitry is configured to:

receive an input query via a user input device, wherein the input query comprises a plurality of words;

identify, from the plurality of words, a first word and a second word;

compute a first representation vector corresponding to a degree to which the first word matches a set of word features, and a second representation vector corresponding to a degree to which the second word matches the set of word features;

retrieve, from a database, a search query template relating to a search intent;

identify, from a plurality of words of the search query template, a third word associated with a third representation vector corresponding to a degree to which the third word matches the set of word features;

identify, from the plurality of words of the search query template, a fourth word associated with a fourth representation vector corresponding to a degree to which the fourth word matches the set of word features;

determine a similarity of the first representation vector with the third representation vector and a similarity of the second representation vector with the fourth representation vector;

select, based on the determined similarities, the search query template;

retrieve search results based on the selected search query template; and

generate for display the retrieved search results.

12. The system of claim 11 , wherein the control circuitry is further configured, when determining a similarity of the first representation vector with the third representation vector and a similarity of the second representation vector with the fourth representation vector, to:

compute a first distance between the first representation vector and the third representation vector;

compute a second distance between the second representation vector and the fourth representation vector;

determine whether the first distance is less than a first threshold distance; and

determine whether the second distance is less than a second threshold distance.

13. The system of claim 12 , wherein the control circuitry is further configured, when computing the first distance between the first representation vector and the third representation vector, to:

compare a first value in the first representation vector with a corresponding second value in the second representation vector to determine whether the first value and the second value differ by less than a threshold value;

in response to determining that the values differ by less than the threshold value, leave the distance unchanged; and

in response to determining that the values do not differ by less than the threshold value, compute a degree to which the values are dissimilar and increment the distance based on the degree to which the values are dissimilar.

14. The system of claim 12 , wherein the control circuitry is further configured, when computing the first distance between the first representation vector and the third representation vector, to base the first distance on an orientation of the first representation vector with respect to the third representation vector in a vector space, such that the first distance is a measure of an angle between the first representation vector and the third representation vector.

15. The system of claim 11 , wherein the control circuitry is further configured to include one of the first word and the second word from the input query in the query to the database.

16. The system of claim 15 , wherein the control circuitry is further configured to:

identify a part of speech associated with the first word; and

in response to determining that the first word is a subject of the input query, include the first word in the query to the database.

17. The system of claim 11 , wherein the control circuitry is further configured to:

compare the first word to a list of stop words to determine whether the first word matches a stop word of the list of stop words; and

in response to determining that the first word matches the stop word:

select a third word of the input query; and

compute a fifth representation vector, wherein values of the first representation vector correspond to degrees to which the third word of the input query matches features of the set of word features.

18. The system of claim 12 , wherein the first distance is smaller than a third distance between the first representation vector and the fourth representation vector when the first word matches a meaning of the third word and does not match a meaning of the fourth word.

19. The system of claim 12 , wherein the search query template is a first search query template, and wherein the control circuitry is further configured to:

in response to determining that the first distance is greater than the first threshold distance:

retrieve a second search query template from the database, wherein the second search query template is associated with a fifth representation vector and a sixth representation vector having respective values corresponding to degrees to which a first word of the second search query template and a second word of the second search query template match features of the set of word features respectively; and

compute a third distance between the first representation vector and the fifth representation vector; and

in response to determining that the third distance is less than the first threshold distance, compute a fourth distance between the second representation vector and the sixth representation vector; and

in response to determining that the fourth distance is less than the second threshold, select the second search query template for retrieving the search results.

20. The system of claim 11 , wherein the control circuitry is further configured, when generating for display the retrieved search results, to:

retrieve a layout from the database associated with the search query template; and

generate for display the retrieved search results based on the layout.