Density sampling map data

• US 10,074,027 B2
• Filed: 09/08/2014
• Issued: 09/11/2018
• Est. Priority Date: 09/08/2014
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Watts, Michael Marcel William, Cohen, Erez David
• Primary Examiner(s): Summers, Geoffrey E
• Application Number:
  US14/480,451
• Publication Number:
  US 20160070983A1
• Time in Patent Office: 1,464 Days
• Field of Search: 382113, 382305
• CPC Class Codes: G01C 21/3679 Retrieval, searching and output of POI information, e.g. hotels, restaurants, shops, filling stations, parking facilities G01C21/3611 takes precedence
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

Sampling data is disclosed. A region of a map to be rendered is determined. It is determined that a first subregion is included in the region. Data points associated with subregions in a neighborhood of the first subregion are analyzed to determine a regional density of points. Data points associated with the first subregion are sampled based on the regional density of points.

Claims

1. A non-transitory machine readable medium storing a program for sampling data points in a map region, the program executable by at least one processor of a device, the program comprising sets of instructions for:

receiving, over a network connection, a request for data points from a first device;

determining a first region of a map to be rendered based on the request received over the network connection;

identifying a first plurality of data points associated with the first region;

indexing the first plurality of data points by assigning a random number to each data point in the first plurality of data points;

determining a set of second regions in a neighborhood of the first region;

identifying a second plurality of data points associated with the set of second regions;

applying a weight to each data point in the second plurality of data points, wherein more weight is applied to data points in a region that is closer to the first region than a region that is farther from the first region;

identifying a regional density of data points by;

analyzing the first plurality of data points and the second plurality of data points and determining a weighted total area of the neighborhood and a weighted total number of data points in the neighborhood based in part on the weights applied to the second plurality of data points and multiplying a desired density by the weighted total area of the neighborhood and dividing by the weighted total number of data points in the neighborhood;

selecting a subset of the first plurality of data points associated with the first region to be rendered based on the identified regional density of data points and the random number assigned to each data point in the first plurality of data points; and

transmitting the subset of the first plurality of data points over the network connection to the first device.

2. The non-transitory machine readable medium of claim 1, wherein the identified regional density comprises a sampling rate to be applied to the first plurality of data points.

3. The non-transitory machine readable medium of claim 2, wherein the set of instructions for selecting the subset comprises a set of instructions for applying the sampling rate to data points of the first plurality of data points, for which, random number is within a certain range of random numbers.

4. The non-transitory machine readable medium of claim 1, wherein the program further comprises a set of instructions for, before selecting the subset, sorting the first plurality of data points based on the random number assigned to each data point in the first plurality of data points.

5. The non-transitory machine readable medium of claim 1, wherein the device is a second device, wherein the program further comprises sets of instructions for:

receiving, from a first device, a request for the first plurality of data points to be displayed on the map region on a display screen of the first device; and

providing the subset of the first plurality of data points instead of the first plurality of data points to the first device, wherein the first device displays the subset of the first plurality of data points on the map region.

6. The non-transitory machine readable medium of claim 5, wherein the first device does not display the set of second regions.

7. The non-transitory machine readable medium of claim 5, wherein the program further comprises a set of instructions for selecting a subset of data points for each region in the set of second regions, wherein the set of instructions for providing the subset of the first plurality of data points further comprises a set of instructions for providing other subsets of data points for the set of second regions.

8. The non-transitory machine readable medium of claim 7, wherein the first device caches the other subsets of data points in order to display when a request for such is received.

9. The non-transitory machine readable medium of claim 1, wherein the set of instructions for determining the region of the map to be rendered further comprises a set of instructions for determining that the set of second regions are not to be rendered.

10. The non-transitory machine readable medium of claim 1, wherein the regional density of data points comprises a sampling rate that identifies a percentage of the first plurality of data points.

11. A method for sampling data points in a map region, the method comprising:

receiving at a processor, over a network connection, a request for data points from a first device;

determining, by the processor, a first subregion of a region of a map to be rendered based on the request received over the network connection;

identifying, by the processor, a first plurality of data points associated with the first subregion;

determining, by the processor, a set of subregions in a neighborhood of the first subregion;

identifying, by the processor, a second plurality of data points associated with the set of subregions;

applying, by the processor, a weight to each data point in the second plurality of data points, wherein more weight is applied to data points in a subregion that is closer to the first subregion than a subregion that is farther from the first subregion;

using the processor to identify a regional density of data points by analyzing the first plurality of data points and the second plurality of data points and determining a weighted total area of the neighborhood and a weighted total number of data points in the neighborhood based in part on the weights applied to the second plurality of data points and multiplying a desired density by the weighted total area of the neighborhood and dividing by the weighted total number of data points in the neighborhood;

selecting a subset of the first plurality of data points associated with the region to be rendered based on the identified regional density of data points; and

transmitting the subset of the first plurality of data points over the network connection to the first device.

12. The method of claim 11 further comprising determining that the set of subregions is not to be rendered with the region of the map to be rendered.

13. The method of claim 11, wherein the desired density comprises a desired baseline number of data points to render per unit area.

14. The method of claim 11, wherein every subregion in the set of subregions is adjacent to the first subregion.

15. The method of claim 11, wherein at least one subregion in the set of subregions is not adjacent to the first subregion.

16. The method of claim 11 further comprising, before selecting the subset:

assigning a random number to each data point in the first plurality of data points; and

ordering each data point in the first plurality of data points based on the assigned random number.