CROSS LINGUAL LOCATION SEARCH

• US 20090326914A1
• Filed: 06/25/2008
• Published: 12/31/2009
• Est. Priority Date: 06/25/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Sengar, Vibhuti Singh, Joshi, Tanuja Abhay, Khurana, Udayan, Kellner, Tobias W. M., Kumaran, Arumugam, Joy, Joseph M.
• Granted Patent: US 8,364,462 B2
• Time in Patent Office: Days
• US Class Current: 704/3
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/3337 Translation of the query language, e.g. Chinese to English
• CPC Class Codes: G06F 40/129 Handling non-Latin characters, e.g. kana-to-kanji conversion
• CPC Class Codes: G06F 40/263 Language identification
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 40/53 Processing of non-Latin text kana-to-kanji conversion G06F40/129; vowelisation G06F40/232

Abstract

A cross-lingual location search uses a combination of translation and transliteration of query tokens to develop a set of candidate matches for further searching. A query is broken up into individual tokens (e.g. address parts) and a list of transliterations and/or translations for each token is developed. The translated and transliterated results are keyed against a spatial database using both literal database keys and transliterated database keys. Matches from the resulting searches are selected when a spatial overlap, or constraint, occurs among subsequences of the query tokens.

Claims

1. A method of selecting candidate matches for a geocoding process, comprising:

receiving a query;

parsing the query into tokens;

detecting the language of the token;

performing a transliteration on each token to give one or more corresponding transliterated token candidates;

comparing each transliterated token sequence against a name attribute of a spatial database;

retaining each transliterated token sequence that has a geometric overlap in the spatial database with another transliterated token;

selecting candidate matches for the geocoding process from the retained transliterated token sequence with a common geometric overlap; and

storing the selected candidate matches in a computer-readable storage medium.

2. The method of claim 1, further comprising:

comparing each token with a language-specific translation dictionary; and

translating each token into a translated token when found in a language-specific translation dictionary.

3. The method of claim 2, further comprising:

abstracting each transliterated token to generate an A(T(q)) token;

comparing each A(T(q)) token against the name attribute of the abstracted spatial database.

4. The method of claim 1, further comprising:

generating a language-specific translation dictionary of geocoder terms.

5. The method of claim 1, further comprising:

generating a transliteration dictionary of geocoder terms.

6. The method of claim 1, further comprising ranking each member of the group of transliterated tokens that have the common geometric overlap in the spatial database.

7. The method of claim 1, further comprising, performing a language identification for each token.

8. The method of claim 1, further comprising abstracting each corresponding transliterated token to a phonetic token;

9. The method of claim 1, further comprising:

transliterating the name attribute of the spatial database before comparing with the transliterated token.

10. A method of determining a candidate match for a query, comprising:

transliterating each name entry in a spatial region database;

receiving the geocoding query;

parsing the query into tokens;

determining a language for each token;

transliterating each token into one or more candidate transliterated tokens;

determining approximate matches between the transliterated tokens and the database name entries;

determining spatial overlaps among matches between the database tokens and the transliterated name entries;

selecting the candidate matches from among those tokens having a spatial overlap; and

storing the candidate matches on a computer-readable storage medium.

11. The method of claim 10, further comprising:

translating each token that is a common noun;

comparing the translated common noun tokens to name entries from the spatial region database.

12. A computer-readable storage medium having computer-executable instructions for performing a method of presenting a qualified search term presented in one language to a geographic search engine database in another language, the method comprising:

receiving a query;

determining a first language for at least one subsequence of the query;

converting the query to at least a first phonetic subsequence and second phonetic subsequence;

determining a first spatial region corresponding the first subsequence;

determining a second spatial region corresponding to the second subsequence;

determining when the first and second spatial regions overlap; and

presenting a composite result that corresponds to the overlapping spatial region and the names of the overlapping results.

13. The computer-readable storage medium of claim 12, wherein converting the query comprises using a language-specific phonetic conversion tool.

14. The computer-readable storage medium of claim 12, wherein the first spatial region corresponds to a collection of geographic regions having a common phonetic root.

15. The computer-readable storage medium of claim 12, wherein the second spatial region corresponds to a collection of geographic regions having a common phonetic root.

16. The computer-readable storage medium of claim 12, wherein determining when the first and second spatial regions overlap comprises comparing each geographic region corresponding to both the first and second tokens.

17. The computer-readable storage medium of claim 12, further comprising building a database having records with a common name, a phonetic name, and one or more geographic regions corresponding to the common name.

18. The computer-readable storage medium of claim 12, wherein converting the query to at least a first and second phonetic subsequence comprises using machine learning based transliteration to generate candidate transliteration terms associated with the query.

19. The computer-readable storage medium of claim 12, wherein converting the query to at least a first and second phonetic subsequence comprises searching a language-specific database for translation terms associated with the query.

20. The computer-readable storage medium of claim 12, further comprising determining a second language for at least another query subsequence.