Efficient and Verifiable Skyline Computation on Blockchain System with Merkle B+ Tree Index
Hao Ding, Xuefeng Piao, Huihui Song, Jian Lì, Zhenzhou Ji, Meng Liu, Jie Liu, Wenjie Dong · 2024
With the advancement of blockchain technology, its application in data management and query processing has garnered increasing attention. However, as a distributed database system, blockchain currently falls short in supporting diverse data query requirements. Skyline computation, which identifies Pareto optimal solutions in multi-dimensional data, has become an increasingly necessary feature in blockchain environments. Traditional skyline computation methods struggle with inefficiency when handling large-scale and multi-dimensional data, and they lack effective verification mechanisms within a blockchain context. This paper proposes a multi-dimensional data index structure for skyline computation based on a hybrid blockchain architecture of full nodes and light nodes, utilizing Merkle tree and B+ tree. Additionally, an early pruning-based divide-and-conquer strategy is designed based on this index structure. This approach optimizes the skyline query process by computing local skylines to derive the global skyline. Simultaneously, by introducing Bloom filter, we reduce unnecessary I/O operations during result verification, enabling light nodes to perform verification operations more efficiently. Extensive experiments have demonstrated the effectiveness of our proposed scheme, which can improve query speed by an average of 90.08% compared to the BNL algorithm and by an average of 86.12% compared to the SFS algorithm.