A very fast approach to auto complete (or search suggestions)

You've seen search engines suggest queries when you begin typing the first few letters of your search string. This is being done by Duck Duck Go as well as Google (to name a few). This is typically done by maintaining a list of past queries and/or important strings that the search engine thinks are worthy of being suggested to a user that is trying to find something similar. These suggestions are effective only if the search engine spits them out very fast since these should show up on the screen before the user has finished typing what he/she wanted to type. Hence the speed with which these suggestions are made is very critical to the usefulness of this feature.

Let us consider a situation (and a possible way of approaching this problem) in which when a user enters the first few letters of a search query, he/she is presented with some suggestions that have as their prefix, the string that the user has typed. Furthermore, these suggestions should be ordered by some score that is associated with each such suggestion.

Approach-1:

Our first attempt at solving this would probably involve keeping the initial list of suggestions sorted in lexicographic order so that a simple binary search can give us the 2 ends of the list of strings that serve as candidate suggestions. These are all the strings that have the user's search query as a prefix. We now need to sort all these candidates by their associated score in non-increasing order and return the first 6 (say). We will always return a very small subset (say 6) of the candidates because it is not feasible to show all candidates since the user's screen is of bounded size and we don't want to overload the user with too many options. The user will get better suggestions as he/she types in more letters into the query input box.

We immediately notice that if the candidate list (for small query prefixes say of length 3) is large (a few thousand), then we will be spending a lot of time sorting these candidates by their associated score. The cost of sorting is O(n log n) since the candidate list may be as large as the original list in the worst case. Hence, this is the total cost of the approch. Apache's solr uses this approach. Even if we keep the scores bound within a certain range and use bucket sort, the cost is still going to be O(n). We should definitely try to do better than this.


Approach-2:

