# US 2020/0004843 A1 · Geocode interpolation

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2020/0004843 A1
- Document ID: US20200004843A1
- Status: Published application
- Kind: A1
- Application number: 16/022,448
- Filed: 2018-06-28
- Published: 2020-01-02
- Earliest claimed: 2018-06-28
- Assignees: Microsoft Technology Licensing, LLC
- Applicants: Microsoft Technology Licensing, LLC
- Inventors: Kumarswamy P. VALEGEREPURA; Kartik KUKREJA; Wei WU; Florin TEODORESCU; William M. GANNON; Jing LI
- Web page: https://patentgrep.com/patent/US20200004843A1

## CPC

- G06F 16/29: Geographical information databases
- G01C 21/20: Instruments for performing navigational calculations (G01C21/24, G01C21/26 take precedence)
- G01C 21/3605: {Destination input or retrieval}
- G06F 16/9537: Spatial or temporal dependent retrieval, e.g. spatiotemporal queries
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S)

## Abstract

The present concepts relate to interpolating a location of an address. In one example, an address index may be generated, which contains rooftop addresses and corresponding percentage values representing the percentage distances along street primitives at which those rooftop addresses are located based on rooftop locations of the rooftop addresses. Upon receiving a query address, whose rooftop location is not known, the address index can be referenced to identify two surrounding rooftop addresses between which the query address lies, and an estimated geographical location of the query address may be calculated by interpolating between the rooftop locations of the two surrounding rooftop addresses.

## Claims

### Claim 1

A method, comprising:
receiving a query address;
determining whether the query address is found in an address index;
upon determining that the query address is not found in the address index, identifying a first rooftop address and a second rooftop address in the address index between which the query address lies; and
calculating an estimated location for the query address by interpolating between a first rooftop location associated with the first rooftop address and a second rooftop location associated with the second rooftop address.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
matching rooftop addresses from address data to corresponding street primitives in map data; and
assigning the rooftop addresses to location points in the map data along the corresponding street primitives.

### Claim 3 (depends on 2)

The method of claim 2, further comprising:
determining which sides of the corresponding street primitives the rooftop addresses are situated.

### Claim 4 (depends on 3)

The method of claim 3, further comprising:
calculating, for the rooftop addresses in the address data, percentage values indicating percentage distances along the corresponding street primitives at which the assigned location points are situated.

### Claim 5 (depends on 4)

The method of claim 4, further comprising:
generating the address index having the rooftop addresses and the percentage values.

### Claim 6 (depends on 5)

The method of claim 5, further comprising:
grouping the rooftop addresses in the address index based at least on the corresponding street primitives and the sides of the corresponding street primitives on which the rooftop addresses are situated.

### Claim 7 (depends on 5)

The method of claim 5, further comprising:
excluding one or more outlier addresses in the address data from the address index.

### Claim 8 (depends on 1)

The method of claim 1, wherein the query address is a postal address including one or more of: street number, street direction, street name, city, state, zip code, and country.

### Claim 9 (depends on 1)

The method of claim 1, wherein the estimated location for the query address is a geographical location represented as a latitude-longitude coordinate.

### Claim 10 (depends on 1)

The method of claim 1, wherein the identifying of the first rooftop address and the second rooftop address in the address index includes:
identifying an address group of rooftop addresses in the address index having the same street name and the same parity of street numbers as the query address.

### Claim 11 (depends on 1)

The method of claim 1, wherein the interpolating uses linear regression between the first rooftop location and the second rooftop location along a street primitive associated with the first rooftop address and the second rooftop address based at least on a first street number in the first rooftop address, a second street number in the second rooftop address, and a query street number in the query address.

### Claim 12 (depends on 1)

The method of claim 1, wherein the interpolating is based at least on a first percentage value stored in association with the first rooftop address and a second percentage value stored in association with the second rooftop address in the address index.

### Claim 13

A system, comprising:
an address index including rooftop addresses and associated percentage values indicating percentage distances along street primitives at which the rooftop addresses are located;
one or more processors; and
at least one computer-readable storage medium storing computer readable instructions which, when executed by the one or more processors, cause the one or more processors to perform:
receiving a query address that is not found in the address index;
identifying, in the address index, a first rooftop address and a second rooftop address between which the query address is located; and
calculating an estimated location for the query address based at least on interpolating between a first rooftop location associated with the first rooftop address and a second rooftop location associated with the second rooftop address.

### Claim 14 (depends on 13)

The system of claim 13, wherein the computer-readable instructions further cause the one or more processors to perform:
assigning the rooftop addresses from address data to corresponding street primitives in map data;
determining which sides of the corresponding street primitives the rooftop addresses are situated; and
calculating the percentage values associated with the rooftop addresses.

### Claim 15 (depends on 13)

The system of claim 13, wherein:
a first street number in the first rooftop address is lower than and closest to a query street number in the query address among street numbers included in the rooftop addresses that have the same street name and the same street number parity as the query address; and
a second street number in the second rooftop address is higher than and closest to the query street number among the street numbers included in the rooftop addresses that have the same street name and the same street number parity as the query address.

### Claim 16 (depends on 13)

The system of claim 13, wherein:
a query street name in the query address matches a first street name in the first rooftop address and a second street name in the second rooftop address;
a parity of a query street number in the query address matches a parity of a first street number in the first rooftop address and a parity of a second street number in the second rooftop address;
the first street number is lower than the query street number; and
the second street number is higher than the query street number.

### Claim 17 (depends on 13)

The system of claim 13, wherein:
a first street number in the first rooftop address is closest to a query street number in the query address among street numbers that are lower than the query street number and are included in the rooftop addresses in the address index having a street name that matches a query street name in the query address; and
a second street number in the second rooftop address is closest to the query street number among street numbers that are higher than the query street number and included in the rooftop addresses in the address index having a street name that matches the query street name.

### Claim 18 (depends on 13)

The system of claim 13, wherein the interpolating uses a linear regression based at least on:
a first street number in the first rooftop address;
the first rooftop location;
a second street number in the second rooftop address;
the second rooftop location; and
a query street number in the query address.

### Claim 19 (depends on 13)

The system of claim 13, wherein the computer-readable instructions further cause the one or more processors to perform:
calculating an estimated offset by which the estimated location is situated from a corresponding street primitive based at least on a first offset by which the first rooftop location is situated from the corresponding street primitive and a second offset by which the second rooftop location is situated from the corresponding street primitive.

### Claim 20

A system, comprising:
an address index having rooftop addresses from address data and associated percentage values indicating percentage distances along corresponding street primitives at which the rooftop addresses are located; and
a geocode component for:
receiving a query address that does not have an associated percentage value stored in the address index;
identifying a first rooftop address and a second rooftop address in the address index, the first rooftop address and the second rooftop address having the same street name and the same street number parity as the query address, the first rooftop address having a first street number that is lower than a query street number in the query address, the second rooftop address having a second street number that is higher than the query street number; and
calculating an estimated location for the query address by interpolating based at least on a first percentage value associated with the first rooftop address, the first street number, a second percentage value associated with the second rooftop address, the second street number, and the query street number.
