Filtering in search engines

• US 8,250,080 B1
• Filed: 01/11/2008
• Issued: 08/21/2012
• Est. Priority Date: 01/11/2008
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Guha, Ramanathan, Wagle, Vrishali
• Primary Examiner(s): Kim, Charles
• Assistant Examiner(s): Le, Jessica N
• Application Number:
  US12/013,260
• Time in Patent Office: 1,684 Days
• Field of Search: None
• US Class Current: 707/754
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9566 URL specific, e.g. using aliases, detecting broken or misspelled links

Abstract

In an embodiment, the size of a filter in a search engine is dynamically adjusted in order to reduce filter error. The filter, for example, may be a domain filter that contains domain(s) of preferred search results. A search engine processes the query and the domain filter to create a set of search results that are relevant to the query terms and for which a selected portion of the search results satisfy the domain filter, in that such portion of the documents comes from domains in the filter. The search results may then be provided to the user, as a set of search results that are relevant to the query terms and which include some portion of results that match the query labels. The construction of the domain filter may be done with a Bloom filter approach, using domain prefixes from annotations.

Claims

1. A method executed by one or more computers, the method comprising:

receiving a search query, the search query including a query label;

identifying, from a data store, one or more uniform resource locator (URL) patterns, each of the one or more URL patterns including a component of a URL and at least one of a wildcard or a regular expression, and each of the one or more URL patterns being associated with a label that matches the query label;

constructing a filter including;

determining a filter size based on a length of the one or more URL patterns and a count of a number of URL patterns having each respective length; and

constructing the filter having the filter size; and

filtering one or more results of the search query using the filter.

2. The method of claim 1, wherein determining the filter size includes:

generating a first data structure wherein each entry corresponds to a count of URL patterns;

generating a second data structure wherein each entry includes a non-zero length of at least one of the one or more URL patterns; and

calculating a value of an offset error for a set of offsets in the one or more URL patterns based on the first data structure and the second data structure.

3. The method of claim 2, further comprising:

generating a third data structure comprising specified values of offsets in the set of offsets.

4. The method of claim 3, further comprising:

identifying from the third data structure one or more offsets that correspond to a minimum value of the offset error.

5. The method of claim 4, wherein:

determining the filter size includes determining a size that corresponds to the minimum value of the offset error.

6. The method of claim 1, wherein the filter is a Bloom filter.

7. The method of claim 6, comprising:

determining a number of hash functions of the Bloom filter based on a number of different domain prefixes associated with each label.

8. The method of claim 6, comprising:

determining a number of hash functions of the Bloom filter based on a pre-defined false positive error rate.

9. The method of claim 1, wherein the URL pattern includes at least one of:

a host suffix pattern;

or

a combination of a URL prefix pattern and a host suffix pattern.

10. The method of claim 1, wherein the label includes a term being associated with at token that indicates that the term is a label.

11. The method of claim 1, wherein determining the filter size includes determining the filter size based on a minimum value of an offset error calculated based on the length of the one or more URL patterns and the count of the URL patterns having the length.

12. The method of claim 1, comprising:

performing an additional filtering function on the filtered one or more results, including applying a pre-determined number or percentage to the filtered one or more results.

13. The method of claim 1, wherein constructing the filter is based on one or more domains and one or more corresponding domain extensions, each domain extension including a pre-defined number of characters appearing after a corresponding domain.

14. The method of claim 1, comprising:

storing the length of the one or more URL patterns in a lengths vector having multiple length elements, each length element being a unique length of one or more URL patterns; and

storing the count of the number of URL patterns having each respective length in a pattern lengths count array having multiple pattern lengths count elements, a value of a pattern lengths count element at an index of the pattern lengths count array being a count of a number of URL patterns having a length that equals to the index.

15. A system comprising:

one or more computers configured to perform operations comprising;

receiving a search query, the search query including a query label;

identifying, from a data store, one or more uniform resource locator (URL) patterns, each of the one or more URL patterns including a component of a URL and at least one of a wildcard or a regular expression, and each of the one or more URL patterns being associated with a label that matches the query label;

constructing a filter including;

determining a filter size based on a length of the one or more URL patterns and a count of a number of URL patterns having each respective length; and

constructing the filter having the filter size; and

filtering one or more results of the search query using the filter.

16. The system of claim 15, wherein determining the filter size includes determining the filter size based on a minimum value of an offset error calculated based on the length of the one or more URL patterns and the count of the URL patterns having the length.

17. The system of claim 15, wherein the URL pattern includes at least one of:

a host suffix pattern;

or

a combination of a URL prefix pattern and a host suffix pattern.

18. The system of claim 15, wherein determining the filter size includes:

