新算法大幅降低超图对偶化内存占用，专注频次分析。
Space efficient implementation of hypergraph dualization in the D-basis algorithm
- 用逆向搜索渐进计算频次，避免存储全部蕴含关系
- 内存使用量显著下降，运行时间更优
- 适合关注属性频次而非完整蕴含集的分析场景
我们提出一种名为 Small Space 的新实现，显著降低 D-basis 算法在数据分析中的内存消耗。此前版本输出输入二值表属性集上所有成立的蕴含关系；新版本仅输出以固定后件属性为前提的蕴含关系中前件属性的出现频率。过去十年中，这类频率已成为数据分析的核心关注点。D-basis 依赖超图对偶化算法，而称为 Reverse Search 的对偶化实现可逐步计算频率，无需存储所有发现的蕴含关系。通过对比新旧版本的运行时间和最大内存占用，验证了 Small Space 实现的有效性。
原文摘要 · Abstract (English)
We present a new implementation of the $D$-basis algorithm called the Small Space which considerably reduces the algorithm's memory usage for data analysis applications. The previous implementation delivers the complete set of implications that hold on the set of attributes of an input binary table. In the new version, the only output is the frequencies of attributes that appear in the antecedents of implications from the $D$-basis, with a fixed consequent attribute. Such frequencies, rather than the implications themselves, became the primary focus in analysis of datasets where the $D$-basis has been applied over the last decade. The $D$-basis employs a hypergraph dualization algorithm, and a dualization implementation known as Reverse Search allows for the gradual computation of frequencies without the need for storing all discovered implications. We demonstrate the effectiveness of the Small Space implementation by comparing the runtimes and maximum memory usage of this new version with the current implementation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。