Compressing an inverted file with LCS

The document index construction is one of the most important concerns in designing an information retrieval system. The most common index structure used in document retrieval is the inverted file, which consists of inverted lists holding lists of pointers to all the locations of the given terms in the documents collected. The size of an inverted file can be reduced by the use of compression techniques. We exploit randomized minimum spanning tree (MST) algorithm, which uses the spanning tree verification and randomized sampling.