玛纳斯HNSW流媒体过滤器

Tim Koh | Software Engineer, Core Product Serving Infra; George Wu | (former) Software Engineer, Core Product Serving Infra

Tim Koh | 软件工程师，核心产品服务于Infra; George Wu | （前）软件工程师，核心产品服务于Infra

Introduction

简介

Embedding-based retrieval is a core center piece of our recommendations engine at Pinterest. We support a myriad of use cases, from retrieval based on content similarity to learned retrieval. It’s powered by our in-house search engine — Manas — which provides Approximate Nearest Neighbor (ANN) search as a service, primarily using Hierarchical Navigable Small World graphs (HNSW).

基于嵌入的检索是我们在Pinterest的推荐引擎的一个核心核心部分。我们支持无数的用例，从基于内容相似性的检索到学习检索。它由我们的内部搜索引擎--Manas--提供近似近邻（ANN）搜索服务，主要使用分层可导航小世界图（HNSW）。

While traditional token-based search retrieves documents on term matching on a tree of terms with logical connectives like ANDs and ORs, ANN search retrieves based on embedding similarity. Oftentimes we’d like to do a hybrid search query that combines the two. For example, “find similar products to this pair of shoes that are less than $100, rated 4 stars or more, and ship to the UK.” This is a common problem, and it’s not entirely unsolved, but the solutions each have their own caveats and trade-offs.

传统的基于标记的搜索是在带有逻辑连接词（如AND和OR）的术语树上进行术语匹配来检索文档，而ANN搜索则是基于嵌入相似性来检索。很多时候，我们想做一个结合两者的混合搜索查询。例如，"找到与这双鞋相似的产品，其价格低于100美元，评级为4星或以上，并运送到英国"。这是一个常见的问题，也不是完全没有解决，但解决方案都有各自的注意事项和权衡。

Existing Solutions

现有的解决方案

Our previous approach was post-filtering, essentially performing the ANN search first followed by a token based search restricted to the result set. Post-filtering suffers from funnel efficiency, and we used an overfetch to work around this problem. However, this is not scalable as clients need to continuously tune their overfetch, and every request can have a different filter rate.

我们以前的方法是后过滤，基本上是先进行ANN搜索，然后再进行基于标记的搜索，仅限于结果集。后期过滤受到漏斗效率的影响，我们使用overfetch来解决这个问题。然而，这不是可扩展的，因为客户需要不断地调整他们的超取，而且每个请求都可能有不同的过滤率。

Pre Filtering

预先过滤

An alternative approach is pre-filtering. First, we figure out the set of docs that match the token-based filte...