面向时空数据的区块链构建及查询方法

doi:10.11772/j.issn.1001-9081.2021111933

《计算机应用》唯一官方网站 ›› 2022, Vol. 42 ›› Issue (11): 3429-3437.DOI: 10.11772/j.issn.1001-9081.2021111933

所属专题： 2021 CCF中国区块链技术大会（CCF CBCC 2021）

• 2021 CCF中国区块链技术大会（CCF CBCC 2021） • 上一篇下一篇

面向时空数据的区块链构建及查询方法

华亚洲, 丁琳琳(), 陈泽, 王俊陆, 朱珠

辽宁大学信息学院，沈阳 110036

收稿日期:2021-11-13 修回日期:2021-12-20 接受日期:2022-01-05 发布日期:2022-01-24 出版日期:2022-11-10
通讯作者: 丁琳琳
作者简介:华亚洲（1996—），男，山东济宁人，硕士研究生，主要研究方向：区块链
丁琳琳（1983—），女，辽宁锦州人，副教授，博士，CCF会员，主要研究方向：大数据管理、图数据管理、区块链 dinglinlin@lnu.edu.cn
陈泽（1996—），男，辽宁锦州人，硕士研究生，CCF会员，主要研究方向：自然语言处理、数据挖掘
王俊陆（1988—），男，辽宁丹东人，博士研究生，CCF会员，主要研究方向：区块链、时序流
朱珠（1983—），女，贵州赫章人，副教授，博士，CCF会员，主要研究方向：物流与供应链、区块链。
基金资助:
国家自然科学基金资助项目(72102096)

Blockchain construction and query method for spatio‑temporal data

Yazhou HUA, Linlin DING(), Ze CHEN, Junlu WANG, Zhu ZHU

College of Information，Liaoning University，Shenyang Liaoning 110036，China

Received:2021-11-13 Revised:2021-12-20 Accepted:2022-01-05 Online:2022-01-24 Published:2022-11-10
Contact: Linlin DING
About author:HUA Yazhou， born in 1996， M. S. candidate. His research interests include blockchain.
DING Linlin， born in 1983， Ph. D.， associate professor. Her research interests include big data management，graph data management， blockchain.
CHEN Ze， born in 1996， M. S. candidate. His research interests include natural language processing， data mining.
WANG Junlu， born in 1988， Ph. D. candidate. His research interests include blockchain， time series flow.
ZHU Zhu， born in 1983， Ph. D.， associate professor. Her research interests include logistics and supply chain， blockchain.
Supported by:
National Natural Science Foundation of China(72102096)

摘要/Abstract

摘要：

时空数据作为一种同时具有时间维度及空间维度的数据类型，被广泛应用于供应链管理、电子商务等领域，它的完整性及安全性在实际应用中具有重要意义。针对目前时空数据集中式存储方式存在数据不透明且易被篡改的问题，将区块链技术的去中心化、防篡改、可追溯等特性与时空数据管理相结合，提出面向时空数据的区块链构建及查询方法。首先，提出一种基于改进图型区块链（Block?DAG）的时空数据区块链架构ST_Block?DAG；其次，为了提升时空数据的存储及查询效率，在ST_Block?DAG区块链内部采取基于四叉树及单链表的结构存储时空数据；最后，在ST?Block?DAG存储结构基础上实现了多种时空数据查询算法，如单值查询、范围查询等。实验结果表明，与STBitcoin、Block?DAG以及STEth相比，ST_Block?DAG的时空数据处理效率提升了70%以上，时空数据综合查询性能提升了60%以上。所提方法能够实现时空数据的快速存储及查询，可以有效支持时空数据的管理。

关键词: 区块链, 时空数据, 存储架构, 索引结构, 查询算法

Abstract:

As a type of data with both temporal and spatial dimensions， spatio?temporal data is widely used in supply chain management， e?commerce and other fields， which integrity and security are of great importance in practical applications. Aiming at the problems of lack of transparency and easily being tampered of data in the current centralized storage of spatial?temporal datasets， a blockchain construction and query method for spatio?temporal data was proposed by combining the decentralized， tamper?proof and traceable characteristics of blockchain technology with spatio?temporal data management. Firstly， an improved Directed Asycline Graph Blockchain （Block?DAG） based blockchain architecture for spatio?temporal data， namely ST_Block?DAG （Spatio?Temporal Block?DAG）， was proposed. Secondly， to improve the efficiency of spatio?temporal data storage and query， a storage structure based on quadtree and single linked list was adopted to store spatio?temporal data in the ST_Block?DAG blockchain. Finally， a variety of spatio?temporal data query algorithms were implemented on the basis of the storage structure of ST_Block?DAG， such as single?value query and range query. Experimental results show that compared with STBitcoin （Spatio?Temporal Bitcoin）， Block?DAG and STEth （Spatio?Temporal Ethereum）， ST_Block?DAG has the spatio?temporal data processing efficiency improved by more than 70% and the comprehensive query performance of spatio?temporal data improved by more than 60%. The proposed method can realize fast storage and query of spatio?temporal data， and can effectively support the management of spatio?temporal data.

