Suggest more recipients (in a chat conference)

If you don't already know, gmail has had a feature called Suggest more recipients for a while now.

From the link above, "Gmail will suggest people you might want to include based on the groups of people you email most often. So if you always email your mom, dad, and sister together, and you start composing a message to your mom and dad, Gmail will suggest adding your sister. Enter at least two recipients and any suggestions will show up like this."

I am planning on extending this even for the chat conversation start page in the chat client that I'm working on. So, if you start entering JIDs of people you want to chat with, the client should automatically suggest more participants.

Thanks to Sandy for the providing the link to gmail blog!!

Update (02/01/2011): This feature is now implemented and part of the dev. versions.

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

It's funny to know....

.... that something you have thought of doing and have done has been thought of by someone else across the world and done in almost exactly the same way as you have....

It's saddening and encouraging at the same time. Saddening because it's not something novel any more. Someone has "been there.. and done that..". Encouraging because you know that you are not having any insanely weird and impractical thoughts and ideas and that you are solving some real problem out there.

This is the second time that this has happened to me, and it is a real confidence booster I should say!!

The project under question is StickyLinks. The exact same thing was done in 1997 and is called WebCite. The funny thing is that it was made for the exact same problem that I was trying to solve, which probably explains why it turned out to be so similar.

The thing that still gets to me is that even the layout of the version page (view where a version of a certain page is displayed) is almost identical. Both projects use frames. Both projects have a bookmarklet.

However, there are ways I plan to extend StickyLinks, so stay posted!!

ps. My next idea: To develop a search engine that will let you search for already existing ideas/concepts/implementations of thoughts that you may have and may think are novel. I use the internet (esp. the search engines) a lot to search for projects that I may want to undertake, just to check if it's already been done by someone else. Most of the time I have to search a lot of times, tweaking my search keywords ever so slightly in the hope of a match. Many a times, I fail to chance upon the right set of keywords (the words that the original author used to describe his/her idea/project) and am under the impression that the idea I have is novel/un-thought of. However, many times it does happen that such a thing does not exist. However, it is only time that lets you ascertain this (if a similar concept exists, you hear of it sooner rather than later, assuming you have shared it with friends).

YAVFS

Yet Another Versioning File System....

I've been reading about Versioning and Snapshoting File Systems and here is a mini-dump of what I think so far. Please correct me if I'm mistaken....

I saw a few file systems with slightly more than a cursory glance, and here are my comments:

1. ext3cow: This is very close to what I have in mind for a versioning and continuous snapshoting file system. However, it does not agree with some of my "requirements of a versioning and continuous snapshoting file system"(below).


2. Elephant File System: This is probably one of the earlier snapshoting/versioning file systems and has been implemented on BSD. It is modeled on BSD's FFS. It does a great job of doing what it says it does. I like everything about it except that I can't use it on Linux.


3. NetApp's WAFL: This again is mainly solving a different problem, that of providing very fast and safe storage on a storage appliance. To the best of my knowledge, you need to trigger a snapshot(though the process itself does not take more than a few seconds), and the number of snapshots are restricted to a fixed number(32 or 256). This may be done using hourly cron jobs, etc.... The interface of getting previous versions of files is a little clumsy though.

Requirements of a Versioning and Continuous Snapshoting file system:

1. It should be able to store a large number of versions of files and directories alike


2. It should be able to do so very fast and without any user intervention. ie. Snapshoting should not be user-triggered, but should be done automatically on every close()


3. You should not need to re-compile the kernel to get this functionality


4. You should be able to apply this to a specific directory root. This means that you should be able to snapshot parts of your directory tree. You should not incur a performance penalty for accessing file out of this region of interest


5. You should have policies for controlling which file to snapshot and version files based on file attributes such as size, name, MIME type, etc....


6. The interface for accessing continuous-in-time file versions should be very clean and fairly intuitive, and it should be fairly easy to write tools around it so that GUI/web-based access can be enabled


7. You should be able to enable this functionality on any file system(and not require to re-format the partition on which you wish to enable it)


8. You should be able to disable this operation at any point in time and get back to accessing the most recent versions of the versioned files using the earlier access methods without any performance penalty. ie. Users should be able to turn on and off this functionality at will and it should allow users to proof this on real workloads without them having to make any drastic changes in their environments


