Decentralized Latent Semantic Index Using Distributed Average Consensus

Abstract

A distributed computing device calculates word counts for each of a set of documents. The word counts are represented as values, each representing a number of times a corresponding word appears in one of the set of documents. The distributed computing device randomly samples the word counts to calculate sampled word counts. The distributed computing device and additional distributed computing devices iteratively execute a process to determine a consensus result for the sampled word counts based on the sampled word counts and additional sampled word counts calculated by the additional distributed computing devices. The distributed computing device determines a latent semantic index (LSI) subspace based on the consensus result for the sampled word count and reflecting contents of the set and additional sets of documents. The distributed computing device projects a document into the LSI subspace to determine the latent semantic content of the document.

What is claimed is: 
     
         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;   calculating, by the distributed computing device, sampled word counts by randomly sampling the word counts;   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; 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 the plurality of values representing the word counts for each document in the set of documents are arranged as a word count vector; the word counts for the set of documents are arranged as a word count matrix; and 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. 
     
     
         3 . The method of  claim 2 , 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. 
     
     
         4 . The method of  claim 3 , 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.   
     
     
         5 . The method of  claim 3 , 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.   
     
     
         6 . 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.   
     
     
         7 . The method of  claim 6 , 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.   
     
     
         8 . The method of  claim 7 , 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. 
     
     
         9 . 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;   calculate sampled word counts by randomly sampling the word counts;   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; and   project a document into the LSI subspace to determine the latent semantic content of the document.   
     
     
         10 . The non-transitory computer readable storage medium of  claim 9 , wherein the plurality of values representing the word counts for each document in the set of documents are arranged as a word count vector; the word counts for the set of documents are arranged as a word count matrix; and wherein the instructions to calculate the sampled word counts by randomly sampling the word counts comprise instructions to calculate a sampled word count matrix by multiplying a random matrix and the word count matrix. 
     
     
         11 . The non-transitory computer readable storage medium of  claim 10 , wherein the consensus result is a global consensus matrix of a same dimensionality as the sampled word count matrix, and wherein the instructions to determine the LSI subspace based on the consensus result for the sampled word counts comprise instructions to extract an LSI subspace matrix from the global consensus matrix using orthogonal decomposition. 
     
     
         12 . The non-transitory computer readable storage medium of  claim 11 , 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.   
     
     
         13 . The non-transitory computer readable storage medium of  claim 12 , 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.   
     
     
         14 . The non-transitory computer readable storage medium of  claim 9 , 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.   
     
     
         15 . The non-transitory computer readable storage medium of  claim 14 , 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.   
     
     
         16 . The non-transitory computer readable storage medium of  claim 15 , 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. 
     
     
         17 . A computer-implemented method for performing a search comprising:
 calculating, by a search device, a word count vector for one of a document or a set of keywords, wherein each element of the word count vector has a value representing instances of a different word in the document or the set of keywords;   projecting, by the search device, the word count vector into a latent semantic index (LSI) subspace to generate a subspace search vector characterizing the document in the LSI subspace, the LSI subspace generated cooperatively by a plurality of distributed computing devices connected by a network based on a corpus of documents, the LSI subspace reflecting contents of the corpus of documents;   transmitting, by the search device, the subspace search vector to target device as a search request; and   receiving, from the target device in response to the search request, data describing a target document that matches the search request, wherein the target 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.   
     
     
         18 . The method of  claim 17 , wherein projecting the word count vector into the LSI subspace comprises multiplying the word count vector by a transpose of an LSI subspace matrix describing the LSI subspace. 
     
     
         19 . The method of  claim 17 , wherein the data describing the target document that matches the search request comprises a match value indicates the measure of distance between the subspace search vector and the target vector, the match value calculated using one of a dot product of the subspace search vector and the target vector and a Euclidean distance between the subspace search vector and the target vector. 
     
     
         20 . The method of  claim 17 , wherein the search device is one of the plurality of distributed computing devices, the search device comprising a portion of the corpus of documents, the method further comprising:
 iteratively executing, by the search device in conjunction with additional ones of the plurality of distributed computing devices, a process to determine a consensus result based on sampled word counts of the corpus of documents generated by the search device and the additional ones of the plurality of distributed computing devices; and   determining the LSI subspace based on the consensus result for the sampled word counts.