Pattern-retaining method for displaying large volumes of geographic based data using statistical depopulation

• US 9,594,773 B2
• Filed: 05/20/2014
• Issued: 03/14/2017
• Est. Priority Date: 05/20/2014
• Status: Active Grant

• Current Assignee: Vesmir, Inc.
• Original Assignee: Vesmir, Inc.
• Inventors: Herron, Dylan Scott
• Primary Examiner(s): Corrielus, Jean M
• Application Number:
  US14/283,047
• Publication Number:
  US 20150339320A1
• Time in Patent Office: 1,029 Days
• Field of Search: 707/722
• US Class Current: 1/1
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/904 Browsing; Visualisation therefor for navigating the web G06F16/954; browsing optimisation for the web G06F16/957

Abstract

Disclosed herein are various embodiments of a method for graphically displaying large volumes of data points on a display in an intuitive and readily understandable manner using statistical depopulation by defining multiple regionation levels using a combination of location based data and density based data with a random selection process to add more data points as more detail is requested while retaining the same overall pattern as when all points are displayed. Also disclosed are various embodiments for using the geographic bounds of a screen display to determine the appropriate level of data to display. The embodiments described ensure that the user is not overwhelmed by too much data on screen for areas with multiple data points, while ensuring that areas with few data points are also represented on the display.

Claims

1. A pattern-retaining method for allocating large volumes of geographic data points to regionation level data sets for providing displays of data points at user controlled zoom levels that are representative of the data distribution and density comprising:

determining the desired number of data cells;

retrieving a requested data set;

randomly selecting from the requested data set one data point from each cell that contains at least one data point to represent that cell and placing the selected data points in location handled data set S_P;

removing the data points in location handled data set S_P from the requested data set;

placing the remaining data points from the requested data set in density handled data set S_D;

allocating data points from location handled data set S_P and density handled data set S_D to regionation levels using a random selection process which further comprises;

creating a table of N regionation levels and specifying the number of data points to be placed in each regionation level and;

creating regionation levels 1 through N by repeating the following steps;

i. for any regionation level n where n is greater than 1, placing all the data points from the regionation level (n−

1) into regionation level n;

ii. if any data points remain in location handled data set S_P, moving randomly chosen data points from location handled data set S_P to regionation level n until the specified number of data points for regionation level n is reached, or no more data points are available in location handled data set S_P;

iii. if more data points are required to reach the specified number of data points in regionation level n, moving randomly chosen points from density handled data set S_D to regionation level n until the specified number of data points for regionation level n is reached, or the process of adding data is terminated.

2. The method of claim 1 wherein the process of adding data is terminated when no more data points remain in density handled data set S_D, and the maximum regionation level N is set to the current value of n.

3. The method of claim 1 wherein the process of adding data is terminated when the number of data points remaining in density handled data set S_D is less than a predetermined percentage of the number of data points required in the next regionation level, all of those data points are moved to the next regionation level (n+1), and the maximum regionation level N is set to the current value of (n+1).

4. The method of claim 1 wherein allocating data points from location handled data set S_P and density handled data set S_D to regionation levels using a random selection process further comprises:

using an algorithm to specify the number of data points to be placed in each regionation level and

creating regionation levels 1 through N by repeating the following steps;

i. for any regionation level n where n is greater than 1, placing all the data points from the regionation level (n−

1) into regionation level n;

ii. if any data points remain in location handled data set S_P, moving randomly chosen data points from location handled data set S_P to regionation level n until the specified number of data points for regionation level n is reached, or no more data points are available in location handled data set S_P;

iii. if more data points are required to reach the specified number of data points in regionation level n, moving randomly chosen data points from density handled data set S_D to regionation level n until the specified number of data points for regionation level n is reached, or the process of adding data is terminated.

5. The method of claim 4 wherein the process of adding data is terminated when no more data points remain in density handled data set S_D, and the maximum regionation level N is set to the current value of N.

6. The method of claim 4 wherein the process of adding data is terminated when the number of data points remaining in density handled data set S_D is less than a predetermined percentage of the number of data points required in the next regionation level, all of those data points are moved to the next regionation level (n+1), and the maximum regionation level N is set to (n+1).

7. The method of claim 4 wherein the algorithm to specify the number of data points to be placed in each regionation level is that the number of data points in any regionation level greater than level 1 is double the number of data points in the previous regionation level.

8. The method of claim 4 wherein the algorithm to specify the number of data points to be placed in each regionation level is that the number of data points in any regionation level greater than level 1 is ten times the number of data points in the previous regionation level.

9. A pattern-retaining method for displaying large volumes of geographic data points on a map providing displays at user controlled zoom levels that are representative of the data distribution and density using regionation data sets comprising:

retrieving a requested data set;

allocating data points from the requested data set to a series of regionation levels by;

(a) randomly selecting from the requested data set one data point from each cell that contains at least one data point to represent that cell and placing the selected data points in location handled data set S_P;

(b) removing the data points in location handled data set S_P from the requested data set;

(c) placing the remaining data points from the requested data set in density handled data set S_D;

