A Study Of Privacy Preserving Anonymization Techniques In Combinatorial Maps

In recent years, the rapid development of information technology has led to a burst increase of data in different areas. The value hidden in data has received extensive attention. How to exploit useful information from data has become a hot research topic in the current academic and industrial fields. In order to make full use of the wisdom of the third party and discover the valuable information hidden in data more conveniently and effectively, data holders often need to publish and share data. However, with some private information often involved in data, if data publishers don’t take effective privacy protection measures to protect the data, it can lead to privacy disclosure and serious results, and it may restricts the data sharing and publishing in turn which is not conducive to mining the potential value of the data. Therefore, researchers has proposed a series of privacy preserving techniques to avoid privacy disclosure and anonymization has become a hot research topic as one of the most common and effective methods. Our main contents and contributions are as follows:First, we introduce the privacy disclosure problem in the process of data publishing and the research status in the area of privacy preserving, and we summarize the common privacy preserving techniques, various attack models and common anonymization techniques in relational data and graph data. Usually data publishers will simply hide or remove user identifier which is not sufficient to achieve privacy preserving. Adversary usually can collect some background knowledge and then erode privacy with data released. It is the main problem of privacy preserving study to ensure both the security of sensitive information and the data utility. We conclude common attack methods and anonymization methods in rational data. Compared with relational data, figure data has more complex structure. Due to the diversity of background knowledge and attack methods in graph data, it is a serious challenge for protecting privacy in graph.Then we discuss the privacy preserving problem in publishing private combinatorial map. Combinatorial map is becoming increasingly popular due to its power in modeling topological structures with subdivided objects, which is widely used in the fields of social network, computer vision, social media and so on. However, due to its specific structural properties, an unprotected release of a combinatorial map may cause the identity disclosure problem. Here we discuss the attack models and present a special attack model which is called involution attack model. Then we formalize a specific anonymizing model to protect privacy message from the special background attacks, design an effective algorithm for anonymization of the combinatorial map and a robust algorithm for map construction with the minimized information loss, and provide an efficient metric to quantify information loss incurred in the perturbation. Our approaches are efficient and practical, and have been validated by experiments.