Indexing documents according to geographical relevance

• US 7,801,897 B2
• Filed: 12/30/2004
• Issued: 09/21/2010
• Est. Priority Date: 12/30/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Egnor, Daniel
• Primary Examiner(s): Wong; Don
• Assistant Examiner(s): Hwa; Shyue Jiunn
• Application Number:
  US11/024,790
• Publication Number:
  US 20060149774A1
• Time in Patent Office: 2,091 Days
• Field of Search: None
• US Class Current: 707/741
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries

Abstract

A local search engine efficiently indexes documents relevant to a geographical area by indexing, for each document, multiple location identifiers that collectively define an aggregate geographic region. When creating the index, the search engine may determine a set of geographical areas surrounding a geographical area relevant to a document and associate references to the set of geographical areas with the document index.

Claims

1. A method, comprising:

determining, by one or more processors in one or more server devices, one, of a plurality of geographical areas in a grid, associated with a document;

determining, by one or more processors in one or more server devices, a subset, of the plurality of geographical areas in the grid, each of the subset being at least partially within a circle of a particular radius from the one, of the plurality of geographical areas, associated with the document; and

indexing, by one or more processors in one or more server devices, the document to include the one, of the plurality of geographical areas, associated with the document and the subset of the plurality of geographical areas.

2. The method of claim 1, where the one, of the plurality of geographical areas, associated with the document and the subset of the plurality of geographical areas are specified by location identifiers.

3. The method of claim 2, where the location identifiers include labels for nodes in a hierarchical triangular mesh.

4. The method of claim 1, where the document is a business listing.

5. The method of claim 1, where the document is a geographically relevant web document.

6. The method of claim 1, where the subset of the plurality of geographical areas are referenced by location identifiers, and the method further comprising:

determining a plurality of sets of location identifiers, each set of location identifiers being associated with a respective one of the subset of the plurality of the plurality of geographical areas.

7. A computer device comprising:

means for storing a document index;

means for dividing a geographical region into a plurality of distinct regions;

means for determining a geographical location associated with a document;

means for identifying one of the plurality of distinct regions in which the geographical location is located;

means for identifying other regions of the plurality of distinct regions surrounding the one, of the plurality of distinct regions, in which the geographical location is located, the other regions being at least partially within a circle of a particular radius from the one of the plurality of distinct regions in which the geographical location is located; and

means for indexing the document to include, in the document index, a reference to the one of the plurality of distinct regions and the other regions of the plurality of distinct regions.

8. A method, comprising:

storing, by one or more processors in one or more server devices, a document index;

determining, by one or more server devices, a geographical location associated with a document;

dividing, by one or more processors in one or more server devices, a geographical region into a plurality of distinct regions;

identifying, by one or more processors in one or more server devices, one of the plurality of distinct regions in which the geographical location is located;

identifying, by one or more processors in one or more server devices, other regions of the plurality of distinct regions that are at least partially within a circle of a particular radius from the one of the plurality of distinct regions in which the geographical location is located;

associating, by one or more processors in one or more server devices, references to the one of the plurality of distinct regions and the other regions of the plurality of distinct regions with the document; and

indexing, by one or more processors in one or more server devices, the document with the associated references.

9. The method of claim 8, further comprising:

determining the associated references to be location identifiers that correspond to nodes in a hierarchical triangular mesh.

10. The method of claim 8, where the plurality of distinct regions are non-overlapping.

11. The method of claim 8, further comprising:

indexing the document by inserting the associated references in an index as if the references were terms in the document.

12. The method of claim 8, where the document is a business listing.

13. The method of claim 8, where the document is a geographically relevant web document.

14. A computer-readable memory device containing programming instructions for execution by a processor, the computer-readable memory device comprising;

programming instructions for dividing a geographical region into a plurality of distinct regions;

programming instructions for identifying a document that is relevant to a geographical location;

programming instructions for identifying one of the plurality of distinct regions in which the geographical location is located;

programming instructions for identifying other regions, of the plurality of distinct regions, surrounding the one of the plurality of distinct regions in which the geographical location is located, the other regions being at least partially within a circle of particular distance from the one of the plurality of distinct regions; and

programming instructions for associating references to the one of the plurality of distinct regions and the other regions of the plurality of distinct regions with an index that includes terms from the document.

15. A method comprising:

storing, by one or more processors in one or more server devices, a document index;

determining, by one or more processors in one or more server devices, a geographical location associated with a document;

dividing, by one or more processors in one or more server devices, a geographical region into a plurality of distinct regions;

identifying, by one or more processors in one or more server devices, one of the plurality of distinct regions in which the geographical location is located;

identifying, by one or more processors in one or more server devices, other regions of the plurality, of distinct regions surrounding the one of the plurality of distinct regions in which the geographical location is located, the other regions being at least partially within a circle of a particular distance from the one of the plurality of distinct regions;

indexing, by one or more processors in one or more server devices, the document to include a reference to the one of the plurality of distinct regions and the other regions of the plurality of distinct regions in the document index;

receiving, by one or more processors in one or more server devices, a search query associated with the geographical region;

determining, by one or more processors in one or more server devices, a location identifier associated with the one of the plurality of distinct regions;

determining, by one or more processors in one or more server devices, a plurality of location identifiers associated with the other regions of the plurality of distinct regions; and

performing, by one or more processors in one or more server devices, a search for documents relevant to the search query based on a comparison of the search query, the location identifier, and the plurality of location identifiers to the document index.

16. The method of claim 15, further comprising:

transmitting relevant documents, determined by the search, to a user.

17. The method of claim 15, where the location identifier references a node in a hierarchical triangular mesh.

18. The method of claim 15, where receiving the search query includes receiving search terms and geographically descriptive terms entered by a user.

19. The method of claim 15, further comprising:

receiving an indication of a desired search region;

determining a difference between the desired search region and a previously indexed search region;

determining a set of location identifiers based on the difference; and

performing the search based on the search query and the set of location identifiers.