Behavioral word segmentation for use in processing search queries

• US 8,825,620 B1
• Filed: 06/13/2011
• Issued: 09/02/2014
• Est. Priority Date: 06/13/2011
• Status: Expired due to Fees

• Current Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Original Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Inventors: Rose, Daniel E., Fliedner, Gerard, Evans, David Kirk
• Primary Examiner(s): Pham, Hung Q
• Application Number:
  US13/159,292
• Time in Patent Office: 1,177 Days
• Field of Search: 707/706
• US Class Current: 707/706
• CPC Class Codes: G06F 16/90335 Query processing
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/953 Querying, e.g. by the use of web search engines

Abstract

Substrings within strings, such as words within words, are identified based at least in part on recorded behavior of users that have submitted the strings or substrings as search queries. The behavior may relate to actions taken by the users upon having submitting the search queries. The actions may be actions taken in connection with an electronic marketplace, such as actions related to the consumption of items offered in the electronic marketplace. The identified strings and corresponding substrings are used in connection with processing search queries. The strings and substrings may be used to update a search index and/or to modify received search queries for processing.

Claims

1. A computer-implemented method of processing search queries, comprising:

under control of one or more computer systems configured with executable instructions,

obtaining, using at least one computing device, behavioral information associated with a plurality of previously-submitted queries, the behavioral information associated with each previously-submitted query indicative of one or more actions taken by one or more of the corresponding searchers in connection with the previously-submitted query;

identifying, from the obtained previously-submitted queries, a set of candidate pairs, each candidate pair including a first query and a second query, the first query including a set of separated words and the second query including a single word composed of a connected combination of at least a subset of the set of separated words, wherein the subset includes at least two words;

refining, using at least one computing device, the set of candidate pairs by, for each member pair of at least a subset of the set of candidate pairs, at least;

obtaining first search results corresponding to the first query of the member pair;

obtaining second search results corresponding to the second query of the member pair;

based at least in part on the first search results, the second search results, the obtained behavioral information associated with the first query of the member pair, and obtained behavioral information associated with the second query of the member pair, removing the member pair from the set of candidate pairs;

updating, based at least in part on the refined set of candidate pairs, a segmentation database that includes a plurality of member pairs, wherein each member pair includes a first member comprising a set of separated words and a second member comprising a single word composed of a connected combination of at least a subset of the set of separated words of the first member;

upon receiving a search query, comparing the search query against the plurality of member pairs in the segmentation database;

upon identifying a corresponding member pair for the search query in the segmentation database, substituting the search query with the corresponding member pair; and

processing the search query using the corresponding member pair.

2. The computer-implemented method of claim 1, wherein updating the segmentation database comprises, for at least one candidate pair of the refined set of candidate pairs, associating one or more documents with both the first query of the candidate pair and the second query of the candidate pair.

3. The computer-implemented method of claim 1, wherein the one or more actions are actions of an electronic marketplace.

4. The computer-implemented method of claim 1, wherein determining whether to remove the member pair from the set of candidate pairs includes calculating a measure of relatedness between the first search results and the second search results.

5. The computer-implemented method of claim 1, wherein the one or more actions are in connection with corresponding items offered for consumption in an electronic marketplace and wherein the computer-implemented method further comprises:

identifying, based at least in part on the obtained behavioral information associated with the first query of the member pair, a first set of items associated with the first query; and

identifying, based at least in part on the obtained behavioral information associated with the second query of the member pair, a second set of items associated with the second query; and

wherein removing the member pair from the set of candidate pairs is additionally based at least in part on a measure of relatedness between the first set of items and second set of items.

6. A computer-implemented method of processing search queries, comprising:

under control of one or more computer systems configured with executable instructions,

obtaining, using at least one computing device, behavioral information associated with a plurality of previously-submitted queries, the behavioral information associated with each previously-submitted query indicative of one or more actions taken by one or more of the corresponding searchers in connection with the previously-submitted query;

identifying, based at least in part on the obtained behavioral information, a set of query pairs, each query pair including a first previously-submitted query composed of a first separated element and a second separated element and a second previously-submitted query composed of a single element that is a combination of the first separated element and the second separated element;

