The Top-k Query Problem Research Of The K-anonymous Data

With the rapid development of the network information technology, information plays an increasingly important role in people’s lives now. The industry needs to search for useful information from the massive amounts of data in order to meet their own needs. However, this practice may lead to the disclosure of individual privacy. For the sake of ensuring that the use of information to meet the needs of industry and personal privacy is not compromised, a variety of researches on searching for solutions to protect private information (such as daily habits, bad history, credit rating, past history, etc.) are started. Among them, the most representative of privacy protection model is K-anonymity privacy protection model. After years of research, K-anonymity privacy protection model has formed a complete theoretical system and will be increasingly applied to various fields. In order to protect private information, the K-anonymous methods imports the uncertainty of the data, but in traditional database applications the existent data are certain and accuracy. Because of the uncertainty of the K-anonymous data, the data storage, query, mining and management encountered problems. These anonymous data can’t be good used in applications. Therefore, all the applications which related with K-anonymous data require immediately solution to enhance the usability of the K-anonymous data. The query is a major operation on data applications which needs a solution too.Firstly,according to the Certainty problem, from the perspective of the Computational complexity theory,and The method of reduction by polynomial time, Prove that the problem is CoNP-completely. Combined with the complexity of the existing query problem for k anonymous privacy protection in the model uncertainty research laid the theoretical foundation of data query method.Secondly, through the research of the existing uncertain data Top-k query algorithm, Coupled with the uniqueness of the K-anonymous data source and its different forms, To explore a kind of based on directed graph K-anonymous Top-K query processing method of data, To improve the K-anonymous data availability, meet different application requirements.(1) Using directed graph to establish efficient index structure, On the basis of the new query algorithm DiGU-Topk is proposed, The algorithm is mainly used to need some sort of query;(2) The priority queue algorithm is optimized, DiGOPTU-Topk algorithm is proposed. Enables the algorithm to a faster convergence to the target ends;(3) According to the rules of pruning to trim directed graph, DiGPU-Topk algorithm is proposed, The algorithm makes the maintenance every time the least vertex is a tuple.Finally, The DiGU-Topk, DiGOPTU-Topk and DiGPU-Topk has carried on the related experiment, Through the experimental results show the availability of these3kinds of query methods, and the amount of data on the query efficiency and the algorithm efficiency of different k value was compared, The experimental results show that with the growth of the k value and quantity of the data, the algorithm takes a linear growth.