In a distributed system that includes a collection of machines, a server system generates a global dictionary from sampling responses received from machines in the collection of machine, at least a subject of the sampling responses including information indicating one or more terms in a corpus of information stored at a respective machine in the collection of machines. The global dictionary includes global document frequency values corresponding to the document frequencies of terms in the corpora of information stored in the collection of machines. The server system generates a similarity search query for a target document, the similarity search query including identifiers of terms in the target document and optionally document frequency information for those terms, obtained from the global dictionary, and sends, through one or more linear communication orbits, the similarity search query to one or more respective machines in the collection of machines.