INDEXING AND CACHING STRATEGY FOR LOCAL QUERIES

• US 20070078848A1
• Filed: 07/28/2006
• Published: 04/05/2007
• 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
• Granted Patent: US 7,634,465 B2
• Time in Patent Office: Days
• 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, each respective bag stores results of a previous location-based query in a location-independent manner, each respective bag is associated with a key that relates to a search string of the previous location-based query; and

a search component that receives a location-based query, removes location information from the query, and selects a subset of the plurality of bags in which a search string of the location-based query matches the key for the subset of bags.

2. The system of claim 1, the results stored in each respective bag are documents that include the key, the documents are ranked in order based upon at least one of criteria of the previous location-based query and a document ID.

3. The system of claim 2, the criteria is at least one of coordinates, distance, reputation, and price.

4. The system of claim 1, the search component selects a best bag from the subset of bags.

5. The system of claim 4, the best bag has a location of the previous location-based query, P₁, that is nearest to a location of the location-based query, P₂,

6. The system of claim 5, the search component determines whether the best bag satisfies a threshold.

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

8. The system of claim 7, the subset of the results is re-ranked based upon criteria of the location-based query.

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

10. The system of claim 9, the back-end results are stored in a bag in the cache.

11. A computer-implemented system that determines if cached results are adequate to satisfy a query, comprising:

a cache with N documents, where N is a positive integer, the documents are ordered 1-N based upon criteria of a previous query, a value of the criteria of the previous query is P₁;

a search component that receives a query based upon the criteria with a value of P₂, the search component determines a subset of the N documents, 1-M, that satisfy the query, where M is a positive integer; and

an interpolation component that graphs a first circle centered at P₁ with a radius, R₁, and an area, S₁, the interpolation component graphs a second circle centered at P₂ with a radius, R₂, and an area, S₂, the interpolation component determines an area of overlap, S₃, and the search component determines if the documents 1-M are adequate to satisfy the query by comparing a ratio to a threshold.

12. The system of claim 11, the radius, R₁ is a distance to the Nth document in terms of the criteria and the radius, R2 is a distance to the Mth document in terms of the criteria.

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

14. The system of claim 11, the documents 1-M satisfy the query when the ratio is greater than or equal to the threshold.

15. The system of claim 11, the threshold is about 0.75.

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

17. The system of claim 11, the criteria is at least one of coordinates, distance, reputation, price, religious requirements, allergy requirements, and a user preference.

18. The system of claim 11, the search component re-orders the 1-M results based upon a distance from P₂.

19. A computer-implemented method for encoding a data store in a location-independent manner such that no join operation is required to retrieve results for a location-based query, comprising:

organizing geographic regions of a surface into blocks such that each block includes a substantially similar magnitude of documents, each of the blocks having a corresponding block code;

sorting the block codes in alpha-numeric order;

assigning a chunk ID to each of the respective sorted block codes;

appending a document ID to a chunk ID for producing a global document ID;

sorting a plurality of documents by global document ID; and

associating the plurality of documents with an inverted index for returning the global document ID of a document that includes a keyword.

20. The method of claim 19, further comprising:

receiving a location-based query with a location and the keyword;

utilizing the inverted index for retrieving a list of global document IDs relating to documents that include the keyword; and

performing a binary search for the chunk ID associated with the location.