随着网络信息技术的飞速发展,今天,信息在社会生活中扮演着越来越重要的角色。各行各业都需要从海量的数据中搜索对自身有用的信息来以满足发展。但这样有很大的可能导致个体隐私的泄露,随之而来的是对各种隐私信息(如日常习惯、敏感信息、不良历史、信誉程度、以往病史等)保护的研究,以减少信息泄露的风险。在多数的隐私保护模型中最有代表性的是K-匿名隐私保护模型,K-匿名模型经过长时间的研究,已经形成了较完善的理论体系。K-匿名数据则越来越多地出现在网络上。在传统数据库中,数据的确定性和精确性均是确定,而K-匿名数据却是不确定的,这就使得数据在存储、查询、挖掘以及管理方面遇到了各种问题,这些匿名的数据不能被企业很好的应用并发挥最大的功效。因此,提高数据的可用性是K-匿名模型亟待解决的问题,而查询是数据应用的一个主要操作。首先,根据Certainty(确定性问题)的定义即(?)I∈rep(T)(S(?)I),其中S是给定的元组集,T是给定的某一k-匿名表,从计算理论的角度,通过多项式时间归约的方法,证明该问题是CoNP-完全的。再结合已有的查询问题的复杂性为k-匿名隐私保护模型中不确定性数据查询方法的研究奠定了理论基础。其次,通过研究已有的不确定数据Top-k查询算法,再结合K-匿名数据来源的独特性和其表现形式的不同,探索了一种基于有向图的K-匿名数据的Top-k查询处理方法,用以提高K-匿名数据的可用性,满足更多不同的应用需求。(1)运用有向图建立高效的索引结构,并在此基础上提出了新的查询算法DiGU-Topk (U-Topk based on direct graph),该算法主要常用于一些需要排序的查询中；(2)采用优先队列对此算法进行优化,提出了DiGOPTU-Topk(U-Topk based on direct graph with optimize queue)算法,使得算法能够更快的收敛到目标顶点；(3)根据剪枝规则对有向图进行修剪,提出了DiGPU-Topk(U-Topk based on direct graph after pruning)算法,该算法使得每次都维护了最少的顶点即元组集。最后,对DiGU-Topk、DiGOPTU-Topk和DiGPU-Topk进行了相关的实验,通过实验结果证明了这三种查询方法的可用性,并对不同的数据量上查询效率和不同k值时的算法效率进行了对比,实验结果表明,随着数据量和k值的增长,算法的耗时呈线性增长。