Cardinality-based inference control in OLAP systems: an information theoretic approach

ABSTRACT

We address the inference control problem in data cubes with some data known to users through external knowledge. The goal of inference controls is to prevent exact values of sensitive data from being inferred through answers to online analytical processing (OLAP) queries. We present an information theoretic approach for cardinality-based inference control, which simply counts the number of cells that all queries have covered thus far to determine whether a new query should be answered. Compared to previous approaches in sum-only data cubes, our new approach has a more general framework (applies to MIN, MAX and SUM) and is more effective.

REFERENCES

• 1: Nabil R. Adam , John C. Worthmann, Security-control methods for statistical databases: a comparative study, ACM Computing Surveys (CSUR), v.21 n.4, p.515-556, Dec. 1989 [doi>10.1145/76894.76895]
• 2: 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
• 3: Dakshi Agrawal , Charu C. Aggarwal, On the design and quantification of privacy preserving data mining algorithms, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.247-255, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375602]
• 4: 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]
• 5: Jon Kleinberg , Christos Papadimitriou , Prabhakar Raghavan, Auditing Boolean attributes, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.86-91, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335210]
• 6: Alexandre Evfimievski , Ramakrishnan Srikant , Rakesh Agrawal , Johannes Gehrke, Privacy preserving mining of association rules, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775080]
• 7: S. J. Rizvi and J. R. Haritsa, "Maintaining data privacy in association rule mining," in Proceedings of 28th International Conference on Very Large Data Bases (VLDB 2002), August 2002, pp. 682--693.
• 8: Jaideep Vaidya , Chris Clifton, Privacy preserving association rule mining in vertically partitioned data, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775142]
• 9: M. Kantarcioglu and C. Clifton, "Privacy-preserving distributed mining of association rules on horizontally partitioned data," in Proc. of ACM SIGMOD Workshop on Research Issues on Data Mining and Knowledge Discovery (DMKD'02), June 2002, pp. 24--31.
• 10: W. Du , M. Atallah, Privacy-Preserving Cooperative Statistical Analysis, Proceedings of the 17th Annual Computer Security Applications Conference, p.102, December 10-14, 2001
• 11: Benny Pinkas, Cryptographic techniques for privacy-preserving data mining, ACM SIGKDD Explorations Newsletter, v.4 n.2, p.12-19, December 2002 [doi>10.1145/772862.772865]
• 12: 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
• 13: Ran Canetti , Yuval Ishai , Ravi Kumar , Michael K. Reiter , Ronitt Rubinfeld , Rebecca N. Wright, Selective private function evaluation with applications to private statistics, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.293-304, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384047]
• 14: Lingyu Wang , Duminda Wijesekera , Sushil Jajodia, Cardinality-Based Inference Control in Sum-Only Data Cubes, Proceedings of the 7th European Symposium on Research in Computer Security, p.55-71, October 14-16, 2002
• 15: N. Zhang, W. Zhao, and J. Chen, "A new scheme on cardinality-based inference control in OLAP systems," Texas A&M University, Tech. Rep. available at http://www.cs.tamu.edu/people/nzhang/ANSCICOS.pdf, 2004.
• 16: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Security, integrity, and protection; Data warehouse and repository

General Terms:
Algorithms, Security

Keywords:
OLAP, data mining, inference control, information theory