PROBI Documentation

PROBI is a data stream algorithm for the probabilistic Euclidean k-median problem. This implementation is an heuristic and fast version of PROBI. It also features a second algorithm for the probabilistic Euclidean k-means problem.

Class hierarchy

FastCoreset implements PROBI. Points are stored and delivered to FastCoreset as instances of Point and ProbabilisticPoint. Metric<Point> is implemented by EuclideanMetric and EuclideanSquaredMetric for k-median and k-means, respectively. Norm<Point> is implemented by EuclideanNorm and EuclideanSquaredNorm. LloydMedian and LloydProbMedian are adaptions of Lloyd's algorithm for k-median and probabilistic k-median, respectively.

Building PROBI

The PROBI sample applications can be built by generating the project files with Premake (see below) in probi-environment and compiling them. A generated Makefile using GCC is provided for convenience.

Example: Generation of a Makefile using Linux

premake4 gmake

Four configurations are available

• "Debug" and "Release" for k-median
• "DebugKmeans" and "ReleaseKmeans" for k-means

Example: Compiling using the "Release" configuration

make config=release

Attention

Debug configurations need header files which are ordinarily available only on Unix based operating systems.

References

• PROBI website
• Premake website