T-Wand算法用不到 600 行代码击败 Lucene - yyhh

21-11-17 banq

Lucene 速度非常快,因为它使用了一种最先进的搜索算法WAND [1]。这是WAND 的工作原理。

它作弊。

好吧,任何足够先进的算法看起来都像是作弊。WAND也不例外。基本上,它跳过了大部分文档集合,并且安全地跳过它们,这意味着如果在不跳过的情况下详尽地进行完整计算,结果将是相同的。它能够通过使用两个技巧安全地跳过文档。

第一个技巧是最巧妙的。我仍然不知道我在 IBM Research 的前同事是如何想出它的。我向他们致敬。让我从后续文章 [2] 中窃取一张图片来说明这一点。

第二个技巧是使用假设的最大可能分数来过滤潜在候选人而无需全面检查他们的想法

.....

 

我说轻松击败 Lucene,因为我们没有做任何 Lucene 中丰富的极端优化。我们的代码是惯用的 Clojure,在关键性能热点处有一些 Java 数据结构的额外帮助。代码少于 600 行,包括注释。

这是向Datalevin添加全文搜索功能,这是我们去年开源的 Datalog 数据库。今天完成了搜索引擎的主要工作,和老牌的Java搜索库Apache Lucene进行了一些基准比较,发现Datalevin搜索引擎平均比Lucene快75%,平均快3倍。

详细点击标题

猜你喜欢