Geographical map-based visualization of big data

• US 10,157,219 B2
• Filed: 11/10/2014
• Issued: 12/18/2018
• Est. Priority Date: 11/10/2014
• Status: Active Grant

• Current Assignee: Dalian University of Technology
• Original Assignee: Dalian University of Technology
• Inventors: Wang, Xingyuan
• Primary Examiner(s): Saeed, Usmaan
• Assistant Examiner(s): Nafziger, David M
• Application Number:
  US14/891,386
• Publication Number:
  US 20160267171A1
• Time in Patent Office: 1,499 Days
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/24554 Unary operations; Data partitioning operations
• CPC Class Codes: G06F 16/26 Visual data mining; Browsing structured data
• CPC Class Codes: G06F 16/287 Visualization; Browsing

Abstract

Embodiments pertaining to techniques of geographical map-based visualization of big data are provided. In one aspect, a random sampling of a dataset may be divided into a plurality of partitions. Each partition of the plurality of partitions may be clustered to provide a plurality of data blocks, each of which may comprise a respective plurality of data items. A respective one or more representative points may be extracted from each data block of the plurality of data blocks to represent the respective data block. The respective one or more representative points for each of the data blocks may then be displayed.

Claims

1. A method, comprising:

performing, by one or more processors of one or more servers, a random sampling of a dataset to obtain a sample representative of the dataset;

dividing, by the one or more processors, the sample into a plurality of partitions;

clustering, by the one or more processors, each partition of the plurality of partitions to provide a plurality of data blocks, wherein each of the plurality of data blocks comprises a respective plurality of data items, and wherein the clustering comprises establishing a tree data structure having a plurality of hierarchical layers;

extracting, by the one or more processor, respective one or more representative points from each data block of the plurality of data blocks to represent the respective data blocks; and

displaying the respective one or more representative points for each of the data blocks, wherein the displaying comprises;

generating, by the one or more processor, a normal graph using a graphical representation of the tree data structure, by conducting two-dimensional normalization of one or more circles in the graphical representation;

generating, by the one or more processor, a contour map corresponding to a height of the normal graph;

transforming, by the one or more processor, each circle of the one or more circles into a polygon of one hundred sides, wherein vertexes of each polygon expands outward with a specific speed according to the height of the respective polygon on the contour map; and

generating, by the one or more processor, based on the contour map, a geographical map-based visualization of the dataset,

wherein the generating the geographical map-based visualization of the data set facilitates reduced requirement of resources, to process the datasets on a host device.

2. The method of claim 1, wherein the clustering further comprises clustering using a clustering using representatives (CURE) data clustering algorithm.

3. The method of claim 1, wherein each of the plurality of hierarchical layers includes one or more nodes, wherein each node of the one or more nodes have zero or more child node, and wherein each node contains a sum of data items of the respective zero or more child node thereof.

4. The method of claim 3, wherein

the graphical representation comprises the one or more circles for the one or more nodes of each layer of the plurality of hierarchical layers, and

wherein each circle of the one or more circles in the graphical representation corresponds to a respective two-dimensional distribution of data overlaying one or more two-dimensional distributions of data of one or more other circles.

5. The method of claim 1, wherein the displaying further comprises:

receiving a user input indicative of a number of layers of visualization; and

displaying the respective one or more representative points for each of the data blocks in the number of layers according to the user input.

6. The method of claim 1, wherein the displaying further comprises displaying the respective one or more representative points for each of the data blocks in a default number of layers.

7. The method of claim 1, wherein the displaying further comprises displaying the respective one or more representative points for each of the data blocks as the geographical map-based visualization of the dataset.

8. The method of claim 1, further comprising:

determining, for each data item of each data block of the plurality of data blocks, a degree of closeness between the each data item and other data items of the respective data block;

determining a clustering threshold based at least in part on the degrees of closeness between the data items of a given data block for at least one data block of the plurality of data blocks; and

determining, for at least two data items of the at least one data block, whether the at least two data items belong to a same class or different classes of data based at least in part on the clustering threshold.

9. The method of claim 1, further comprising:

receiving a user input indicative of a minimum threshold of a size of an amount of data contained in each of the data blocks for visualization.

10. A non-transitory computer-readable storage medium having stored thereon computer-executable instructions executable by one or more processors to perform or control performance of operations comprising:

perform operations related to cluster a random sampling of a dataset, wherein the cluster of the random sampling of the dataset comprises establishment of a tree data structure that have a plurality of hierarchical layers; and

display results of the performed operations as a geographical map-based visualization of the dataset, wherein the operations to display comprises at least one operation to;

generate a normal graph by use of a graphical representation of the tree data structure, by conducting two-dimensional normalization of one or more circles in the graphical representation;

generate a contour map that corresponds to a height of the normal graph;

transform each circle of the one or more circles into a polygon of one hundred sides, wherein vertexes of each polygon expands outward with a specific speed according to the height of the respective polygon on the contour map; and

generate, based on the contour map, the geographical map-based visualization of the dataset,

wherein the generation of the geographical map-based visualization of the data set facilitates reduced requirement of resources, to process the datasets on a host device.

11. The non-transitory computer-readable storage medium of claim 10, wherein to perform the operations related to cluster the random sampling of the dataset, comprises:

perform the random sampling of the dataset to obtain a sample representative of the dataset;

