In this paper we introduce the notion of explicit worst-case bounded adaptive algorithms for applications with fixed process-completion requirements. Such applications demand that a process be guaranteed to complete within an established time interval while adaptively reducing computational overhead during that interval, e.g., so as to reduce total energy usage. Our principal contribution is the Access-Adaptive Priority Search Tree (AAPST), which can provide efficient distribution-sensitive performance comparable to the splay tree, but do so within strict—and <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11334_2025_598_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="61" /> </InlineMediaObject> <EquationSource Format="TEX">$O(\log n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> optimal—worst-case per-query bounds. More specifically, while the splay tree is conjectured to offer optimal adaptive amortized query complexity, it may require O(n) for individual queries, whereas the AAPST offers competitive distribution-sensitive performance with strict <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11334_2025_598_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="61" /> </InlineMediaObject> <EquationSource Format="TEX">$O(\log n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> time complexity. This makes the AAPST more suitable for certain interactive (e.g., online and real-time) applications such as space system modules with reliability constraints involving rigid process-completion time intervals with secondary energy-minimization incentives.

Access-adaptive priority search tree

期刊论文
发表日期：

2025年2月13日

查看全文

Haley Massa,
Jeffrey Uhlmann

摘要

In this paper we introduce the notion of explicit worst-case bounded adaptive algorithms for applications with fixed process-completion requirements. Such applications demand that a process be guaranteed to complete within an established time interval while adaptively reducing computational overhead during that interval, e.g., so as to reduce total energy usage. Our principal contribution is the Access-Adaptive Priority Search Tree (AAPST), which can provide efficient distribution-sensitive performance comparable to the splay tree, but do so within strict—and $O(\log n)$ $O (log n)$ optimal—worst-case per-query bounds. More specifically, while the splay tree is conjectured to offer optimal adaptive amortized query complexity, it may require O(n) for individual queries, whereas the AAPST offers competitive distribution-sensitive performance with strict $O(\log n)$ $O (log n)$ time complexity. This makes the AAPST more suitable for certain interactive (e.g., online and real-time) applications such as space system modules with reliability constraints involving rigid process-completion time intervals with secondary energy-minimization incentives.