Decentralized latent semantic index using distributed average consensus

1. A computer-implemented method for generating a latent semantic index comprising:

calculating, by a distributed computing device, word counts for each of a set of documents, wherein the word counts for each of the set of documents are represented as a plurality of values, each value representing a number of times a corresponding word appears in one of the set of documents, wherein the plurality of values representing the word counts for each document in the set of documents are arranged as a word count vector, wherein the word counts for the set of documents are arranged as a word count matrix;

calculating, by the distributed computing device, sampled word counts by randomly sampling the word counts, wherein calculating the sampled word counts by randomly sampling the word counts comprises calculating a sampled word count matrix by multiplying a random matrix and the word count matrix;

iteratively executing, by the distributed computing device, in conjunction with a plurality of additional distributed computing devices connected to the distributed computing device by a network, a process to determine a consensus result for the sampled word counts, the consensus result based on the sampled word counts calculated by the distributed computing device and additional sampled word counts calculated by the plurality of additional distributed computing devices, the additional sampled user word counts based on additional sets of documents;

determining, by the distributed computing device, a latent semantic index (LSI) subspace based on the consensus result for the sampled word counts, the LSI subspace reflecting contents of the set of documents and the additional sets of documents, wherein the consensus result is a global consensus matrix of a same dimensionality as the sampled word count matrix, and wherein determining the LSI subspace based on the consensus result for the sampled word counts comprises extracting an LSI subspace matrix from the global consensus matrix using orthogonal decomposition; and

projecting, by the distributed computing device, a document into the LSI subspace to determine the latent semantic content of the document.

2. The method of claim 1 , wherein projecting a document into the LSI subspace to determine the latent semantic content of the document comprises multiplying a search word count vector of the document by a transpose of the LSI subspace matrix to generate a subspace search vector characterizing the document in the LSI subspace, the method further comprising:

transmitting the subspace search vector to a second distributed computing device as a search request; and

receiving, from the second distributed computing device, data describing a target document that matches the search request, wherein the second distributed computing device determines the target document matches the search request by comparing the subspace search vector to a target vector characterizing the target document in the LSI subspace.

3. The method of claim 1 , wherein projecting a document into the LSI subspace to determine the latent semantic content of the document comprises:

multiplying a document word count vector of the document by a transpose of the LSI subspace matrix and the LSI subspace matrix to generate a resulting vector, each element in the resulting vector having a value corresponding to a different word; and

extracting, as keywords to describe the document; a set of words corresponding to elements in the resulting vector having high values.

4. The method of claim 1 , wherein iteratively executing the process to determine the consensus result comprises, for a first iteration of the process:

transmitting, over the network, the sampled word counts of the distributed computing device to a second distributed computing device of the plurality of additional distributed computing devices;

receiving, over the network, second sampled word counts generated by the second distributed computing device from the second distributed computing device; and

calculating consensus sampled word counts by computing an average of the sampled word counts and the second sampled word counts.

5. The method of claim 4 , wherein iteratively executing the process to determine the consensus result comprises, for a second iteration of the process:

transmitting, over the network, the consensus sampled word counts of the distributed computing device to a third distributed computing device of the plurality of additional distributed computing devices;

receiving, over the network, additional consensus sampled word counts generated by the third distributed computing device from the third distributed computing device; and

updating the consensus sampled word counts by computing an average of the consensus sampled word counts and the additional consensus sampled word counts.

6. The method of claim 5 , wherein, after a plurality of iterations, the consensus sampled word counts calculated by the distributed computing device substantially converge with consensus sampled word counts calculated by each of remaining ones of the plurality of additional computing devices, and the consensus sampled word counts calculated by the distributed computing device are the consensus result.

7. A non-transitory computer readable storage medium configured to store program code, the program code comprising instructions that, when executed by one or more processors, cause the one or more processors to:

calculate word counts for each of a set of documents of a distributed computing device, wherein the word counts for each of the set of documents are represented as a plurality of values, each value representing a number of times a corresponding word appears in one of the set of documents, wherein the plurality of values representing the word counts for each document in the set of documents are arranged as a word count vector, wherein the word counts for the set of documents are arranged as a word count matrix;

calculate sampled word counts by randomly sampling the word counts, wherein calculating the sampled word counts by randomly sampling the word counts comprises calculating a sampled word count matrix by multiplying a random matrix and the word count matrix;

iteratively execute, in conjunction with a plurality of additional distributed computing devices connected to the distributed computing device by a network, a process to determine a consensus result for the sampled word counts, the consensus result based on the sampled word counts calculated by the distributed computing device and additional sampled word counts calculated by the plurality of additional distributed computing devices, the additional sampled user word counts based on additional sets of documents;

determine a latent semantic index (LSI) subspace based on the consensus result for the sampled word counts, the LSI subspace reflecting contents of the set of documents and the additional sets of documents, wherein the consensus result is a global consensus matrix of a same dimensionality as the sampled word count matrix, and wherein determining the LSI subspace based on the consensus result for the sampled word counts comprises extracting an LSI subspace matrix from the global consensus matrix using orthogonal decomposition; and

project a document into the LSI subspace to determine the latent semantic content of the document.

8. The non-transitory computer readable storage medium of claim 7 , wherein the instructions to project a document into the LSI subspace to determine the latent semantic content of the document comprise instructions to multiply a search word count vector of the document by a transpose of the LSI subspace matrix to generate a subspace search vector characterizing the document in the LSI subspace, and the instructions further comprise instructions to:

transmit the subspace search vector to a second distributed computing device as a search request; and

receive, from the second distributed computing device, data describing a target document that matches the search request, wherein the second distributed computing device determines the target document matches the search request by comparing the subspace search vector to a target vector characterizing the target document in the LSI subspace.

9. The non-transitory computer readable storage medium of claim 8 , wherein the instructions to project a document into the LSI subspace to determine the latent semantic content of the document comprise instructions to:

multiply a document word count vector of the document by a transpose of the LSI subspace matrix and the LSI subspace matrix to generate a resulting vector, each element in the resulting vector having a value corresponding to a different word; and

extract, as keywords to describe the document; a set of words corresponding to elements in the resulting vector having high values.

10. The non-transitory computer readable storage medium of claim 7 , wherein the instructions to iteratively execute the process to determine the consensus result comprise instructions to, for a first iteration of the process:

transmit, over the network, the sampled word counts of the distributed computing device to a second distributed computing device of the plurality of additional distributed computing devices;

receive, over the network, second sampled word counts generated by the second distributed computing device from the second distributed computing device; and

calculate consensus sampled word counts by computing an average of the sampled word counts and the second sampled word counts.

11. The non-transitory computer readable storage medium of claim 10 , wherein the instructions to iteratively execute the process to determine the consensus result comprise instructions to, for a second iteration of the process:

transmit, over the network, the consensus sampled word counts of the distributed computing device to a third distributed computing device of the plurality of additional distributed computing devices;

receive, over the network, additional consensus sampled word counts generated by the third distributed computing device from the third distributed computing device; and

update the consensus sampled word counts by computing an average of the consensus sampled word counts and the additional consensus sampled word counts.

12. The non-transitory computer readable storage medium of claim 11 , wherein, after a plurality of iterations, the consensus sampled word counts calculated by the distributed computing device substantially converge with consensus sampled word counts calculated by each of remaining ones of the plurality of additional computing devices, and the consensus sampled word counts calculated by the distributed computing device are the consensus result.