Systems, methods, and computer-readable media for validating addresses

• US 10,311,756 B1
• Filed: 06/28/2013
• Issued: 06/04/2019
• Est. Priority Date: 06/28/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Poppen, Richard Frederick
• Primary Examiner(s): Fleischer, Mark A
• Application Number:
  US13/930,968
• Time in Patent Office: 2,167 Days
• CPC Class Codes: G09B 29/006 Representation of non-cartographic information on maps, e.g. population distribution, wind direction, radiation levels, air and sea routes

Abstract

Systems, methods, and computer-readable media for validating addresses of a settlement are provided. An address validation model for a settlement is generated from an address numbering system inferred from observed addresses located in the settlement, based on the assumption that a most settlements use a regular addressing scheme. The address validation model has a first axis and a second axis having headings determined from are generated by determining known address points and headings to matched points. A mapping is determined between the coordinates of the first axis and the address points and between the coordinates of the second axis and the address points. The address validation model having the mapping is used to validate addresses for the settlement. Invalid addresses may be flagged for further review by an operator.

Claims

1. A computer-implemented method for validating addresses of a settlement, comprising:

obtaining, by one or more processors from a server, address data that specifies a plurality of addresses located in the settlement and observed manually or automatically, each of the plurality of observed addresses having an address number;

for each of the plurality of observed addresses;

selecting, by the one or more processors from among the plurality of observed addresses, a matched observed address within a certain fixed radius of the observed address, when a difference in address numbers between the observed address and the matched observed address is not greater than a minimum address number threshold, and

determining, by the one or more processors, a directional heading from the observed address to the matched observed address, to generate a respective directional heading for each of the plurality of observed addresses;

using a distribution of the generated directional headings for the plurality of observed addresses, identifying (i) a first axis and a second axis such that respective address numbers for at least some of the plurality of observed addresses correspond to coordinates along the first axis or the second axis, (ii) a respective scale to be applied to the first axis and the second axis to provide the coordinates along the first axis or the second axis, wherein the first axis, the second axis, and the respective scales define components of an address validation model;

receiving, by the one or more processors, an address to be tested;

applying, by the one or more processors, the address validation model to the address to be tested to determine whether the address fits the address validation model; and

generating an indication of whether the address likely contains an error when the address does not fit the address validation model.

2. The computer-implemented method of claim 1, further comprising:

for each of the plurality of observed addresses, discarding a street name and converting the observed address into a point.

3. The computer-implemented method of claim 2, wherein the plurality of observed addresses includes an address range, and wherein converting the address range to a point includes determining a midpoint of the address range.

4. The method of claim 2, further comprising:

for each of the plurality of points, (i) associating the point with the first axis if the directional heading generated for the point is not greater than a heading threshold from the first axis or with the second axis if the directional heading generated for the point is greater than the heading threshold from the second axis, or (ii) discarding the point if the directional heading generated for the point is greater than the heading threshold from both the first axis and the second axis;

for each of the plurality of points associated with one of the axis, assigning a coordinate to the point along the axis with which the point is associated; and

generating a mapping between the address numbers of the plurality of observed addresses and the first and second axis.

5. The method of claim 4, further comprising applying a least squares line fit to the points associated with the first axis based on the assigned coordinates and the address numbers.

6. The method of claim 2, wherein the plurality of observed addresses includes a road segment, and wherein converting the road segment to a point includes selecting a point halfway down an arc length of the road segment.

7. The computer-implemented method of claim 1, wherein using the distribution of the generated directional headings to identify the first axis and the second axis comprises:

applying a modulo 180 degrees operation to each of the determined directional headings to generate a histogram for the plurality of observed addresses;

identifying a first peak and a second peak in the histogram;

determining the heading of the first axis from a center of the first peak; and

determining the heading of the second axis from a center of the second peak.

8. The computer-implemented method of claim 1, wherein the settlement comprises a city.

9. A non-transitory tangible computer-readable storage medium having executable computer code stored thereon for validating addresses of settlement, the code comprising a set of instructions that causes one or more processors to perform a method comprising:

obtaining, by one or more processors from a server, address data that specifies a plurality of addresses located in the settlement and observed manually or automatically, each of the plurality of observed addresses having an address number;

for each of the plurality of observed addresses;

selecting, by the one or more processors from among the plurality of observed addresses, a matched observed address within a certain fixed radius of the observed address, when a difference in address numbers between the observed address and the matched observed address is not greater than a minimum address number threshold, and

determining, by the one or more processors, a directional heading from the observed address to the matched observed address, to generate a respective directional heading for each of the plurality of observed addresses;

using a distribution of the generated directional headings for the plurality of observed addresses, identifying (i) a first axis and a second axis such that respective address numbers for at least some of the plurality of observed addresses correspond to coordinates along the first axis or the second axis, (ii) a respective scale to be applied to the first axis and the second axis to provide the coordinates along the first axis or the second axis, wherein the first axis, the second axis, and the respective scales define components of an address validation model;

