SEMANTIC RELATIONSHIP-BASED LOCATION DESCRIPTION PARSING

• US 20090306961A1
• Filed: 06/04/2008
• Published: 12/10/2009
• Est. Priority Date: 06/04/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Qian, Zhenyu, Peng, Shuang, Yang, Guang, Li, Jin
• Granted Patent: US 8,682,646 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

An automated arrangement for parsing location descriptions is provided in which semantic verification is integrated into a parsing process to reduce the generation of false results. The semantic verification involves checking up to three semantic relationships between keywords (i.e., syntactical components) parsed from the location description in a tokenization process to determine if a tokenization result is valid. The semantic relationships include: a) a spatial “part-of” relationship between location keywords; b) a spatial “near-by” relationship; and, c) a spatial “intersect” relationship. The semantic relationships between particular locations may be pre-calculated and stored as extended vocabulary to enable the semantic verification to occur early in the parsing process to thus increase overall parsing efficiency. The results of the parsing are sorted based on a rank score that is derived using the semantic relationships between the locations.

Claims

1. A method for performing semantic verification of location keywords extracted from a user query, the method comprising the steps of:

extracting the location keywords from a location description formulated by a user through the application of grammatical rules by which the location description is composed; and

checking a semantic relationship among the location keywords to derive a semantic meaning for the location description that is sensible, the semantic relationship including at least one of

a) a spatial part-of relationship between two locations represented by respective location keywords in the location description,

b) a spatial near-by relationship between two locations represented by respective location keywords in the location description, and

c) a spatial intersects relationship between two locations represented by respective location keywords in the location description.

2. The method of claim 1 in which the checking comprises verifying the semantic relationship against semantic relationship attributes associated with each of the location keywords in the location description.

3. The method of claim 2 in which the semantic relationship attributes are pre-calculated in advance of the semantic verification.

4. The method of claim 1 in which the grammatical rules are implemented by one or more of tokenization technologies, pattern matching technologies, or dictionary-driven technologies.

5. The method of claim 1 including a further step of implementing a ranking system for calculating a rank score for the location description using the semantic relationship.

6. A method for parsing a location description to generate parsed results, the method comprising the steps of:

applying stored patterns to the location description to break the location description into syntactic trunks;

tokenizing the syntactic trunks into location keywords using location vocabulary;

checking one or more semantic relationships between the location keywords, to verify whether the locations represented by the location keywords are nearby, intersect, or are part of each other, the verifying utilizing pre-calculated semantic relationship attributes that are associated with each of the location keywords; and

pruning one or more keywords from the location description if a semantic relationship is found to be invalid through the step of checking.

7. The method of claim 6 including a further step of identifying a primary location based on the checked one or more semantic relationships.

8. The method of claim 7 including a further step of calculating a score from the location keywords and the checked one or more semantic relationships.

9. The method of claim 8 including a further step of sorting parsed results based on the score.

10. The method of claim 9 in which the location keywords comprise one or more of street number, street name, landmark name, point-of-interest name, neighborhood name, city name, country name, or description of direction and distance.

11. The method of claim 10 in which the pre-calculated semantic relationship attributes are calculated by a semantic relationship module and integrated with a location vocabulary.

12. The method of claim 11 in which the score is calculated using a product of a linguistic probability of a location keyword when it stands alone and a linguistic probability of two location keywords when they stand together.

13. The method of claim 12 in which the tokenizing and verifying are performed in an integrated manner.

14. A location description parsing system, comprising:

a location pattern module containing patterns usable for matching with a location description formulated by a user to break the location description into syntactic trunks;

a location vocabulary module containing vocabulary usable for tokenizing the syntactic trunks to identify location keywords and retrieve semantic relationship attributes associated with each location keyword; and

a semantic relationship module arranged for calculating the semantic relationship attributes and exposing the semantic relationship attributes to a semantic verification process by which tokenization results are semantically verified.

15. The location description parsing system of claim 14 in which the vocabulary is one of common vocabulary or domain-specific vocabulary.

16. The location description parsing system of claim 14 in which the semantic relationship attributes are pre-calculated in advance of the tokenizing.

17. The location description parsing system of claim 14 as adapted for use with a geocoding system in which the location description comprises a geo-query and the geocoding system outputs semantic relationship attributes as latitude and longitude coordinates.

18. The location description parsing system of claim 14 in which the location keywords include at least one of address, landmark name, street intersection description, or location description using direction and distance.

19. The location description parsing system of claim 14 as adapted for use with a location detection system in which the location description comprises any arbitrary location description and the location detection system includes at least one of content crawling, analysis, or data mining tool configured for using parsed results and the semantic relationship attributes when collecting data from web-based resources.

20. The location description parsing system of claim 14 as adapted for use with a local search system in which the location description comprises any arbitrary query having local content and the location vocabulary module and semantics relationship module are each configured with local content categories.