Please wait a minute...
 首页  期刊介绍 期刊订阅 联系我们 横山亮次奖 百年刊庆
 
最新录用  |  预出版  |  当期目录  |  过刊浏览  |  阅读排行  |  下载排行  |  引用排行  |  横山亮次奖  |  百年刊庆
清华大学学报(自然科学版)  2016, Vol. 56 Issue (7): 785-792    DOI: 10.16511/j.cnki.qhdxxb.2016.21.044
  计算机科学与技术 本期目录 | 过刊浏览 | 高级检索 |
LBS大数据中基于固定网格划分四叉树索引的查询验证
宁博, 裴晓霞, 李玉居, 裴新宇
大连海事大学 信息科学技术学院, 大连 116026
Query authentications based on a fixed grid partitioning quad-tree index in LBS big data
NING Bo, PEI Xiaoxia, LI Yuju, PEI Xinyu
School of Information Science and Technology, Dalian Maritime University, Dalian 116026, China
全文: PDF(1374 KB)  
输出: BibTeX | EndNote (RIS)      
摘要 基于位置的服务(LBS)进行数据发布时,数据拥有者委派第三方服务商来发布数据,服务提供商代表数据拥有者向用户提供服务。但是LBS中的服务提供商可能是不可信的,这样会在LBS大数据的查询中形成由于商业目的而篡改的不准确的结果。LBS大数据中移动对象的位置随时间而变化,因此数据的动态性导致了索引结构大量的更新操作。该文提出了一种基于固定网格划分四叉树索引机制的空间范围查询验证技术,该技术采用网格划分的方法对空间数据进行划分,并采用四叉树对划分后的网格进行索引。该空间索引结构更新代价低,方便了数据的管理,缩短了检索的时间,四叉树索引对于范围查询具有较高的查询验证效率。该方法确保了用户查询结果的真实性、完整性和正确性。通过实验验证了该方法是有效的。
服务
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章
宁博
裴晓霞
李玉居
裴新宇
关键词 基于位置的服务查询验证四叉树隐私保护大数据    
Abstract:When publishing data from location-based services (LBS), the data owner authorizes a third party publisher to be responsible for forwarding the appropriate result to the mobile clients. However, the service provider in the LBS big data may be susceptible to attacks which may lead to garbled or incorrect query results that can have commercial interest. This paper describes a quad-tree indexing structure based on a fixed grid partitioning mechanism for spatial range query authentication that partitions and indexes the spatial data. The position of an object in the LBS big data changes with time, so the data requires a dynamic index structure that can deal with many update operations. The spatial index structure presented here to update the price has low overhead, is convenient for data management systems, shortens the retrieval time for range queries, and uses a quad-tree index for high query efficiencies. The system ensures the authenticity, completeness and correctness of the query results. Tests show that this method is effective.
Key wordslocation-based service    query authentication    quad-tree    privacy preservation    big data
收稿日期: 2015-09-28      出版日期: 2016-07-22
ZTFLH:  TP309.2  
基金资助:国家自然科学基金青年基金项目(61202083)国家自然科学基金面上项目(61272369)辽宁省教育厅一般项目(L2014055)辽宁省电力有限公司科技项目(2015YF-67)中央高校基本科研业务费项目(3132016034)
引用本文:   
宁博, 裴晓霞, 李玉居, 裴新宇. LBS大数据中基于固定网格划分四叉树索引的查询验证[J]. 清华大学学报(自然科学版), 2016, 56(7): 785-792.
NING Bo, PEI Xiaoxia, LI Yuju, PEI Xinyu. Query authentications based on a fixed grid partitioning quad-tree index in LBS big data. Journal of Tsinghua University(Science and Technology), 2016, 56(7): 785-792.
链接本文:  
http://jst.tsinghuajournals.com/CN/10.16511/j.cnki.qhdxxb.2016.21.044  或          http://jst.tsinghuajournals.com/CN/Y2016/V56/I7/785
  图1 LBS大数据商业模型的应用场景
  图2 范围查询验证
  图3 数字签名链
  图4 Merkle哈希树
  图5 LBS的四叉树索引
  图6 固定网格划分四分树和验证对象
  图7 服务器查询算法
  图8 服务器查询算法
  图9 数据集大小对查询结果的影响
  图10 数据集大小对查询时间的影响
  图11 查询时间对比图
