Fuzzy Substring Matching: On-device Fuzzy Friend Search at Snapchat
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.
Code (0)
등록된 구현이 없습니다.
Tasks
RetrievalSimilar Papers 제목 키워드 기반
Fuzzy Segmentations of a String
This article discusses a particular case of the data clustering problem, where it is necessary to find groups of adjacent text segments of the appropriate length that match a fuzzy pattern represented as a sequence of fu…
ClusteringSegmentationText SegmentationFuzzyLogic.jl: a Flexible Library for Efficient and Productive Fuzzy Inference
This paper introduces \textsc{FuzzyLogic.jl}, a Julia library to perform fuzzy inference. The library is fully open-source and released under a permissive license. The core design principles of the library are: user-frie…
A Study of an Modeling Method of T-S fuzzy System Based on Moving Fuzzy Reasoning and Its Application
To improve the effectiveness of the fuzzy identification, a structure identification method based on moving rate is proposed for T-S fuzzy model. The proposed method is called "T-S modeling (or T-S fuzzy identification m…
Dealing with natural language interfaces in a geolocation context
In the geolocation field where high-level programs and low-level devices coexist, it is often difficult to find a friendly user inter- face to configure all the parameters. The challenge addressed in this paper is to pro…
Two Online Map Matching Algorithms Based on Analytic Hierarchy Process and Fuzzy Logic
Our aim of this paper is to develop new map matching algorithms and to improve upon previous work. We address two key approaches: Analytic Hierarchy Process (AHP) map matching and fuzzy logic map matching. AHP is a decis…
Decision Making