Indexing and caching strategy for local queries

• US 7,634,465 B2
• Filed: 07/28/2006
• Issued: 12/15/2009
• Est. Priority Date: 10/04/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kumar, Girish, Sareen, Gaurav, Zou, Qinghua
• Primary Examiner(s): Ali; Mohammad
• Assistant Examiner(s): Hocker; John P
• Application Number:
  US11/460,807
• Publication Number:
  US 20070078848A1
• Time in Patent Office: 1,236 Days
• Field of Search: 707 1- 10
• US Class Current: 1/1
• CPC Class Codes: G06T 3/4038 Image mosaicing, e.g. composing plane images from plane sub-images
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

The claimed subject matter relates to a computer-implemented architecture that can, at a high level, store query results in a location-independent manner in order to facilitate caching of local results. To store query results in a location-independent manner such that cached results to location-based queries can be useful, the architecture can further include a mechanism for encoding a surface or area (e.g., the earth) based upon document density rather than geography. The encoding mechanism can also organize an inverted index so that no join operation is required to return valid results to a location-based query. The architecture can also include a mechanism for determining when previously cached results are adequate to satisfy a query.

Claims

1. A computer-implemented system that facilitates caching of local results for location-based queries, comprising:

a cache with a plurality of bags stored therein,

wherein each respective bag stores results of a previous location-based query in a location-independent manner while still preserving geographic location information associated with the previous location-based query,

wherein each respective bag is associated with a location-independent key that relates to a search string of the previous location-based query that returned the results stored in the bag, and

wherein the results stored in each respective bag are documents that include the location-independent key and are ranked in order based upon at least one of criteria of the previous location-based query or a document ID; and

a search component that;

receives a location-based query,

generates a location-independent search string key by removing geographic location information from the received location-based query while still preserving the geographic location information,

selects a subset of the plurality of bags in the cache in which the location-independent key associated with each respective bag matches the generated location-independent search-string key,

selects a best bag from the selected subset of bags that stores the best available results for the received query by comparing the preserved geographic location information associated with each of the bags in the selected subset of bags to the preserved geographic location information of the received location-based query and identifying as the best bag the bag associated with a geographic location nearest to the geographic location associated with the received query,

and returns a subset of results stored in the best bag when the best bag meets a threshold, even if the geographic location associated with the received location-based query is not an exact match with the geographic location associated with the best bag.

2. The system of claim 1, wherein the documents are ranked in order based upon criteria of the previous location-based query, and wherein the criteria is at least one of coordinates, distance, reputation or price.

3. The system of claim 1, wherein the search component determines whether the best bag satisfies a threshold.

4. The system of claim 3, wherein if the best bag satisfies the threshold, it is likely that there are a sufficient number of results in the best bag to satisfy the location-based query.

5. The system of claim 3, wherein the search component, in response to the location-based query, returns the subset of the results stored in the best bag if the threshold is satisfied.

6. The system of claim 5, wherein the subset of the results is re-ranked based upon criteria of the location-based query.

7. The system of claim 3, further comprising a data store, wherein the search component, in response to the location-based query, returns back-end results from the data store if the threshold is not satisfied.

8. The system of claim 7, wherein the back-end results are stored in a bag in the cache.

9. The system of claim 1, further comprising:

an interpolation component that;

graphs a first circle centered at a point P₁ with a radius, R₁, which is the distance from P₁ to an Nth document, and an area S₁,

wherein point P₁ represents the geographic location associated with the previous query whose results are stored in the best bag,

wherein N is the number of documents stored in the best bag, and

wherein the N documents are ordered 1 through N;

graphs a second circle centered at a point P₂ with a radius R₂, which is the distance from P₂ to an Mth document, and an area S₂,

wherein point P₂ represents the geographic location associated with the query received by the search component,

wherein M is the number of documents in a subset of the N documents stored in the best bag that meet criteria of the query, and

wherein the M documents are ordered 1 through M; and

determines an area of overlap, S₃,

wherein the search component determines if the M documents are adequate to satisfy the query by comparing a ratio based in part on the area of overlap, S₃, to a threshold, and

wherein the search component returns the M documents as a result of the received query when the M documents are determined to be adequate to satisfy the query.

10. The system of claim 9, wherein the radius, R₁ is a distance to the Nth document in terms of the criteria, and wherein the radius, R₂ is a distance to the Mth document in terms of the criteria.

11. The system of claim 9, wherein the area of overlap, S₃, is an intersection of S₁ and S₂, and wherein the ratio is S₃/S₂.

12. The system of claim 9, wherein the M documents satisfy the query when the ratio is greater than or equal to the threshold.

13. The system of claim 9, wherein the threshold is 0.75.

14. The system of claim 9, further comprising an intelligence component that dynamically sets the threshold.

15. The system of claim 9, wherein the criteria is at least one of coordinates, distance, reputation, price, religious requirements, allergy requirements, or a user preference.

16. The system of claim 9, wherein the search component re-orders the 1 through M documents based upon a respective distance from P₂.