Parallel latent semantic analysis using a graphics processing unit

ABSTRACT

Latent Semantic Analysis (LSA) can be used to reduce the dimensions of large Term-Document datasets using Singular Value Decomposition. However, with the ever expanding size of data sets, current implementations are not fast enough to quickly and easily compute the results on a standard PC. The Graphics Processing Unit (GPU) can solve some highly parallel problems much faster than the traditional sequential processor (CPU). Thus, a deployable system using a GPU to speedup large-scale LSA processes would be a much more effective choice (in terms of cost/performance ratio) than using a computer cluster. In this paper, we presented a parallel LSA implementation on the GPU, using NVIDIA R Compute Unified Device Architecture (CUDA) and Compute Unified Basic Linear Algebra Subprograms (CUBLAS). The performance of this implementation is compared to traditional LSA implementation on CPU using an optimized Basic Linear Algebra Subprograms library. For large matrices that have dimensions divisible by 16, the GPU algorithm ran five to six times faster than the CPU version.

REFERENCES

• 1: N. Adams, G. Blunt, D. Hand, and M. Kelly. Data mining for fun and profit. Statistical Science, 15(2):111--131, 2000.
• 2: M. Berry. Large-scale sparse singular value computations. The International Journal of Supercomputer Applications, 6(1):13--49, 1992.
• 3: S. T. Dumais , G. W. Furnas , T. K. Landauer , S. Deerwester , R. Harshman, Using latent semantic analysis to improve access to textual information, Proceedings of the SIGCHI conference on Human factors in computing systems, p.281-285, May 15-19, 1988, Washington, D.C., United States [doi>10.1145/57167.57214]
• 4: N. Galoppo, N. Govindaraju, M. Henson, and D. Manocha. E±cient algorithms for solving dense linear systems on graphics hardware. In Proceedings of the 2005 Coordinated and Multiple Views in Exploratory Visualization Conference, Washington, D.C., United States, March 2005.
• 5: H.-P. Kersken and U. Kuster. A parallel lanczos algorithm for eigensystem calculation. Technical Report 310, University of Stuttgart, 1999.
• 6: C. Lanczos. An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. J. Res. Natl. Bureau Stand., 45(1):255--282, 1950.
• 7: S. Manavski and G. Valle. Cuda compatible gpu cards as efficient hardware accelerators for smith-waterman sequence alignment. BMC Bioinformatics, 9(2), 2008.
• 8: Nvidia. Cuda:compute unied device architecture. Technical Report 2, NVIDIA, 2008.
• 9: J. Owens, D. Luebke, N. Govindaraju, M. Harris, J. Kruger, A. Lefohn, and T. Purcell. A survey of general-purpose computation on graphics hardware. Computer Graphics Forum, 26(1):80--113, 2007.
• 10: C. Paige, B. Parlett, and H. V. der Vorst. Approximate solutions and eigenvalue bounds from krylov subspaces. Numerical Linear Algebra with Applications, 2(2):115--134, 1995.
• 11: B. Parlett and D. Scott. The lanczos algorithm with selective orthogonalization. Mathematics of Computation, 33(145):217--238, 1979.
• 12: P. Robert, S. Schoepke, and H. Bieri. Hybrid ray tracing -- ray tracing using gpu-accelerated image-space methods. In Proceedings of the 2007 International Conference on Computer Graphics Theory, pages 305--311, Barcelona, Spain, 2007.
• 13: Gerard Salton , Christopher Buckley, Term-weighting approaches in automatic text retrieval, Information Processing and Management: an International Journal, v.24 n.5, p.513-523, 1988 [doi>10.1016/0306-4573(88)90021-0]
• 14: H. Simon. The lanczos algorithm with partial reorthogonalization. Mathematics of Computation, 42(165):115--142, 1984.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.m Miscellaneous

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures; Process metrics

General Terms:
Algorithms, Performance

Keywords:
gpu, latent semantic indexing, text mining