Differentially Private Clustering Algorithms

הרקע לפרויקט:

Differential privacy has been established in recent years as the "de-facto" gold standard of privacy preserving data analysis. In this project the students are expected to read, understand, implement and test a differentially private algorithm for locating a cluster / multiple clusters in a given dataset of points in the Euclidean space.

מטרת הפרויקט:

This project is centered around the problem of private data clustering. The students are expected to implement randomized algorithms that deal with clustering, including: noisy counting, above-threshold, locally-sensitive hashing, and randomly chosen axes.

Furthermore, the students are expected to test and compare the performance of said algorithms over multiple datasets.

Academically, the goal of the project is to have the students acquainted with differential privacy (DP) and the high-level ideas of differential privacy, as well as the technical difficulties that arise from the promise of DP.

Practically, the goal is to publish the project's code online, available for researchers world-wide.

תכולת הפרויקט:

The project's main focus is on understanding and implementing a scientific paper in differential privacy.

The project is based on 3 stages:

1. reading and understanding existing work,
2. implementation of algorithms in code and
3. testing empirical performance over synthetic / real-life data.

The main focus of the project is the 1-cluster algorithm of Nissim and Stemmer, composed of multiple building blocks.

The students are required to implement each of these subroutines and then wrap it all together in an algorithm of bounded privacy lose (i.e. a (\epsilon,\delta)-DP algorithm).

קורסי קדם:

• 83224- מבני נתונים ואלגוריתמים 2
• 83216- מבוא להסתברות וסטטיסטיקה

דרישות נוספות:

• 83908- פרטיות דפרנציאלית (המומלץ)

מקורות:

1. arxiv.org/pdf/1804.08001
2. arxiv.org/pdf/1707.04766
3. www.cis.upenn.edu/~aaroth/Papers/privacybook.pdf