One way of speeding things up is to use a Trie and store (pointers or references to) the top 6 suggestions at or below that node in the node itself. This idea is mentioned here. This results in O(m) query time, where m is the length of the prefix (or user's search query).

However, this results in too much wasted space because:

1. Tries are wasteful of space and
2. You need to store (pointers or references to) 6 suggestions at each node which results in a lot of redundancy of data

We can mitigate (1) by using Radix(or Patricia) Trees instead of Tries.


Approach-3:

There are also other approaches to auto-completion such as prefix expansion that are using by systems such as redis. However, these approaches use up memory proportional to the square of the size of each suggestion (string). The easy way to get around this is to store all the suggestions as a linear string (buffer) and represent each suggestion as an (index,offset) pair into that buffer. For example, suppose you have the strings:

1. hello world
2. hell breaks lose
3. whiteboard
4. blackboard

Then your buffer would look like this:
hello worldhell breaks losewhiteboardblackboard
And the 4 strings are actually represented as:
(0,11), (11,16), (27,10), (37,10)

Similarly, each prefix of the suggestion "whiteboard" is:

1. w => (27,1)
2. wh => (27,2)
3. whi => (27,3)
4. whit => (27,4)
5. white => (27,5)
6. whiteb => (27,6)
7. and so on...

Approach-4:

We can do better by using Segment (or Interval) Trees. The idea is to keep the suggestions sorted (as in approach-1), but have an additional data structure called a Segment Tree which allows us to perform range searches very quickly. You can query a range of elements in Segment Tree very efficiently. Typically queries such as min, max, sum, etc... on ranges in a segment tree can be answered in O(log n) where n is the number of leaf nodes in the Segment Tree. So, once we have the 2 ends of the candidate list, we perform a range search to get the element with the highest score in the list of candidates. Once we get this node, we insert this range (with the maximum score in that range as the key) into the priority queue. The top element in the queue is popped and split at the location where the element with the highest score occurs and the scores for the 2 resulting ranges are computed and pushed back into the priority queue. This continues till we have popped 6 elements from the priority queue. It is easy to see that we will have never considered more than 2k ranges (here k = 6).

Hence, the complexity of the whole process is the sum of:

1. The complexity for the range calculation: O(log n) (omitting prefix match cost) and
2. The complexity for a range search on a Segment Tree performed 2k times: O(2k log n) (since the candidate list can be at most 'n' in length)

Giving a total complexity of:
O(log n) + O(2k log n)
which is: O(k log n)

Update (29^th October, 2010): I have implemented the approach described above in the form of a stand-alone auto-complete server using Pyhton and Mongrel2. You can download it from here. (11th February, 2012): lib-face is now called cpp-libface and has a new home at github!

Some links I found online:
LingPipe - Text Processing and Computationsal Linguistics Tool Kit
What is the best open source solution for implementing fast auto-complete?
Suggest Trees (SourceForge): Though these look promising, treaps in practice can degenerate into a linear list.
Autocomplete Data Structures
Why is the autocomplete for Quora so fast?
Autocomplete at Wikipedia
How to implement a simple auto-complete functionality? (Stack Overflow)
Auto Compete Server (google code)
Three Autocomplete implementations compared
Trie Data Structure for Autocomplete?
What is the best autocomplete/suggest algorithm,datastructure [C++/C] (Stack Overflow)
Efficient auto-complete with a ternary search tree

What you've always wanted to know about GRE preparation

When I was preparing for the General GRE, it was a completely mad rush, with me having to ask anyone and everyone for help and advice. So, the conglomeration of all that information is what guided me throughout. Today, I am going to put that all down (combined with my own experiences) so that others don't have to grapple with the same questions and uncertainties and can really concentrate on studying for the exam.

1. Don't fall into the trap of not booking a date!! You will find it hard to study if you haven't booked a date
2. Book a date sufficiently into the future (say 2-3 months) and work towards it as if the date can not be postponed. I've seen many people postpone the date just because they can. Don't fall into that trap
3. I used the Barron's book for everything
4. Don't take the quant section lightly. Even though it is easy, it is time critical and there are many trick questions
5. Even though the word list will seem daunting at first, keep at at and try to do as much of it as you can. I must have landed up knowing close to 3000 (out of the 3500) words in the Barron's word list
6. Attack the High Frequency Words first (about 350). Make sure you use the list from both Barron and Kaplan. This file contains all such words and words that I found hard. Use the Barron's and Kaplan's list from here and make you own list of "hard" words (everyone will find a different set hard)
7. Then do the words list-by-list. There are about 50 word lists in the Barron's book. Each word list can take you anywhere from 1 to 3 hours to do if you are doing it the first time. Towards the end, you should be able to do all the word lists in 2-3 days (assuming 5-6 working hours each day)
8. Solve as many exercise problems in the Barron's book as you can in the quant section
9. For quant practice, use The Nova GRE prep. book. The quant in this book is easier than what you will get in the GRE, so use this as your first round of preparation
10. Take the 5 sample tests given at the end of the Barron's book. They are very close to the actual GRE test in terms of difficulty
11. The Kaplan tests too are of GRE difficulty level (I would say a tiny bit more difficult, but that shouldn't be something you should factor in). The 6 practice exercises in Kaplan are way too easy (for quant) and the 30 min you get to solve them is sufficient. The quant in the 3 sample tests is harder and is of GRE difficulty level
12. POWERPREP (the official GRE prep. software) is something you must do before the test. They give you 2 sample tests. Take them 1-3 days before the real test when you are sudo prepared for the test. These will give you a great indicator of what score you might land up getting. If you do badly in some section, try to spruce up your act in that section. The drawback of taking it so late (just before the test) is that you don't give yourself enough time to rectify your weak areas. However, I wouldn't want anyone to "waste" these tests before they are fully prepared for the simple reason that these tests are really good indicators of how much you might land up getting
13. None of the other tests I took were of the GRE difficulty level, so make sure that you take all of the tests above before you take the GRE
14. On the day of the test, make sure you arrive at the test center on time and have all the required documents
15. That's about it and all the best!!

How things go wrong (reprise)

About 3 years ago, I wrote a post on How things go wrong. I should have made everyone I know read it since we just ran into an issue that bit us in the ass... Yes, it was caused as a result of:

• Lack of return value checking from system calls and
• Lack of sufficient error checking/handling code

and further complicated by a lack of logging in the application.

I can't begin saying how important each of them are. Oh well, I only have 2 things to say:

• You need to learn for yourself
• You can never be too careful
• You can't learn from other's mistakes (yes, this and the 1^st one are the same thing)

Using Titanium Desktop to test web sites

I have been using Titanium Desktop for a while now at work, and am not at all impressed with the implementation or stability of the product and wouldn't want to see it being used in any serious project. HOWEVER, it is a brilliant concept which if done well can be humongously successful.

I was faced with the daunting task of testing a web-site written in Drupal the other day. Now, I don't know Drupal but have been told that its got these magic form elements which it used for validation. That couples with cookies meant that I would have to do a lot of work to test even slightly complex flows using python/perl/ruby::Mechanize. That apart, I can NEVER simulate the javascript and other asset loads that a normal user would exercise. For complete end-to-end-testing, I couldn't find anything that I would like using.

Here is where Titanium comes in. It doesn't have the sandboxing rules that normal browsers have, so you can load pretty much any page in a Titanium IFrame and do pretty much anything you want with it!!!!

I have given here an example of using Titanium to search for some text on Duck Duck Go.

To run the example, start Titanium Desktop as kboot --query "Your Search String"

Enjoy!!

Update: Here is a video showing how the automation works.

Aaloo, mutter and tamater sabzi

This is the recipe for my current favourite vegetable. Translated to english, it means Potato, peas and tomatoes. (makes sabzi to serve 4). Dedicated to my mom since she makes this dish in the most awesome way I have ever tasted it to be and to sandy since he is going to learn it this time ;)

Ingredients:

Medium sized aaloo(potatoes); boiled:	about 3 nos
Fresh green peas:	about 100g
Medium sized tomates:	about 4 nos.
Clarified Butter (Ghee):	1 Tbsp
Hing (asafoetida):	1/2 tsp
Cumin seeds (jeera):	1 1/2 tsp
Turmeric (haldi):	1/4 tsp
Salt (namak):	to taste
Red chilli powder (this is mainly used for the red color):	1/4 tsp (or to taste)
Fresh green chilli (cut and seeded):	1/2 nos.
Dhania and jeera powder:	1 tsp
Fresh corriander leaves:	(to garnish)

Procedure:

1. You need not skin the boiled potatoes. Just cut it into about ¹/₂" X ¹/₂" cubes
2. Heat the ghee and when it is hot, add the hing, jeera and green chilli to it. When the jeera starts popping, and water to it
3. Add peas to the water, and boil them till they are soft
4. Now, cut the tomatoes (unskinned) into small pieces and add it to the boiling water and peas. Keep boiling till the tomatoes have softened
5. Now, add the cut potatoes into the mixture and add red chilli powder, dhania and jeera powder, turmeric and salt
6. Boil for about 2 more minutes till the potatoes have soaked the gravy
7. Garnish with fresh corriander leaves and cover or serve

Actions speak...

... louder than words

Guess what?

            _________
            |*      |
            |       |
    (------------   |-------)
    (               |       )
    (       |--------       )
    (       |               )
     -------|   ------------
            |       |
            |      *|
            ---------

Or this (if you are having a problem with the one above ;))
            _________
            I *     |
            I       |
    (------------   |-------)
    (               |       )
    (       |--------       )
    (       |               )
     -------|   ------------
            |       I
            |       I
            |_____*_I

