论文标题
访问自适应优先搜索树
Access-Adaptive Priority Search Tree
论文作者
论文摘要
在本文中，我们介绍了针对具有固定流程完成要求的应用的明显最坏情况有限的自适应算法的概念。这种应用要求保证在确定的时间间隔内完成一个过程，同时在此间隔内适应减少计算开销，例如，以减少总能源的使用情况。我们的主要贡献是访问自适应优先级搜索树（AAPST），它可以提供与Splay树相当的有效分配敏感性的性能，但在严格的 - 和O（logn）最佳 - 最佳 - 最糟糕的案例中。更具体地说，虽然splay树被猜想以提供最佳的自适应摊销查询复杂性，但对于单个查询，可能需要O（n），而AAPST则具有严格的O（logN）时间复杂性提供竞争性分布敏感的性能。这使AAPST更适合某些交互式（例如在线和实时）应用程序，例如具有可靠性限制的空间系统模块，涉及具有二级能量最小化激励措施的刚性过程完成时间间隔。
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(logn) 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(logn) 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.
