Blockchain construction and query method for spatio‑temporal data

doi:10.11772/j.issn.1001-9081.2021111933

Journal of Computer Applications ›› 2022, Vol. 42 ›› Issue (11): 3429-3437.DOI: 10.11772/j.issn.1001-9081.2021111933

• 2021 CCF China Blockchain Conference （CCF CBCC 2021） • Previous Articles

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)

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

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

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

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

Abstract

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

摘要：

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

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

CLC Number:

TP311

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.

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

Figures/Tables 7

Fig. 1 Coarse?grained Block?DAG structure

Fig. 2 Network architecture of spatio?temporal data blockchain

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

Fig. 4 Query result verification process

Fig. 5 Comparison of data processing time among four architectures

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

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

References 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]	Wei LIU, Cong ZHANG, Wei SHE, Xuan SONG, Zhao TIAN. Data trusted traceability method based on Merkle mountain range [J]. Journal of Computer Applications, 2022, 42(9): 2765-2771.
[2]	Yangnan GUO, Wenbao JIANG, Shuai YE. Supervisable blockchain anonymous transaction system model [J]. Journal of Computer Applications, 2022, 42(9): 2757-2764.
[3]	Hongliang TIAN, Jiayue WANG, Chenxi LI. Data storage scheme based on hybrid algorithm blockchain and node identity authentication [J]. Journal of Computer Applications, 2022, 42(8): 2481-2486.
[4]	Xu WANG, Yumin SHEN, Xiaoyun XIONG, Peng LI, Jinlong WANG. Data management method for building internet of things based on Hashgraph [J]. Journal of Computer Applications, 2022, 42(8): 2471-2480.
[5]	Jie ZHANG, Shanshan XU, Lingyun YUAN. Internet of things access control model based on blockchain and edge computing [J]. Journal of Computer Applications, 2022, 42(7): 2104-2111.
[6]	Chunming TANG, Yuqing CHEN, Zidi ZHANG. Improved consensus algorithm based on binomial swap forest and HotStuff [J]. Journal of Computer Applications, 2022, 42(7): 2112-2117.
[7]	Zheng DI, Yifan CAO, Chao QIU, Tao LUO, Xiaofei WANG. New computing power network architecture and application case analysis [J]. Journal of Computer Applications, 2022, 42(6): 1656-1661.
[8]	Yuntao XU, Junwu ZHU, Binwen SUN, Maosheng SUN, Sihai CHEN. Election-based supply chain： a supply chain autonomy framework based on blockchain [J]. Journal of Computer Applications, 2022, 42(6): 1770-1775.
[9]	Yang LI, Long XU, Yanqiang LI, Shaopeng LI. Smart contract-based access control architecture and verification for internet of things [J]. Journal of Computer Applications, 2022, 42(6): 1922-1931.
[10]	Xiuli REN, Lei ZHANG. Improved multi-primary-node consensus mechanism based on practical Byzantine fault tolerance [J]. Journal of Computer Applications, 2022, 42(5): 1500-1507.
[11]	Jiagui XIE, Zhiping LI, Jian JIN. Cross-chain mechanism based on Spark blockchain [J]. Journal of Computer Applications, 2022, 42(2): 519-527.
[12]	Rui SUN, Chao LI, Wei WANG, Endong TONG, Jian WANG, Jiqiang LIU. Research progress of blockchain‑based federated learning [J]. Journal of Computer Applications, 2022, 42(11): 3413-3420.
[13]	Shanshan LI, Yanze WANG, Yinglong ZOU, Huanlei CHEN, He ZHANG, Ou WU. Consensus transaction trajectory visualization tracking method for Fabric based on custom logs [J]. Journal of Computer Applications, 2022, 42(11): 3421-3428.
[14]	Hexiong CHEN, Yuwei LUO, Yunkai WEI, Wei GUO, Feilu HANG, Zhengxiong MAO, Zhenhong ZHANG, Yingjun HE, Zhenyu LUO, Linjiang XIE, Ning YANG. Blockchain-based data frame security verification mechanism in software defined network [J]. Journal of Computer Applications, 2022, 42(10): 3074-3083.
[15]	Li LI, Yi WU, Zhikun YANG, Yunpeng CHEN. Medical electronic record sharing scheme based on sharding-based blockchain [J]. Journal of Computer Applications, 2022, 42(1): 183-190.

Blockchain construction and query method for spatio‑temporal data

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 20

Related Articles 15

Recommended Articles

Metrics