Use of the EPSILON Decomposition and the SVD Based LSI Techniques for Reduction of the Large Indexing Structures

摘要

Storage of indexing structures in the Vector Space Model (VSM) form has a number of advantages. In the case when text documents are considered, the indexing structure states the Term-By-Document (TBD) matrix. Its size is proportional to the product of the indexed documents number and the keywords number. In the case of large text documents databases, the size of the indexing structure is a serious limitation. Too large TBD matrix may not be able to be stored in memory or the process of searching for documents may take too much time. The article presents a methodology that allows to reduce the size of the large TBD matrix. The operation performed on the TBD matrix is the Singular Value Decomposition (SVD). It allows to transform the original indexing structure vectors into a space with fewer dimensions. As a result of the operation, keywords used in the indexing process are generalized. This is a desirable effect, methods for generalizing the keywords are called the Latent Sematic Indexing (LSI) methods. Despite the undeniable advantages of the SVD decomposition, it has a big disadvantage. Its computational complexity is O(n~3). In practice, this prevents the application of the method to a large indexing structure. The methodology presented in the article assumes the use of the Epsilon decomposition in order to divide the original TBD matrix into parts before the reduction process. The proposed modification allows the use of the SVD decomposition for the indexing structure of any size.