Search cache for document search

• US 8,612,423 B2
• Filed: 10/29/2010
• Issued: 12/17/2013
• Est. Priority Date: 10/29/2010
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Nath, Suman Kumar, Athivarapu, Pavan Kumar
• Primary Examiner(s): NGUYEN, CAM LINH T
• Application Number:
  US12/915,045
• Publication Number:
  US 20120110015A1
• Time in Patent Office: 1,145 Days
• Field of Search: 707/715, 707/999.004, 707/780, 707/830
• US Class Current: 707/715
• CPC Class Codes: G06F 16/3349 Reuse of stored results of previous queries
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching

Abstract

A method is described herein that includes receiving a query from a user at a computing device. The method also includes performing a search for one or more documents based at least in part upon the received query, wherein performing the search comprises causing a processor to perform the search through utilization of a search cache retained on the computing device, wherein the search cache comprises a results cache, an index cache, and a Boolean cache.

Claims

1. A method, comprising:

receiving, at a computing device, a local search cache, wherein the local search cache comprises a portion of a global index stored at a remote coordinator device communicatively coupled to a network comprising the computing device, the remote coordinator device and at least one other computer device, the global index indexing a plurality of documents stored across the computing device, the remote coordinator device and the at least one other computer device;

receiving, at the computing device, a query directed to the local search cache, wherein the query includes at least one keyword; and

performing, at the computing device, a search based at least in part upon the received query, wherein performing the search comprises causing a processor to perform the search through utilization of the local search cache, the local search cache comprising a results cache, an index cache, and a Boolean cache, wherein the results cache includes a previously submitted query and search results for the previously submitted query, the index cache indexes keywords with identities and locations of a subset of the plurality of documents stored between the computing device, the remote coordinator device and at least one other computer device, and wherein the Boolean cache is a data structure that indicates whether the at least one keyword is included in an element set that corresponds to the plurality of documents that are stored between the computing device, the remote coordinator device and at least one other computer device.

2. The method of claim 1, wherein the Boolean cache is a Bloom filter and wherein the computing device is a mobile computing device.

3. The method of claim 1, further comprising:

determining respective sizes of the results cache, the index cache, and the Boolean cache; and

determining respective content of the results cache, the index cache, and the Boolean cache based at least in part upon the respective sizes of the results cache, the index cache, and the Boolean cache and search history with respect to the plurality of documents being stored between the computing device, the remote coordinator device and the at least one other computer device.

4. The method of claim 1, wherein performing the search comprises:

comparing the received query with queries in the results cache; and

if the received query is resident in the results cache, outputting an identity and location of at least one document, stored between the computing device, the remote device and at least one other computer device, that corresponds to the received query in the results cache.

5. The method of claim 4, wherein performing the search further comprises:

comparing keywords in the index cache with the at least one keyword in the query; and

if the at least one keyword is resident in the index cache, outputting an identity and location of at least one document, stored between the computing device, the remote device and at least one other computer device, that corresponds to the at least one keyword in the index cache.

6. The method of claim 5, wherein performing the search further comprises:

determining if the at least one keyword is in a range that corresponds to the Boolean cache; and

if the at least one keyword is not in the range that corresponds to the Boolean cache, transmitting the query to the remote coordinator device.

7. The method of claim 5, wherein performing the search further comprises:

determining that the at least one keyword is in a range that corresponds to the Boolean cache;

searching the Boolean cache for the at least one keyword; and

if the at least one keyword is included in the Boolean cache, transmitting the received query to the remote coordinator device.

8. The method of claim 7, further comprising:

receiving, from the remote coordinator device, an update for the local server cache, wherein the update relating to a content of the received query transmitted to the remote coordinator device.

9. The method of claim 8, wherein the update comprising at least one keyword for incorporation into the results cache, the index cache, or the Boolean filter.

10. The method of claim 5, wherein performing the search further comprises:

determining that the at least one keyword is in a range that corresponds to the Boolean cache;

searching the Boolean cache for the at least one keyword; and

if the at least one keyword is not included in the Boolean cache, responding to the received query with a null result set.

11. The method of claim 10, wherein the comparing of the received query with the at least one query in the results cache is undertaken prior to the comparing of the at least one keyword in the index cache with the at least one keyword in the received query, and wherein the comparing of the at least one keyword in the index cache with the at least one keyword in the received query is undertaken prior to the searching of the Boolean cache for the at least one keyword.

12. The method of claim 11, wherein the range that corresponds to the Boolean cache is a range of alphabetical characters, wherein a first letter of the at least one keyword included in the query is in the range of alphabetical characters.

13. A computing device, comprising:

a processor; and

a memory that comprises a plurality of components that are executed by the processor, the plurality of components comprising;

a receiver component configured to;

receive, from a remote coordinator device, a local search cache, wherein the local search cache comprises a portion of a global index stored at the remote coordinator device communicatively coupled to a network comprising the computing device, the remote coordinator device and at least one other computer device, the global index indexing a plurality of documents stored between the computing device, the remote coordinator device and the at least one other computer device, and the local search cache relating to a subset of the plurality of documents; and

while disconnected from the network, receive a query; and

a search component configured to perform a search for at least one document in the plurality of documents based at least in part upon the query through utilization of the local search cache, wherein the local search cache comprises a results cache, an index cache, and a Bloom filter, and wherein the search component returns a search result set based at least in part upon the search.

14. The system of claim 13, wherein the local search cache comprises data indicative of at least one document available by way of the World Wide Web.

15. The system of claim 13, wherein the computing device is a mobile computing device.

16. The system of claim 15, wherein the mobile computing device is a mobile telephone.

17. The system of claim 13, wherein the search component searches the results cache prior to searching the index cache, and wherein the search component searches the index cache prior to searching the Bloom filter.

18. The system of claim 13, wherein the search component transmits the query to the remote coordinator device subsequent to searching the Bloom filter.

19. The system of claim 13, wherein, on subsequent reconnection of the computing device with the network, contents of the local search cache are updated by the remote coordinator device, and wherein the remote coordinator device determines sizes of the results cache, the index cache, and the Bloom filter, respectively.

20. A method, comprising:

receiving a search cache from a coordinator device, wherein the search cache comprises a results cache, an index cache, and a Bloom filter;

receiving a query from a user;

searching over the search cache based at least in part the query, wherein searching over the search cache comprises;

initially searching over the results cache for the query;

when the results cache comprises the query, returning an identity and location of at least one document corresponding to the query in the results cache to the user;

when the results cache does not comprise the query, subsequently searching over the index cache for at least one keyword in the query;

when the index cache comprises the at least one keyword, returning identity and location of at least one document corresponding to the at least one keyword in the index cache to the user;

when the index cache does not comprise the at least one keyword, subsequently determining if the at least one keyword is in a range corresponding to the Bloom filter;

when the at least one keyword is in the range corresponding to the Bloom filter, searching the Bloom filter for the at least one keyword;

when the Bloom filter fails to include the at least one keyword, subsequently returning a null result set to the user;

otherwise

transmitting the query to the coordinator device; and

receiving a result set from the coordinator device.