receiving, by the one or more processors, an address to be tested;

applying, by the one or more processors, the address validation model to the address to be tested to determine whether the address fits the address validation model; and

generating an indication of whether the address likely contains an error when the address does not fit the address validation model.

10. The non-transitory tangible computer-readable storage medium of claim 9, the method further comprising:

for each of the plurality of observed addresses, discarding a street name and converting the observed address into a point.

11. The non-transitory tangible computer-readable storage medium of claim 10, wherein the plurality of observed addresses includes an address range, and wherein converting the address range to a point includes determining a midpoint of the address range.

12. The non-transitory tangible computer-readable storage medium of claim 10, the method further comprising:

for each of the plurality of points, (i) associating the point with the first axis if the directional heading generated for the point is not greater than a heading threshold from the first axis or with the second axis if the directional heading generated for the point is not greater than the heading threshold from the second axis, or (ii) discarding the point if the directional heading generated for the point is greater than the heading threshold from both the first axis and the second axis;

for each of the plurality of points associated with one of the axis, assigning a coordinate to the point along the axis with which the point is associated; and

generating a mapping between the address numbers of the plurality of observed addresses and the first and second axis.

13. The non-transitory tangible computer-readable storage medium of claim 12, further comprising applying a least squares line fit to the points associated with the first axis based on the assigned coordinates and the address numbers.

14. The non-transitory tangible computer-readable storage medium of claim 10, wherein the plurality of observed addresses includes a road segment, and wherein converting the road segment to a point includes selecting a point halfway down an arc length of the road segment.

15. The non-transitory tangible computer-readable storage medium of claim 9, wherein using the distribution of the generated directional headings to identify the first axis and the second axis comprises:

applying a modulo 180 degrees operation to each of the determined directional headings to generate a histogram for the plurality of observed addresses;

identifying a first peak and a second peak in the histogram;

determining the heading of the first axis from a center of the first peak; and

determining the heading of the second axis from a center of the second peak.

16. The non-transitory tangible computer-readable storage medium of claim 9, wherein the settlement comprises a city.

17. A system for validating addresses of a settlement, the system comprising:

one or more processors;

a tangible non-transitory memory accessible by the one or more processors, the memory having computer code stored thereon, the code comprising a set of instructions that causes one or more processors to perform a method comprising;

obtaining, by one or more processors from a server, address data that specifies a plurality of addresses located in the settlement and observed manually or automatically, each of the plurality of observed addresses having an address number;

for each of the plurality of observed addresses;

selecting, by the one or more processors from among the plurality of observed addresses, a matched observed address within a certain fixed radius of the observed address, when a difference in address numbers between the observed address and the matched observed address is not greater than a minimum address number threshold, and

determining, by the one or more processors, a directional heading from the observed address to the matched observed address, to generate a respective directional heading for each of the plurality of observed addresses,

using a distribution of the generated directional headings for the plurality of observed addresses, identifying (i) a first axis and a second axis such that respective address numbers for at least some of the plurality of observed addresses correspond to coordinates along the first axis or the second axis, (ii) a respective scale to be applied to the first axis and the second axis to provide the coordinates along the first axis or the second axis, wherein the first axis, the second axis, and the respective scales define components of an address validation model;

receiving, by the one or more processors, an address to be tested;

applying, by the one or more processors, the address validation model to the address to be tested to determine whether the address fits the address validation model; and

generating an indication of whether the address likely contains an error when the address does not fit the address validation model.

18. The system of claim 17, the method further comprising:

for each of the plurality of observed addresses, discarding a street name and converting the observed address into a point.

19. The system of claim 18, wherein the plurality of observed addresses includes an address range, and wherein converting the address range to a point includes determining a midpoint of the address range.

20. The system of claim 18, wherein the method further comprises:

for each of the plurality of points, (i) associating the point with the first axis if the directional heading generated for the point is not greater than a heading threshold from the first axis or with the second axis if the directional heading generated for the point is not greater than the heading threshold from the second axis, or (ii) discarding the point if the directional heading generated for the point is greater than the heading threshold from both the first axis and the second axis;

for each of the plurality of points associated with one of the axis, assigning a coordinate to the point along the axis with which the point is associated; and

generating a mapping between the address numbers of the plurality of observed addresses and the first and second axis.

21. The system of claim 20, the method further comprising applying a least squares line fit to the points associated with the first axis based on the assigned coordinates and the address numbers.

22. The system of claim 18, wherein the plurality of observed addresses includes a road segment, and wherein converting the road segment to a point includes selecting a point halfway down an arc length of the road segment.

23. The system of claim 17, wherein using the distribution of the generated directional headings to identify the first axis and the second axis comprises:

applying a modulo 180 degrees operation to each of the determined directional headings to generate a histogram for the plurality of observed addresses;

identifying a first peak and a second peak in the histogram;

determining the heading of the first axis from a center of the first peak; and

determining the heading of the second axis from a center of the second peak.

24. The system of claim 17, wherein the settlement comprises a city.