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

Special Issue: 2021 CCF中国区块链技术大会（CCF CBCC 2021）

• 2021 CCF China Blockchain Conference （CCF CBCC 2021） • Previous Articles Next 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]	Tingwei CHEN, Jiacheng ZHANG, Junlu WANG. Random validation blockchain construction for federated learning [J]. Journal of Computer Applications, 2024, 44(9): 2770-2776.
[2]	Xiaoling SUN, Danhui WANG, Shanshan LI. Dynamic ciphertext sorting and retrieval scheme based on blockchain [J]. Journal of Computer Applications, 2024, 44(8): 2500-2505.
[3]	Baoyan SONG, Junxiang DING, Junlu WANG, Haolin ZHANG. Consortium blockchain modification method based on chameleon hash and verifiable secret sharing [J]. Journal of Computer Applications, 2024, 44(7): 2087-2092.
[4]	He HUANG, Yu JIN. Cloud data auditing scheme based on voting and Ethereum smart contracts [J]. Journal of Computer Applications, 2024, 44(7): 2093-2101.
[5]	Jiao LI, Xiushan ZHANG, Yuanhang NING. Blockchain sharding method for reducing cross-shard transaction proportion [J]. Journal of Computer Applications, 2024, 44(6): 1889-1896.
[6]	Meihong CHEN, Lingyun YUAN, Tong XIA. Data classified and graded access control model based on master-slave multi-chain [J]. Journal of Computer Applications, 2024, 44(4): 1148-1157.
[7]	Lipeng ZHAO, Bing GUO. Blockchain consensus improvement algorithm based on BDLS [J]. Journal of Computer Applications, 2024, 44(4): 1139-1147.
[8]	Gaimei GAO, Jin ZHANG, Chunxia LIU, Weichao DANG, Shangwang BAI. Privacy protection scheme for crowdsourced testing tasks based on blockchain and CP-ABE policy hiding [J]. Journal of Computer Applications, 2024, 44(3): 811-818.
[9]	Haifeng MA, Yuxia LI, Qingshui XUE, Jiahai YANG, Yongfu GAO. Attribute-based encryption scheme for blockchain privacy protection [J]. Journal of Computer Applications, 2024, 44(2): 485-489.
[10]	Yifan WANG, Shaofu LIN, Yunjiang LI. Highway free-flow tolling method based on blockchain and zero-knowledge proof [J]. Journal of Computer Applications, 2024, 44(12): 3741-3750.
[11]	Ziqian CHEN, Kedi NIU, Zhongyuan YAO, Xueming SI. Review of blockchain lightweight technology applied to internet of things [J]. Journal of Computer Applications, 2024, 44(12): 3688-3698.
[12]	Tingting GAO, Zhongyuan YAO, Miao JIA, Xueming SI. Overview of on-chain and off-chain consistency protection technologies [J]. Journal of Computer Applications, 2024, 44(12): 3658-3668.
[13]	Miao JIA, Zhongyuan YAO, Weihua ZHU, Tingting GAO, Xueming SI, Xiang DENG. Progress and prospect of zero-knowledge proof enabling blockchain [J]. Journal of Computer Applications, 2024, 44(12): 3669-3677.
[14]	Kedi NIU, Min LI, Zhongyuan YAO, Xueming SI. Review of blockchain consensus algorithms for internet of things [J]. Journal of Computer Applications, 2024, 44(12): 3678-3687.
[15]	Yiting WANG, Wunan WAN, Shibin ZHANG, Jinquan ZHANG, Zhi QIN. Linkable ring signature scheme based on SM9 algorithm [J]. Journal of Computer Applications, 2024, 44(12): 3709-3716.

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