providing, using the at least one processor, the set of query pairs to a segmentation data store for use in processing subsequently received search queries, the segmentation data store including a plurality of query pairs each including a first member comprising a set of separated elements and a second member comprising a single element composed of a connected combination of at least a subset of the set of separated elements of the first member;

upon receiving a search query, comparing the search query against the plurality of query pairs in the segmentation data store;

upon identifying a corresponding query pair for the search query in the segmentation data store, substituting the search query with the corresponding query pair; and

processing the search query using the corresponding query pair.

7. The computer-implemented method of claim 6, wherein providing the set of query pairs for use in processing search queries includes:

updating, based at least in part on the set of query pairs, a search index; and

providing the updated segmentation data store for use in processing subsequently received queries.

8. The computer-implemented method of claim 7, wherein updating the search index comprises, for at least one query pair of the set of query pairs, associating one or more documents with both a set of one or more separated elements and a combination of elements corresponding to the query pair.

9. The computer-implemented method of claim 6, further comprising:

for each search query of a plurality of subsequently received search queries;

segmenting, based at least in part on the set of query pairs, at least one component of the search query to generate a transformed search query; and

processing the transformed search query to identify one or more search results matching the transformed query; and

providing information identifying the identified one or more search results in response to the search query.

10. The computer-implemented method of claim 6, wherein the one or more actions are user actions in an electronic marketplace.

11. The computer-implemented method of claim 6, wherein the one or more actions for the previously submitted query include at least one of:

purchases in an electronic marketplace, placement in an electronic shopping cart of the electronic marketplace, and navigating to content dedicated to an item offered for consumption in the electronic marketplace.

12. The computer-implemented method of claim 6, wherein identifying the set of query pairs includes, for each query pair of at least a subset of the set of query pairs:

identifying a first set of items associated with a corresponding set of separated query elements;

identifying a second set of items associated with a corresponding combination of query elements; and

determining that the first set of items and second set of items are sufficiently similar.

13. The computer-implemented method of claim 6, wherein the separated query elements are words separated from one another by a space or other delimiting character.

14. The computer-implemented method of claim 6, wherein the separated query elements are sets of one or more sequential characters from a corresponding combination of query elements.

15. A computer-implemented method of processing search queries, comprising:

under control of one or more computer systems configured with executable instructions,

obtaining, using at least one computing device, a plurality of character strings forming at least part of queries previously submitted by corresponding searchers;

obtaining, using the at least one processor, behavioral information associated with the plurality of obtained character strings, the behavioral information associated with each character string indicative of one or more actions taken by one or more of the corresponding searchers in connection with the character string;

identifying, based at least in part on the obtained behavioral information, a plurality of pairs, each pair comprising a single character string from the obtained character strings and one or more substrings of the character string, the single character string being a connected combination of the one or more substrings; and

providing, using the at least one processor, the plurality of pairs to a segmentation data store for use in processing subsequently received search queries, the segmentation data store including a plurality of pairs each including a first member composed of one or more substrings of a character string and a second member composed of a single connected combination of at least a subset of the one or more substrings of the character string of the first member;

upon receiving a search query, comparing the search query against the plurality of pairs in the segmentation database;

upon identifying a corresponding pair for the search query in the segmentation database, substituting the search query with the corresponding pair; and

processing the search query using the corresponding pair.

16. The computer-implemented method of claim 15, wherein identifying the plurality of pairs includes, for each query pair of at least a subset of the query pairs:

identifying a first set of search results matching a character string corresponding to the query pair;

identifying a second set of search results matching one or more substrings of the character string; and

determining that the first set of search results and second set of search results are sufficiently similar.

17. The computer-implemented method of claim 15, wherein the one or more substrings are words.

18. The computer-implemented method of claim 15, further comprising updating a search index by at least associating a document with a character string and substring of at least one pair, and wherein using the identified pairs to process search queries includes using the updated search index.

19. The computer-implemented method of claim 15, wherein using the identified pairs to process search queries includes:

receiving queries comprising character strings;

determining whether the character strings are part of pairs; and

when the character strings are determined to be part of pairs, using corresponding substrings to process the queries.

20. The computer-implemented method of claim 15, wherein the one or more actions include actions taken in connection with items offered for consumption in an electronic marketplace.

21. The computer-implemented method of claim 15, wherein identifying the plurality of pairs includes:

