- 1次围观
概率基数估计器（HyperLogLog）、相似性草图（MinHash）和频率估计器（Count-Min Sketch）是基础性的近似数据结构，它们各自主要针对一个核心问题。我们提出了 DynamicDemiLog（DDL），这是一种统一了基数估计、集合相似性、包含关系、元素频率和组成信息的草图结构；该结构仅需对输入流进行一次扫描即可构建完成，且数据结构极小。 通过对 200,687 个 RefSeq 草图（对应 159,567 个生物体）建立倒排索引，DDL 可在 30 秒内完成整个数据库的全对全草图相似性比较（128 线程，使用索引）——按单次查询计，其速度比 Mash 对 91,282 个草图进行的暴力全对全比较快 375 倍以上；即使不使用索引，在草图分辨率加倍的情况下，DDL 仍快 31 倍。 DDL 通过为 LogLog 寄存器扩展尾数部分来实现这一点：每个寄存器存储一个采用浮点编码的哈希值，该值由整数指数（前导零计数）和小数尾数（次前导零位）构成，而不是仅仅存储整数形式的前导零计数。这保留了足够的哈希信息，从而可以进行有意义的逐寄存器比较——这是标准 6 位寄存器所不具备的性质——同时还改进了 LogLog 的基数估计机制，包括 DynamicLogLog 面向高吞吐流处理的早退出掩码。 在默认设置下，DDL 使用 10 位尾数（16 位寄存器、2,048 个桶、4 KB），对于无关的、大小相同的随机集合，其逐寄存器假匹配率可达到 0.018%（相比之下，LL6——一种基础的 HyperLogLog 实现——为 17.0%），从而仅通过寄存器比较即可实现加权 k-mer 一致性（WKID）、平均核苷酸一致性（ANI）、包含关系和完整性估计。 每寄存器 16 位的观测计数器以几乎可以忽略的额外计算成本提供元素频率信息，另加一个字节用于跟踪元素组成信息（在生物数据中即 GC 含量）。此外，DDL 的高特异性寄存器还支持一种倒排索引结构（DDLIndex），可在 O(B + M) 时间内回答针对包含 N 个草图的数据库的相似性查询，其中 M 为匹配的索引项数量；相比之下，两两比较的时间复杂度为 O(NxB)。
概率基数估计器（HyperLogLog）、相似性草图（MinHash）和频率估计器（Count-Min Sketch）是基础的近似数据结构，各自针对一个主要问题。我们提出 DynamicDemiLog（DDL），这是一种将基数估计、集合相似性、包含关系、元素频率和组成信息统一于单个微型数据结构中的草图，它仅通过对输入流进行一次扫描即可构建。利用 200,687 个 RefSeq 草图（159,567 个生物体）上的倒排索引，DDL 可在 30 秒内（128 线程，带索引）对完整数据库执行全对全草图相似性比较——在每次查询上比 Mash 对 91,282 个草图进行暴力全对全比较快超过 375 倍；即使不使用索引，也快 31 倍，同时草图分辨率加倍。DDL 在 LogLog 寄存器中增加了尾数：每个寄存器存储一个浮点编码的哈希值，由整数指数（前导零计数）和分数尾数（次前导零位）组成，而不仅仅是整数前导零计数。这样既保留了足够的哈希信息，能够进行有意义的逐寄存器比较——这是标准 6 位寄存器所不具备的特性——同时还改进了 LogLog 的基数估计机制，包括 DynamicLogLog 用于高吞吐流处理的早停掩码。采用默认的 10 位尾数（16 位寄存器、2,048 个桶、4 KB）时，DDL 在无关的随机同尺寸集合上实现了每寄存器 0.018% 的假匹配率（相比之下，基础 HyperLogLog 实现 LL6 为 17.0%），从而仅凭寄存器比较即可估计加权 k-mer 恒等性（WKID）、平均核苷酸恒等性（ANI）、包含度和完整性。一个 16 位的每寄存器观测计数器以极低的额外计算成本提供元素频率信息，而额外的一个字节则用于跟踪元素组成（对于生物数据而言为 GC 含量）。此外，DDL 的高特异性寄存器支持一种倒排索引结构（DDLIndex），可在 O(B + M) 时间内对数据库中 N 个草图回答相似性查询，其中 M 为匹配索引项的数量，相较于成对比较的 O(N×B) 更为高效。
📄 原文链接：https://www.biorxiv.org/content/10.64898/2026.06.12.731986v1?rss=1
🏷️ 草图数据结构 基数估计 相似性计算 k-mer分析 倒排索引 高通量序列比较