Query auto-completion (QAC) facilitates faster user query input by predicting users' intended queries. Most QAC algorithms take a learning-based approach to incorporate various signals for query relevance prediction. However, such models are trained on simulated user inputs from query log data. The lack of real user interaction data in the QAC process prevents them from further improving the QAC performance. In this work, for the first time we have collected a high-resolution QAC query log that records every keystroke in a QAC session. Based on this data, we discover two types of user behavior, namely the horizontal skipping bias and vertical position bias which are crucial for relevance prediction in QAC. In order to better explain them, we propose a novel two-dimensional click model for modeling the QAC process with emphasis on these types of behavior. Extensive experiments on our QAC data set from both PC and mobile devices demonstrate that our proposed model can accurately explain the users' behavior in interacting with a QAC system, and the resulting relevance model significantly improves the QAC performance over existing click models. Furthermore, the learned knowledge about the skipping behavior can be effectively incorporated into existing learning-based QAC models to further improve their performance. Copyrightc 2014 ACM.