generating a first data structure wherein each entry corresponds to a count of URL patterns;

generating a second data structure wherein each entry includes a non-zero length of at least one of the one or more URL patterns; and

calculating a value of an offset error for a set of offsets in the one or more URL patterns based on the first data structure and the second data structure.

19. The system of claim 18, the operations further comprising:

generating a third data structure comprising specified values of offsets in the set of offsets.

20. The system of claim 19, the operations further comprising:

identifying from the third data structure one or more offsets that correspond to a minimum value of the offset error.

21. The system of claim 19, wherein:

determining the filter size includes determining a size that corresponds to the minimum value of the offset error.

22. The system of claim 15, wherein the label includes a term being associated with at token that indicates that the term is a label.

23. The system of claim 15, wherein the filter is a Bloom filter.

24. The system of claim 23, the operations comprising:

determining a number of hash functions of the Bloom filter based on a number of different domain prefixes associated with each label.

25. The system of claim 23, the operations comprising:

determining a number of hash functions of the Bloom filter based on a pre-defined false positive error rate.

26. The system of claim 15, the operations comprising:

performing an additional filtering function on the filtered one or more results, including applying a pre-determined number or percentage to the filtered one or more results.

27. The system of claim 15, wherein constructing the filter is based on one or more domains and one or more corresponding domain extensions, each domain extension including a pre-defined number of characters appearing after a corresponding domain.

28. The system of claim 15, the operations comprising:

storing the length of the one or more URL patterns in a lengths vector having multiple length elements, each length element being a unique length of one or more URL patterns; and

storing the count of the number of URL patterns having each respective length in a pattern lengths count array having multiple pattern lengths count elements, a value of a pattern lengths count element at an index of the pattern lengths count array being a count of a number of URL patterns having a length that equals to the index.

30. The computer instructions of claim 17, wherein the filter is a Bloom filter.

31. The computer instructions of claim 30, the operations comprising:

determining a number of hash functions of the Bloom filter based on a number of different domain prefixes associated with each label.

32. The computer instructions of claim 30, the operations comprising:

determining a number of hash functions of the Bloom filter based on a pre-defined false positive error rate.

29. Computer instructions stored on a computer-readable storage medium, the computer instructions configured to cause one or more computers to perform operations comprising:

receiving a search query, the search query including a query label;

identifying, from a data store, one or more uniform resource locator (URL) patterns, each of the one or more URL patterns including a component of a URL and at least one of a wildcard or a regular expression, and each of the one or more URL patterns being associated with a label that matches the query label;

constructing a filter including;

determining a filter size based on a length of the one or more URL patterns and a count of a number of URL patterns having each respective length; and

constructing the filter having the filter size; and

filtering one or more results of the search query using the filter.

33. The computer instructions of claim 29, wherein determining the filter size includes:

generating a first data structure wherein each entry corresponds to a count of URL patterns;

generating a second data structure wherein each entry includes a non-zero length of at least one of the one or more URL patterns; and

calculating a value of an offset error for a set of offsets in the one or more URL patterns based on the first data structure and the second data structure.

34. The computer instructions of claim 33, the operations further comprising:

generating a third data structure comprising specified values of offsets in the set of offsets.

35. The computer instructions of claim 34, the operations further comprising:

identifying from the third data structure one or more offsets that correspond to a minimum value of the offset error.

36. The computer instructions of claim 35, wherein:

determining the filter size includes determining a size that corresponds to the minimum value of the offset error.

37. The computer instructions of claim 29, wherein the URL pattern includes at least one of:

a host suffix pattern;

or

a combination of a URL prefix pattern and a host suffix pattern.

38. The computer instructions of claim 29, wherein the label includes a term being associated with at token that indicates that the term is a label.

39. The computer instructions of claim 29, wherein determining the filter size includes determining the filter size based on a minimum value of an offset error calculated based on the length of the one or more URL patterns and the count of the URL patterns having the length.

40. The computer instructions of claim 29, the operations comprising:

performing an additional filtering function on the filtered one or more results, including applying a pre-determined number or percentage to the filtered one or more results.

41. The computer instructions of claim 29, wherein constructing the filter is based on one or more domains and one or more corresponding domain extensions, each domain extension including a pre-defined number of characters appearing after a corresponding domain.

42. The computer instructions of claim 29, the operations comprising:

storing the length of the one or more URL patterns in a lengths vector having multiple length elements, each length element being a unique length of one or more URL patterns; and

storing the count of the number of URL patterns having each respective length in a pattern lengths count array having multiple pattern lengths count elements, a value of a pattern lengths count element at an index of the pattern lengths count array being a count of a number of URL patterns having a length that equals to the index.