Crate ff_k_center

This is the Rust implementation for the fast privacy preserving representative k-center (priv-Rep-kC) algorithm described in our ICML paper. For an instance with n data points that should be covered by at most k centers, this algorithm has a running time guarantee of O(nk² + k⁵). The code is a Rust library that implements a python interface, leading to the following two options to run our algorithm:

• It can be imported into another Rust project.
• After installing the python wheel, the algorithm can be executed from any python script or jupyter notebook.

Quick Start

First create a metric space with color classes by either loading them through a file or by manually entering the distance matrix and colors. The metric space must implement the ColoredMetric-trait. For details on how to create or load metric spaces see: SpaceMatrix and SpaceND.

Then create a ClusteringProblem by specifying the maximal number of clusters k, the lower bound for privacy condition privacy_bound, and a list intervals (one for each color class) for the representative condition.

With compute_privacy_preserving_representative_k_center a Clustering is created, which contains a list of centers (see Centers) and an assignment of each point to a center. This clustering is a 15-approximation on the optimal “privacy-preserving representative k-center”-clustering.

Example

The code below shows an example that creates a data set of 5000 random points on which Priv-Rep-kC is solved with our algorithm.

use ff_k_center::*;
let n = 5_000;
let k = 8;
let space = SpaceND::new_random(n);
let prob = ClusteringProblem{
    k, // number of centers;
    privacy_bound : n/k, // number of points to represent;
    rep_intervals : vec!((0,500),(0,500),(0,500)), // representation interval [a,b] for each color class;
                                                   // for color classes without interval we subsitute [0. inf]
};
let (clustering, total_time) = compute_privacy_preserving_representative_k_center(&space, &prob, None);
println!("Radius: {}; Running time: {}s.", clustering.get_radius(), total_time);

Python Interface

The python interface is the most convenient way to use our algorithm. See the GitHub repository for more details on how to install the python wheel and how to use the python interface.

Structs

• Centers
  A list of centers.
• Clustering
  A (partial) clustering specified by a list of centers and an assignment of clients to centers.
• ClusteringProblem
  ClusteringProblem defines for a given colored metric space a problem instance of privacy preserving representative k-clustering.
• OptionalParameters
  A collection of optional parameters. Each can be set to None to use the default values.
• Point
  A point of a metric space. Their only attribute is an index, which can be obtained by idx(). Points are created by metric spaces and can only be accessed via the ColoredMetric::point_iter.
• SpaceMatrix
  A general finite metric space with color classes.
• SpaceND
  A metric space in the euklidean space of some dimension N. Implements the ColoredMetric trait. Beside the color it also stores the position of type Vec<f32> of each point. The distance is computed by the Eucleadean metric.

Traits

• ColoredMetric
  Trait for a metric space with colored points.

Functions

• PyInit_ff_k_center^⚠
  This autogenerated function is called by the python interpreter when importing the module.
• assert_clustering_problem
  Asserts a clustering problem. Checks whether the clustering problem is feasible. If this assertion runs through, the main algorithm will return a feasible clustering.
• compute_privacy_preserving_representative_k_center
  Computes a privacy preserving representative k-clustering. The radius is a 15-approximation and the running time is O(nk² + k⁵).

Type Aliases

• ColorCount
  Type of the number of color classes.
• DurationInSec
  Type of the running time return value. Computing time in millisecends.
• Interval
  Type of the representative intervals [a, b].
• PointCount
  Type of the number of points in the metric space.