Private coresets

ABSTRACT

A coreset of a point set P is a small weighted set of points that captures some geometric properties of $P$. Coresets have found use in a vast host of geometric settings. We forge a link between coresets, and differentially private sanitizations that can answer any number of queries without compromising privacy. We define the notion of private coresets, which are simultaneously both coresets and differentially private, and show how they may be constructed. We first show that the existence of a small coreset with low generalized sensitivity (i.e., replacing a single point in the original point set slightly affects the quality of the coreset) implies (in an inefficient manner) the existence of a private coreset for the same queries. This greatly extends the works of Blum, Ligett, and Roth [STOC 2008] and McSherry and Talwar [FOCS 2007]. We also give an efficient algorithm to compute private coresets for k-median and k-mean queries in Re^d, immediately implying efficient differentially private sanitizations for such queries. Following McSherry and Talwar, this construction also gives efficient coalition proof (approximately dominant strategy) mechanisms for location problems. Unlike coresets which only have a multiplicative approximation factor, we prove that private coresets must have an additive error. We present a new technique for showing lower bounds on this error.

REFERENCES

• 1: P. Agarwal, S. Har-Peled, and K.R. Varadarajan. Geometric approximations via coresets. Combinatorial and Computational Geometry -- MSRI Publications, 52:1--30, 2005.
• 2: Pankaj K. Agarwal , Sariel Har-Peled , Kasturi R. Varadarajan, Approximating extent measures of points, Journal of the ACM (JACM), v.51 n.4, p.606-635, July 2004 [doi>10.1145/1008731.1008736]
• 3: Pankaj K. Agarwal , Cecilia Magdalena Procopiuc , Kasturi R. Varadarajan, Approximation Algorithms for k-Line Center, Proceedings of the 10th Annual European Symposium on Algorithms, p.54-63, September 17-21, 2002
• 4: Mihai Bādoiu , Sariel Har-Peled , Piotr Indyk, Approximate clustering via core-sets, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509947]
• 5: Boaz Barak , Kamalika Chaudhuri , Cynthia Dwork , Satyen Kale , Frank McSherry , Kunal Talwar, Privacy, accuracy, and consistency too: a holistic solution to contingency table release, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China [doi>10.1145/1265530.1265569]
• 6: Amos Beimel , Kobbi Nissim , Eran Omri, Distributed Private Data Analysis: Simultaneously Solving How and What, Proceedings of the 28th Annual conference on Cryptology: Advances in Cryptology, August 17-21, 2008, Santa Barbara, CA, USA [doi>10.1007/978-3-540-85174-5_25]
• 7: Avrim Blum , Cynthia Dwork , Frank McSherry , Kobbi Nissim, Practical privacy: the SuLQ framework, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065184]
• 8: Avrim Blum , Katrina Ligett , Aaron Roth, A learning theory approach to non-interactive database privacy, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374464]
• 9: L.S. Buriol, G. Frahling, S. Leonardi, and C. Sohler. Estimating clustering indexes in data streams. ESA, pages 618--632, 2007.
• 10: Timothy M. Chan, Faster core-set constructions and data stream algorithms in fixed dimensions, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997843]
• 11: Ke Chen, On k-Median clustering in high dimensions, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1177-1185, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109687]
• 12: Kenneth L. Clarkson, Subgradient and sampling algorithms for l1 regression, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 13: Artur Czumaj , Funda Ergün , Lance Fortnow , Avner Magen , Ilan Newman , Ronitt Rubinfeld , Christian Sohler, Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time, SIAM Journal on Computing, v.35 n.1, p.91-109, 2005 [doi>10.1137/S0097539703435297]
• 14: Artur Czumaj , Christian Sohler, Sublinear-time approximation algorithms for clustering via random sampling, Random Structures & Algorithms, v.30 n.1-2, p.226-256, January 2007 [doi>10.1002/rsa.v30:1/2]
• 15: Irit Dinur , Kobbi Nissim, Revealing information while preserving privacy, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.202-210, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773173]
• 16: C. Dwork. Differential privacy. ICALP, LNCS, pages 1--12, 2006.
• 17: C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor. Our data, ourselves: Privacy via distributed noise generation. EUROCRYPT, LNCS, pages 486--503. Springer, 2006.
• 18: C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. TCC, pages 265--284, 2006.
• 19: Cynthia Dwork , Frank McSherry , Kunal Talwar, The price of privacy and the limits of LP decoding, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250804]
• 20: C. Dwork and K .Nissim. Privacy-preserving datamining on vertically partitioned databases. CRYPTO, pages 528--544, 2004.
• 21: Cynthia Dwork , Sergey Yekhanin, New Efficient Attacks on Statistical Disclosure Control Mechanisms, Proceedings of the 28th Annual conference on Cryptology: Advances in Cryptology, August 17-21, 2008, Santa Barbara, CA, USA [doi>10.1007/978-3-540-85174-5_26]
• 22: Alexandre Evfimievski , Johannes Gehrke , Ramakrishnan Srikant, Limiting privacy breaches in privacy preserving data mining, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.211-222, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773174]
• 23: Dan Feldman , Amos Fiat , Micha Sharir, Coresets forWeighted Facilities and Their Applications, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.315-324, October 21-24, 2006 [doi>10.1109/FOCS.2006.22]
• 24: Dan Feldman , Amos Fiat , Micha Sharir , Danny Segev, Bi-criteria linear-time approximations for generalized k-mean/median/center, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea [doi>10.1145/1247069.1247073]
• 25: Dan Feldman , Morteza Monemizadeh , Christian Sohler, A PTAS for k-means clustering based on weak coresets, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea [doi>10.1145/1247069.1247072]
• 26: G. Frahling, P. Indyk, and C. Sohler. Sampling in dynamic data streams and applications. Int. J. Comput. Geometry Appl, 18(1/2):3--28, 2008.
• 27: Gereon Frahling , Christian Sohler, Coresets in dynamic geometric data streams, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060622]
• 28: R. L. Graham and N. J. A. Sloane. Lower bounds for constant weight codes. IEEE Trans. Inform. Theory, 26(1):37--43, 1980.
• 29: S. Har-Peled, Clustering Motion, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.84, October 14-17, 2001
• 30: S. Har-Peled. No coreset, no cry. FSTTCS, pages 324--335, 2004.
• 31: Sariel Har-Peled , Akash Kushal, Smaller coresets for k-median and k-means clustering, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064114]
• 32: Sariel Har-Peled , Soham Mazumdar, On coresets for k-means and k-median clustering, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007400]
• 33: Sariel Har-Peled , Kasturi R. Varadarajan, High-Dimensional Shape Fitting in Linear Time, Discrete & Computational Geometry, v.32 n.2, p.269-288, July 2004 [doi>10.1007/s00454-004-1118-2]
• 34: Sariel Har-Peled , Kasturi Varadarajan, Projective clustering in high dimensions using core-sets, Proceedings of the eighteenth annual symposium on Computational geometry, p.312-318, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513440]
• 35: Shiva Prasad Kasiviswanathan , Homin K. Lee , Kobbi Nissim , Sofya Raskhodnikova , Adam Smith, What Can We Learn Privately?, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.531-540, October 25-28, 2008 [doi>10.1109/FOCS.2008.27]
• 36: Christiane Lammersen , Christian Sohler, Facility Location in Dynamic Geometric Data Streams, Proceedings of the 16th annual European symposium on Algorithms, September 15-17, 2008, Karlsruhe, Germany [doi>10.1007/978-3-540-87744-8_55]
• 37: Frank McSherry , Kunal Talwar, Mechanism Design via Differential Privacy, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.94-103, October 21-23, 2007 [doi>10.1109/FOCS.2007.41]
• 38: Nina Mishra , Mark Sandler, Privacy via pseudorandom sketches, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142373]
• 39: K. Nissim. Private data analysis via output perturbation. In Charu Aggarwal and Philip S. Yu, editors, Privacy-Preserving Data Mining, Models and Algorithms, pages 383--414.
• 40: Kobbi Nissim , Sofya Raskhodnikova , Adam Smith, Smooth sensitivity and sampling in private data analysis, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250803]
• 41: Vibhor Rastogi , Dan Suciu , Sungho Hong, The boundary between privacy and utility in data publishing, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Security, Theory

Keywords:
coresets, differential privacy, privacy