Hilbert curve partitioning for parallelization of DBSCAN
View Patent ↗DBSCAN clustering analyses can be improved by pre-processing of a data set using a Hilbert curve to intelligently identify the centers for initial partitional analysis by a partitional clustering algorithm such as CLARANS. Partitions output by the partitional clustering algorithm can be process by DBSCAN running in parallel before intermediate cluster results are merged.
1. A computer program product comprising a non-transitory machine-readable medium storing instructions that, when executed by at least one programmable processor, cause the at least one programmable processor to perform operations comprising:
indexing a data set using a Hilbert curve that assigns a Hilbert distance to each of a plurality of data points in the data set;
initiating a partitional clustering algorithm with parameters for a plurality of clusters identified using the indexing of the data set, the partitional clustering algorithm outputting the data set grouped into a plurality of partitions, the parameters comprising one or more cluster center values selected based on one or more sequences identified from the Hilbert distances;
determining the one or more cluster center values, the determining comprising grouping the Hilbert distances for the plurality of points into the plurality of clusters, identifying one or more sequences of Hilbert distances as members of a cluster of the plurality of clusters, and choosing a cluster center value for the cluster based on a median of the Hilbert distances in the cluster;
constraining the partitional clustering algorithm to randomly choose a new cluster center value for the cluster with a greater preference for the new cluster value to be within the grouped Hilbert distances for the cluster;
processing the plurality of partitions, the processing comprising running a DBSCAN algorithm on the partitions in parallel to generate intermediate cluster results for each partition; and
generating a final result, the generating comprising merging the intermediate results.
2. The computer program product of claim 1 , wherein the operations further comprise merging two or more of the plurality of clusters prior to the initiating of the partitional clustering algorithm, the merging comprising identifying data points in adjacent cells of the indexed data set.
3. The computer program product of claim 1 , wherein the partitional clustering algorithm comprises a CLARANS algorithm.
4. A system comprising:
computer hardware configured to perform operations comprising:
indexing a data set using a Hilbert curve that assigns a Hilbert distance to each of a plurality of data points in the data set;
initiating a partitional clustering algorithm with parameters for a plurality of clusters identified using the indexing of the data set, the partitional clustering algorithm outputting the data set grouped into a plurality of partitions, the parameters comprising one or more cluster center values selected based on one or more sequences identified from the Hilbert distances;
determining the one or more cluster center values, the determining comprising grouping the Hilbert distances for the plurality of points into the plurality of clusters, identifying one or more sequences of Hilbert distances as members of a cluster of the plurality of clusters, and choosing a cluster center value for the cluster based on a median of the Hilbert distances in the cluster;
constraining the partitional clustering algorithm to randomly choose a new cluster center value for the cluster with a greater preference for the new cluster value to be within the grouped Hilbert distances for the cluster;
processing the plurality of partitions, the processing comprising running a DBSCAN algorithm on the partitions in parallel to generate intermediate cluster results for each partition; and
generating a final result, the generating comprising merging the intermediate results.
5. The system of claim 4 , wherein the operations further comprise merging two or more of the plurality of clusters prior to the initiating of the partitional clustering algorithm, the merging comprising identifying data points in adjacent cells of the indexed data set.
6. The system of claim 4 , wherein the partitional clustering algorithm comprises a CLARANS algorithm.
7. The system of claim 4 , wherein the computer hardware comprises:
a programmable processor; and
a computer readable medium storing instructions that, when executed by the programmable processor, cause the programmable processor to perform at least some of the operations.
8. A computer implemented method comprising:
indexing a data set using a Hilbert curve that assigns a Hilbert distance to each of a plurality of data points in the data set;
initiating a partitional clustering algorithm with parameters for a plurality of clusters identified using the indexing of the data set, the partitional clustering algorithm outputting the data set grouped into a plurality of partitions, the parameters comprising one or more cluster center values selected based on one or more sequences identified from the Hilbert distances;
determining the one or more cluster center values, the determining comprising grouping the Hilbert distances for the plurality of points into the plurality of clusters, identifying one or more sequences of Hilbert distances as members of a cluster of the plurality of clusters, and choosing a cluster center value for the cluster based on a median of the Hilbert distances in the cluster;
constraining the partitional clustering algorithm to randomly choose a new cluster center value for the cluster with a greater preference for the new cluster value to be within the grouped Hilbert distances for the cluster;
processing the plurality of partitions, the processing comprising running a DBSCAN algorithm on the partitions in parallel to generate intermediate cluster results for each partition; and
generating a final result, the generating comprising merging the intermediate results.
9. The computer implemented method of claim 8 , further comprising merging two or more of the plurality of clusters prior to the initiating of the partitional clustering algorithm, the merging comprising identifying data points in adjacent cells of the indexed data set.
10. The computer implemented method of claim 8 , wherein the partitional clustering algorithm comprises a CLARANS algorithm.
11. The computer implemented method of claim 8 , wherein the indexing, the initiating, the processing, and the generating are performed by at least one system comprising computer hardware.