Detecting spatial outliers in a location entity dataset

• US 9,063,226 B2
• Filed: 01/14/2009
• Issued: 06/23/2015
• Est. Priority Date: 01/14/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Zheng, Yu, Feng, Jianqiao, Xie, Xing, Ma, Wei-Ying
• Primary Examiner(s): HAQ, NAEEM U
• Application Number:
  US12/353,940
• Publication Number:
  US 20100179759A1
• Time in Patent Office: 2,351 Days
• Field of Search: 700/300, 382/113, 701/300
• US Class Current: 1/1
• 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, wherein individual ones of the location entities comprise global positioning system (GPS) coordinates captured by a GPS device;

storing the plurality of location entities on a location search server, the location search server being remotely located from the computing device;

determining, by the computing device, whether one location entity of the plurality of location entities is a spatial outlier based on determining whether a number of other location entities within a predetermined distance of the one location entity exceeds a threshold number, the other location entities and the one location entity sharing a location descriptor;

in response to determining that the one location entity is the spatial outlier, deleting, by the computing device, the one location entity; and

sending an update to the location search server such that the plurality of location entities on the location search server reflects the deletion of the spatial outlier.

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

3. The method of claim 1, wherein at least one of the plurality of location entities comprises a location name, a location address, and a GPS position.

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

5. The method of claim 4, wherein the segmenting comprises segmenting based on one or more of commas and 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 of a framework and a dictionary.

7. The method of claim 4, wherein the segmenting comprises segmenting based at least in part on one or more frameworks, and wherein the one or more frameworks is includes a tree structure of the location descriptors generated from a published description of a geographic area.

8. The method of claim 4, wherein the segmenting comprises segmenting based at least in part on one or more dictionaries, and wherein the one or more dictionaries include either a collection of breaker words used to separate location descriptors or a collection of categories derived from name fields of the plurality of location entities.

9. The method of claim 1, wherein the arranging further comprises inserting a descriptor of each of the plurality of location entities derived from an address field of each of the plurality of location entities as a leaf node in a tree of the 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 at least two leaf nodes share a 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 number.

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 at least two leaf nodes at a lowest level in the hierarchy in which a number of occurrences of the at least two leaf nodes exceeds a second threshold number.

12. The method of claim 1, wherein the one location entity is determined to be the spatial outlier based on the number of other location entities within the predetermined distance of the one location entity not exceeding the threshold number.

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 the spatial outlier.

14. An article of manufacture comprising:

a storage device; and

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

arranging a plurality of location entities into a hierarchy of location descriptors, the plurality of location entities including yellow page entities and point of interest entities, wherein individual ones of the location entities comprise global positioning system (GPS) coordinates captured by a GPS device;

storing the plurality of location entities on a location search server, the location search server being remotely located from the computing device;

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 of the yellow page entities, the at least one of the point of interest entities and the one of the yellow page entities sharing a location descriptor;

in response to determining that the one of the yellow page entities is the spatial outlier, deleting the one of the yellow page entities; and

sending an update to the location search server such that the plurality of location entities on the location search server reflects the deletion of the spatial outlier.

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

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

17. The article of claim 14, wherein at least one of the yellow page entities comprises a location name, a location address, and a GPS position.

18. The article of claim 14, wherein the operations further comprise segmenting address fields of the location entities into location descriptors.

19. A system comprising:

a processor of a computing device; and

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

sending a plurality of location entities to a location search server for storage on the location search server, wherein individual ones of the location entities comprise global positioning system (GPS) coordinates captured by a GPS device, and wherein the location search server is remotely located from the computing device;

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 plurality of location entities into a hierarchy of location descriptors, the arranging including;

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

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

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

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

in response to determining that the one of the plurality of location entities is the spatial outlier, deleting the one of the plurality of location entities; and

sending an update to the location search server such that the plurality of location entities on the location search server reflects the deletion of the spatial outlier.

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

in response to determining that the number of one or more other location entities within the predetermined distance of the one of the plurality of location entities does not exceed the third threshold number, determining that the one of the plurality of location entities is the spatial outlier.