Algoritmos distribuídos para a construção de arquivos invertidos

Abstract

This work presents a family of distributed algorithms to build global inverted files over large text collections. Given a document collection which is distributed among workstations in a network, a global inverted file is an index that allows fast searching in the distributed text as awhole. The index is composed by two parts: the global vocabulary - the set of all distinct words appearing in the distributed text - and the global lists of occurrences pointing to the documents in which each term in the vocabulary occurs. The operating environment considered is a highbandwidth network of workstations which allows the machines to communicate with hardly no contention. The analysis assume that the text is evenly distributed among the workstations and that the index to be generated is considerably larger than the main memory available inthe environment. The inverted lists are sorted by the frequencies of the terms in the documents and compressed in order to reduce the space requirements and the volume of data transferred through the disks and the network. Three alternatives are discussed and their analytical andexperimental results are compared. The experiments show that with four machines the most efficient algorithm can invert 3 gigabytes of text in less than 14 minutes and the analysis point that in the same environment it is feasible to invert a 100-gigabyte collection in less than 6 hours.