评估简单基线方法在基于IDD的A*外存搜索中的表现
Evaluation of Baseline Methods for IDD-based SSD External Memory Search
- 采用简单基线方法实现基于即时去重的A*外存搜索
- 发现页缓存等操作系统机制显著提升外存访问效率
- 为外存搜索算法设计提供可复用的性能基准
许多复杂搜索问题无法仅依靠仅使用内存（RAM）的算法（如A*）解决。此前研究提出利用外部存储（如SSD、HDD）进行搜索，其容量远超内存，但多数工作集中于延迟去重策略或复杂的即时去重（IDD）方法，而对相对简单的IDD方法缺乏系统性研究。此外，操作系统层面用于管理与加速外部内存访问的机制（如页缓存）的影响也未被考察。本文填补这一空白，系统评估并分析了基于即时去重（IDD）的A*算法中若干简单基线方法的性能表现。
原文摘要 · Abstract (English)
Many difficult search problems cannot be solved by algorithms such as A* using only RAM. Search algorithms which use external memory such as SSDs and HDDs with much higher capacity than RAM have been proposed in previous work, but previous work has focused on delayed duplicate detection approaches, as well as complex immediate duplicate detection (IDD) methods, and relatively simple methods for IDD have not been systematically studied. In addition, the effect of OS-level mechanisms for managing and speeding up accesses to external memory, such as page caches, has not been studied. This paper addresses these gaps in the literature by evaluating and analyzing the performance of simple baseline approaches for IDD-based A*.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。