| 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 |
摘要:
| |||
| 摘要基于位置的服务（LBS）进行数据发布时，数据拥有者委派第三方服务商来发布数据，服务提供商代表数据拥有者向用户提供服务。但是LBS中的服务提供商可能是不可信的，这样会在LBS大数据的查询中形成由于商业目的而篡改的不准确的结果。LBS大数据中移动对象的位置随时间而变化，因此数据的动态性导致了索引结构大量的更新操作。该文提出了一种基于固定网格划分四叉树索引机制的空间范围查询验证技术，该技术采用网格划分的方法对空间数据进行划分，并采用四叉树对划分后的网格进行索引。该空间索引结构更新代价低，方便了数据的管理，缩短了检索的时间，四叉树索引对于范围查询具有较高的查询验证效率。该方法确保了用户查询结果的真实性、完整性和正确性。通过实验验证了该方法是有效的。 | |||
| 关键词 ：基于位置的服务,查询验证,四叉树,隐私保护,大数据 | |||
| 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 words：location-based servicequery authenticationquad-treeprivacy preservationbig data | |||
| 收稿日期: 2015-09-28 出版日期: 2016-07-22 | |||
| |||
| 基金资助:国家自然科学基金青年基金项目（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 |
图表:
 |
| 图１ LBS大数据商业模型的应用场景 |
 |
| 图２ 范围查询验证 |
 |
| 图３ 数字签名链 |
 |
| 图４ Merkle哈希树 |
 |
| 图５ LBS的四叉树索引 |
 |
| 图６ 固定网格划分四分树和验证对象 |
 |
| 图７ 服务器查询算法 |
 |
| 图８ 服务器查询算法 |
 |
| 图９ 数据集大小对查询结果的影响 |
 |
| 图１０ 数据集大小对查询时间的影响 |
 |
| 图１１ 查询时间对比图 |
参考文献:
| [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. |
相关文章:
|
