Search engine users nowadays heavily depend on query completion and correction to shape their queries.  Typically, the completion is done by database lookup which does not understand the context and cannot generalize to prefixes not in the database . In the paper, we propose to use unsupervised deep language models to complete and correct the queries given an arbitrary prefix .  We show how to address two main challenges that renders this method practical for large-scale deployment : 1) we propose a method for integrating error correction into the language model completion via a edit-distance potential and a variant of beam search that can exploit these potential functions; and 2) we show how to efficiently perform CPU-based computation to complete the queries, with error correction, in real time (generating top 10 completions within 16 ms). Experiments show that the method substantially increases hit rate over standard approaches, and is capable of handling tail queries.

realtime search query completion using character-level LSTM language models This paper presents methods for query completion that includes prefix correction, and some engineering details to meet particular latency requirements on a CPU. The authors propose an algorithm for solving the query completion problem with error correction, and adopt character-level RNN-based modeling and optimize the inference part to achieve targets in real time.