Semantic relationship-based location description parsing

• US 8,682,646 B2
• Filed: 06/04/2008
• Issued: 03/25/2014
• Est. Priority Date: 06/04/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Li, Jin, Yang, Guang, Peng, Shuang, Qian, Zhenyu
• Primary Examiner(s): Saint Cyr, Leonard
• Application Number:
  US12/132,623
• Publication Number:
  US 20090306961A1
• Time in Patent Office: 2,120 Days
• Field of Search: 704 4- 10
• 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 performed on a computing device, the method comprising:

extracting, based on grammatical rules, location keywords from a location description; and

checking for a semantic relationship among the extracted location keywords to derive a valid semantic meaning of the location description, the checking configured for further deriving;

a) a spatial part-of relationship between two locations represented by the location keywords extracted from the location description, where a first of the two locations as indicated by a first of the extracted location keywords is a part of a second of the two locations as indicated by a second of the extracted location keywords,

b) a spatial near-by relationship between the two locations represented by the location keywords extracted from the location description, where the first of the two locations as indicated by the first of the extracted location keywords is located proximate to the second of the two locations as indicated by the second of the extracted location keywords, and

c) a spatial intersects relationship between the two locations represented by the location keywords extracted from the location description, where the first of the two locations as indicated by the first of the extracted location keywords intersects the second of the two locations as indicated by the second of the extracted location keywords.

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. The method of claim 1 where the extracting further comprises extracting semantic relationship attributes that are associated with the location keywords.

7. The method of claim 1 where the extracted location keywords share a valid spatial relationship.

8. A system comprising at least one computing device and at least one module that are together configured for performing actions comprising:

extracting, based on grammatical rules, location keywords from a location description; and

checking for a semantic relationship among the extracted location keywords to derive a valid semantic meaning of the location description, the checking configured for further deriving;

a) a spatial part-of relationship between two locations represented by the location keywords extracted from the location description, where a first of the two locations as indicated by a first of the extracted location keywords is a part of a second of the two locations as indicated by a second of the extracted location keywords,

b) a spatial near-by relationship between the two locations represented by the location keywords extracted from the location description, where the first of the two locations as indicated by the first of the extracted location keywords is located proximate to the second of the two locations as indicated by the second of the extracted location keywords, and

c) a spatial intersects relationship between the two locations represented by the location keywords extracted from the location description, where the first of the two locations as indicated by the first of the extracted location keywords intersects the second of the two locations as indicated by the second of the extracted location keywords.

9. The system of claim 8 where the checking comprises verifying the semantic relationship against semantic relationship attributes associated with each of the location keywords in the location description.

10. The system of claim 9 where the semantic relationship attributes are pre-calculated in advance of the semantic verification.

11. The system of claim 8 where the grammatical rules are implemented by one or more of tokenization technologies, pattern matching technologies, or dictionary-driven technologies.

12. The system of claim 8, the actions further comprising implementing a ranking system for calculating a rank score for the location description using the semantic relationship.

13. The system of claim 8 where the extracting further comprises extracting semantic relationship attributes that are associated with the location keywords.

14. The system of claim 8 where the extracted location keywords share a valid spatial relationship.

15. At least one computer storage device storing modules that, when utilized by a computing device, cause the computing device to perform actions comprising:

extracting, based on grammatical rules, location keywords from a location description; and

checking for a semantic relationship among the extracted location keywords to derive a valid semantic meaning of the location description, the checking configured for further deriving;

a) a spatial part-of relationship between two locations represented by the location keywords extracted from the location description, where a first of the two locations as indicated by a first of the extracted location keywords is a part of a second of the two locations as indicated by a second of the extracted location keywords,

b) a spatial near-by relationship between the two locations represented by the location keywords extracted from the location description, where the first of the two locations as indicated by the first of the extracted location keywords is located proximate to the second of the two locations as indicated by the second of the extracted location keywords, and

c) a spatial intersects relationship between the two locations represented by the location keywords extracted from the location description, where the first of the two locations as indicated by the first of the extracted location keywords intersects the second of the two locations as indicated by the second of the extracted location keywords.

16. The at least one computer storage device of claim 15 where the checking comprises verifying the semantic relationship against semantic relationship attributes associated with each of the location keywords in the location description.

17. The at least one computer storage device of claim 16 where the semantic relationship attributes are pre-calculated in advance of the semantic verification.

18. The at least one computer storage device of claim 15, the actions further comprising implementing a ranking system for calculating a rank score for the location description using the semantic relationship.

19. The at least one computer storage device of claim 15 where the extracting further comprises extracting semantic relationship attributes that are associated with the location keywords.

20. The at least one computer storage device of claim 15 where the extracted location keywords share a valid spatial relationship.