吉林大学学报(工学版) ›› 2014, Vol. 44 ›› Issue (01): 164-170.doi: 10.13229/j.cnki.jdxbgxb201401028

• 论文 • 上一篇    下一篇

云计算中偏好top-k查询的正确性验证

盛刚1, 温涛1, 郭权2, 印莹3   

  1. 1. 东北大学 软件中心, 沈阳 110819;
    2. 大连东软信息学院 辽宁省网络安全与计算技术重点实验室, 辽宁 大连 116023;
    3. 东北大学 信息科学与工程学院, 沈阳 110819
  • 收稿日期:2012-07-30 出版日期:2014-01-01 发布日期:2014-01-01
  • 通讯作者: 温涛（1962-），男，教授，博士生导师.研究方向：网络安全.E-mail：wentao@neusoft.edu.cn E-mail:wentao@neusoft.edu.cn
  • 作者简介:盛刚（1978-），男，博士研究生.研究方向：云计算安全.E-mail：shenggang@neusoft.edu.cn
  • 基金资助:

    国家自然科学基金项目（61170169，61170168，61100028）；新世纪优秀人才支持计划项目（NCET-11-0085）；中央高校基本科研业务费基金项目（N110404017）.

Correctness authentication of preference top-k query in cloud computing

SHENG Gang1, WEN Tao1, GUO Quan2, YIN Ying3   

  1. 1. Software Center, Northeastern University, Shenyang 110819, China;
    2. Liaoning Key Lab of Network Security and Computing Technology, Neusoft Information Institute, Dalian 116023, China;
    3. College of Information Science and Engineering, Northeastern University, Shenyang 110819, China
  • Received:2012-07-30 Online:2014-01-01 Published:2014-01-01

RICH HTML

0   

PDF (PC)

2896

摘要：

为解决云计算环境下偏好top-k查询结果的正确性验证问题，在现有支配图的基础上，提出了基于哈希的验证支配图（ADG-H）和基于数字签名的验证支配图（ADG-S）。ADG-H能够有效地对一次性查询进行验证。而对于连续监控，采用ADG-H会引起大量的网络传输，因此提出了ADG-S，只有当数据更新影响到查询结果或验证对象时才进行必要的网络传输。实验表明了ADG-H和ADG-S的有效性。

关键词: 计算机应用, 偏好top-k查询, 验证对象, 支配图, 连续监控

Abstract:

The problem of correctness of authenticating results of preference top-k query in cloud computing is investigated. On the basis of existing dominant graph, Authenticated Dominant Graph with Hash (ADG-H) and Authenticated Dominant Graph with Signature (ADG-S) are proposed. ADG-H can be used to authenticate the result correctness of snapshot query effectively. For continuous monitor, an adoptation of ADG-H can incur prohibitive network overhead, so ADG-S was proposed, by which necessary network transmission can be conducted only when the query results or verification objects are affected by data update. Extensive experiments demonstrate the effectiveness of the proposed ADG-H and ADG-S.

Key words: computer application, preference top-k query, verification object, dominant graph, continuous monitor

中图分类号: 

  • TP309.2

[1] Ilyas Ihab F, Beskales George, Soliman Mohamed A. A survey of top-k query processing techniques in relational database systems[J]. ACM Computing Surveys, 2008, 40(4):1-58.

[2] Chang Yuan-chi, Lawrence Bergman, Vittorio Castelli, et al. The onion technique: indexing for linear optimization queries[C]//Proc of the 2000 ACM SIGMOD, New York: ACM, 2000:391-402.

[3] Hristidis Vagelis, Koudas Nick, Papakonstantinou Yannis. Prefer:a system for the efficient execution of multi-parametric ranked queries[C]//Proc of the 2001 ACM SIGMOD, New York: ACM, 2001: 259-270.

[4] Zou Lei, Chen Lei. Dominant graph: an efficient indexing structure to answer top-k queries[C]//Proc of the 24th ICDE, Washington: IEEE Computer Society, 2008:536-545.

[5] Hacigumus H, Iyer B R, Mehrotra S. Providing database as a service[C]//Proc of the 18th ICDE. Washingtong: IEEE Computer Society, 2002: 29-40.

[6] Merkle R. A certified digital signature[C]//Advance in Cryptology-Crypto'89, Berlin: Springer, LNCS 435, 1990: 218-238.

[7] Premkumar Devanbu, Michael Gertz, Charles Martel, et al. Authentic data publication over the internet[J]. Journal of Computer Security, 2003, 11(3):291-314.

