Indexing algorithms to develop an app like google desktop search ?

Question

Hi Friends, I want to develop google desktop search like application, I want to know that which Indexing Techniques/ Algorithms I should use so I can get very fast data retrival.

Thanks, Sunny.

Answer 1

The Burrows-Wheeler transform, used to compress data in bzip2, can be used to make substring searching of text a constant time function.

http://en.wikipedia.org/wiki/Burrows-Wheeler%5Ftransform

I haven't seen a simple introduction online, but here is a lot of detail:

http://www.ddj.com/architect/184405504

Answer 2

In general, what you want is an Inverted Index. You can do the indexing yourself, but it's a lot of work to get right - you need to handle stemming, stop words, extending the posting list to include positions in the document so you can handle multi-word queries, and so forth. Then, you need to store the index, probably in a B-Tree on disk - or you can make life easier for yourself by using an existing database for the disk storage, such as BDB. You also need to write a query planner that interprets user queries, performs query expansion and converts them to a series of index scans. Wikipedia's article on Search Engine Indexing provides a good overview of all the challenges, too.

Or, you can leverage existing work and use ready-made full text indexing solutions like Apache Lucene and Compass (which is built on Lucene). These tools handle practically everything detailed above (and more), which just leaves you writing the tool to build and update the index by feeding all your documents into Lucene, and the UI to allow users to search it.