Classification of ambiguous geographic references

• US 7,716,162 B2
• Filed: 12/30/2004
• Issued: 05/11/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,785
• Publication Number:
  US 20060149742A1
• Time in Patent Office: 1,958 Days
• Field of Search: None
• US Class Current: 707/724
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/31 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A location classifier generates location information based on textual strings in input text. The location information defines potential geographical relevance of the input text. In determining the location information, the location classifier may receive at least one geo-relevance profile associated with at least one string in the input text, obtain a combined geo-relevance profile for the document from the at least one geo-relevance profile, and determine geographical relevance of the input text based on the combined geo-relevance profile.

Claims

1. A method of determining a geographical relevance of a document, performed by one or more processors associated with one or more server devices, the method comprising:

generating, using a processor associated with the one or more server devices, a plurality of histograms associated with a plurality of respective strings in the document by comparing strings in the document to a pre-existing plurality of strings for which histograms were previously generated, where the plurality of histograms relates occurrences of strings to geographical regions;

generating, using a processor associated with the one or more server devices, a combined histogram for the document from the plurality of histograms by multiplying together values for each histogram of the plurality of histograms; and

identifying, using a processor associated with the one or more server devices, a geographical relevance of the document based on the combined histogram.

2. The method of claim 1, where identifying the geographical relevance of the document based on the combined histogram includes:

analyzing the combined histogram for peaks.

3. The method of claim 1, where one or more strings in the plurality of strings comprise a single term string.

4. The method of claim 1, where one or more strings in the plurality of strings comprise bi-grams.

5. The method of claim 1, where the document includes a web page.

6. The method of claim 1, where the document includes a search query.

7. A location classifier implemented within a computing device, comprising:

means for receiving input text;

a memory to store the input text;

means for locating strings within the input text that were previously determined to be geographically relevant;

means for comparing located strings in the input text to a pre-existing plurality of strings for which histograms were previously generated, where the histograms relate occurrences of strings to geographical regions;

means for combining the retrieved histograms, to form a combined histogram, by multiplying together values for each histogram of the retrieved histograms; and

means for determining whether the input text is geographically relevant based on the peaks of the combined histogram.

8. The location classifier of claim 7, where the plurality of histograms relate zip codes to a number of occurrences of a string in documents associated with a particular zip code.

9. A memory device containing programming instructions for execution by a processor, the memory device comprising:

programming instructions for generating a plurality of histograms associated with a respective plurality of strings in a document by examining the document to locate strings for the respective plurality of strings by comparing strings in the document to a pre-existing plurality of strings for which histograms were previously generated, the histograms defining a geographical relevance of the plurality of strings with respect to geographical regions;

programming instructions for combining the plurality of histograms to obtain a combined histogram for the document by multiplying together values for each histogram of the plurality of histograms; and

programming instructions for determining a geographical relevance of the document based on the combined histogram.

10. The memory device of claim 9, where the programming instructions for a determining geographical relevance of the document further includes:

programming instructions for analyzing the combined histogram for peaks.

11. The memory device of claim 9, where the strings include single term strings.

12. The memory device of claim 9, where the strings include bi-grams.

13. The memory device of claim 9, where the document includes a web page.

14. The memory device of claim 9, where the document includes a search query.

15. A method for generating a histogram for a string, performed by a server device, the method comprising:

determining, using a processor of the server device, a plurality of sections of training text in which each section of training text is associated with a geographical region;

accumulating, using the processor, occurrences of the string in the plurality of sections of training text when terms to a left or right of the string are different from previous instances of terms to the left or right of the string; and

generating, using the processor, the histogram based on the accumulated occurrences of the string, where the histogram relates the occurrences of the string to geographical regions.

16. The method of claim 15, where determining a plurality of sections of training text includes:

locating known geographic signals in a plurality of documents; and

selecting the sections of training text from those of the plurality of documents that include the known geographic signals.

17. The method of claim 15, where the documents include web documents.

18. The method of claim 15, further comprising:

normalizing the generated histogram based on a global distribution of geographical regions within the training text.

19. The method of claim 15, where the geographical regions are represented by zip codes.

20. The method of claim 15, further comprising:

saving the generated histogram for future use when the histogram includes statistically relevant peaks.

21. A device comprising:

a processor; and

a computer-readable memory coupled to the processor and containing instructions that when executed by the processor cause the processor to;

determine a plurality of sections of training text in which each section of training text is associated with a geographical region;

accumulate occurrences of a string in the plurality of sections of training text when terms to a left or right of the string are different from previous instances of the terms to the left or right of the string; and

generate a histogram that defines the geographical relevance of the string with respect to geographical regions based on the accumulated occurrences of the string.

22. The device of claim 21, further comprising analyzing the histogram for peaks.

23. The device of claim 21, where the string comprises a single term.

24. The device of claim 21, where the string comprises a bi-gram.

25. A method performed by one or more processors associated with one or more server devices, the method comprising:

examining, using a processor associated with the one or more server devices, a document to locate strings that were previously determined to have geographical relevance;

generating, using a processor associated with the one or more server devices, a plurality of histograms associated with the located strings, in the document, by comparing the located strings in the document to a pre-existing plurality of strings for which histograms were previously generated;

receiving, using a communication interface or an input device of the one or more server devices, the histograms associated with the strings, where the histograms relate occurrences of the strings to geographic regions;

obtaining, using a processor associated with the one or more server devices, a combined histogram for the document from the received histograms by multiplying values for each of the received histograms together;

analyzing, using a processor associated with the one or more server devices, the combined histogram for peaks; and

determining, using a processor associated with the one or more server devices, geographical relevance of the document based on whether peaks are present in the combined histogram.

26. The method of claim 25, further comprising normalizing the received histograms based on a global distribution of geographical regions within the training text.

27. The method of claim 25, where the strings comprise one of a single term or a bi-gram.

28. The method of claim 25, where the histograms relate zip codes to a number of occurrences of a string in documents associated with a particular zip code.