Compression of Boolean inverted files by document ordering

Boolean queries are used to search a document collection for the documents that contain specific terms, independently of the frequency of a term in the document. To perform such queries, a search engine maintains an inverted file, which lists for each keyword the documents containing it. The size of such a file is comparable with that of the document collection, which is a considerable storage overhead. We show how the inverted file can be compressed by ordering the documents in the collection in a specific way. Finding the near-optimal order can be recast as a Hamming-distance traveling salesman problem.