DENSITY SAMPLING MAP DATA

• US 20160070983A1
• Filed: 09/08/2014
• Published: 03/10/2016
• Est. Priority Date: 09/08/2014
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Mapsense, Inc. (Apple Inc.)
• Inventors: Watts, Michael Marcel William, Cohen, Erez David
• Granted Patent: US 10,074,027 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 system for sampling, comprising:

a processor configured to;

determine a region of a map to be rendered;

determine that a first subregion is included in the region;

analyze data points associated with subregions in a neighborhood of the first subregion to determine a regional density of points; and

sample data points associated with the first subregion based on the regional density of points; and

a memory coupled to the processor and configured to provide the processor with instructions.

2. The system of claim 1, wherein the region of the map corresponds to a portion of the map to be displayed on a client device.

3. The system of claim 1, further comprising a communication interface configured to is provide sampled data points of the first subregion to a client device for rendering.

4. The system of claim 1, wherein the map is divided into subregions.

5. The system of claim 1, wherein the first subregion is associated with a data structure that includes entries corresponding to data points located within the first subregion.

6. The system of claim 5, wherein the data structure is ordered using a random value assigned to each data point entry of the data structure.

7. The system of claim 1, wherein the neighborhood of the first subregion includes the first subregion and one or more subregions located adjacent to the first subregion.

8. The system of claim 1, wherein analyzing the data points includes determining a total number of data points in the neighborhood of the first subregion.

9. The system of claim 1, wherein analyzing the data points includes determining a total number of data points in the neighborhood of the first subregion that match a search query.

10. The system of claim 1, wherein analyzing the data points includes determining a total area of the neighborhood of the first subregion.

11. The system of claim 1, wherein analyzing the data points includes determining a weighted total area of the neighborhood of the first subregion by summing together an area of each subregion of the neighborhood multiplied by a corresponding weight.

12. The system of claim 1, wherein analyzing the data points includes determining a desired density factor to be utilized to determine the regional density of points.

13. The system of claim 1, wherein the regional density of points is a sampling rate.

14. The system of claim 1, wherein determining the regional density of points includes multiplying a desired density by a total area of the neighborhood and dividing by a total number of data points in the neighborhood.

15. The system of claim 1, wherein determining the regional density of points includes multiplying a desired density by a weighted total area of the neighborhood and dividing by a weighted total number of data points in the neighborhood.

16. The system of claim 15, wherein a first weight assigned to a second subregion included in the neighborhood is based on a distance between the first subregion and the second subregion.

17. The system of claim 1, wherein sampling data points associated with the first subregion includes selecting a portion of the data points associated with the first subregion and an amount of the portion is indicated by the regional density of points.

18. The system of claim 1, wherein sampling data points associated with the first subregion based on the regional density of points includes selecting a portion of the data points associated with a predetermined random number that is within a range associated with the regional density of points.

19. A method for sampling, comprising:

determining a region of a map to be rendered;

determining that a first subregion is included in the region;

using a processor to analyze data points associated with subregions in a neighborhood of the first subregion to determine a regional density of points; and

sampling data points associated with the first subregion based on the regional density of points.

20. A computer program product for sampling, the computer program product being embodied in a tangible computer readable storage medium and comprising computer instructions for:

determining a region of a map to be rendered;

determining that a first subregion is included in the region;

analyzing data points associated with subregions in a neighborhood of the first subregion to determine a regional density of points; and

sampling data points associated with the first subregion based on the regional density of points.