收藏切换
Functional Modeling, Verification and Access Optimization of Adaptive Priority Search Tree
收藏切换
Zhengkang Zuo1, 2, 3, Chao Zhou1, Yuhan Ke1, Zhen You1, Changjing Wang1, 2, 3, *
Journal of Computer Research and Development | 2026, 63(5) : 1139 - 1157
Less
收藏切换
Journal of Computer Research and Development | 2026, 63(5): 1139-1157
• Special Issue on Security and Trustworthiness for AI-Enabled Human-Cyber-Physical Systems •
Functional Modeling, Verification and Access Optimization of Adaptive Priority Search Tree
Full
Zhengkang Zuo1, 2, 3, Chao Zhou1, Yuhan Ke1, Zhen You1, Changjing Wang1, 2, 3, *
Affiliations
  • 1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022
  • 2Jiangxi Provincial Key Laboratory for High Performance Computing (Jiangxi Normal University), Nanchang 330022
  • 3Language Intelligence Research Center (Jiangxi Normal University), Nanchang 330022
  • born in 1980. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interest includes high-confidence and intelligent software

    born in 2001. Master candidate. Student member of CCF. His main research interest includes formal method

    born in 1998. Master candidate. Student member of CCF. His main research interest includes formal method

    born in 1982. PhD, associate professor, Master supervisor. Senior member of CCF. Her main research interests include formal methods, distributed virtual reality, and concurrent distributed computing

    born in 1977. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interests include high-confidence software and intelligent software

About Author:

born in 1980. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interest includes high-confidence and intelligent software

born in 2001. Master candidate. Student member of CCF. His main research interest includes formal method

born in 1998. Master candidate. Student member of CCF. His main research interest includes formal method

born in 1982. PhD, associate professor, Master supervisor. Senior member of CCF. Her main research interests include formal methods, distributed virtual reality, and concurrent distributed computing

born in 1977. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interests include high-confidence software and intelligent software

Published: 2026-05-01 doi: 10.7544/issn1000-1239.202550901
Outline
收藏切换

The priority search tree (PST) is a data structure that combines the characteristics of search trees and priority queues, enabling efficient retrieval of high-priority elements while maintaining worst-case search efficiency comparable to that of search trees. Nipkow et al. further modeled and mechanized the verification of PST with a static priority mechanism, laying an important foundation for its formal analysis and subsequent theoretical exploration. However, static priority mechanisms can lead to degraded performance under highly skewed access distributions, limiting their applicability in practice. To overcome this limitation, a functional adaptive priority search tree (FAPST) is proposed. FAPST adopts dynamic priority adjustment based on access frequency and is formally modeled and verified at the formal level to ensure functional correctness and reliability. This structure preserves balance and worst-case efficiency while adaptively responding to access patterns, thereby significantly improving the retrieval of frequently accessed elements. To further address the shifting nature of data hotspots in practical scenarios, a hotspot migration mechanism is introduced. This mechanism incorporates a priority decay strategy to accelerate responses to emerging hotspots and mitigate the stagnation of outdated ones. Experimental results demonstrate that, in both access-sensitive and hotspot-shifting workloads, the formally verified FAPST achieves notable reductions in the number of key function calls of 64.8% and 46.3% respectively, compared with conventional PSTs.

functional adaptive priority search tree  /  dynamic priority  /  functional modeling  /  mechanical verification  /  hotspot migration
左正康, 周超, 柯雨含, 游珍, 王昌晶. 自适应优先搜索树的函数式建模、验证及访问优化. 计算机研究与发展, 2026 , 63 (5) : 1139 -1157 . DOI: 10.7544/issn1000-1239.202550901
Zhengkang Zuo, Chao Zhou, Yuhan Ke, Zhen You, Changjing Wang. Functional Modeling, Verification and Access Optimization of Adaptive Priority Search Tree[J]. Journal of Computer Research and Development, 2026 , 63 (5) : 1139 -1157 . DOI: 10.7544/issn1000-1239.202550901
Year 2026 volume 63 Issue 5
70
30
Cite this Article
BibTeX
Article Info
doi: 10.7544/issn1000-1239.202550901
  • Receive Date:2025-12-15
  • Online Date:2026-11-17
  • Published:2026-05-01
Article Data
Affiliations
History
  • Received:2025-12-15
  • Revised:2026-03-05
Affiliations
    1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022
    2Jiangxi Provincial Key Laboratory for High Performance Computing (Jiangxi Normal University), Nanchang 330022
    3Language Intelligence Research Center (Jiangxi Normal University), Nanchang 330022
References
Share
https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/10.7544/issn1000-1239.202550901
Share to
QR

Scan QR to access full text

Cite this article
BibTeX
Citations
表12种不同金属材料的力学参数
科
Family
属数
Number of
genus
种数
Number of
species
占总种数比例
Percentage of
total species (%)
属
Genus
种数
Number of
species
占总种数比例
Percentage of total
species (%)
鹅膏菌科Amanitaceae 2 11 5.26 鹅膏菌属 Amanita 10 4.78
小菇科 Mycenaceae 2 12 5.74 丝盖伞属 Inocybe 5 2.39
多孔菌科 Polyporaceae 8 14 6.70 蜡蘑属 Laccaria 5 2.39
红菇科 Russulaceae 3 23 11.00 小皮伞属 Marasmius 6 2.87
小菇属 Mycena 11 5.26
光柄菇属 Pluteus 5 2.39
红菇属 Russula 17 8.13
栓菌属 Trametes 5 2.39
关闭全屏
  • BibTeX
  • EndNote
  • RefWorks
  • TxT