Articles in Press

Accepted articles here

Latest Issues

Volume 18 Issue 2
Volume 18 Issue 1

Volume 17 Issue 3
Volume 17 Issue 2
Volume 17 Issue 1

Volume 16 Issue 3
Volume 16 Issue 2
Volume 16 Issue 1

Volume 15 Issue 3
Volume 15 Issue 2
Volume 15 Issue 1

Volume 14 Issue 3
Volume 14 Issue 2
Volume 14 Issue 1

Volume 13 Issue 3
Volume 13 Issue 2
Volume 13 Issue 1

Volume 12 Issue 3
Volume 12 Issue 2
Volume 12 Issue 1

Volume 11 Issue 3
Volume 11 Issue 2
Volume 11 Issue 1

Volume 10 Issue 3
Volume 10 Issue 2
Volume 10 Issue 1

Volume 9 Issue 3
Volume 9 Issue 2
Volume 9 Issue 1

Volume 8 Issue 3
Volume 8 Issue 2
Volume 8 Issue 1

Volume 7 Issue 3
Volume 7 Issue 2
Volume 7 Issue 1

Volume 6 Issue 3
Volume 6 Issue 2
Volume 6 Issue 1

Volume 5 Issue 3
Volume 5 Issue 2
Volume 5 Issue 1

Volume 4 Issue 3
Volume 4 Issue 2
Volume 4 Issue 1

Volume 3 Issue 3
Volume 3 Issue 2
Volume 3 Issue 1

Volume 2 Issue 3
Volume 2 Issue 2
Volume 2 Issue 1

Volume 1 Issue 3
Volume 1 Issue 2
Volume 1 Issue 1

Volume 5 Issue 1

A Practical Differentially Private Random Decision Tree Classifier

Geetha Jagannathan^(a),(*), Krishnan Pillaipakkamnatt^(b), Rebecca N. Wright^(c)

Transactions on Data Privacy 5:1 (2012) 273 - 295

Abstract, PDF

(a) Department of Computer Science; Columbia University; NY; USA.

(b) Department of Computer Science; Hofstra University; Hempstead; NY; USA.

(c) Department of Computer Science; Rutgers University; New Brunswick; NJ; USA.

e-mail:geetha @cs.columbia.edu; csckzp @hofstra.edu; rebecca.wright @rutgers.edu

Abstract

In this paper, we study the problem of constructing private classifiers using decision trees, within the framework of differential privacy. We first present experimental evidence that creating a differentially private ID3 tree using differentially private low-level queries does not simultaneously provide good privacy and good accuracy, particularly for small datasets.

In search of better privacy and accuracy, we then present a differentially private decision tree ensemble algorithm based on random decision trees. We demonstrate experimentally that this approach yields good prediction while maintaining good privacy, even for small datasets. We also present differentially private extensions of our algorithm to two settings: (1) new data is periodically appended to an existing database and (2) the database is horizontally or vertically partitioned between multiple users.

^* Corresponding author.