ETD

• edit distance
• forward index
• fuzzy
• information retrieval
• inverted index
• query auto-completion

Query autocompletion (QAC) is a critical component of modern information retrieval systems, designed to reduce user effort by suggesting relevant queries in real-time. This thesis addresses the challenge of fuzzy multi-term prefix-search in QAC systems. Unlike standard prefix matching, this mode requires identifying completions where each term in the user's partial query matches the prefix of a distinct term in the target completion, independent of word order. A key contribution of this work is the integration of error tolerance, enabling the system to robustly handle user typos while maintaining high precision. Furthermore, we address the challenge of scalability, proposing data structures and algorithms that ensure sub-millisecond latency even within million-scale search spaces.