I have a huge database of job titles, I want to build a system where if you enter something like "jav " then it should suggest next some similar job titles like (java developer, java engineer) etc..

How should one approach this problem? How can build something like this, the latency is biggest concern because it has to be real time. We have to integrate this in UI at the end.

Any suggestions how to proceed further?

  • $\begingroup$ Did you try elastic search where you can reverse index and retrieve. Its the simplest and most effective. If you want to treat for spelling mistakes then you might want to run a batch process of spell mapping and then submit them to elastic search $\endgroup$ Nov 7 '20 at 7:52
  • $\begingroup$ @maheshghanta I am not familiar with elastic search. The main idea is not for spelling correction. Actually, I am trying to provide user with suggestions for the query they are typing in? Can you explain a bit on what you meant by spell mapping? $\endgroup$
    – Sai Kumar
    Nov 7 '20 at 8:03

Autocompletion algorithms usually build on either tree or hash structure for the sake of efficiency. One famous approach is the Ternary Search Tree. Use this source to have an initial idea. It is also a comparably space-efficient solution. You can find more complex systems build on the Ternary Search Tree.

Another good solution is Trie. Trie data structure is a good alternative of Ternary Search Trees, as an example implementation check this.

These both are handy at the front end of the application since they are simple but powerful approaches. Other than that, they have a good balance of time and space complexity.

Moreover, a fast-autocomplete library may help you. Since, in your case, you may have two names for the same job, it has synonym functionality.

In general, tree structures are what you are looking for. You can do this task even using Binary Trees. However, I would suggest you consider the case that in reality many times there appears spelling problems, so in that case, you either will not be able to suggest a word or the suggestion will be incorrect. For such problems, you can also have a spelling check algorithm that first checks if such a word exists, if not using spell check you can have proposed words and you can suggest the autocompletion based on those suggestions. E.g. instead of 'Java' one may type in 'Jsva' and your algorithm will find the correct word and make the suggestion accordingly. This is a one-of-the best algorithms that does auto-completion using ML techniques. You can also build a simple one using Levenshtein distance. (However, spelling error cases mostly discarded in the systems because of its being costly to fix them)

  • 1
    $\begingroup$ Thanks for these suggestions. It gave me a starting point. +1 $\endgroup$
    – Sai Kumar
    Nov 7 '20 at 8:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.