Fixed phrase detection for search

• US 8,176,067 B1
• Filed: 02/24/2010
• Issued: 05/08/2012
• Est. Priority Date: 02/24/2010
• Status: Active Grant

• Current Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Original Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Inventors: Jain, Deepak, Ahmad, Waseem
• Primary Examiner(s): Lewis, Cheryl
• Assistant Examiner(s): Hutton, Nan
• Application Number:
  US12/712,081
• Time in Patent Office: 804 Days
• Field of Search: 707/765, 707/767
• US Class Current: 707/765
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A set of search requests may be analyzed to detect fixed phrases suitable for inclusion in a search index. Sets of candidate phrases may be identified among the search requests. Fixed phrases may be detected among the candidate phrases using statistical techniques, for example, by identifying phrases having a relatively high pointwise mutual information (PMI) with respect to component keywords. Fixed phrase detection may include keyword and/or phrase clustering. Clusters may correspond to topics defined using a latent Dirichlet allocation (LDA) procedure. Fixed phrase detection may include identifying phrases having relatively high PMI within particular clusters.

Claims

1. A computer-implemented method facilitating a search of a collection of content, comprising:

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

associating keywords of previous searches of the collection of content with topics in accordance with a latent Dirichlet allocation;

for each of the topics,

identifying candidate phrases of the previous searches that contain at least one of the keywords associated with the topic;

determining pointwise mutual information scores for the candidate phrases; and

selecting at least some of the candidate phrases as fixed phrases based at least in part on a greatest pointwise mutual information score determined for the topic;

determining relevance scores for each of at least some of the keywords and each of at least some of the fixed phrases with respect to the collection of content; and

providing at least one result of the search for presentation, said at least one result at least referencing content selected from the collection of content based at least in part on the determined relevance scores.

2. A computer-implemented method according to claim 1, wherein associating the keywords with the topics comprises determining, for each of at least some of the keywords, associative measures between the keyword and each of a plurality of the topics.

3. A computer-implemented method according to claim 2, wherein associating the keywords with the topics further comprises associating the keyword with a topic of the plurality of the topics having a greatest associative measure.

4. A computer-implemented method according to claim 1, wherein each of the candidate phrases has less than a threshold number of the keywords.

5. A computer-implemented method according to claim 1, wherein selecting the fixed phrases comprises:

determining a pointwise mutual information score threshold based at least in part on the greatest pointwise mutual information score determined for the topic; and

selecting candidate phrases with pointwise mutual information scores greater than the pointwise mutual information score threshold.

6. A computer-implemented method according to claim 5, wherein the pointwise mutual information score threshold is a specified fraction of the greatest pointwise mutual information score.

7. A computer-implemented method facilitating a search, comprising:

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

clustering search terms extracted from previous searches into a plurality of search term clusters independent of human supervision;

identifying at least one search phrase comprising at least two search terms from a distinguished cluster of the plurality of search term clusters as having a relative high pointwise mutual information score with respect to search phrases of the distinguished cluster;

determining at least one relevance score for said at least one search phrase with respect to a collection of content; and

providing at least one result of the search for presentation, said at least one result at least referencing content selected from the collection of content based at least in part on said at least one relevance score.

8. A computer-implemented method according to claim 7, wherein each search phrase comprises a plurality of words.

9. A computer-implemented method according to claim 7, wherein clustering search terms comprises assigning each search term to at least one of a plurality of topics.

10. A computer-implemented method according to claim 7, wherein clustering search terms comprises determining an associative measure between each search term and each of a plurality of topics in accordance with latent Dirichlet allocation.

11. A computer-implemented method according to claim 10, wherein clustering search terms further comprises assigning each search term to one of the plurality of topics with which the search term has a greatest associative measure.

12. A computer-implemented method according to claim 7, wherein identifying said at least one search phrase comprises determining a pointwise mutual information score for each search phrase in the distinguished cluster.

13. A computer-implemented method according to claim 12, wherein the pointwise mutual information measure for each search phrase is based at least in part on a count of the search phrase in the distinguished cluster and counts of search phrases containing at least one search term of the search phrase in the distinguished cluster.

14. A computer-implemented method according to claim 7, wherein identifying said at least one search phrase as statistically significant comprises determining that said at least one search phrase has a pointwise mutual information score greater than a threshold.

15. A computer-implemented method facilitating a search, comprising:

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

determining pointwise mutual information scores for search phrases of previous searches;

selecting at least one of the search phrases for which the pointwise mutual information score is greater than a threshold;

determining at least one relevance score for said at least one search phrase with respect to a collection of content; and

providing at least one result of the search for presentation, said at least one result at least referencing content selected from the collection of content based at least in part on said at least one relevance score.

16. A computer-implemented method according to claim 15, wherein, for each of at least some of the search phrases, the pointwise mutual information score is determined with respect to component keywords of the search phrase.

17. A computer-implemented method according to claim 15, wherein, for each of at least some of the search phrases, the pointwise mutual information score is determined with respect to component keywords of the search phrase occurring in the searching phrases of the previous searches having a same length as the search phrase.

18. A computer-implemented method according to claim 15, wherein the threshold is based at least in part on a fraction of a greatest of the pointwise mutual information scores.

19. A computer-implemented method according to claim 18, wherein the fraction is determined at least in part by modeling an ordered set of the pointwise mutual information scores as an exponential decay.

20. A computerized system facilitating a search, comprising:

a fixed phrase detector configured to, at least;

cluster keywords of previous searches into a plurality of keyword clusters; and

detect at least one fixed phrase at least in part by identifying at least one search phrase comprising keywords of a distinguished cluster of the keyword clusters as having a relative high pointwise mutual information score with respect to counts of search phrases comprising keywords of the distinguished cluster;

an index maintenance module configured at least to update a search index comprising a relevance score of each of a plurality of keywords and said at least one fixed phrase for at least some of a collection of content;

a search module configured at least to provide at least one result of the search for presentation based at least in part on the search index; and

one or more hardware processors collectively facilitating at least the fixed phrase detector, the index maintenance module and the search module.

21. A computerized system according to claim 20, wherein at least some of the plurality of keyword clusters correspond to unsupervised topics defined at least in part by a latent Dirichlet allocation.

22. A computerized system according to claim 20, wherein identifying said at least one search phrase as statistically significant comprises determining at least one pointwise mutual information score for said at least one search phrase.

23. One or more non-transitory computer-readable media having collectively thereon computer-executable instructions that configure one or more computers to collectively, at least:

cluster keywords of previous searches into a plurality of keyword cluster independent of human supervision;

identify at least one search phrase comprising keywords of a distinguished cluster of the keyword clusters as having a relative high pointwise mutual information score with respect to counts of search phrases comprising keywords of the distinguished cluster;

determine at least one relevance score for said at least one search phrase with respect to a collection of content; and

provide at least one search result for presentation, said at least one result at least referencing content selected from the collection of content based at least in part on said at least one relevance score.

24. One or more computer-readable media according to claim 23, wherein said at least one relevance score is based at least in part on detected interaction with one or more search results previously presented responsive to said at least one search phrase.

25. One or more computer-readable media according to claim 24, wherein the counts of search phrases are weighted with respect to age.