Clustering for geo-enriched data

Patent metadata

Field	Value
Publication number	US-11301500-B2
Application number	US-201615394142-A
Country	US
Kind code	B2
Filing date	Dec 29, 2016
Priority date	Dec 29, 2016
Publication date	Apr 12, 2022
Grant date	Apr 12, 2022

Abstract

Some embodiments provide a program that receives a set of clusters generated from a set of geo-enriched data. The program further identifies a subset of the set of clusters that intersect a map extent of a map. Upon determining that a number of geo-enriched data represented by the subset of the set of clusters is greater than a threshold number, the program renders the map extent of the map to include the subset of the set of clusters. Upon determining that the number of geo-enriched data represented by the subset of the set of clusters is not greater than the threshold number, the program further sends a query for a subset of the set of geo-enriched data that is within the map extent, receives the subset of the set of geo-enriched data and renders the map extent of the map to include the subset of the set of geo-enriched data.

First claim

What is claimed is:

1. A non-transitory machine-readable medium storing a program executable by at least one processing unit of a computing device, the program comprising sets of instructions for:
sending, from the computing device to a computing system, a query for clusters generated from a set of geo-enriched data, wherein the query specifies a maximum number of clusters, wherein each geo-enriched data in the set of geo-enriched data comprises spatial data to which location data is converted, wherein the location data describes a location, area, or region;
receiving, at the computing device from the computing system, a set of clusters responsive to the query and generated from the set of geo-enriched data, wherein each cluster in the set of clusters comprises a number of geo-enriched data represented by the cluster;
identifying, by the computing device, a subset of the set of clusters that intersect a map extent of a map;
determining, by the computing device, whether the number of geo-enriched data defined by the subset of the set of clusters is greater than a threshold number of data points;
upon determining that the number of geo-enriched data defined by the spatial data represented by the subset of the set of clusters is greater than the threshold number, rendering the map extent of the map to include the number of geo-enriched data of the subset of the set of clusters, the rendering comprising:
merging, by the computing device, the subset of the set of clusters to form a set of cluster groups; and
rendering the map extent of the map to include the set of cluster groups; and

upon determining that the number of geo-enriched data defined by the spatial data represented by the subset of the set of clusters is not greater than the threshold number:
sending the computing system a query for geo-enriched data in the set of geo-enriched data that is within the map extent;
receiving from the computing system the geo-enriched data in the set of geo-enriched data that is within the map extent; and
rendering the map extent of the map to include the number of geo-enriched data defined by the spatial data represented by the geo-enriched data in the set of geo-enriched data that is within the map extent.

2. The non-transitory machine-readable medium of claim 1 , wherein merging the subset of the set of clusters comprises, for each cluster in the subset of the set of clusters:
determining, by the computing device, a pixel distance between the cluster and a cluster group in the set of cluster groups by calculating a spatial distance between a reference point of the cluster and a reference point of the cluster group and dividing the spatial distance by a map resolution;
adding, by the computing device, the cluster to the cluster group in the set of cluster groups when the pixel distance between the cluster and the cluster group is less than a defined pixel distance; and
creating, by the computing device, a new cluster group in the set of cluster groups and adding the cluster to the new cluster group when the pixel distance between the cluster and the cluster group is not less than the defined pixel distance.

3. The non-transitory machine-readable medium of claim 2 , wherein adding the cluster to the cluster group in the set of cluster groups comprises updating the reference point of the cluster group based on the reference point of the cluster, a size of the cluster, and a size of the cluster group.

4. The non-transitory machine-readable medium of claim 2 , wherein adding the cluster to the cluster group in the set of cluster groups comprises updating a size of the cluster group based on a size of the cluster and the size of the cluster group.

5. The non-transitory machine-readable medium of claim 1 , wherein each geo-enriched data in the set of geo-enriched data comprises an attribute, wherein the program further comprises a set of instructions for sending a request for a maximum value of the attribute in the set of geo-enriched data and a minimum value of the attribute in the set of geo-enriched data, wherein rendering the map extent of the map to include the subset of the set of geo-enriched data comprises rendering a visual representation of a geo-enriched data in the subset of the set of geo-enriched data based on a value of the attribute of the geo-enriched data relative to the maximum value and the minimum value.

6. The non-transitory machine-readable medium of claim 1 , wherein the map extent is a first map extent of the map, wherein the subset of the set of clusters is a first subset of the set of clusters, wherein the query is a first query, wherein the subset of the set of geo-enriched data is a first subset of the set of geo-enriched data, wherein the program further comprises sets of instructions for:
receiving a request to render a second map extent of the map;
identifying, by the computing device, a second subset of the set of clusters that intersect the second map extent;
determining, by the computing device, whether a number of geo-enriched data defined by the second subset of the set of clusters is greater than the threshold number;
upon determining that the number of geo-enriched data defined by the spatial data represented by the second subset of the set of clusters is greater than the threshold number, rendering the second map extent of the map to include the number of geo-enriched data of the second subset of the set of clusters; and
upon determining that the number of geo-enriched data defined by the spatial data represented by the second subset of the set of clusters is not greater than the threshold number:
sending the computing system a second query for geo-enriched data in the set of geo-enriched data that is within the second map extent;
receiving from the computing system the geo-enriched data in the set of geo-enriched data that is within the second map extent; and
rendering the second map extent of the map to include the number of geo-enriched data defined by the spatial data represented by the geo-enriched data in the set of geo-enriched data that is within the second map extent.

7. A method comprising:
sending, from a computing device to a computing system, a query for clusters generated from a set of geo-enriched data, wherein the query specifies a maximum number of clusters, wherein each geo-enriched data in the set of geo-enriched data comprises spatial data to which location data is converted, wherein the location data describes a location, area, or region;
receiving, at the computing device from the computing system, a set of clusters responsive to the query and generated from the set of geo-enriched data, wherein each cluster in the set of clusters comprises a number of geo-enriched data represented by the cluster;
identifying, by the computing device, a subset of the set of clusters that intersect a map extent of a map;
determining, by the computing device, whether the number of geo-enriched data defined by the spatial data represented by the subset of the set of clusters is greater than a threshold number of data points;
upon determining that the number of geo-enriched data defined by the spatial data represented by the subset of the set of clusters is greater than the threshold number, rendering the map extent of the map to include the number of geo-enriched data of the subset of the set of clusters, the rendering comprising:
merging, by the computing device, the subset of the set of clusters to form a set of cluster groups; and
rendering the map extent of the map to include the set of cluster groups; and

upon determining that the number of geo-enriched data defined by the spatial data represented by the subset of the set of clusters is not greater than the threshold number:
sending the computing system a query for ge

Assignees

• Sap Se

Inventors

• Jin Xing
• Tiu Jonathan
• Nam Kyoung Woo
• Om Sae-Won

Classifications

• G06F16/35

  Clustering; Classification · CPC title

• G06F16/29 Primary

  Geographical information databases · CPC title

• G06F16/26

  Visual data mining; Browsing structured data · CPC title

• G06F16/24

  Querying · CPC title

• G06F16/287

  Visualization; Browsing · CPC title