identifying a plurality of candidate pairs; and

for each candidate pair of the plurality of candidate pairs that comprises a corresponding character string and corresponding one or more substrings;

identifying a first set of one or more items associated with the corresponding character string and identifying a second set of one or more items associated with the corresponding one or more substrings;

calculating a measure of relatedness between the first set and the second set; and

when the calculated measure indicates insufficient relatedness, discarding the candidate pair.

22. The computer-implemented method of claim 21, wherein the one or more items of the first set and the one or more items of the second set are items offered for consumption in an electronic marketplace and wherein the one or more items of the first set and the one or more items of the second set are associated with the corresponding character string and corresponding one or more substrings, respectively, due to recorded user actions in the electronic marketplace taken by users that have submitted the corresponding character string or corresponding one or more substrings as part of search queries.

23. A computer system for processing queries, comprising:

one or more processors; and

memory in communication with the one or more processors that includes executable instructions that, when executed by the one or more processors, cause the computer system to at least;

obtain behavioral information associated with a plurality of previously-submitted queries, the behavioral information associated with each previously-submitted query indicative of one or more actions taken by one or more corresponding searchers in connection with the previously-submitted query;

identify, based at least in part on the obtained behavioral information, a set of query pairs, each query pair including a first previously-submitted query composed of a first separated element and a second separated element and a second previously-submitted query composed of a single element that is a combination of the first separated element and the second separated element;

provide the identified set of query pairs to a segmentation data store for use in processing subsequently received queries, the segmentation data store including a plurality of query pairs each including a first member comprising a set of separated elements and a second member comprising a single element composed of a connected combination of at least a subset of the set of separated elements of the first member;

upon receiving a search query, compare the search query against the plurality of query pairs in the segmentation data store;

upon identifying a corresponding query pair for the search query in the segmentation database, substitute the search query with the corresponding query pair; and

process the search query using the corresponding query pair.

24. The computer system of claim 23, wherein identifying the plurality of pairs includes:

identifying a plurality of candidate pairs; and

for each candidate pair of the plurality of candidate pairs that comprises a corresponding character string and corresponding one or more substrings;

identifying a first set of one or more items associated with the corresponding character string and identifying a second set of one or more items associated with the corresponding one or more substrings;

calculating a measure of relatedness between the first set and the second set; and

when the calculated measure indicates insufficient relatedness, discarding the candidate pair.

25. The computer system of claim 24, wherein the one or more items of the first set and the one or more items of the second set are items offered for consumption in an electronic marketplace and wherein the one or more items of the first set and the one or more items of the second set are associated with the corresponding character string and corresponding one or more substrings, respectively, due to recorded user actions in the electronic marketplace taken by users that have submitted the corresponding character string or corresponding one or more substrings as part of search queries.

26. A computer-readable storage medium having stored thereon instructions that, when executed by one or more processors of a computer system, cause the computer system to at least:

obtain a plurality of character strings forming at least part of queries previously submitted by corresponding searchers;

obtain behavioral information associated with the character strings, the behavioral information associated with each character string indicative of one or more actions taken by one or more of the corresponding searchers in connection with the character string;

identify, based at least in part on the obtained behavioral information, a plurality of pairs, each pair comprising a single character string from the obtained character strings and one or more substrings of the character string, the single character string being a connected combination of the one or more substrings;

provide the identified plurality of pairs to a segmentation data store for use in processing subsequently received queries, the segmentation data store including a plurality of pairs each including a first member composed of one or more substrings of a character string and a second member composed of a single connected combination of at least a subset of the one or more substrings of the character string of the first member;

upon receiving a search query, compare the search query against the plurality of pairs in the segmentation data store;

upon identifying a corresponding pair for the search query in the segmentation data store, substitute the search query with the corresponding pair; and

process the search query using the corresponding pair.

27. The computer-readable storage medium of claim 26, wherein using the identified pairs to process search queries includes:

receiving queries comprising character strings;

determining whether the character strings are part of pairs; and

when the character strings are determined to be part of pairs, using corresponding substrings to process the queries.

28. The computer-readable storage medium of claim 26, further comprising updating a search index by at least associating a document with a character string and substring of at least one pair, and wherein using the identified pairs to process search queries includes using the updated search index.