python - 当语料库有 100 亿个独特的 DNA 序列时，如何使用 BK 树实现快速模糊搜索引擎？

Question

我正在尝试使用 BK-tree python 中的数据结构来存储具有约 100 亿个条目 ( 1e10 ) 的语料库，以实现快速模糊搜索引擎。
一旦我将超过约 1000 万( 1e7 )个值添加到单个 BK 树中，我开始发现查询性能显着下降。
我想将语料库存储到一千个 BK 树的森林中并并行查询它们。
这个想法听起来可行吗？我应该同时创建和查询 1,000 个 BK 树吗？为了在这个语料库中使用 BK 树，我还能做什么。
我用 pybktree.py我的查询旨在查找编辑距离内的所有条目 d .
是否有一些架构或数据库可以让我存储这些树？
备注 :我没有用完内存，而是树开始效率低下(大概每个节点都有太多子节点)。

Answer 1

很少的想法
BK-trees
感谢 Ben Hoyt 及其与 issue 的链接我将从中吸取。话虽如此，上述问题的第一个观察结果是 BK 树并不完全是对数的。根据你告诉我们的，你通常的 d 是 ~6，这是你的字符串长度的 3/10。不幸的是，这意味着如果我们从问题中查看表格，您将获得介于 O(N^0.8) 到 O(N) 之间的复杂度。在乐观的情况下
指数为 0.8(可能会稍微差一些)，您的 10B 条目的改进系数约为 100。因此，如果您有一个相当快的 BK 树实现，那么使用它们或将它们用作进一步优化的基础仍然是值得的。
这样做的缺点是，即使您并行使用 1000 棵树，您也只能从并行化中获得改进，因为树的性能取决于 d 而不是树中节点的数量。但是，即使您用一台大型机器一次运行所有 1000 棵树，我们也会在大约 1000 万个节点/树上，您报告说它很慢。尽管如此，在计算方面，这似乎是可行的。
蛮力方法
如果你不介意付一点钱，我会研究一下谷歌云大查询之类的东西，如果这不与某种数据 secret 性发生冲突。他们将为您强力解决方案 - 收费。当前的费率是 5 美元/TB 的查询。您的数据集是 ~10B 行 * 20chars。每个字符占用一个字节，一个查询将占用 200GB，所以如果你走懒惰的方式，每个查询大约 1 美元。
但是，由于费用是按列中数据的每个字节而不是按问题的复杂性计算的，您可以通过将字符串存储为位来改进这一点 - 每个字母 2 位，这将为您节省 75% 的费用。
进一步改进，您可以将查询编写为一次请求十几个字符串的方式。您可能需要谨慎使用一批类似的字符串来进行查询，以避免过多的一次性结果阻塞结果。
BK 树的暴力破解
因为如果你按照上面的路线走，你将不得不根据数量付费，所需计算量减少约 100 倍，价格减少约 100 倍，这可能很有用，特别是如果你有很多查询运行。
但是，您需要找到一种方法将这棵树存储在多层数据库中以递归查询，因为 Bigquery 定价取决于查询表中的数据量。
为查询的递归处理构建智能批处理引擎以最小化成本可能是有趣的优化练习。
语言选择
还有一件事。虽然我认为 Python 是一种用于快速原型(prototype)设计、分析和总体代码思考的好语言，但您已经过了那个阶段。您目前正在寻找一种方法来做 具体、定义明确且经过深思熟虑 操作尽可能快。 Python 不是一种很好的语言，因为 this example显示。虽然我在 Python 中使用了我能想到的所有技巧，但 Java 和 C 解决方案仍然快了几倍。 (更不用说打败我们所有人的 rust 了——但他也通过算法打败了我们，所以很难比较。)所以如果你从 python 转向一种更快的语言，你可能会获得另一个或十个甚至更多的因素性能增益。这可能是另一个有趣的优化练习。
备注 :我对估计相当保守，因为fuzzywuzzy已经提供在后台使用C库，所以我不太确定有多少工作仍然依赖于python。我在类似情况下的经验是，从纯 python(或更糟，纯 R)到编译语言，性能增益可以是 100 倍。