Research On The K-Anomonity Based Algorithms For Privacy Protection Supporting Large Number Of Queries

Some current open platforms such as social network, micro-blog platform, user data sometimes is opening to all other users in the network even for the anonymous users. This phenomenon is a big threat to user privacy once it’s hacked by some illegal users, without related measures to prevent potential privacy disclosure would leads to exposure of privacy data, even further threat all users in the platform. Among all the privacy attack methods, inference attacking and related strategies to prevent it from indirect privacy leakage are always the important issues in privacy protection area. But existing methods remains two challenges:Firstly, they only can detect the direct privacy leakage phenomenon analogous to k equals to1in the K-anonymity model, it presents a small granularity for privacy protection and wastes much more resources to maintain the query history and their results which cannot assure both the minimum detection cost and lower response delay; Secondly, existing generalization methods are not effective when they work globally on the leaked data because generalization problem is a proved N-P hard problem.As to the prevention of the inference attack, this paper works on two aspects:Firstly, detect one time query’s result and judge whether if it can be linked with history queries and leaks out some non-obvious privacy; Secondly, locally generalize the query results according to previous detect result.To detect and analysis the user query result in time, we propose a K-anonymity based privacy disclosure detection algorithm named K-Q, it can analysis and inference the current query result against history query results to explore whether current query leaks out the privacy or not, while assure a proved high detection accuracy. Existing inference detection methods present a scale problem on the storage needed to complete whole exploration, K-Q utilizes K-anonymity to optimize the storage problem. It uses a graph likewise data structure called KGraph to maintain the relation between history query node, which makes it possible to process current query result and all connected history output in time. Based on above of which K-Q can improve the detection accuracy and decrease response delay and also assure a fine-grained privacy protection level. The experiments on the real dataset demonstrate K-Q performs better than existing tuple inference algorithm T-D on detection accuracy and memory consumption.Within the detection result using K-Q algorithm, we implement a new generalization algorithm named G-Q, unlike the global methods it just generalizes the specific records’ attributes in current output which is proved to leak out privacy after linking with history published data. G-Q selects the attributes based on the K value determined in K-Q, only the attribute set whose value group’s size is under K could it be generalized, such a strategy decreases the information loss a lot and also keeps the data quality. The output processed by G-Q presents a certain privacy protection function in the system with predefined K. And the experiment also shows that G-Q can keep high output accuracy effectively.