Dynamic community-based cache for mobile search

• US 8,943,043 B2
• Filed: 01/24/2010
• Issued: 01/27/2015
• Est. Priority Date: 01/24/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Lymberopoulos, Dimitrios, Koukoumidis, Emmanouil, Liu, Jie, Zhao, Feng, Burger, Douglas Christopher
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): Almani, Mohsen
• Application Number:
  US12/692,626
• Publication Number:
  US 20110184936A1
• Time in Patent Office: 1,829 Days
• Field of Search: 707/767
• US Class Current: 707/721
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching

Abstract

A “Community-Based Mobile Search Cache” provides various techniques for maximizing the number of query results served from a local “query cache”, thereby significantly limiting the need to connect to the Internet or cloud using 3G or other wireless links to service search queries. The query cache is constructed remotely and downloaded to mobile devices. Contents of the query cache are determined by mining popular queries from mobile search logs, either globally or based on queries of one or more groups or subgroups of users. In various embodiments, searching and browsing behaviors of individual users are evaluated to customize the query cache for particular users or user groups. The content of web pages related to popular queries may also be included in the query cache. This allows cached web pages to be displayed without first displaying cached search results when a corresponding search result has a sufficiently high click-through probability.

Claims

1. A method for providing query search results for mobile communications devices, comprising steps for:

for each of two or more different communities of mobile communications devices, constructing at least one query cache from contents of one or more historical query logs of each of the communities of mobile communications devices;

wherein constructing at least one query cache for each of the two or more different communities of mobile communications devices inherently results in the construction of a set of two or more different query caches;

wherein the contents of each query cache include a set of query terms and corresponding links from the historical query logs;

selecting one or more of the query caches from the set of two or more query caches by determining which of the corresponding communities are similar to a community associated with one or more particular mobile communications devices and providing the selected query caches to the one or more particular mobile communications devices; and

on one or more of the mobile communications devices, locally servicing queries using one or more of the query caches provided to each particular mobile communications device without accessing an external query search service.

2. The method claim 1 wherein constructing any of the query caches from contents of the historical query logs further comprises steps for:

examining the contents of historical query logs to extract pairs of queries and corresponding user selected links (i.e., “

query/link pairs”

) returned by individual search histories recorded in those logs;

sorting the extracted query/link pairs in order of aggregate user selection volume associated with each query/link pair to construct a set of sorted query/link pairs; and

adding sorted query/link pairs to the query cache, beginning with the query/link pair having the highest aggregate volume then sequentially selecting the query/link pair having the next highest aggregate volume, until the query cache reaches a desired size.

3. The method of claim 2 further comprising steps for locally personalizing the query cache previously provided to a particular mobile communications device by re-ranking query/link pairs in the query cache as a direct function of user interactions with any corresponding link and regardless of any aggregate volume associated with the corresponding query/link pair.

4. The method of claim 2 wherein locally servicing queries further comprises steps for using matching query/link pairs corresponding to the query for dynamically synthesizing and displaying a search results page on the mobile communication device, and wherein links on the search results page are ordered by aggregate volume.

5. The method of claim 4 wherein probabilistic search string matching is used to determine whether a query is a match to query/link in the query cache.

6. The method of claim 4 further comprising steps for associating a click-through probability with one or more of the query/link pairs, and wherein any link having a click-through probability above a predetermined threshold is used to directly present contents of that link in response to a corresponding query without first presenting a search results page on the mobile communication device.

7. The method of claim 1 wherein a hash table architecture is used to construct each query cache, such that each unique link is stored only once in the query cache, with a unique hash of that link being stored along with every corresponding query term.

8. The method of claim 1 wherein each query cache is constructed using a “

cache saturation threshold”

that limits the contents of the query cache to query/link pairs having a normalized volume greater than a predetermined threshold.

9. The method of claim 1 wherein a specific community of mobile communications devices determined to reside within a predetermined geographic region is used to construct at least one of the query caches.

10. The method of claim 1 wherein a specific community of mobile communications devices determined to correspond to a predetermined demographic group is used to construct at least one of the query caches.

11. The method of claim 1 further comprising periodically updating the contents of one or more query caches by providing a set of update information to one or more corresponding mobile communications devices.

12. The method of claim 1 further comprising steps for:

locally caching additional content, including any of electronic documents, advertisements, and web pages, in conjunction with one or more of the query caches provided to one or more of the mobile communications devices; and

wherein any of the additional content corresponding to a selected link is presented from the cache without accessing an external network.

13. The method of claim 1 wherein a specific community of mobile communications devices determined to correspond to a predetermined demographic group is used to construct the query cache.

14. A system for servicing queries on mobile devices, comprising:

a device for constructing a “

query cache”

for each of two or more different communities of mobile communications devices from contents of a historical query log of each corresponding community of mobile communications devices, each said query cache including a set of query terms and corresponding links (i.e., “

query/link pairs”

) extracted from the historical query logs;

wherein constructing a query cache for each of the two or more different communities of mobile communications devices inherently results in the construction of a set of two or more different query caches;

a device for selecting one or more of the query caches from the set of two or more query caches by determining which of the corresponding communities are similar to a community associated with one or more particular mobile communications devices and providing the selected query caches to the one or more particular mobile communications devices; and

a device on each mobile communications device for locally servicing queries using the local query cache provided to each particular mobile communications device without accessing an external network to interact with a remote query search service.

15. The system of claim 14 wherein locally servicing queries further comprises a device for using query/link pairs matching the query for dynamically synthesizing and displaying a search results page on the mobile communication device.

16. The system of claim 14 wherein a hash table architecture is used to map queries to links in the query cache.

17. A computer-readable hardware storage device having computer executable instructions stored therein for generating a query cache to be provided to mobile communications devices for locally handling searches of query terms, said instructions comprising:

allowing user selection of one or more of query caches from a set of two or more different query caches, each query cache generated from a different community of mobile devices, and providing the selected query caches to a mobile communications device of the user; and

on the user'"'"'s mobile communications device, locally servicing queries using one or more of the query caches provided to the user'"'"'s mobile communications device in response to the user selection without accessing an external query search service.

18. The computer-readable hardware storage device of claim 17 wherein the computer executable instructions for constructing the query caches further comprises instructions for:

examining the contents of historical query logs to extract pairs of queries and corresponding user selected links (i.e., “

query/link pairs”

) returned by individual search histories recorded in those logs;

sorting the extracted query/link pairs in order of aggregate user selection volume associated with each query/link pair to construct a set of sorted query/link pairs; and

adding sorted query/link pairs to the query cache, beginning with the query/link pair having the highest aggregate volume then sequentially selecting the query/link pair having the next highest aggregate volume, until the query cache reaches a desired size.

19. The computer-readable hardware storage device of claim 17 wherein a specific community of mobile communications devices determined to correspond to a predetermined demographic group is used to construct at least one of the query caches.