An Auto-completion Algorithm Using Conditional Probability

Anuj Vaijapurkar, Rishon Patani, Vaibhav Kashyap Jha

Abstract


In this paper, we present an algorithm to auto-complete words that work on user-input by suggesting the highly probabilistic words to the user.  Our algorithm uses trie Data structure we use this trie for efficient suggestion of words to the user.  Our algorithm implements trie efficiently and modify its structure quickly and correctly every time a user enters a word.  Typically browsers implement this feature by caching a fixed number of queries, previously entered by the user on the client side.  Our algorithm can be used as an offline model for heavy user-input interaction interfaces.  Typically browsers implement this feature by caching a fixed number of queries, previously entered by the user on the client side.

Keywords


Graph theory, Conditional probability, Suggestion algorithm, Auto-complete algorithm

Full Text:

PDF

References


K. Kukich. Technique for automatically correcting words in text. ACM Computing Surveys (CSUR), 24(4):377–439, 1992.

C. MacArthur. Word Processing with Speech Synthesis and Word Prediction: Effects on the Dialogue Journal Writing of Students with Learning Disabilities. Learning Disability Quarterly, 21(2):151–166, 1998.

G. Manku and R. Motwani. Approximate frequency counts over data streams. Proceedings of the Twenty-Eighth International Conference on Very Large Data Bases, 2002.

L. Paulson. Building rich web applications with Ajax. Computer, 38(10):14–17, 2005.

"Autocomplete 0. 0. 104 : Python Package Index". Pypi. python. org. N. p. , 2016. Web. 18 Feb. 2016.

E. M. McCreight. A space-economical suffix tree construction algorithm. J. ACM, 23(2):262–272, 1976

Y. Liu. Learning to rank for information retrieval. Foundation and Trends in Information Retrieval, 3(3):225–331, Mar. 2009. ISSN 1554-0669.

Shokouhi and K. Radinsky. Time-sensitive query autocompletion. In Proc. SIGIR, pages 601–610, Portland, Oregon, USA, 2012. ISBN 978-1-4503-1472-5.

J. Teevan, S. T. Dumais, and E. Horvitz. Personalizing search via automated analysis of interests and activities. In Proc. SIGIR, SIGIR ’05, Salvador, Brazil, 2005. ISBN 1-59593-034-5.

Weber and C. Castillo. The demographics of web search. In Proc. SIGIR, pages 523–530, Geneva, Switzerland, 2010. ISBN 978-1-4503-0153-4.

UMLSKS SUGGEST: An Auto-complete Feature for the UMLSKS interface using AJAX,Anantha Bangalore, Allen Browne, and Guy Divita.

L. Zhang, T. Tran, and A. Rettinger. Probabilistic Query Rewriting for Efficient and Effective Keyword Search on Graph Data.

S. Tata, R. Hankins, and J. Patel. Practical Suffix Tree Construction. Proceedings of the Thirtieth International Conference on Very Large Data Bases, Toronto, Canada, August, pages 36–47.

B. Davison and H. Hirsh. Predicting sequences of user actions. Notes of the AAAI/ICML 1998 Workshop on Predicting the Future: AI Approaches to Time-Series Analysis, 1998

A. Nandi and H. V. Jagadish. Effective phrase prediction. In Proc. VLDB, pages 219–230, Vienna, Austria, 2007.

Reda, Y. Park, M. Tiwari, C. Posse, and S. Shah. Metaphor: a system for related search recommendations. In Proc. CIKM, pages 664–673, Maui, HI, 2012. ISBN 978-1-4503-1156-4.

102–113, 2001. [9] M. Farach. Optimal suffix tree construction with large alphabets. Foundations of Computer Science, 1997. Proceedings. , 38th Annual Symposium on, pages 137–143, 1997.

Gregory Smits, Olivier Pivert, et al. AGGREGO SEARCH: Interactive Keyword Query Construction.


Refbacks

  • There are currently no refbacks.


Copyright (c) 2016 Anuj Vaijapurkar, Rishon Patani, Vaibhav Kashyap Jha

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.