[8] Xie Min, Wang Hai-xun, Yin Jian, et al. Integrity auditing of outsourced data[C]//Proc of the 33rd VLDB, New York: ACM, 2007: 782-793.

[9] 张敏, 洪澄, 陈驰. 一种服务器透明的外包数据库查询验证方案[J]. 计算机研究与发展, 2010, 47(1):182-190. Zhang Min, Hong Cheng, Chen Chi. Server transparent query authentication of outsourced database[J]. Journal of Computer Research and Development, 2010, 47(1):182-190.

[10] 咸鹤群, 冯登国. 外包数据库模型中的完整性检测方案[J].计算机研究与发展, 2010, 47(6):1107-1115. Xian He-qun, Feng Deng-guo. An integrity checking scheme in outsourced database model[J]. Journal of Computer Research and Development, 2010, 47(6):1107-1115.

[11] 温涛, 盛刚, 郭权, 等. 追加型数据库外包中的查询结果验证[J]. 计算机研究与发展, 2012, 49(10):2077-2085. Wen Tao, Sheng Gang, Guo Quan, et al. Query results authentication of outsourced append-only databases[J]. Journal of Computer Research and Development, 2012, 49(10): 2077-2085.

[12] Yang Yin, Stavros Papadopoulos, Dimitris Papadias, et al. Authenticated indexing for outsourced spatial databases[J]. The VLDB Journal, 2009, 18(3):631-648.

[13] Stavros Papadopoulos, Wang Li-xing, Yang Yin, et al. Authenticated multi-step nearest neighbor search[J]. IEEE Transactions on Knowledge and Data Engineering, 2011, 23(5): 641-654.

[14] Stavros Papadopoulos, Yang Yin, Dimitris Papadias. Continuous authentication on relational streams[J]. The VLDB Journal, 2010, 19(2): 161-180.
[1] 刘富,宗宇轩,康冰,张益萌,林彩霞,赵宏伟. 基于优化纹理特征的手背静脉识别系统[J]. 吉林大学学报(工学版), 2018, 48(6): 1844-1850.
[2] 王利民,刘洋,孙铭会,李美慧. 基于Markov blanket的无约束型K阶贝叶斯集成分类模型[J]. 吉林大学学报(工学版), 2018, 48(6): 1851-1858.
[3] 金顺福,王宝帅,郝闪闪,贾晓光,霍占强. 基于备用虚拟机同步休眠的云数据中心节能策略及性能[J]. 吉林大学学报(工学版), 2018, 48(6): 1859-1866.
[4] 赵东,孙明玉,朱金龙,于繁华,刘光洁,陈慧灵. 结合粒子群和单纯形的改进飞蛾优化算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1867-1872.
[5] 刘恩泽,吴文福. 基于机器视觉的农作物表面多特征决策融合病变判断算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1873-1878.
[6] 欧阳丹彤, 范琪. 子句级别语境感知的开放信息抽取方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1563-1570.
[7] 刘富, 兰旭腾, 侯涛, 康冰, 刘云, 林彩霞. 基于优化k-mer频率的宏基因组聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1593-1599.
[8] 桂春, 黄旺星. 基于改进的标签传播算法的网络聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1600-1605.
[9] 刘元宁, 刘帅, 朱晓冬, 陈一浩, 郑少阁, 沈椿壮. 基于高斯拉普拉斯算子与自适应优化伽柏滤波的虹膜识别[J]. 吉林大学学报(工学版), 2018, 48(5): 1606-1613.
[10] 车翔玖, 王利, 郭晓新. 基于多尺度特征融合的边界检测算法[J]. 吉林大学学报(工学版), 2018, 48(5): 1621-1628.
[11] 赵宏伟, 刘宇琦, 董立岩, 王玉, 刘陪. 智能交通混合动态路径优化算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.
[12] 黄辉, 冯西安, 魏燕, 许驰, 陈慧灵. 基于增强核极限学习机的专业选择智能系统[J]. 吉林大学学报(工学版), 2018, 48(4): 1224-1230.
[13] 傅文博, 张杰, 陈永乐. 物联网环境下抵抗路由欺骗攻击的网络拓扑发现算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1231-1236.
[14] 曹洁, 苏哲, 李晓旭. 基于Corr-LDA模型的图像标注方法[J]. 吉林大学学报(工学版), 2018, 48(4): 1237-1243.
[15] 侯永宏, 王利伟, 邢家明. 基于HTTP的动态自适应流媒体传输算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1244-1253.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 《吉林大学学报(工学版)》编辑部
地址：长春市人民大街5988号　电话：+86-431-85095297　传真：+86-431-85094074　E-mail: xbgxb@jlu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发