Usage based query response

• US 8,428,933 B1
• Filed: 12/17/2009
• Issued: 04/23/2013
• Est. Priority Date: 12/17/2009
• Status: Active Grant

• Current Assignee: Connexity, Inc.
• Original Assignee: Shopzilla Incorporated
• Inventors: Roizen, Igor, Dutton, Keith, Jawor, Wojciech
• Primary Examiner(s): Vo, Huyen X.
• Application Number:
  US12/640,964
• Time in Patent Office: 1,223 Days
• Field of Search: 704 1- 10, 704/251, 704/255, 704/257, 704/270, 704/270.1
• US Class Current: 704/9
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates

Abstract

It is possible to provide meaningful responses to queries using systems which consider usage of words in the queries when analyzing those queries and determining what information is possibly relevant. This approach can be applied in online shopping systems by identification of nouns or noun phrases reflecting products available through the system.

Claims

1. A non-transitory computer readable medium having stored thereon a set of data operable to configure a computer to perform a set of tasks comprising:

a) receiving an input string, the input string comprising a plurality of words;

b) determining a plurality of divisions for the input string, wherein each division comprises a set of word groups, wherein each word from the plurality of words is a member of exactly one word group in each division;

c) for each division, determining;

1) a set of parts of speech, wherein;

i) cardinality for the set of word groups for the division and the set of parts of speech for the division is identical;

ii) each part of speech from the set of parts of speech for the division is associated with a single word group from the set of word groups for the division; and

iii) each part of speech from the set of parts of speech for the division is selected from a plurality of parts of speech, the plurality of parts of speech comprising an invented part of speech;

2) a rating, wherein the rating is based on a confidence that the set of parts of speech for the division corresponds to the set of word groups for the division; and

d) identifying the input string as corresponding to the set of parts of speech and the set of word groups from a division selected from the plurality of divisions based on the rating for the division.

2. The non-transitory computer readable medium of claim 1, wherein:

a) the invented part of speech is product noun;

b) the plurality of parts of speech comprises a natural language part of speech; and

c) the natural language part of speech is noun.

3. The non-transitory computer readable medium of claim 1, wherein the set of tasks further comprises:

a) receiving a raw input string, the raw input string comprising the plurality of words; and

b) processing the raw input string to create the input string, wherein processing the raw input string comprises cleaning dimension data from the raw input string.

4. The non-transitory computer readable medium of claim 1, wherein:

a) the input string is associated with a position in a taxonomy; and

b) for each division, the task of determining the set of parts of speech is performed based on;

1) a set of probabilities, the set of probabilities comprising, for each part of speech from the plurality of parts of speech, a probability that the part of speech is followed by a second part of speech, wherein the set of probabilities is determined based on the position in the taxonomy;

2) a first rule varying likelihood of the invented part of speech based on string position;

3) a second rule decreasing likelihood of a plurality of instances of the invented part of speech in the set of parts of speech; and

4) a list of word groups corresponding to the invented part of speech, wherein the list of word groups is determined based on the position in the taxonomy.

5. A non-transitory computer readable medium having stored thereon a set of data operable to configure a computer to perform a set of tasks comprising:

a) receiving an input string, the input string comprising a plurality of words;

b) determining a division for the input string, wherein the division comprises a set of word groups, wherein each word from the plurality of words is a member of exactly one word group from the set of word groups; and

c) determining a set of parts of speech, wherein;

1) cardinality for the set of parts of speech and the set of word groups is identical;

2) each part of speech from the set of parts of speech is associated with a single word group from the set of word groups;

3) each part of speech from the set of parts of speech is selected from a plurality of parts of speech, the plurality of parts of speech comprising an invented part of speech;

4) the task of determining the set of parts of speech is performed based on;

i) a set of probabilities, the set of probabilities comprising, for each part of speech from the plurality of parts of speech, a probability that the part of speech is followed by a second part of speech;

ii) a first rule varying likelihood of the invented part of speech based on string position;

iii) a second rule decreasing likelihood of a plurality of instances of the invented part of speech in the set of parts of speech.

6. The non-transitory computer readable medium of claim 5, wherein the set of tasks further comprises:

a) receiving a raw input string, the raw input string comprising the plurality of words; and

b) processing the raw input string to create the input string, wherein processing the raw input string comprises cleaning dimension data from the raw input string.

7. The non-transitory computer readable medium of claim 5, wherein the first rule increases likelihood of the invented part of speech exponentially with proximity to string termination.

8. The non-transitory computer readable medium of claim 5, wherein the second rule increases the likelihood of there being only one instance of the invented part of speech in the set of parts of speech.

9. The non-transitory computer readable medium of claim 5, wherein the first rule varies the likelihood of the invented part of speech beginning the set of parts of speech based on a cardinality for the plurality of words.

10. A machine comprising a first computer configured to perform a first set of tasks comprising:

a) receiving a first input string, wherein;

1) the first input string comprises a first plurality of words;

2) the first input string is associated with a position on a taxonomy;

b) determining a first division for the first input string, wherein;

1) the first division comprises a first set of word groups;

2) each word from the first plurality of words is a member of exactly one word group from the first set of word groups;

c) determining a first set of parts of speech, wherein;

1) cardinality for the first set of parts of speech and the first set of word groups is identical;

2) each part of speech from the first set of parts of speech is associated with a single word group from the first set of word groups;

3) each part of speech from the first set of parts of speech is selected from a plurality of parts of speech, the plurality of parts of speech comprising an invented part of speech;

4) the task of determining the first set of parts of speech is performed based on;

i) a first set of probabilities, the first set of probabilities comprising, for each part of speech from the plurality of parts of speech, a probability that the part of speech is followed by a second part of speech, wherein the first set of probabilities is determined based on the position in the taxonomy; and

ii) a first list of word groups corresponding to the invented part of speech, wherein the first list of word groups is determined based on the position in the taxonomy.

11. The machine of claim 10, wherein the first set of tasks comprises determining the position in the taxonomy.

12. The machine of claim 10 further comprising a second computer configured to perform a second set of tasks comprising:

a) receiving a second input string, wherein the second input string comprises a second plurality of words;

b) determining a second division for the second input string, wherein;

1) the second division comprises a second set of word groups;

2) each word from the second plurality of words is a member of exactly one word group from the second set of word groups;

c) determining a second set of parts of speech, wherein;

1) cardinality for the second set of parts of speech and the second set of word groups is identical;

2) each part of speech from the second set of parts of speech is associated with a single word group from the second set of word groups;

3) each part of speech from the second set of parts of speech is selected from the plurality of parts of speech;

4) the task of determining the second set of parts of speech is performed based on;

i) a second set of probabilities, wherein the second set of probabilities is a superset of the first set of probabilities; and

ii) a second list of word groups corresponding to the invented part of speech, wherein the second list of word groups is a superset of the first list of word groups.

13. The machine of claim 12, wherein:

a) the first computer is communicatively coupled to a database comprising a plurality of documents;

b) each document from the plurality of documents corresponds to a product offered by a vendor;

c) each document from the plurality of documents comprises a title;

d) the first input string is derived from a document from the plurality of documents;

e) the second computer comprises a network connection; and

f) the second input string is derived from a search query received via the network connection.