Towards efficient top-k fuzzy auto-completion queries

Abstract

Finding relevant objects in a large repository is a fundamental research problem occurring in many applications, such as: data cleaning, data integration, web search, and information retrieval. Instant type-ahead fuzzy search, where user types her query character by character and find the top-k relevant objects, has become widely involved in many applications because it provides the users with rapid response results and improves the user’s experience. The state-of-the-art algorithms are generally inefficient due to their breadth first search algorithm that results in repeated computations.To this end, we propose a novel depth-oriented instant type-ahead fuzzy search algorithm, that largely avoids repeated computations. The efficiency and effectiveness of the proposed approach are empirically demonstrated using real-world datasets. Experimental results show that our approach is 5–10 times faster than state-of-the-art approaches.

Keywords

• Fuzzy string similarity
• Preference-aware query processing
• Edit distance