divide the sample into a plurality of partitions;

cluster each partition of the plurality of partitions to provide a plurality of data blocks, wherein each of the plurality of data blocks comprises a respective plurality of data items; and

extract respective one or more representative points from each data block of the plurality of data blocks to represent the respective data block,

wherein the display of the results further comprises display of the respective one or more representative points for each of the data blocks.

12. The non-transitory computer-readable storage medium of claim 10, wherein the operations to cluster comprises at least one operation to cluster using a clustering using representatives (CURE) data clustering algorithm.

13. The non-transitory computer-readable storage medium of claim 11, wherein each of the plurality of hierarchical layers includes one or more nodes, wherein each node of the one or more nodes have zero or more child node, and wherein each node contains a sum of data items of the respective zero or more child node thereof.

14. The non-transitory computer-readable storage medium of claim 13, wherein

the graphical representation comprises the one or more circles for the one or more nodes of each layer of the plurality of hierarchical layers, and

wherein each circle of the one or more circles in the graphical representation corresponds to a respective two-dimensional distribution of data overlaying one or more two-dimensional distributions of data of one or more other circles.

15. The non-transitory computer-readable storage medium of claim 11, wherein the operations to display further comprises at least one operation to:

receive a user input indicative of a number of layers of visualization; and

display the respective one or more representative points for each of the data blocks in the number of layers according to the user input.

16. The non-transitory computer-readable storage medium of claim 11, wherein the operations to display further comprises at least one operation to display the respective one or more representative points for each of the data blocks in a default number of layers.

17. The non-transitory computer-readable storage medium of claim 11, wherein the operations to display further comprises at least one operation to display the respective one or more representative points for each of the data blocks as the geographical map-based visualization.

18. The non-transitory computer-readable storage medium of claim 11, wherein the computer-executable instructions further comprise instructions that, in response to execution, cause the one or more processors to perform at least one operation to:

determine, for each data item of each data block of the plurality of data blocks, a degree of closeness between the each data item and other data items of the respective data block;

determine a clustering threshold based at least in part on the degrees of closeness between the data items of a given data block for at least one data block of the plurality of data blocks; and

determine, for at least two data items of the at least one data block, whether the at least two data items belong to a same class or different classes of data based at least in part on the clustering threshold.

19. The non-transitory computer-readable storage medium of claim 11, wherein the computer-executable instructions further comprise instructions that, in response to execution, cause the one or more processors to perform at least one operation to:

receive a user input indicative of a minimum threshold of a size of an amount of data contained in each of the data blocks for visualization.

20. An apparatus, comprising:

memory configured to store one or more instructions; and

one or more processors coupled to the memory, wherein the one or more processors are configured to execute the one or more instructions to perform or control performance of operations comprising;

perform a random sampling of a dataset to obtain a sample representative of the dataset;

divide the sample into a plurality of partitions;

cluster each partition of the plurality of partitions to provide a plurality of data blocks, wherein each of the plurality of data blocks comprises a respective plurality of data items, and wherein to cluster each partition of the plurality of partitions, the one or more processors are configured to establish a tree data structure that have a plurality of hierarchical layers;

extract respective one or more representative points from each data block of the plurality of data blocks to represent the respective data blocks; and

display the respective one or more representative points for each of the data blocks as a geographical map-based visualization of the dataset, wherein the operations to display comprises at least one operation to;

generate a normal graph, by use of a graphical representation of the tree data structure, by conducting two-dimensional normalization of one or more circle in the graphical representation;

generate a contour map that corresponds to a height of the normal graph;

transform each circle of the one or more circles into a polygon of one hundred sides, wherein vertexes of each polygon expands outward with a specific speed according to the height of the respective polygon on the contour map; and

generate, based on the contour map, the geographical map-based visualization of the dataset,

wherein the generation of the geographical map-based visualization of the data set facilitates reduced requirement of resources to process the datasets on a host device.

21. The apparatus of claim 20, wherein to cluster further comprises clustering using a clustering using representatives (CURE) data clustering algorithm.

22. The apparatus of claim 20, wherein each of the plurality of hierarchical layers includes one or more nodes, wherein each node of the one or more nodes have zero or more child node, and wherein each node contains a sum of data items of the respective zero or more child node thereof.

23. The apparatus of claim 22, wherein

the graphical representation comprises the one or more circles for the one or more nodes of each layer of the plurality of hierarchical layers, and

wherein each circle of the one or more circles in the graphical representation corresponds to a respective two-dimensional distribution of data overlaying one or more two-dimensional distributions of data of one or more other circles.

24. The apparatus of claim 20, wherein, to display the one or more processors perform operations comprising display the respective one or more representative points for each of the data blocks in a default number of layers or in a user-specified number of layers.

25. The apparatus of claim 20, wherein the one or more processors further perform operations comprising:

determine, for each data item of each data block of the plurality of data blocks, a degree of closeness between the each data item and other data items of the respective data block;

determine a clustering threshold based at least in part on the degrees of closeness between the data items of a given data block for at least one data block of the plurality of data blocks;

determine, for at least two data items of the at least one data block, whether the at least two data items belong to a same class or different classes of data based at least in part on the clustering threshold; and

receive a user input indicative of a minimum threshold of a size of an amount of data contained in each of the data blocks for visualization.