2

I'm trying to implement an autocomplete feature for a search engine. I have a database of words(stemmed) that occur in the documents that I have for users to search.

What I am thinking of doing is:

  • Constructing a graph with words as nodes and weighted edges with weights as the number of times those 2 words have been searched together.

  • Each node also keeps track of which is the most commonly typed word next to it.

  • Whenever a user starts typing his query, this graph is queried and the first word is predicted by string matching and then ranking the matched words according to search frequency.

  • When the user starts typing the next word, the graph is visited and the neighbours of this node are retrieved and shown to the user in order of frequency (weight of edges).

This is a rough overview of what I am trying to achieve. I have not implemented it yet. It would require a fair amount of work to implement this, and I think it would be quite slow. And to be quite honest, I don't think doing that much work knowing that it'll be quite slow is worth it.

If I am on the right track with this conceptual design, are there any optimizations that should be made to this to improve performance? Or perhaps an entirely different design that I should be using instead?

I found only 2 papers on query prediction, this and this. I went through the latter but it isn't that related to my use-case.

  • You have 'database' tagged. Is this in a database that you need to query? or is it in an accessible memory structure? Are you encountering any existing performance issues (there are many things that can affect performance - and describing the existing architecture and systems can help in identifying possible places to improve the performance)? – user40980 Mar 10 '16 at 19:19
  • 2
    ... In other words, there's not enough information here to make your question reasonably answerable. Any attempt at an answer would be guessing. – Robert Harvey Mar 10 '16 at 19:20
  • 1
    @MichaelT I removed the tag database. The 'database' I have here is this which contains all the words that I have. I need to construct a graph with these words and then query this graph for the abovementioned information. – Ayush Gupta Mar 10 '16 at 19:34
  • 2
    @RobertHarvey I have not implemented it yet. It would require a fair amount of work to implement this, and it would be quite slow. To be quite honest, I don't think doing that much work already knowing that it'll be quite slow is worth it. – Ayush Gupta Mar 10 '16 at 19:46
  • 2
    @JayElston I found only 2 papers on query prediction, this and this. I went through the latter but it isn't that related to my use-case. Do you know of any papers I that could help me? – Ayush Gupta Mar 10 '16 at 19:58
1

What you're describing will require tremendous overhead and calculating the effencicy is a non-polynomial problem (traveling salesman).

At the same time it should be noted that if properly implemented this solution will deliver as intended. However you can achieve the same result with far less overhead.

You will need:

A hash-table dictionary that provides pointers to

A priority heap of priority heaps, the top-level heap is for the first word, and subsequent heaps are for the 2nd, 3rd, etc level words.

This will provide fast access and place all penalties on the write functions.

1

N-Grams can be a solution here.

  1. Process the corpus to prepare an index of N-Grams
  2. Find out all possible suffixes phrases for current query

Creation of N-Grams would be slow, but lookups should be nlog(n)

Edit :

Two examples of this technique :

https://qbox.io/blog/multi-field-partial-word-autocomplete-in-elasticsearch-using-ngrams

http://www.andornot.com/blog/post/Advanced-autocomplete-with-Solr-Ngrams-and-Twitters-typeaheadjs.aspx

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.