Privacy preservation of aggregates in hidden databases: why and how?

ABSTRACT

Many websites provide form-like interfaces which allow users to execute search queries on the underlying hidden databases. In this paper, we explain the importance of protecting sensitive aggregate information of hidden databases from being disclosed through individual tuples returned by the search queries. This stands in contrast to the traditional privacy problem where individual tuples must be protected while ensuring access to aggregating information. We propose techniques to thwart bots from sampling the hidden database to infer aggregate information. We present theoretical analysis and extensive experiments to illustrate the effectiveness of our approach.

REFERENCES

• 1: M. Atallah , A. Elmagarmid , M. Ibrahim , E. Bertino , V. Verykios, Disclosure Limitation of Sensitive Rules, Proceedings of the 1999 Workshop on Knowledge and Data Engineering Exchange, p.45, November 07-07, 1999
• 2: Rakesh Agrawal , Alexandre Evfimievski , Ramakrishnan Srikant, Information sharing across private databases, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872771]
• 3: Rakesh Agrawal , Ramakrishnan Srikant, Privacy-preserving data mining, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.439-450, May 15-18, 2000, Dallas, Texas, United States
• 4: Rakesh Agrawal , Ramakrishnan Srikant , Dilys Thomas, Privacy preserving OLAP, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066187]
• 5: Krishna Bharat , Andrei Broder, A technique for measuring the relative size and overlap of public Web search engines, Proceedings of the seventh international conference on World Wide Web 7, p.379-388, April 1998, Brisbane, Australia
• 6: Ziv Bar-Yossef , Maxim Gurevich, Random sampling from a search engine's index, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135833]
• 7: Ziv Bar-Yossef , Maxim Gurevich, Efficient search engine measurements, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242627]
• 8: N. Bruno, L. Gravano, A. Marian: Evaluating Top-k Queries over Web-Accessible Databases. ICDE 2002.
• 9: Jamie Callan , Margaret Connell, Query-based sampling of text databases, ACM Transactions on Information Systems (TOIS), v.19 n.2, p.97-130, April 2001 [doi>10.1145/382979.383040]
• 10: Kevin Chen-Chuan Chang , Seung-won Hwang, Minimal probing: supporting expensive predicates for top-k queries, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564731]
• 11: Michael J. Cafarella , Alon Halevy , Daisy Zhe Wang , Eugene Wu , Yang Zhang, WebTables: exploring the power of tables on the web, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453916]
• 12: Chris Clifton , Murat Kantarcioglu , Jaideep Vaidya , Xiaodong Lin , Michael Y. Zhu, Tools for privacy preserving distributed data mining, ACM SIGKDD Explorations Newsletter, v.4 n.2, p.28-34, December 2002 [doi>10.1145/772862.772867]
• 13: Arjun Dasgupta , Gautam Das , Heikki Mannila, A random walk approach to sampling hidden databases, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247550]
• 14: C. Dwork, F. McSherry, K. Nissim, and A. Smith, Calibrating noise to sensitivity in private data analysis. Theory of Cryptography Conference 2006.
• 15: Arjun Dasgupta , Nan Zhang , Gautam Das, Leveraging COUNT Information in Sampling Hidden Databases, Proceedings of the 2009 IEEE International Conference on Data Engineering, p.329-340, March 29-April 02, 2009 [doi>10.1109/ICDE.2009.112]
• 16: A. Dasgupta, N. Zhang, G. Das, S. Chaudhuri, On Privacy Preservations of Aggregates in Hidden Databases, Technical Report TR-GWU-CS-09-001, George Washington University, 2009.
• 17: J. Elson, J. R. Douceur, J. Howell, J. Saul: Asirra: a CAPTCHA that exploits interest-aligned manual image categorization, CCS 2007.
• 18: http://code.google.com/apis/soapsearch/api_faq.html
• 19: Aris Gkoulalas-Divanis , Vassilios S. Verykios, An integer programming approach for frequent itemset hiding, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183721]
• 20: S. Hettich and S. D. Bay, The UCI KDD Archive {http://kdd.ics.uci.edu}. Irvine, CA: University of California, Department of Information and Computer Science. 1999.
• 21: Y. L. Hedley , M. Younas , A. James , M. Sanderson, A two-phase sampling technique for information extraction from hidden web databases, Proceedings of the 6th annual ACM international workshop on Web information and data management, November 12-13, 2004, Washington DC, USA [doi>10.1145/1031453.1031456]
• 22: Yih-Ling Hedley , Muhammad Younas , Anne James , Mark Sanderson, Sampling, information extraction and summarisation of hidden web databases, Data & Knowledge Engineering, v.59 n.2, p.213-230, November 2006 [doi>10.1016/j.datak.2006.01.009]
• 23: Panagiotis G. Ipeirotis , Luis Gravano, Distributed search over the hidden web: hierarchical database sampling and selection, Proceedings of the 28th international conference on Very Large Data Bases, p.394-405, August 20-23, 2002, Hong Kong, China
• 24: Sushil Jajodia , Pierangela Samarati , Maria Luisa Sapino , V. S. Subrahmanian, Flexible support for multiple access control policies, ACM Transactions on Database Systems (TODS), v.26 n.2, p.214-260, June 2001 [doi>10.1145/383891.383894]
• 25: Krishnaram Kenthapadi , Nina Mishra , Kobbi Nissim, Simulatable auditing, 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.1065183]
• 26: Ashwin Machanavajjhala , Daniel Kifer , Johannes Gehrke , Muthuramakrishnan Venkitasubramaniam, L-diversity: Privacy beyond k-anonymity, ACM Transactions on Knowledge Discovery from Data (TKDD), v.1 n.1, p.3-es, March 2007 [doi>10.1145/1217299.1217302]
• 27: Jayant Madhavan , David Ko , Łucja Kot , Vignesh Ganapathy , Alex Rasmussen , Alon Halevy, Google's Deep Web crawl, Proceedings of the VLDB Endowment, v.1 n.2, August 2008 [doi>10.1145/1454159.1454163]
• 28: Shubha U. Nabar , Bhaskara Marthi , Krishnaram Kenthapadi , Nina Mishra , Rajeev Motwani, Towards robustness in query auditing, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 29: Ravi S. Sandhu , Edward J. Coyne , Hal L. Feinstein , Charles E. Youman, Role-Based Access Control Models, Computer, v.29 n.2, p.38-47, February 1996 [doi>10.1109/2.485845]
• 30: Latanya Sweeney, k-anonymity: a model for protecting privacy, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, v.10 n.5, p.557-570, October 2002 [doi>10.1142/S0218488502001648]
• 31: Vassilios S. Verykios , Ahmed K. Elmagarmid , Elisa Bertino , Yucel Saygin , Elena Dasseni, Association Rule Hiding, IEEE Transactions on Knowledge and Data Engineering, v.16 n.4, p.434-447, April 2004 [doi>10.1109/TKDE.2004.1269668]
• 32: Nan Zhang , Wei Zhao, Privacy-Preserving Data Mining Systems, Computer, v.40 n.4, p.52-58, April 2007 [doi>10.1109/MC.2007.142]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration

General Terms:
Algorithms, Management, Measurement, Performance, Security

Keywords:
hidden databases, privacy preservation