The Crux of a Search Engine

The job of a search engine is given a term to find all documents within a document collection which contain the term. To answer queries in a reasonable amount of time even in the presence of a vast document collection, an index of all search terms is prepared in advance. The index is in its simplest form nothing more than a sorted list of search terms; where each term has the list of the documents, wherein it is found, associated.

If the total size of the document collection is so small that the entire index fits into main memory it is straightforward to generate the index. The real challenge is to handle large document collections on small machines. Using a harddisk to store the index trades memory for time. Compressing the stored index will keep the space usage down. If the CPU is fast compared to disk throughput it is quite possible that compressing the index will achieve a time saving too.

The book Managing Gigabytes by Ian H. Witten, Alistair Moffat and Timothy C. Bell has the following table over predicted resource requirements to invert (i.e. build an index) a document collection with a total size of 5 Gbytes. The algorithms are more-or-less listed in order of increasing sophistication. The somewhat arbitrary limit of 40 Mbytes of main memory stems from the first edition of the book from 1993.

Method	Memory (Mbytes)	Disk (Mbytes)	Time (hours)
Linked lists (memory)	4,000	0	6
Linked lists (disk)	30	4,000	1,100
Sort-based	40	8,000	20
Sort-based compressed	40	680	26
Sort-based multiway compressed	40	540	11
In-memory compressed	420	1	12
Lexcion-based, no extra disk	0	0	79
Lexcion-based, extra disk	40	4,000	12
Text-based partition	40	35	15

The first two entries illustrate the the space/time tradeoff really well.

The "Linked lists (memory)" algorithm builds an index in memory in the naïve way: all terms are stored as keys in a hash table, their associated value is the list of documents containing the term. It uses the almost as much memory as the entire collection.

The "Linked lists (disk)" uses the same approach, but stores the linked lists on a disk. Memory usage is fine, but due to the speed difference between main memory and disk the time usage explodes to the unreasonable.

The "Sort-based" approach builds the index in three tempi. First a temporary file consisting of (term-number, document-number) tuples are generated by looping over all terms in all documents. Second, the temporary file is sorted by an external sort; two tuples are compared by looking at the terms, the document number is used to break ties. Finally the sorted file is used to generate the index. This approach brings the execution time down in a reasonable range again. Due to tempoary file the space usage is almost twice the size of the total collection.

The "Sort-based compressed" algorithm refines the previous technique and reduces the disk space needed by using compression techniques.

"Sort-based multiway compressed" improves upon the sorting methods with much improved time usage as consequence.


For this project I'll implement the "Sort-based compressed" method.