Key words: blockchain, spatio?temporal data, storage architecture, index structure, query algorithm

中图分类号:

TP311

华亚洲, 丁琳琳, 陈泽, 王俊陆, 朱珠. 面向时空数据的区块链构建及查询方法[J]. 计算机应用, 2022, 42(11): 3429-3437.

Yazhou HUA, Linlin DING, Ze CHEN, Junlu WANG, Zhu ZHU. Blockchain construction and query method for spatio‑temporal data[J]. Journal of Computer Applications, 2022, 42(11): 3429-3437.

图/表 7

图1 粗粒度Block?DAG结构

Fig. 1 Coarse?grained Block?DAG structure

图2 时空数据区块链网络架构

Fig. 2 Network architecture of spatio?temporal data blockchain

图3 时空范围划分及F?L Tree节点划分过程

Fig. 3 Spatio?temporal division and F?L Tree node division process

图4 查询结果验证过程

Fig. 4 Query result verification process

图5 四种架构的数据处理时间比较

Fig. 5 Comparison of data processing time among four architectures

图6 单区块下单值查询与范围查询比较

Fig. 6 Comparison of single?value query and range query under single block

图7 多区块下单值查询与范围查询比较

Fig. 7 Comparison of single?value query and range query under multiple blocks

参考文献 20

1	NAKAMOTO S. Bitcoin： a peer‑to‑peer electronic cash system［EB/OL］. ［2021-07-25］.. 10.2139/ssrn.3977007
2	BUTERIN V. A next‑generation smart contract and decentralized application platform［EB/OL］. ［2021-07-28］. . 10.1007/978-981-15-6218-1_9
3	WOOD G. Ethereum： a secure decentralised generalised transaction ledger［EB/OL］. ［2021-07-30］..
4	XU J， WEI L， ZHANG Y， et al. Dynamic fully homomorphic encryption‑based Merkle tree for lightweight streaming authenticated data structures［J］. Journal of Network and Computer Applications， 2018， 107： 113-124. 10.1016/j.jnca.2018.01.014
5	袁勇，王飞跃. 区块链技术发展现状与展望［J］. 自动化学报， 2016， 42（4）： 481-494. 10.16383/j.aas.2016.c160158
	YUAN Y， WANG F Y. Blockchain： the state of the art and future trends［J］. Acta Automatica Sinica， 2016， 42（4）：481-494. 10.16383/j.aas.2016.c160158
6	ANDROULAKI E， BARGER A， BORTNIKOV V， et al. Hyperledger Fabric： a distributed operating system for permissioned blockchains［C］// Proceedings of the 13th EuroSys Conference. New York： ACM， 2018： No.30. 10.1145/3190508.3190538
7	EL‑HINDI M， BINNIG C， ARASU A， et al. BlockchainDB — a shared database on blockchains［J］. Proceedings of the VLDB Endowment， 2019， 12（11）： 1597-1609. 10.14778/3342263.3342636
8	QU Q， NURGALIEV I， MUZAMMAL M， et al. On spatio‑temporal blockchain query processing［J］. Future Generation Computer Systems， 2019， 98： 208-218. 10.1016/j.future.2019.03.038
9	中国科学院深圳先进技术研究院. 一种区块链时空数据查询方法，系统及电子设备： 201810765882.9［P］. 2018-09-28. 10.26420/austinjnutrmetab.2020.1081
	Shenzhen Institute of Advanced Technology， Chinese Academy of Sciences. A blockchain spatio‑temporal data query method， system and electronic device： 201810765882.9［P］. 2018-09-28. 10.26420/austinjnutrmetab.2020.1081
10	中国地质大学（武汉. 一种基于区块链的时间序列数据组织记录方法及系统： 201810351188.2［P］. 2018-11-16. 10.25103/jestr.114.13
	China University of Geosciences （Wuhan）. A time series data organization and recording method and system based on blockchain： 201810351188.2［P］. 2018-11-16. 10.25103/jestr.114.13
