k-匿名数据上的聚集查询及其性质

J4 ›› 2014, Vol. 36 ›› Issue (01): 176-185.

k-匿名数据上的聚集查询及其性质

张君宝，刘国华，王碧颖，王梅，王羽婷，石丹妮，翟红敏

（东华大学计算机科学与技术学院，上海 201620）

收稿日期:2013-08-10 修回日期:2013-10-20 出版日期:2014-01-25 发布日期:2014-01-25
基金资助:
国家自然科学基金资助项目（61070032，61103046）

Aggregate query and its properties over kanonymous data

ZHANG Junbao,LIU Guohua,WANG Biying,WANG Mei,WANG Yuting,SHI Danni,ZHAI Hongmin

（School of Computer Science and Technology,Donghua University,Shanghai 201620,China）

Received:2013-08-10 Revised:2013-10-20 Online:2014-01-25 Published:2014-01-25

摘要/Abstract

摘要：

k-匿名数据中存在大量的有用信息，如何从k-匿名数据中得到有用的知识是目前亟待解决的问题。OLAP是知识发现的主要手段，聚集查询是OLAP的关键操作。为了解决k-匿名数据聚集查询问题，首先，给出了描述k-匿名数据的数据模型。其次，将聚集查询分为两个阶段，在第一阶段，给出k-匿名数据满足的性质和独立属性集的概念，利用k-匿名的性质和独立属性集给出求解满足查询约束的值和概率集合的算法，并将该集合作为第二阶段的输入。在第二阶段，给出聚集查询的语义。为了满足用户不同的查询需求，给出WITH子句约束及不同WITH子句约束的语义，作为聚集查询的第一阶段的补充。最后，讨论了聚集查询的性质，并用实验验证了查询的有效性。

关键词: 数据共享；OLAP；隐私保护； k-匿名；聚集查询

Abstract:

A great deal of information exists in kanonymous data. How to get useful information from kanonymous data is an urgent pending problem. OLAP (OnLine Analytical Processing) is the main approach of knowledge discovery, and the aggregate query is the key operation of OLAP. In order to solve the problem of aggregate query over kanonymous data, firstly, the definition of data model describing kanonymous data is given. Secondly, the aggregate query is separated into two phases. On the first phase, the properties of kanonymous data satisfication and the notion of Independent Attribute Set is presented. Using these properties and the Independent Attribute Set, an algorithm is given to compute the set of value and its probability that satisfy the query constraint, and then take the set as the input of second phase. On the second phase, the semantics of the aggregate query over kanonymous data are defined. In order to meet user’s different query, the definition and the semantic of WITH clause constraint is given as a supplement to first phase. At last, properties of the aggregate query are shown and an experiment is done to prove the validity of our method.

Key words: data sharing;on-line analytical processing;privacy preserve;kanonymity;aggregate query

张君宝，刘国华，王碧颖，王梅，王羽婷，石丹妮，翟红敏. k-匿名数据上的聚集查询及其性质[J]. J4, 2014, 36(01): 176-185.

ZHANG Junbao,LIU Guohua,WANG Biying,WANG Mei,WANG Yuting,SHI Danni,ZHAI Hon. Aggregate query and its properties over kanonymous data [J]. J4, 2014, 36(01): 176-185.

参考文献［13］

［1］	Samarati P, Sweeney L. Protecting privacy when disclosing information:kanonymity and its enforcement through generalization and suppression［R］. Technical Report, SRI International, 1998.
［2］	Samarati P. Protecting respondents’ identities in microdata release ［J］. IEEE Transactions on Knowledge and Data Engineering, 2001, 13 (6):10101027.
［3］	Burdick D, Deshpande P M, Jayram T S, et al. OLAP over uncertain and imprecise data［C］∥Proc of the 31st International Conference on Very Large Data Bases, 2005:970981.
［4］	Burdick D, Doan A H, Ramakrishnam R, et al. OLAP over imprecise data with domain constraints［C］∥Proc of the 33rd International Conference on Very Large Data Bases, 2007:3950.
［5］	Burdick D, Deshpande P M, Jayram T S, et al. Efficient allocation algorithms for OLAP over imprecise data［C］∥Proc of the 32nd International Conference on Very Large Data Bases, 2006:391402.
［6］	Burdick D, AnHai Doan, Ramakrishnan R, et al. OLAP over Imprecise data with domain constraints［C］∥Proc of the 33rd International Conference on Very Large Data Bases, 2007:3950.
［7］	Zhou Aoying, Jin Cheqing, Wang Guoren, et al. A survey on the management of uncertain data［J］. Chinese Journal of Computers, 2009, 32(1):116.(in Chinese)
［8］	Jayram T S, Kale S, Vee E. Efficient aggregation algorithms for probabilistic data［C］∥Proc of the 18th Annual ACMSIAM Symposium on Discrete Algorithms, 2007:346355.
［9］	Cormode G, Srivastava D, Shen E, et al. Aggregate query answering on possibilistic data with cardinality constraints［C］∥Proc of the 28th IEEE International Conference on Data Engineering, 2012：258269.
［10］	Roy A, Sarkar C, Angryk R A. Using taxonomies to perform aggregated querying over imprecise data［C］∥Proc of the 10th IEEE International Conference on Data Mining, 2010:989996.
［11］	Procopiuc C M, Srivastava D. Efficient table anonymization for aggregate query answering［C］∥Proc of the 25th International Conference on Data Engineering, 2009:12911294.
［12］	Arbee L, Chen P, Chiu Juishang, et al. Evaluating aggregate operations over imprecise data［J］. IEEE Transactions on Knowledge Data Engineering, 1996,8(2):273284.
［13］	Zhou Xun, Li Jianzhong, Shi Shengfei. Distributed algorithms for aggregation queries over uncertain data［C］∥Proc of the 26th Chinese Conference on Database, 2009:126134.(in Chinese)
［14］	RebolloMonedero D, Forné J, Pallarès E, et al. A modification of the Lloyd algorithm for kanonymous quantization［J］. Information Sciences, 2012,222:185202.
［15］	Zhang Qing,Koudas N,Srivastava D,et al.Aggregate query answering on anonymized tables［C］∥Proc of the 23rd International Conference on Data Engineering, 2007:116125.
［16］	Jung E, Ahn S, Hwang S. kARQ:kAnonymous ranking queries［C］∥Proc of the 15th International Conference, Database Systems for Advanced Applications，2010:414428.
［17］	Martínez S,Sánchez D,Valls A.Towards kanonymous nonnumerical data via semantic resampling［C］∥Proc of the 14th International Conference on Information Processing and Management of Uncertainty in KnowledgeBased System, 2012:519528.
［18］	RebolloMonedero D,Forné J,Soriano M.An algorithm for kanonymous microaggregation and clustering inspired by the design of distortionoptimized quantizers［J］. Data and Knowledge Engineering, 2011,70(10):892921.
［19］	Calì A, Calvanese D, De Giacomo G, et al. Data integration under integrity constraints［C］∥Proc of the 14th International Conference, 2002:262279.
	附中文参考文献：
［7］	周傲英, 金澈清, 王国仁,等. 不确定性数据管理技术研究综述［J］. 计算机学报, 2009, 32(1):116.
［13］	周逊, 李建中, 石胜飞. 不确定数据上聚集查询的分布式处理算法［C］∥第26届中国数据库学术会议论文集(A), 2009:126134.