Bloom filter for storing file access history

• US 8,849,838 B2
• Filed: 01/15/2008
• Issued: 09/30/2014
• Est. Priority Date: 01/15/2008
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Wang, Cheuksan Edward
• Primary Examiner(s): NGUYEN, CAM LINH T
• Application Number:
  US12/014,718
• Publication Number:
  US 20090182726A1
• Time in Patent Office: 2,450 Days
• Field of Search: 707/672, 707/673, 707/694, 707/698, 707/700, 707/701, 707/705, 707/706, 707/709, 707/721, 707/723, 707/732, 707/754, 709/219, 709/224
• US Class Current: 707/754
• CPC Class Codes: G06F 16/90335 Query processing

Abstract

A method of producing a search query result that incorporates information about previously accessed search results includes retrieving a list of results responsive to a search request from a user at a first client. A Bloom filter is applied to the results in the list of results to identify one or more first results, if any, in the list of results that the user has previously accessed. A result list is generated. The result list includes at least a portion of the list of results, based at least in part on the identified one or more first results. The result list is sent to the first client.

Claims

1. A method performed on a server system having one or more processors and memory storing one or more programs for execution by the one or more processors to perform the method, comprising:

retrieving a list of results responsive to a search request from a user at a first client;

applying a multi-user Bloom filter to results in the list of results to identify one or more first results, if any, in the list of results that the user has previously accessed, wherein applying the multi-user Bloom filter to results in the list of results includes applying a plurality of hash functions to a value, which includes a user identifier of the user and a content identifier associated with a respective result, to produce a plurality of location values, and accessing the plurality of locations in the multi-user Bloom filter;

generating a result list comprising at least a portion of the list of results, based at least in part on the identified one or more first results; and

sending the result list to the first client.

2. The method of claim 1, wherein the results in the list of results comprise content items, and the multi-user Bloom filter stores information with respect to content items accessed by respective users of a plurality of users.

3. The method of claim 1, wherein the result list includes information identifying results, if any, in the result list that the user has previously accessed.

4. The method of claim 1, wherein the result list includes formatting information for distinctively displaying results, if any, in the result list that the user has previously accessed.

5. The method of claim 1, wherein the generating excludes from the result list any results that the user has previously accessed.

6. The method of claim 1, wherein the results in the list of results comprise multimedia files.

7. The method of claim 1, further including updating the multi-user Bloom filter in accordance with results in the result list that are accessed by the user.

8. The method of claim 1, wherein applying the multi-user Bloom filter to results in the list of results includes:

identifying a Bloom filter in a plurality of Bloom filters in accordance with the user, wherein each Bloom filter in the plurality of Bloom filters corresponds to a respective plurality of users; and

applying the identified Bloom filter to results in the list of results to identify the one or more first results, if any, in the list of results that the user has previously accessed.

9. The method of claim 1, wherein applying the multi-user Bloom filter to results in the list of results includes:

identifying a Bloom filter in a plurality of Bloom filters in accordance with the user; and

filtering the list of results with the identified Bloom filter to identify the one or more first results, if any, in the list of results that the user has previously accessed.

23. The method of claim 1, further comprising:

concatenating the user identifier with the content identifier for each result in the list of results to produce a plurality of concatenated results; and

applying the multi-user Bloom filter to the concatenated results to identify one or more first results, if any, in the list of results that the user has previously accessed.

10. A method performed on a server system having one or more processors and memory storing one or more programs for execution by the one or more processors to perform the method, comprising:

in response to search requests from each of a plurality of users at respective clients, retrieving a list of results responsive to each of the search request, including a first list of results responsive to a first search request from a first user at a first client and a second list of results responsive to a second search request from a second user at a second client;

filtering results in the first list of results and results in the second list of results with a shared Bloom filter to produce a first filtered result list, comprising at least a portion of the first list of results, and a second filtered result list, comprising at least a portion of the second list of results;

sending the first filtered result list to the first client; and

sending the second filtered result list to the second client.

11. The method of claim 10, wherein the filtering identifies first results, if any, in the first list of results that the first user has previously accessed and identifies second results, if any, in the second list of results that the second user has previously accessed.

12. The method of claim 11 further including attaching information to the identified first and second results to indicate the respective user has previously accessed the identified first and second results.

13. The method of claim 10, wherein filtering the results in the first list and the second list includes:

identifying a single Bloom filter in a plurality of Bloom filters in accordance with the first user and second user; and

applying results in the first list of results and results of the second list of results to the identified single Bloom filter to produce the first filtered result list and the second filtered result list.

14. A method performed on a server system having one or more processors and memory storing one or more programs for execution by the one or more processors to perform the method, comprising:

receiving a plurality of requests from a plurality of clients, each request comprising a request for a respective item by a respective client of the plurality of clients;

for each received request, sending the requested respective item to the respective client; and

updating a Bloom filter associated with the plurality of clients to indicate each respective item sent to a respective client, including storing in an array a plurality of values for each of the retrieved items, wherein updating the Bloom filter includes hashing a value comprising a combination of a plurality of values, including an item identifier representing an item sent to a respective client and a user identifier representing the respective client.

15. The method of claim 14, including filtering a first request for a first item by a first user associated with one of the plurality of clients with the Bloom filter to determine if the first user has previously requested the first item.

16. The method of claim 14, wherein the items are multimedia files.

17. The method of claim 14, further comprising retrieving a list of items responsive to a search request from one of the plurality of clients and filtering the list of items with the Bloom filter to identify a previously retrieved item.

18. The method of claim 14, further comprising sending a filtered list of items, filtered by the Bloom filter, to a respective client of the plurality of clients.

19. The method of claim 18 wherein, the filtered list identifies a previously sent item by highlighting information identifying the previously sent item.

20. The method of claim 14, further comprising

maintaining a set of records identifying items requested or items sent to respective clients of the plurality of clients;

upon occurrence of a predefined event;

replacing the Bloom filter with a new Bloom filter generated from a subset of the set of records.

21. A computer system comprising:

memory;

one or more processors; and

one or more programs stored in the memory to be executed by the one or more processors, the one or more programs including;

instructions for retrieving a list of results responsive to a search request from a user at a first client;

instructions for concatenating a user identifier with a content identifier for each result in the list of results to produce a plurality of concatenated results;

instructions for applying a multi-user Bloom filter to the concatenated results to identify one or more first results, if any, in the list of results that the user has previously accessed;

instructions for generating a result list comprising at least a portion of the list of results, based at least in part on the identified one or more first results; and

instructions for sending the result list to the first client.

22. A non-transitory computer-readable storage medium storing one or more programs for execution by one or more processors of a computer system, the one or more programs comprising:

instructions for retrieving a list of results responsive to a search request from a user at a first client;

instructions for concatenating a user identifier with a content identifier for each result in the list of results to produce a plurality of concatenated results;

instructions for applying a multi-user Bloom filter to the concatenated results to identify one or more first results, if any, in the list of results that the user has previously accessed;

instructions for generating a result list comprising at least a portion of the list of results, based at least in part on the identified one or more first results; and

instructions for sending the result list to the first client.