Detecting Spatial Outliers in a Location Entity Dataset

• US 20100179759A1
• Filed: 01/14/2009
• Published: 07/15/2010
• Est. Priority Date: 01/14/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Feng, Jianqiao, Ma, Wei-Ying, Xie, Xing, Zheng, Yu
• Granted Patent: US 9,063,226 B2
• Time in Patent Office: Days
• US Class Current: 701/300
• CPC Class Codes: G01S 19/40 Correcting position, velocity or attitude

Abstract

Disclosed herein are one or more embodiments that arrange a plurality of location entities into a hierarchy of location descriptors. One or more of the disclosed embodiments may determine whether one of the location entities is a spatial outlier based at least in part on presence of one or more other location entities within a predetermined distance of the one location entity. Also, the other location entities and the one location entity may share a location descriptor.

Claims

1. A method comprising:

arranging, by a computing device, a plurality of location entities into a hierarchy of location descriptors; and

determining, by the computing device, whether one of the location entities is a spatial outlier based at least in part on presence of one or more other location entities within a predetermined distance of the one location entity, the other location entities and the one location entity sharing a location descriptor.

2. The method of claim 1, wherein the location entities comprise yellow page entities and point of interest entities.

3. The method of claim 1, wherein at least one of the location entities comprises a location name, a location address, and a global positioning system (GPS) position.

4. The method of claim 1 further comprising segmenting address fields of the location entities into location descriptors.

5. The method of claim 4, wherein the segmenting comprises segmenting based on commas and/or other characters indicating a separation between two or more terms.

6. The method of claim 4, wherein the segmenting comprises segmenting based at least in part on one or more frameworks and/or dictionaries.

7. The method of claim 6, wherein the framework is a tree structure of location descriptors generated from a published description of a geographic area.

8. The method of claim 6, wherein the dictionaries include either a collection of breaker words used to separate location descriptors or a collection of categories derived from name fields of the location entities.

9. The method of claim 1, wherein the arranging further comprises inserting a descriptor of each location entity derived from an address field of each location entity as a leaf node in a tree of location descriptors.

10. The method of claim 9, wherein the arranging further comprises determining that at least two leaf nodes refer to a same instance if the nodes share the same descriptor and if the same descriptor is shared by a number of descendant nodes of a same parent, the number exceeding a first threshold.

11. The method of claim 10, wherein the arranging further comprises combining the at least two leaf nodes, the combining including retaining one of the leaf node at a lowest level in the hierarchy in which a number of occurrences of the at least two leaf nodes exceeds a second threshold.

12. The method of claim 1, wherein the determining further comprises:

determining whether the number of other location entities within the predetermined distance of the one location entity exceeds a threshold; and

in response to determining that the number does not exceed the threshold, determining that the one location entity is a spatial outlier.

13. The method of claim 1, wherein the one location entity is a yellow page entity and the other location entities are point of interest entities, and the determining further comprises:

determining whether at least one of the point of interest entities is present within a predetermined distance of the yellow page entity; and

in response to determining that no point of interest entity is present within the predetermined distance, determining that the yellow page entity is a spatial outlier.

14. The method of claim 1 further comprising, in response to determining that the one location entity is a spatial outlier, deleting the one location entity.

15. An article of manufacture comprising:

a storage medium; and

a plurality of executable instructions stored on the storage medium which, when executed by a computing device, perform operations including;

arranging a plurality of location entities into a hierarchy of location descriptors, the location entities including yellow page entities and point of interest entities; and

determining whether one of the yellow page entities is a spatial outlier based at least in part on presence of at least one of the point of interest entities within a predetermined distance of the one yellow page entity, the one point of interest entity and the one yellow page entity sharing a location descriptor.

16. The article of claim 15, wherein the arranging further comprises inserting a descriptor of each location entity derived from an address field of each location entity as a leaf node in a tree of location descriptors.

17. The article of claim 15, wherein the determining further comprises, in response to determining that no point of interest entity is present within the predetermined distance, determining that the yellow page entity is a spatial outlier.

18. The article of claim 17, wherein the executable instructions, when executed by the computing device, further perform operations including, in response to determining that the yellow page entity is a spatial outlier, deleting the yellow page entity.

19. A system comprising:

a processor; and

logic configured to be executed by the processor to perform operations including;

segmenting address fields of a plurality of location entities into location descriptors, the segmenting including either or both of;

segmenting based on commas and/or other characters indicating a separation between two or more terms; and

segmenting based at least in part on one or more frameworks and/or dictionaries;

arranging the location entities into a hierarchy of location descriptors, the arranging including;

inserting a descriptor of each location entity derived from an address field of each location entity as a leaf node in a tree of location descriptors;

determining that at least two leaf nodes refer to a same instance if the nodes share the same descriptor and if the same descriptor is shared by a number of descendant nodes of a same parent, the number exceeding a first threshold; and

combining the at least two leaf nodes, the combining including retaining one of the leaf node at a lowest level in the hierarchy in which a number of occurrences of the at least two leaf nodes exceeds a second threshold;

determining whether one of the location entities is a spatial outlier based at least in part on presence of one or more other location entities within a predetermined distance of the one location entity, the other location entities and the one location entity sharing a location descriptor; and

in response to determining that the one location entity is a spatial outlier, deleting the one location entity.

20. The system of claim 19, wherein determining whether the one location entity is a spatial outlier further comprises:

determining whether the number of other location entities within the predetermined distance of the one location entity exceeds a threshold; and

in response to determining that the number does not exceed the threshold, determining that the one location entity is a spatial outlier.