[1] Li F, Hadjieleftheriou M, Kollios G, et al. Dynamic authenticated index structures for outsourced databases[C]//Proceedings of the 2006 ACM SIGMOD international conference of data. Chicago, IL, USA:ACM, 2006:121-132.
[2] Hu H, Xu J, Chen Q, et al. Authenticating location-based services without compromising location privacy[C]//Proceedings of the 2012 ACM SIGMOD International Conference of Data. New York, NY, USA:ACM, 2012:301-312.
[3] Guttman A. R-trees:A Dynamic Index Structure for Spatial Searching[M]. ACM, 1984.
[4] Finkel R A, Bentley J L. Quad trees a data structure for retrieval on composite keys[J]. Acta informatica, 1974, 4(1):1-9.
[5] Xie M, Wang H, Yin J, et al. Integrity auditing of outsourced data[C]//Proceedings of the 33rd international conference on Very large data bases. Vienna, Austria:VLDB Endowment, 2007:782-793.
[6] 范红, 冯登国, 邹良惠. 数字签名技术及其在网络通信安全中的应用[J]. 中国科学院研究生院学报, 2001, 18(2):101-104. FAN Hong, FENG Dengguo, ZOU Lianghui. The digital signature technology and its application in the network communication security[J]. Graduate school of Chinese academy of sciences journal, 2001, 18(2):101-104.
[7] 卓先德, 赵菲, 曾德明. 非对称加密技术研究[J]. 四川理工学院学报:自然科学版, 2010, 23(5):562-564.ZHUO Xiande, ZHAO Fei, ZENG Deming. Authentication encryption technology research[J]. Journal of Sichuan University of Science and Engineering, 2010, 23(5):562-564.
[8] Narasimha M, Tsudik G. Authentication of outsourced databases using signature aggregation and chaining[C]//Database Systems for Advanced Applications. Jeju Island, Korea:Springer Berlin Heidelberg, 2006:420-436.
[9] Pang H H, Tan K L. Authenticating query results in edge computing[C]//Data Engineering, 2004. Proceedings of the 20th International Conference on. Chicago, IL, USA:IEEE, 2004:560-571.
[10] Merkle R C. A certified digital signature[C]//Advances in Cryptology-CRYPTO'89 Proceedings. New York, NY, USA:Springer, 1990:218-238.
[11] Yuan D, Wang X. Query authentication method based on merkle hash tree in outsourced database[J]. Computer Engineering, 2010, 36(4):115-117.
[12] Sion R. Query execution assurance for outsourced databases[C]//Proceedings of the 31st international conference on Very large data bases. Trondheim, Norway:VLDB Endowment, 2005:601-612.
[13] Mykletune, Naras Imuha M, Tsudik G. Authentication and integrity in outsourced databases[J]. ACM Transactions on Storage, 2006, 2(2):107-138.
[14] Lin X, Xu J, Hu H. Authentication of location-based skyline queries[C]//Proceedings of the 20th ACM international conference on Information and knowledge management. Glasgow, UK:ACM, 2011:1583-1588.
[15] Yiu M L, Lo E, Yung D. Authentication of moving kNN queries[C]//Data Engineering (ICDE), 2011 IEEE 27th International Conference on. IEEE, 2011:565-576.
[16] Hu H, Chen Q, Xu J. VERDICT:Privacy-preserving authentication of range queries in location-based services[C]//Data Engineering (ICDE), 2013 IEEE 29th International Conference on. IEEE, 2013:1312-1315.
[17] Jing Y, Hu L, Ku W S, et al. Authentication of k nearest neighbor query on road networks[J]. Knowledge and Data Engineering, IEEE Transactions on, 2014, 26(6):1494-1506.
[18] Wang J, Du X, Lu J, et al. Bucket-based authentication for outsourced databases[J]. Concurrency and Computation:Practice and Experience, 2010, 22(9):1160-1180.
[19] Samet H. The quadtree and related hierarchical data structures[J]. ACM Computing Surveys (CSUR), 1984, 16(2):187-260.
[20] Nievergelt J, Hinterberger H, Sevcik K C. The grid file:An adaptable, symmetric multikey file structures[J]. ACM Transactions on Database Systems (TODS), 1984, 9(1):38-71.
[1] 严素蓉, 冯小青, 廖一星. 基于矩阵分解的社会化推荐模型[J]. 清华大学学报(自然科学版), 2016, 56(7): 793-800.
[2] 孙智源, 陆化普. 考虑交通大数据的交通检测器优化布置模型[J]. 清华大学学报(自然科学版), 2016, 56(7): 743-750.
[3] 朱涵钰, 吴联仁, 吕廷杰. 社交网络用户隐私量化研究: 建模与实证分析[J]. 清华大学学报(自然科学版), 2014, 54(3): 402-406.
[4] 张珂, 丁巧林, 刘涛, 赵伟. 基于细节空间关系的自然语言组合描述方法[J]. 清华大学学报(自然科学版), 2014, 54(3): 341-347.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
版权所有 © 《清华大学学报(自然科学版)》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn