Skip to main content

GPU implementation of clustering by fast search and find density peak.

Project description

Image Algorithm for General Purpose

Image Algorithm is a clustering algorithm based fast search and find of density peaks. Comparing with other popular clustering methods, such as DBSCAN, one of the most prominent advantages of Image Algorithm is being highly parallelizable. This repository is an implementation of Image Algorithm for general purpose, supporting strong and easy GPU acceleration.

For now, the implementation includes three backends: numpy, CUDA and OpenCL.

backend dependency Support Platform Support Device
numpy None Mac/Linux/Windows CPU
CUDA pycuda Linux Only NVIDIA GPU
OpenCL pyopencl Mac NVIDIA/AMD/Intel GPU, multi-core CPU

It has been tested that all three backends give the identical clustering results. Therefore users can feel free to choose whichever faster and easier for their purposes.

For all three backends, two kinds of data structure can be taken in: Flat list and kdbin. KDBin, bins in k-dimention, accommodates points inside spatial bins in k-dimention with dynamic bin distribution and flexible bin capacity. Techniqually it uses hashmap and a set of memory references to obtain nearest neighboring bins and points inside, such that query of neighborhood for each point is O(1) complexity. Performance test shows a strong acceleration in density calculation using KDBin data structure.

supported data structure rho Calculation rhorank and nh Calculation
numpy list/bin list/bin
CUDA list/bin list
OpenCL list/bin list

For density rho calculation, performance tested is shown below.

To do list

  • <input type="checkbox" disabled="" /> Calculate rhorank in CUDA/OpenCL via 'Merge Sorted List' for parallel sorting.
  • <input type="checkbox" disabled="" /> Support nh search in nearest neighboring bins in CUDA/OpenCL


pip install ImageAlgoKD

Regarding dependency, no dependency is required for numpy backend. And it usually does a good job dealing with small dataset and needs no extra packages. However, for users wanting to use GPU acceleration with either CUDA or OpenCL backend, extra dependency is required.

# if want to use opencl backend
pip install pyopencl
# if want to use CUDA backend
pip install pycuda

Quick Start

The primary usage of the module is the following First of all, import ImageAlgo class for K-Dimension

from ImageAlgoKD import *

Declare an instance of ImageAlgoKD with your algorithm parameters. Then give it the input data points.

ia = ImageAlgoKD(MAXDISTANCE=20, KERNEL_R=1.0)

Then run the clustering over input data points."numpy")
#"opencl") or"cuda") if want run in parallel

In the end, the clustering result can be access by


Algorithm Parameters

Parameters Comments Default Value
MAXDISTANCE the separation distance of the point with highest density. 10.0
KERNEL_R 'd_c' in density calculation 1.0
KERNEL_R_NORM 'd_0' in density calculation 1.0
KERNEL_R_POWER 'k' in density calculation. 0.0
DECISION_RHO_KAPPA the ratio of density threshold of seeds to the highest density 4.0
DECISION_NHD the separation threshold of seeds 1.0
CONTINUITY_NHD the separation threshold of continuous clusters 1.0

where density is defined as


I. Basic

Perform IA clustering on 1000 toy 2D points, sampled from two Gaussian Distrituion and noise. The toy data is in data/basic.csv, while the corresponding jupyter notebook can be found here in examples/.


Perform IA clustering on 1000 MNIST 28x28 dimension points. The MNIST data is in data/mnist.csv, while the corresponding jupyter notebook can be found here in examples/.


This is an event of 10 Pions with 300 GeV energy in CMS HGCal. A 3D interactive visualization can be found here. In addition, for event with pile up, here is an 300GeV pion with PU200 event. A PU200 event typically includes about 200k HGVCal reconstructed detector hits, which is input into IA clustering

Project details

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for ImageAlgoKD, version 0.0.4
Filename, size File type Python version Upload date Hashes
Filename, size ImageAlgoKD-0.0.4-py3-none-any.whl (14.0 kB) File type Wheel Python version py3 Upload date Hashes View

Supported by

AWS AWS Cloud computing Datadog Datadog Monitoring DigiCert DigiCert EV certificate Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page