Parallel Methods in Updating/Downdating Problems of the Latent Semantic Indexing

Abstract. In the case of large databases, which are encoded on some sort of a parallel computer (e.g., a supercomputer or a cluster of personal computers), it is frequently needed to update or downdate either documents or terms. This task can be done in parallel based on the theory of the Singular Value Decomposition (SVD) of a Term-Document Matrix (TDM). However, the TDM is usually not explicitly stored and only its truncated SVD in the form of a chosen set of left and right singular vectors and corresponding singular values is at our disposal. Moreover, in the case of huge databases, these components of the truncated SVD may be themselves distributed over a set of processors rather than placed on one processor. For such a distributed system, we will analyze the data structure and computation flow in an updating/downdating problem. It turns out that the most important feature is a special, near-to-triangular form of the TDM, which has to be processed. Therefore, the first step of our method consists of transforming the TDM to triangular form. For triangular matrices, we design a parallel algorithm based on the parallel block Kogbetliantz method under the Message Passing paradigm of communication between processors.