9. The operations performed should be safe, and should not result in data corruption


10. The system should be easy to install and set up

I have in mind something that satisfies the requirements mentioned above....

NextGen Storage??

I've been thinking about what storage systems have in store for us in the future. I mean I've been trying to follow the progress of these beasts, and the next big thing I think should be storage devices that have in-built support for some form of transactional memory. Lots of file-system drivers are building consistency mechanisms into their implementation by using logging in some form or the other. This logging is happening on the same medium as the one where data is being stored. A consistent view of the data is formed by looking at (data+log) as a unit of storage.

I think that logging implementations would benefit a great deal if they had some sort of hardware support. For example, NetApp's WAFL is utilizing Flash memory to store it's writes. This I think is a nice way to look at the problem at hand, and if device manufacturers could integrate some of this on to their device using some nice interface, I think that file-systems of the future could be much faster than they presently are.

The only problem that I do however see with this approach is that the flash memory may wear out and cease to function much faster than the magnetic stable storage. A log-based file-system(or storage structure) would be needed to store the writes on the flash storage(something like JFFS maybe).

Once bitten, twice backed.

Have you ever seriously thought about backing up your data? If not, chances are that you haven't been the victim of a system/hardware/disk failure. Most of the people who seriously think backing up their data and maintaining snapshots is an important part of their routine are the ones who have spent countless hours of their time trying to recover/rebuild their lost data after a system crash. Why does it require someone to suffer before they start becoming cautious with their precious data? Maybe the reason for it is; to quote from Shakespeare's The Merchant of Venice: "For sufferance is the badge of all our tribe".

Whatever, it may be, I would like to say that it's important to always back up your important data and protect it against system failure(s). In fact, I have set up an RAID-1(mirrored) array at home where I store my important data and my home directory. This way, even if one of my Hard Disks were to crash, I'd have the data safely backed up on the other one in the mirrored array. However, this solution does not prevent against:

1. Accidental file deletion,


2. Accidental Disk formatting.


3. File System corruption.

To prevent against such problems, I'd want to have a separate backup(or preferably snapshotting) utility which saves versions of files as you save them. Ideally, the solution would be to introduce a surrogate file system such as a one written using the fuse file system, and have that file system save versions of the files as you save them. So, changes between an open() and close() on a file should be logged and saved as a file version. This way, the user will be able to recover files by how old it is and also get a fairly fine granularity control over the changes that happened. An optimization that could be done is to store only the changes to a file if only edits were made to it, whereas save a complete copy if the file size was changed.

I'm looking for more ideas and people interested in helping me develop such a solution, so if anyone is interested in helping out, please let me know and we'll try to work something out.

An HTTP server with diff capabilities.

These days, there is a surge in the traffic content on the internet. Many sites are serving dynamic content to their users. However, the static content doesn't seem to have lost popularity. Many sites still serve a lot of their pages more or less statically. Furthermore, these static pages don't change very often even though clients are always re-requesting these pages, and asking them to be refreshed. An example would be google's home page. That apart, site administrators always want clients to not cache the page content, because they want clients to see the latest version of any static content that may have changed since the last time they visited. This makes them advertise HTTP headers which forbid the caching of web-pages by browser and proxy caches.

If you notice carefully, even if use wisely, the If-modified-since header involves sending the entire page back in case it was modified. What I'm suggesting here is to use a diff based scheme, wherein the client sends a request to the server indicating a previous page version that it already possesses, along with a flag indicating that it is willing to accept a diff to the current version of the page. The server will now(optionally) send back a patch to the client which it applies to the page that it already possesses. This sending of the patch is optional since the server may not have cached the page to which the client is referring, so that generation of the patch may not be possible at the server end. In this case, the server will send back the whole page as it would in the current scenario.

What this scheme will effectively do is reduce bandwidth consumption dramatically in places where a central proxy is being used to serve many users, and those users seem to be accessing the same static content repeatedly. If the content changes by a bit, or doesn't change at all, this scheme will result in a definite reduction in bandwidth consumption on the internet. However, the trade off here would be CPU time to network bandwidth, since the diff generation and application of the generated patch are both CPU intensive activities as compared to normally sending the whole page.