11	RUAN P C， DINH T T A， LIN Q， et al. LineageChain： a fine‑ grained， secure and efficient data provenance system for blockchains［J］. The VLDB Journal， 2021， 30（1）：3-24. 10.1007/s00778-020-00646-1
12	XU C， ZHANG C， XU J L. vChain： enabling verifiable boolean range queries over blockchain databases［C］// Proceedings of the 2019 International Conference on Management of Data. New York： ACM， 2019： 141-158. 10.1145/3299869.3300083
13	CHAN W， OLMSTED A. Ethereum transaction graph analysis［C］// Proceedings of the 12th International Conference for Internet Technology and Secured Transactions. Piscataway： IEEE， 2017： 498-500. 10.23919/icitst.2017.8356459
14	SALAH K， NIZAMUDDIN N， JAYARAMAN R， et al. Blockchain‑based soybean traceability in agricultural supply chain［J］. IEEE Access， 2019， 7： 73295-73305. 10.1109/access.2019.2918000
15	傅易文晋，陈华辉，钱江波，等. 面向时空数据的区块链研究综述［J］. 计算机工程， 2020， 46（3）：1-10. 10.19678/j.issn.1000-3428.0056025
	FU Y W J， CHEN H H， QIAN J B， et al. Survey of blockchain research for spatiotemporal data［J］. Computer Engineering， 2020， 46（3）：1-10. 10.19678/j.issn.1000-3428.0056025
16	WANG J P， WANG H. Monoxide： scale out blockchain with asynchronous consensus zones［C］// Proceedings of the 16th USENIX Conference on Networked Systems Design and Implementation. Berkeley： USENIX Association， 2019：95-112.
17	WORLEY C， SKJELLUM A. Blockchain tradeoffs and challenges for current and emerging applications： generalization， fragmentation， sidechains， and scalability［C］// Proceedings of the 2018 IEEE International Conference on Internet of Things/ Green Computing and Communications/ Cyber， Physical and Social Computing/ Smart Data/ Blockchain/ Computer and Information Technology. Piscataway： IEEE 2018：1582-1587. 10.1109/cybermatics_2018.2018.00265
18	HELMER S， ROGGIA M， IOINI N EL， et al. EthernityDB — integrating database functionality into a blockchain［C］// Proceedings of the 2018 European Conference on Advances in Databases and Information Systems， CCIS 909. Cham： Springer， 2018：37-44
19	张长贵，张岩峰，李晓华，等. 区块链新技术综述：图型区块链和分区型区块链［J］. 计算机科学， 2020， 47（10）：282-289. 10.11896/jsjkx.191000057
	ZHANG C G， ZHANG Y F， LI X H， et al. Survey of new blockchain techniques： DAG based blockchain and sharding based blockchain［J］. Computer Science， 2020， 47（10）：282-289. 10.11896/jsjkx.191000057
20	VAN RENESSE R， DUMITRIU D， GOUGH V， et al. Efficient reconciliation and flow control for anti‑entropy protocols［C］// Proceedings of the 2nd Workshop on Large‑Scale Distributed Systems and Middleware. New York： ACM， 2008： No.6. 10.1145/1529974.1529983

[1]	陈廷伟, 张嘉诚, 王俊陆. 面向联邦学习的随机验证区块链构建[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2770-2776.
[2]	孙晓玲, 王丹辉, 李姗姗. 基于区块链的动态密文排序检索方案[J]. 《计算机应用》唯一官方网站, 2024, 44(8): 2500-2505.
[3]	黄河, 金瑜. 基于投票和以太坊智能合约的云数据审计方案[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2093-2101.
[4]	李欢欢, 黄添强, 丁雪梅, 罗海峰, 黄丽清. 基于多尺度时空图卷积网络的交通出行需求预测[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2065-2072.
[5]	李皎, 张秀山, 宁远航. 降低跨分片交易比例的区块链分片方法[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1889-1896.
[6]	赵莉朋, 郭兵. 基于BDLS的区块链共识改进算法[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1139-1147.
[7]	陈美宏, 袁凌云, 夏桐. 基于主从多链的数据分类分级访问控制模型[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1148-1157.
[8]	高改梅, 张瑾, 刘春霞, 党伟超, 白尚旺. 基于区块链与CP-ABE策略隐藏的众包测试任务隐私保护方案[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 811-818.
[9]	周思艺, 李天瑞. 面向源-目的地流的多元时空数据可视分析[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 452-459.
[10]	马海峰, 李玉霞, 薛庆水, 杨家海, 高永福. 用于实现区块链隐私保护的属性基加密方案[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 485-489.
[11]	王一帆, 林绍福, 李云江. 基于区块链和零知识证明的高速公路自由流收费方法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3741-3750.
[12]	王伊婷, 万武南, 张仕斌, 张金全, 秦智. 基于SM9算法的可链接环签名方案[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3709-3716.
[13]	刘德渊, 张金全, 张鑫, 万武南, 张仕斌, 秦智. 基于无证书签密的跨链身份认证方案[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3731-3740.
[14]	孙科硕, 高海英, 宋杨. 面向公有区块链上的私有区块链的多权威属性加密方案[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3699-3708.
[15]	方鹏, 赵凡, 王保全, 王轶, 蒋同海. 区块链3.0的发展、技术与应用[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3647-3657.

面向时空数据的区块链构建及查询方法

Blockchain construction and query method for spatio‑temporal data

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 20

相关文章 15

编辑推荐

Metrics