+5 to the first one who guesses correctly

Murphy's Law (for Python programmers)

Download it here
Please rename the file to murphy.py and from your interpreter:
import murphy

YASNOSC

Yet another SQL and NoSQL comparison

1. Scalability != NoSQL


2. Performance != NoSQL [not always]


3. Scalability == Good schema design


4. Performance == Good schema design

But...

1. Performance != Scalability


2. Scalability != Performance

(but we should also note that NoSQL isn't NOt SQL, but Not Only SQL)

A new water pump for our washing machine

(This blog post has the potential to be discursive and go in no particular direction, so I'll try my best to remain as unwavering as I can)

It all started off when our washing machine konked off and decided to stop working. My grandma sent it off to the repairers who fixed it and then had the brilliant idea to suggest attaching a water pump so that water from the tank above would flow in much faster. Now, anyone who has played with a syringe would know that no matter how hard you push (or pull), you just can NOT for the love of anything (or anyone) get more than a certain amount of liquid through the syringe (or in this case the pipe).

Now, our pipes are really old and are rusting from the inside. This is the reason that the flow of water has gone down as compared to the time when they were first installed. Even though I suggested getting the pipes changed due to the above mentioned reason (since that is the real problem, my grandma would hear nothing from me... Oh well... so be it...)

The brilliant engineer's suggestion came as a massive shock to me and it almost felt funny. Anyways, the pump has been installed and guess what... The flow of water in the pipe is still the same!! I wonder how that happened. Isn't the pump working (scratch head, etc...)

The rate of flow of water in a pipe depends upon many things. One of them being the inner diameter of the pipe and another being the friction offered by the sides of the pipe. I don't know the exactly formula, but I am guessing it is easy to come by. The pressure exerted by the water in the tank is more than sufficient to max. out the flow rate in the pipe and I would have guessed those engineers to know that. I guess it's back to the drawing board for them ;)

How to write bug-free code

Listen hard and listen fast. Listen once; I won't repeat myself...

While writing code, if you ever say to yourself:

• Oh! but this will hardly ever happen OR


• The user will never do this OR


• What are the odds of this happening??

Please please please go ahead and write some code and comments to handle that situation. You can't ever be too careful.

Signing off,
Captain S.K.Eptic

Python generators and the dict.items() function

During the course of yesterday's session, there was an example of iterating over a dictionary(dict) in python. The code looks something like this:

d = {
     "name": "chuck norris",
     "age": "positive infinity",
}
for k,v in d.items():
    print "Key: " + str(k) + ", Value: " + str(v)

The d.items() function returns a list which will take up a non-trivial amount of memory for large dicts that we wish to iterate over. For simplicity's sake if we assume that each pointer takes up 8 bytes and the python tuple type takes up 32 bytes(say) and there are 1 million(10⁶) entities in the dict(d), then we land up with 10⁶ x 56 (Two 8 byte pointers, each to each the key and the value objects, 8 for a pointer to the tuple and 32 for the tuple object itself) which is about 56MB of memory used for just iterating over the dictionary.

If however, we use generators, then we can save all that memory.
However, you can directly print the result of d.items(). Printing a generator object doesn't do anything spectacular, so we will need to create a proxy object to print the result of generation if string coercion is requested. The code for doing so is shown below. Notice that we use the .keys() function within our custom generator. We won't need to use it if we really were the dict object and had handles to the internal variables.

d = {
     "name": "chuck norris",
     "age": "positive infinity",
}

def dict_items(d):
    """
    Returns an object which can be iterated over in a for loop
    as well as printed. This is achieved by returning an object
    which is both iterable as well as convertible to a string.
    However, iteration involves using a generator for fetching
    the next value in the sequence
    """
    def dict_generator():
        dkeys = d.keys()
        for k in dkeys:
            yield (k, d[k])
    dg = dict_generator()

    def dgen_to_str():
        return str(d.items())

    class Dummy(object):
        def __getattr__(self, attr):
            return getattr(dg, attr)
        def __str__(self):
            return dgen_to_str()
        def __iter__(self):
            return dg

    proxy = Dummy()
    return proxy

diter = dict_items(d)
print diter

for k,v in diter:
    print "Key: " + str(k) + ", Value: " + str(v)

However, the major difference comes when you try to do something like this:

for k,v in d.items():
    d.clear()
    print "Key: " + str(k) + ", Value: " + str(v)

The code above will work as expected and print all the elements of the dict(d)

for k,v in diter:
    d.clear()
    print "Key: " + str(k) + ", Value: " + str(v)

However, the code above will throw an exception since our generator caches all the keys and dereferences the dict(d) to get the value for the corresponding key.

So, applications that mutate the dict while iterating over it won't quite work as expected.

Python Interest Group(PIG) Act-1; Scene-1

We had the first session of the python interest group(affectively called PIG) at Directi yesterday (1st June, 2010).

Here are the links to the presentation in:

• .odp(open office)


• .ppt(excel) format


• along with the code snippets in a .zip archive

You will need python 2.5 to run the sample programs.
The documentation for python 2.5 is available here

Happy Hacking!!

5 months of salad... and counting...

I started having salad for lunch daily sometime early January, 2010. Since then, it's been fairly smooth sailing and I've added a few ingredients to the mix.

A lot of people have asked me if I got bored of the monotony of salad, but I highly disagree with them all. The deal with salad is that you get so many flavours in every bit that it's really hard to get bored of it. Besides, it's fairly juicy and crunchy that you enjoy having it -- really!!

Either ways, I have added a few extra ingredients over the months, so would like to share those with the very few and faithful readers of this blog.

• Hazelnuts (halves)


• Cashews (halves)


• Pomegranates (in season)


• Dates


• Dried Anjeer (figs)


• I've pretty much knocked off the mixed herbs in the dressing and just stick to Olive Oil and Honey


• The baby corn is fresh baby corn, which needs to be stripped off it's covering; like you would for normal corn. The baby corn which results is really so sweet that you can eat it as-is!!

Enjoy your salad people!!

Can't come to terms with inheritance

I've been racking my brains over inheritance for a while now, but am still not completely able to get around it.

For example, the other day I was thinking about relating an Infallible Human and a Fallible Human. Let's first define the two:

• Infallible Human: A human that can never make a mistake. It's do_task() method will never throw an exception


• Fallible Human: A human that will occasionally make a mistakes. It's do_task() method may occasionally throw a ErrorProcessingRequest Exception

The question was:
IS an infallible human A fallible human OR IS a fallible human AN infallible human?

The very nice answer I received was in the form of a question (I love these since it gives me rules to answer future questions I may have).

"Can you pass an infallible human where a fallible human is expected OR can you pass a fallible human where an infallible human is expected?"

It seems apparent that you can pass an infallible human where a fallible human is expected, but not the other way around. I guess that answered my question.

However, it still feels funny saying "An infallible human is a fallible human". Does anyone else feel queasy when they say it? It almost feels as if speaking out inheritance trees is like reading out statements from propositional calculus in plain English (the if/then implication connectives don't mean the same as that in spoken English). Does anyone else feel the same?

update: This thread on stackoverflow discusses the same issue.

A few rules to live by

• you can only lie to others, never to yourself
• don't hurt others -- it will only come back to you
• you can justify anything -- we all can -- but don't try too hard. you might end up lying
• python rocks
• java bites shite
• java has resulted in more deaths and cases of insanity than road accidents world-wide
• the average lifespan of a java programmer is 10 years less than that of a python programmer and 7 years less than the average for a human
• what can kill chuck norris -- programming in java
• listen to music you like -- don't pretend
• eat food you like -- don't pretend
• wear what you like (if you want to wear anything that is) -- don't pretend
• criticize -- don't be diplomatic when you don't need to
• praise -- it spreads good vibes -- but don't praise falsely -- it doesn't help at all
• music will set you free ;)
• do what you want to, not what you have to or need to -- sometimes you may "need/have" to do the things though; but don't stretch it too much
• listen to "sunscreen" if you haven't yet
• don't recommend it to others because it's "cool", but because you think it's worth doing
• don't do anything "just" because it's "cool"
• don't not to anything just because it's not cool
• the arts are purgative and cathartic; write, act, sing, cook, code... anything is art and art is everything...
• you may need to twist your finger to get the fat out(transated from a hindi proverb); but do it only if it's absolutely necessary
• talk is cheap; actions are not
• neither is code
• show me the code you piece of shite

We aren't responsible

I was reading the paper and The Mumbai Mirror's headlines a few days ago went something like this "Criminal Negligence Leaves WR Commuter Critical". The article was with reference to a commuter who had been injured by a plank that fell on him because of negligence on part of the workers working at Churchgate station. This injury unfortunately has left him comatose and he is currently in a critical state in hospital. I wish him a speedy recovery.

Coming from a software centric world where EULAs and licenses accompany any piece of code that is shipped, it seems only natural that no one is really responsible for anything that they do and that any action on their behalf may have negative influences on others. Others need to watch out for anything that may hurt or otherwise injure them. It is the user's and only the user's sole responsibility to ensure his/her fitness and properiety and the user must account for anything that may go wrong during the course of using the product/software mentioned.

I have yet to see any license that says that they take sole responsibility for their product and that they could be held responsible for any damage arising due to negligence on their behalf. The closest I have come to it is Knuth's exponentially increasing reward for finding bugs in TeX. As far as free software is concerned, we shouldn't expect it. However in case we are paying for the software, shouldn't we demand it? I mean we are literally shelling out hard cash for that piece of code. We seem to have a right to want it to be bug-free...

Either ways, it seems no one wants to take responsibility for their code, so why not make it a de-facto standard. Instead, if someone out there is willing to say that they will take responsibility for screw ups (of any) then they should include it in the license agreement.

It starts off with software saying that it may not work well and ends up at coffee cups and hot dogs saying that their contents may be too hot for consumption.

What next? From what I see, there may now be notices on every pavement saying that people should walk on it on their own risk. Each lift will say that it could crash any minute and if it does; even due to any manufacturing defect or installation glitch, then company providing it should not be held responsible. Airplane and trains will warn travelers before they enter saying "Please account for the fact that you may not make it if you step in". Books may say "Read at your own peril. Your eyes may gouge out while reading this book, but don't blame us!!". When will all this end???

Events: How to use them to your advantage

A very interesting conversation between a colleague and me resulted in some equally interesting learnings as far as I was concerned.

The topic of discussion was about whether certain functionality in a software should be implemented via events or via function calls directly to the concerned component. More concretely, should the coupling be via events as in a pubsub based system or should it be via known function end-points on specific objects.

If the event based approach is used, there is lose coupling, and the coupling is on events. Using the other approach, there is strong coupling and one component needs to know about the interfaces of the other component.

Let's take a toy example to analyze this situation.

Consider an interior stylist that is developing an integrated home theatre system. Say there are multiple components involved:
1. Speaker system
2. Television
3. CD player
4. Satellite system

For all practical purposes, users should not need to turn on each of the separate components separately (as they do today). They need not even know what the individual constituents of the system are. For that purpose, having a separate button that turns on the Television, one that turns on the speakers and one that controls the CD player seem overkill. Just the press of a single "start CD" button should do the needful.

Let's discuss various ways in which we can achieve the desired effect:

1. Strongly couple all the components together so that starting the CD player also triggers the TV and the speaker system.
   
   What happens if the satellite system is turned on? It must also turn on the TV and speaker system. Tomorrow if there is a new device "USB photo viewer" that needs to use the display that the Television provides, it will also need to do the needful.
   
   This method seems to waste a lot of developer time and seems to be prone to errors. What if someone forgets to turn on the TV? Also each component needs to handle the case of when the TV/speaker is already on, etc...
   
   The CD player will work only with that TV set and speaker system that speaks a language that it understands (tied to an interface). Vendors will try to tie users to their interface in the hope of selling them all the components.
   
2. 
   Instead, if we just decouple all the system and couple them on events, things become much clearer and easier to work with.
   
   The "button.enterteinment.cdplayer", "button.enterteinment.satellite" and "button.enterteinment.usbdevice" events should be listened to by each of the components and they should react accordingly.
   
   Another thing to remember is how to name the events. We should NOT name events as "start.enterteinment.cdplayer". That sounds very imperative. Naming plays a very important role in how the rest of our system is built around these events. Wrongly named events can cause a lot of confusion and screw up the system even more than what you thought capable of doing!!! Event names should be suggestive of "something happening" and not of "something being asked for".
   
   Accordingly, events should not be named "do-this" and "do-that". Instead, prefer names like "this-happened" and "that-happened" so that listeners can react to these events in the way they deem most fit.
   
   By naming events imperatively, we immediately constrict their use cases to what we think they should be; defeating the original purposes of using events -- which is to free event raisers from thinking of what is to be done in reaction to a raised event.
   

One line to teach you Object Oriented Programming (OOP)

"When modeling objects, model behaviour, not attributes"
Courtesy: Ramki

Probably the hottest summer I've seen in Mumbai

This is by far the hottest and stickiest summer I have seen in Mumbai since my stint on this planet.