Systems and methods for identifying outlying point of interest search results

• US 9,864,783 B1
• Filed: 12/02/2014
• Issued: 01/09/2018
• Est. Priority Date: 12/02/2014
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Mittleman, Jessa Deborah
• Primary Examiner(s): Fleurantin, Jean B
• Application Number:
  US14/558,025
• Time in Patent Office: 1,134 Days
• Field of Search: 707748, 707758
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/444 Spatial browsing, e.g. 2D maps, 3D or virtual spaces
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries

Abstract

Systems and methods for identifying and eliminating outlying point of interest search results to improve the readability of the mapped results are provided. One exemplary method includes obtaining, by one or more computing devices, a plurality of points of interest. Each point of interest has an associated location. The method includes determining, by the one or more computing devices, a distance score for each of the plurality of points of interest. The method includes determining, by the one or more computing devices, a distance ratio. The distance ratio compares the distance score associated with the point of interest having the distance score of greatest magnitude to the distance score associated with the point of interest having the distance score of second greatest magnitude.

Claims

1. A computer-implemented method for identifying an outlying point of interest search result, the method comprising:

Obtaining, by one or more computing devices, a plurality of points of interest, wherein each of the plurality of points of interest has an associated location;

determining, by the one or more computing devices, a distance score for each of the plurality of points of interest, wherein the distance score is associated with a distance between the respective point of interest relative to each of the other points of interest;

determining, by the one or more computing devices, a distance ratio, wherein the distance ratio compares the distance score associated with the point of interest having the distance score of greatest magnitude to the distance score associated with the point of interest having the distance score of second greatest magnitude;

determining, by the one or more computing devices, whether the distance ratio is greater than a threshold value;

identifying, by the one or more computing devices, a point of interest having the distance score of greatest magnitude as art outlier when a distance ratio is greater than the threshold value; and

providing, by the one or more computing devices, a viewport that is sized to include the plurality of points of interest without any identified outlier point of interest.

2. The method of claim 1, wherein obtaining, by the one or more computing devices, the plurality of points of interest comprises identifying, by the one or more computing devices, the plurality of points of interest in response to a search query received in one of a mapping application or a geographic information system.

3. The method of claim 1, wherein the location associated with each of the plurality of points of interest comprises a latitude and a longitude.

4. The method of claim 1, wherein the distance score for each point of interest comprises a sum of the distance between such point of interest and each of the other points of interest.

5. The method of claim 4, wherein the distance between each point of interest and each of the other points of interest comprises a linear Earth distance.

6. The method of claim 4, wherein the distance between each point of interest and each of the other points of interest comprises an L1 distance.

7. The method of claim 4, wherein the distance between each point of interest and each of the other points of interest comprises a distance capable of being driven.

8. The method of claim 1, wherein determining, by the one or more computing devices, the distance ratio comprises dividing, by the one or more computing devices, a distance score associated with a point of interest having a distance score of greatest magnitude by a distance score associated with a point of interest having a distance score of second greatest magnitude.

9. The method of claim 1, wherein determining, by the one or more computing devices, the distance ratio comprises:

ordering, by the one or more computing devices, the plurality of points of interest into a sequence from distance score of greatest magnitude to distance score of smallest magnitude; and

dividing, by the one or more computing devices, the distance score associated with the first sequential point of interest by the distance score associated with the second sequential point of interest to obtain the distance ratio.

10. The method of claim 1, wherein the threshold value comprises a constant value times the number of points of interest included in the plurality of points of interest having the 1 subtracted therefrom.

11. The method of claim 10, wherein the constant value is adjustable.

12. The method of claim 1, wherein identifying, by the one or more computing devices, a point of interest having a distance score of greatest magnitude as an outlier when the distance ratio is greater than the threshold value comprises discarding, by the one or more computing devices, a point of interest having a distance score of greatest magnitude from the plurality of points of interest when the distance ratio is greater than the threshold value, such that a second plurality of points of interest is formed.

13. The method of claim 1, further comprising retaining, by the one or more computing devices, a point of interest having a distance score of greatest magnitude when the distance ratio is less than the threshold value.

14. A computing system, comprising:

one or more processors; and

one or more memory devices, the one or more memory devices comprising computer-readable instructions that when executed by the one or more processors cause the one or more processors to perform operations, the operations comprising;

obtaining a plurality of points of interest, wherein each of the plurality of points of interest has an associated location;

determining a distance score for each of the plurality of points of interest, wherein the distance score is associated with a distance between the respective point of interest relative to each of the other points of interest;

determining a distance ratio, wherein the distance ratio compares the distance score associated with the point of interest having the distance score of greatest magnitude to the distance score associated with the point of interest having the distance score of second greatest magnitude;

determining whether the distance ratio is greater than a threshold value;

identifying, by the one or more computing devices, a point of interest having a distance score of greatest magnitude as an outlier when the distance ratio is greater than the threshold value; and

providing a viewport that is sized to include the plurality of points of interest without any identified outlier point of interest.

15. The computing system of claim 14, wherein determining the distance ratio comprises dividing, by the one or more computing devices, the distance score associated with a point of interest having a distance score of greatest magnitude by a distance score associated with a point of interest having a distance score of second greatest magnitude.

16. The computing system of claim 14, wherein the threshold value comprises a constant value times the number of points of interest included in the plurality of points of interest having the 1 subtracted therefrom.

17. The computing system of claim 14, wherein identifying a point of interest having a distance score of greatest magnitude as an outlier when the distance ratio is greater than the threshold value comprises discarding a point of interest having a distance score of greatest magnitude from the plurality of points of interest when the distance ratio is greater than the threshold value, such that a second plurality of points of interest is formed.

18. The computing system of claim 14, further comprising retaining a point of interest having a distance score of greatest magnitude when the distance ratio is less than the threshold value.

19. One or more non-transitory computer-readable media storing instructions that, when executed by one or more processors, cause the one or more processors to perform operations, the operations comprising:

obtaining a plurality of points of interest, wherein each of the plurality of points of interest has an associated location;

determining a distance score for each of the plurality of points of interest, wherein the distance score is associated with a distance between the respective point of interest relative to each of the other points of interest;

determining a distance ratio, wherein the distance ratio compares the distance score associated with the point of interest having the distance score of greatest magnitude to the distance score associated with the point of interest having the distance score of second greatest magnitude;

determining whether the distance ratio is greater than a threshold value;

identifying, by the one or more computing devices, a point of interest having a distance score of greatest magnitude as an outlier when the distance ratio is greater than the threshold value; and

providing a viewport that is sized to include the plurality of points of interest without any identified outlier point of interest.