Spatio-Temporal Keyword Query in Hybrid-Storage Blockchain

doi:10.12068/j.issn.1005-3026.2023.12.004

Abstract

Abstract: Hybrid-storage blockchain supports trustworthy data sharing in supply-chain with multi-party collaboration through on-chain and off-chain storage model. Aiming at the inefficiency problem caused by the existing spatio-temporal keyword query method which reads all the off-chain data in advance and adopts B+ tree as index， a spatio-temporal keyword query method in hybrid-storage blockchain is proposed. Firstly， an attribute classified blockchain model is designed， and a B²M-BKM two-level index structure is designed within and between blocks to support relational query and efficiently retrieve block data. Secondly， an on-chain and off-chain spatio-temporal keyword query method is designed to improve the queries efficiency. Finally， experiments are carried out on public data sets to verify the effectiveness of the proposed method.

Key words: blockchain; on-off chain hybrid storage; two-level index structure; spatio-temporal keyword query; kD-tree

CLC Number:

TP39

JIANG Ji-ning， XIN Jun-chang， HAO Kun， HUANG Min5. Spatio-Temporal Keyword Query in Hybrid-Storage Blockchain[J]. Journal of Northeastern University(Natural Science), 2023, 44(12): 1696-1704.

References

[1]Liu X P，Wan C X，Xiong N N，et al.What happened then and there:top-k spatio-temporal keyword query［J］.Information Sciences，2018，453:281-301.
[2]Nakamoto S.Bitcoin:a peer-to-peer electronic cash system［EB/OL］.(2008-10-31)［2021-05-10］.http://bitcoin.org/bitcoin.pdf.
[3]Wood G.Ethereum:a secure decentralised generalised transaction ledger［J］.Ethereum Project Yellow Paper，2014，151:19-32.
[4]Amiri M J，Agrawal D，Abbadi A E.Caper:a cross-application permissioned blockchain［J］.Proceedings of the VLDB Endowment，2019，12(11):1385-1398.
[5]Sani A S，Yuan D，Bao W，et al.Xyreum:a high-perfor-mance and scalable blockchain for IIoT security and privacy［C］//2019 IEEE 39th International Conference on Distributed Computing Systems(ICDCS).Dallas，2019:1920-1930.
[6]Dorling K，Heinrichs J，Messier G G，et al.Vehicle routing problems for drone delivery［J］.IEEE Transactions on Systems，Man，and Cybernetics-Systems，2017，47(1):70-85.
[7]Zhu Y C，Zhang Z，Jin C Q，et al.SEBDB:semantics empowered blockchain database［C］//2019 IEEE 35th International Conference on Data Engineering(ICDE).Macau，2019:1820-1831.
[8]Li Y，Zheng K，Yan Y，et al.EtherQL:a query layer for blockchain system［C］//International Conference on Database Systems for Advanced Applications.Suzhou，2017:556-567.
[9]Peng Z，Wu H T，Xiao B，et al.VQL:providing query efficiency and data authenticity in blockchain systems［C］//2019 IEEE 35th International Conference on Data Engineering Workshops.Macau，2019:1820-1831.
[10]Mcconaghy T，Marques R，Müller A，et al.BigchainDB:a scalable blockchain database［EB/OL］.(2016-06-08)［2021-05-12］.https://www.bigchaindb.com/whitepaper/bigchaindbwhitepaper.pdf.
[11]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.Chengdu，2019:141-158.
[12]Wang H X，Xu C，Zhang C，et al.vChain:a blockchain system ensuring query integrity［C］//Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data.Amsterdam，2020:2693-2696.
[13]Qu Q，Nurgaliev I，Muzammal M，et al.On spatio-temporal blockchain query processing［J］.Future Generation Computer Systems，2019，98:208-218.
[14]Chowdhury M J M，Colman A，Kabir M A，et al.Blockchain as a notarization service for data sharing with personal data store［C］//2018 17th IEEE International Conference on Trust，Security and Privacy in Computing and Communications.Berlin，2018:1330-1335.
[15]Zhang C，Xu C，Xu J L，et al.GEM2-tree:a gas-efficient structure for authenticated range queries in blockchain［C］//2019 IEEE 35th International.Salt Lake City，2019:842-853.
[16]Zhang C，Xu C，Wang H X，et al.Authenticated keyword search in scalable hybrid-storage blockchains［C］//2021 IEEE 37th International Conference on Data Engineering(ICDE).Chania，2021:996-1007.
[17]潘晓，于启迪，马昂，等.支持OR语义的高效受限Top-k空间关键字查询技术［J］.软件学报，2020，31(10):3197-3215.(Pan Xiao，Yu Qi-di，Ma Ang，et al.Efficient algorithm of top-k spatial keyword search with OR semantics［J］.Journal of Software，2020，31(10):3197-3215.)
[18]Huang Q L，Du J B，Yan G Y，et al.Privacy-preserving spatio-temporal keyword search for outsourced location-based services［J］.IEEE Transactions on Services Computing，2022，15(6):3443-3456.
[19]Mahapatra R P，Chakraborty P S.Comparative analysis of nearest neighbor query processing techniques ［C］//3rd International Conference on Recent Trends in Computing(ICRTC).Delhi，2015:1289-1298.
[20]Sarwat M，Levandoski J J，Eldawy A，et al.LARS^*:an efficient and scalable location-aware recommender system［J］.Transactions on Knowledge and Data Engineering，2012，6(1):1-16.
[21]Levandoski J J，Sarwat M，Eldawy A，et al.LARS:a location-aware recommender system［C］//2012 IEEE 28th International Conference on Data Engineering.Washington D C，2012:450-461.
[22]Yelp Dataset［EB/OL］.(2020-01-30)［2021-05-12］.http://www.kaggle.com/yelp-dataset/yelp-dataset.(上接第1695页)
[16]Agárdi A，Kovács L，Bányai T.An attraction map framework of a complex multi-echelon vehicle routing problem with random walk analysis［J］.Applied Sciences，2021，11:2100.
[17]梁承姬，崔佳诚，丁一.基于混合蚁群算法的车辆路径问题研究［J］.重庆交通大学学报(自然科学版)，2016，35(3):94-99.(Liang Cheng-ji，Cui Jia-cheng，Ding Yi.Vehicle routing problem based on hybrid ant colony algorithm［J］.Journal of Chongqing Jiaotong University(Natural Science)，2016，35(3):94-99.)
[18]张晓楠，范厚明.混合分散搜索算法求解带容量约束车辆路径问题［J］.控制与决策，2015，30(11):1937-1944.(Zhang Xiao-nan，Fan Hou-ming.Hybrid scatter search algorithm for capacitated vehicle routing problem［J］.Control and Decision，2015，30(11):1937-1944.)
[19]Teoh B E，Ponnambalam S G，Kanagaraj G.Differential evolution algorithm with local search for capacitated vehicle routing problem［J］.International Journal of Bio-inspired Computation，2015，7(5):321-342.
[20]夏小云，庄鹤林，杨火根，等.自适应大邻域搜索的人工蜂群算法求解带容量约束车辆路径问题［J］.计算机集成制造系统，2022，28(11):3545-3557.(Xiao Xiao-yun，Zhuang He-lin，Yang Huo-gen，et al.Adaptive large neighborhood search based artificial bee colony algorithm for CVRP［J］.Computer Integrated Manufacturing Systems，2022，28(11):3545-3557.)