(d) creating a table of N regionation levels and specifying the number of data points to be placed in each regionation level

(e) creating regionation levels 1 through N by repeating the following steps;

i. for any regionation level n where n is greater than 1, placing all the data points from the regionation level (n−

1) into regionation level n;

ii. if any data points remain in location handled data set S_P, moving randomly chosen data points from location handled data set S_P to regionation level n until the specified number of data points for regionation level n is reached, or no more data points are available in location handled data set S_P;

iii. if more data points are required to reach the specified number of data points in regionation level n, moving randomly chosen points from density handled data set S_D to regionation level n until the specified number of data points for regionation level n is reached, or the process of adding data is terminated;

specifying the maximum number of data points to be displayed on screen;

determining the bounds of the geographic area displayed on screen;

determining the number of data points in each regionation level that fall within the bounds of the geographic area displayed on screen;

determining the regionation level N with the maximum number of data points that fall within the bounds of the geographic area displayed on screen wherein the number of data points in the regionation level is less than the specified the maximum number of data points to be displayed on screen;

displaying the data points in regionation level N on the screen and

adjusting the geographic bounds and the corresponding regionation level and displaying the corresponding data from the appropriate regionation level as the user pans and zooms the screen display.

10. A pattern-retaining method for displaying large volumes of geographic data points on a map providing displays at user controlled zoom levels that are representative of the data distribution and density using regionation data sets comprising:

determining the desired number of data cells;

retrieving a requested data set;

randomly selecting from the requested data set one data point from each cell that contains at least one data point to represent that cell and placing the selected data points in location handled data set S_P;

removing the data points in location handled data set S_P from the requested data set;

placing the remaining data points from the requested data set in density handled data set S_D;

allocating data points from location handled data set S_P and density handled data set S_D to regionation levels using a random selection process;

specifying the maximum number of data points to be displayed on screen;

determining the bounds of the geographic area displayed on screen;

determining the number of data points in each regionation level that fall within the bounds of the geographic area displayed on screen;

determining the regionation level N with the maximum number of data points that fall within the bounds of the geographic area displayed on screen wherein the number of data points in the regionation level is less than the specified the maximum number of data points to be displayed on screen;

displaying the data points in regionation level N on the screen and

adjusting the geographic bounds and the corresponding regionation level and displaying the corresponding data from the appropriate regionation level as the user pans and zooms the screen display.

11. The method of claim 10 wherein allocating data points from location handled data set S_P and density handled data set S_D to regionation levels further comprises:

creating a table of N regionation levels and specifying the number of data points to be placed in each regionation level and

creating regionation levels 1 through N by repeating the following steps;

i. for any regionation level n where n is greater than 1, placing all the data points from the regionation level (n−

1) into regionation level n;

ii. if any data points remain in location handled data set S_P, moving randomly chosen data points from location handled data set S_P to regionation level n until the specified number of data points for regionation level n is reached, or no more data points are available in location handled data set S_P;

iii. if more data points are required to reach the specified number of data points in regionation level n, moving randomly chosen points from density handled data set S_D to regionation level n until the specified number of data points for regionation level n is reached, or the process of adding data is terminated.

12. The method of claim 11 wherein the process of adding data is terminated when no more data points remain in density handled data set S_D, and the maximum regionation level N is set to the current value of n.

13. The method of claim 11 wherein the process of adding data is terminated when the number of data points remaining in density handled data set S_D is less than a predetermined percentage of the number of data points required in the next regionation level, all of those data points are moved to the next regionation level (n+1), and the maximum regionation level N is set to the current value of (n+1).

14. The method of claim 10 wherein allocating data points from location handled data set S_P and density handled data set S_D to regionation levels further comprises:

using an algorithm to specify the number of data points to be placed in each regionation level and

creating regionation levels 1 through N by repeating the following steps;

i. for any regionation level n where n is greater than 1, placing all the data points from the regionation level (n−

1) into regionation level n;

ii. if any data points remain in location handled data set S_P, moving randomly chosen data points from location handled data set S_P to regionation level n until the specified number of data points for regionation level n is reached, or no more data points are available in location handled data set S_P;

iii. if more data points are required to reach the specified number of data points in regionation level n, moving randomly chosen data points from density handled data set S_D to regionation level n until the specified number of data points for regionation level n is reached, or the process of adding data is terminated.

15. The method of claim 14 wherein the process of adding data is terminated when no more data points remain in density handled data set S_D, and the maximum regionation level N is set to the current value of N.

16. The method of claim 14 wherein the process of adding data is terminated when the number of data points remaining in density handled data set S_D is less than a predetermined percentage of the number of data points required in the next regionation level, all of those data points are moved to the next regionation level (n+1), and the maximum regionation level N is set to (n+1).

17. The method of claim 14 wherein the algorithm to specify the number of data points to be placed in each regionation level is that the number of data points in any regionation level greater than level 1 is double the number of data points in the previous regionation level.

18. The method of claim 14 wherein the algorithm to specify the number of data points to be placed in each regionation level is that the number of data points in any regionation level greater than level 1 is ten times the number of data points in the previous regionation level.