论文标题
模糊的子字符串匹配：snapchat上的设备模糊朋友搜索
Fuzzy Substring Matching: On-device Fuzzy Friend Search at Snapchat
论文作者
论文摘要
Snapchat应用程序上的所有查询中约有50％的目标是寻找合适的朋友与之互动。由于每个人都有一个独特的朋友列表，并且该列表不是很大（最多几千），因此在用户的设备上本地执行此搜索是有意义的。此外，朋友列表已经可用于其他目的，例如显示聊天供稿，并且通过避免使用服务器往返通话，延迟节省可能很重要。从历史上看，我们求助于子字符串匹配，在结果列表的顶部排名前缀匹配。介绍在资源受限的设备上执行模糊搜索的能力以及在错别字普遍存在的环境中既谨慎又具有挑战性。在本文中，我们描述了我们的高效和准确的两步方法模糊搜索的方法，其特征在于跳过式检索层和用于最终排名的新型局部Levenshtein距离计算。
About 50% of all queries on Snapchat app are targeted at finding the right friend to interact with. Since everyone has a unique list of friends and that list is not very large (maximum a few thousand), it makes sense to perform this search locally, on users' devices. In addition, the friend list is already available for other purposes, such as showing the chat feed, and the latency savings can be significant by avoiding a server round-trip call. Historically, we resorted to substring matching, ranking prefix matches at the top of the result list. Introducing the ability to perform fuzzy search on a resource-constrained device and in the environment where typo's are prevalent is both prudent and challenging. In this paper, we describe our efficient and accurate two-step approach to fuzzy search, characterized by a skip-bigram retrieval layer and a novel local Levenshtein distance computation used for final ranking.
