An Incremental Updating Method for the K-anonymous Dataset using a Similar-B-tree

An Incremental Updating Method for the K-anonymous Dataset using a Similar-B-tree

Jinling Song* Liming Huang Yan Gao Haibin Liu

Hebei Normal University of Science & Technology, Qinhuangdao 066004, China

Liaoning Institute of Science and Technology, Benxi 117004, China

Corresponding Author Email: 
songjinling99@126.com
Page: 
189-209
|
DOI: 
https://doi.org/10.18280/ama_b.600112
Received: 
15 March 2017
| |
Accepted: 
15 April 2017
| | Citation

OPEN ACCESS

Abstract: 

K-anonymity is an effective method to prevent linking attacks and protect privacy. Although the k-anonymous dataset guarantees privacy, it must be constantly updated because the original dataset updates occasionally after a version of k-anonymous dataset has been exposed. So, how to update the k-anonymous dataset simultaneously when the original dataset has been updated becomes an urgent problem. To solve this problem, according to the mapping relation between tuples of the original dataset and k-anonymous dataset, a kind of tree structure similar to a B-tree is proposed, so that the update operations on the original dataset can be converted into the corresponding operations of leaf node in the similar-B-tree. Based on this, an incremental updating method for the k-anonymous dataset using a similar-B-tree is presented. This method can reflect the changes in the original dataset to the k-anonymous dataset in time, and it can greatly improve the update efficiency of the k-anonymous dataset.

Keywords: 

Incremental update; k-anonymous dataset; similar-B-tree; spatial point

1. Introduction
2. Related Work
3. Basic Definition
4. Description of Similar-B-Tree
5. Conversion of Tuple to Multidimensional Spatial Point
6. Creating a Similar-B-Tree
7. Incremental Updating Method Basing on Similar-B-Tree for K-Anonymous Dataset
8. Experimental Analysis
9. Conclusion
Acknowledgement
  References

[1] L. Sweeney, K-Anonymity: a model for protecting privacy, 2002, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, vol. 10, no. 5, pp. 557-570.

[2] X.K. Xiao, Y.F. Tao, Dynamic Anonymization: Accurate Statistical Analysis with Privacy Preservation. 2008, SIGMOD, 2008, Vancouver, Canada, pp. 107-120.

[3] L. Sweeney, Achieving k-anonymity privacy protection using generalization and suppression, 2002, Int’l Journal on Uncertainty, Fuzziness and Knowledge-Based Systems, vol. 10, no. 5, pp. 571-588.

[4] K. Lefvre, D. DeWitt, Ramakrishnan. R, Incognito: Efficient full-domain k-anonymity, SIGMOD, 2005, Baltimore, USA, pp. 49–60.

[5] K. LeFevre, D.J. DeWitt, Ramakrishnan Raghu, Mondrian Multidimensional K-Anonymity, 2006, ICDE, 2006, Atlanta, USA, pp. 25-35.

[6] A. Machanavajjhala, J. Gehrke, D. Kifer, l-diversity: Privacy beyond k-anonymity, 2006, ICDE, 2006, Atlanta, USA, pp. 1-12.

[7] G. Ghinita, P. Kalnis, Y.F. Tao, Anonymous Publication of Sensitive Transactional Data, 2011, IEEE Transactions on Knowledge and Data Engineering, vol. 23, no. 2, pp. 161-174.

[8] X.K. Xiao, K. Yi, Y.F. Tao, The Hardness and Approximation Algorithms for L-Diversity, EDBT , 2010, Lausanne, Switzerland, pp. 135-146.

[9] J.Q. Liu, K. Wang, On Optimal Anonymization for L+-Diversity, ICDE, 2010, Long Beach, USA, pp. 213-224.

[10] K. Wang, Y.B. Xu, R.C.W. Wong, W.C. Fu, Anonymizing Temporal Data, 2010, the 10th International Conference on Data Mining, 2010, Sydney, Australia, pp. 1109-1114.

[11] P. Shi, L. Xiong, B.C.W. Fung, Anonymizing Data with Quasi-Sensitive Attribute Values, 2010, 19th International Conference on Information and Knowledge Management, Toronto, Canada, pp. 1389-1392.

[12] N. Mohammed, B.C.M. Fung, M. Debbabi, Anonymity Meets Game Theory: Secure Data Integration with Malicious Participants, 2011, The VLDB Journal, vol. 20, no. 4, pp. 567-588.

[13] B. Wang, J. Yang, Personalized (α, k)-Anonymity Algorithm Based on Entropy Classification, 2012, Journal of Computational Information Systems, vol. 8, no. 1, pp. 259- 266.

[14] Q.Y. Gong, M. Yang, J.Z. Luo, Data Anonymization Approach for Incomplete Microdata, 2013, Journal of Software, vol. 24, no. 12, pp. 2883-2896.

[15] Z.Y. Zhang, J.M. Han, H.Y. Wang, X.C. Chen, (k,l,e)-Anonymity: A Resisting Approximate Attack Model for Sensitive Attributes, 2014,  Journal of Chinese Computer Systems, vol. 35, no. 7, pp. 1491-1495.

[16] J.W. Byun, Y. Sohn, Bertino E, N. Li, Secure Anonymization for Incremental Datasets, 2006, the 3rd VLDB Workshop on Secure Data Management, Seoul, Korea, pp. 48-63. 

[17] J. Pei, J. Xu, Z. Wang Z, W. Wang, Maintaining K-Anonymity against Incremental Updates, 2007, the 19th International Conference on Scientific and Statistical Database Management, Banff, Canada, pp. 5.

[18] J.W. Byun, T.C. Li, B. Elisa, N. Li, Y. Sohn, Privacy-Preserving Incremental Data Dissemination, 2009, Journal of Computer Security, vol. 17, no. 1, pp. 43-68.

[19] Y.J. Wu, Z.H. Sun, X.D. Wang, Privacy Preserving k-Anonymity for Re-publication of Incremental Datasets, 2009, WRI World Congress on Computer Science and Information Engineering, Los Angeles, California, pp. 53-60.

[20] X. Xiao, Y. Tao, M-invariance: towards privacy preserving re-publication of dynamic datasets, 2007, SIGMOD, Beijing, China, pp. 689-700.

[21] M.T. Traian, C. Alina, K-anonymization incremental maintenance and optimization techniques, 2007, ACM symposium on Applied computing, Seoul, Korea, pp. 380-387.

[22] K. Guo, Q.S. Zhang, Fast Clustering-Based Anonymization Algorithm for Data Streams, 2013, Journal of Software, vol. 24, no. 8, pp. 1852-1867.

[23] D.J. Newman, S. Hettich, C.L. Blake, C.J. Merz, UCI Repository of Machine Learning Databases, 1998, www.ics.uci.edu/~mlearn/MLRepository.html, University of California, Irvine.