Latent semantic indexing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Latent semantic indexing: a probabilistic analysis

Full text

Pdf (1.08 MB)

Source

Symposium on Principles of Database Systems archive
Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems table of contents

Seattle, Washington, United States

Pages: 159 - 168

Year of Publication: 1998

ISBN:0-89791-996-3

Authors

Christos H. Papadimitriou	Computer Science Division, U. C. Berkeley
Hisao Tamaki	Computer Science Department, Meiji University
Prabhakar Raghavan	IBM Almaden Research Center
Santosh Vempala	Department of Mathematics, M.I.T.

Sponsors

SIGART: ACM Special Interest Group on Artificial Intelligence
SIGMOD: ACM Special Interest Group on Management of Data
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 21, Downloads (12 Months): 163, Citation Count: 71

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/275487.275505 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Michael W. Berry , Susan T. Dumais , Gavin W. O'Brien, Using linear algebra for intelligent information retrieval, SIAM Review, v.37 n.4, p.573-595, Dec. 1995 [doi>10.1137/1037127]
	2	Michael Berry , Theresa Do , Gavin O''Brien , Vijay K %A , Sowmini Varadhan, SVDPACKC (Version 1.0) User''s Guide, University of Tennessee, Knoxville, TN, 1993
	3	E. Brewer. Invited talk, 1997 PODS}SIGMOD, 1997.
	4	S. Chakrabarti, B. Dora, D. Gibson, J. Kleinberg, P. Raghavan and S. Rajagopalan. "Mining information networks through spectral methods". In preparation, IBM Almaden Research Center, 1997.
	5	D.M. Cvetkovi~, M. Doob, and H. Sachs, Spectra of Graphs, Academic Press, 1979.
	6	S. Deerwester, S. T. Dumais, T.K. Landauer, G.W. Furnas, and R.A. Harshman. Indexing by latent semantic analysis. :Journal of the Society for Information Science, 41(6), 391-407, 1990.
	7	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]
	8	S.T. Dumais. Improving the retrieval of information from external sources. Behavior Research Methods, Instruments and Computers, 23(2), 229- 236, 1991.
	9	Ronald Fagin, Combining fuzzy information from multiple systems (extended abstract), Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.216-226, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237715]
	10	Christos Faloutsos , Douglas W. Oard, A survey of information retrieval and filtering methods, University of Maryland at College Park, College Park, MD, 1995
	11	P. Frankl , H. Maehara, The Johnson-Lindenstrauss Lemma and the sphericity of some graphs, Journal of Combinatorial Theory Series A, v.44 n.3, p.355-362, June 1987
	12	A. Frieze, R. Kannan and S. Vempala, "Fast Monte-Carlo Algorithms for finding low-rank approximations," preprint, http://wwwmath.mit.edu/vempala/papers/fastev.ps , 1998.
	13	Norbert Fuhr, Probabilistic models in information retrieval, The Computer Journal, v.35 n.3, p.243-255, June 1992 [doi>10.1093/comjnl/35.3.243]
	14	D. Gibson, J.M. Kleinberg and P. Rag.havan. "Using nonlinear dynamical systems to mine categorical data". Submitted for publication, 1997.
	15	G. Golub and G. Reinsch. Handbook for matrix computation II, Linear Algebra. Springer-Veflag, New York, 1971.
	16	G, H. Golub and G. F. Van Loan. Matrix computations. Johns Hopkins University Press, London, 1989.
	17	W, Hoeffding. Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association 58 13-30, 1963.
	18	Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
	19	W, B. Johnson and J. Lindenstrauss. Extensions of Lipshitz mapping into Hflbert space, Contemp. Math. 26 (1984), 189-206.
	20	M. Jerrum , Alistair Sinclair, Approximating the permanent, SIAM Journal on Computing, v.18 n.6, p.1149-1178, Dec. 1989 [doi>10.1137/0218077]
	21	Prabhakar Raghavan, Information retrieval algorithms: a survey, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.11-18, January 05-07, 1997, New Orleans, Louisiana, United States
	22	C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
	23	Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
	24	Howard R. Turtle , W. Bruce Croft, A comparison of text retrieval models, The Computer Journal, v.35 n.3, p.279-290, June 1992 [doi>10.1093/comjnl/35.3.279]
	25	J. H. Wilkinson, The algebraic eigenvalue problem, Oxford University Press, Inc., New York, NY, 1988

CITED BY 72

	Inderjit S. Dhillon , Dharmendra S. Modha, Concept Decompositions for Large Sparse Text Data Using Clustering, Machine Learning, v.42 n.1-2, p.143-175, January-February 2001
	Ravindran Kannan , Santosh Vempala, Spectral Algorithms, Foundations and Trends® in Theoretical Computer Science, v.4 n.3–4, p.157-288, March 2009
	Petros Drineas , Iordanis Kerenidis , Prabhakar Raghavan, Competitive recommendation systems, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Charu C. Aggarwal, On the effects of dimensionality reduction on high dimensional similarity search, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.256-266, May 2001, Santa Barbara, California, United States
	Chris H. Q. Ding, A similarity-based probability model for latent semantic indexing, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.58-65, August 15-19, 1999, Berkeley, California, United States
	Alessandra Alaniz Macedo , Maria da Graca Campos Pimentel , Jose Antonio Camacho-Guerrero, An infrastructure for open latent semantic linking, Proceedings of the thirteenth ACM conference on Hypertext and hypermedia, June 11-15, 2002, College Park, Maryland, USA
	Andrew Y. Ng , Alice X. Zheng , Michael I. Jordan, Stable algorithms for link analysis, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.258-266, September 2001, New Orleans, Louisiana, United States
	Jong P. Yoon , Vijay Raghavan , Venu Chakilam , Larry Kerschberg, BitCube: A Three-Dimensional Bitmap Indexing for XML Documents, Journal of Intelligent Information Systems, v.17 n.2-3, p.241-254, December 2001
	Chris H. Q. Ding, A probabilistic model for latent semantic indexing in information retrieval and filtering, Computational information retrieval, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2001
	Dimitris Achlioptas, Database-friendly random projections, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.274-281, May 2001, Santa Barbara, California, United States
	Ella Bingham , Heikki Mannila, Random projection in dimensionality reduction: applications to image and text data, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.245-250, August 26-29, 2001, San Francisco, California
	Parry Husbands , Horst Simon , Chris H. Q. Ding, On the use of the singular value decomposition for text retrieval, Computational information retrieval, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2001
	Rie Kubota Ando, Latent semantic space: iterative scaling improves precision of inter-document similarity measurement, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.216-223, July 24-28, 2000, Athens, Greece
	Thorsten Joachims, A statistical learning learning model of text classification for support vector machines, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.128-136, September 2001, New Orleans, Louisiana, United States
	Dimitris Achlioptas , Frank McSherry, Fast computation of low rank matrix approximations, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.611-618, July 2001, Hersonissos, Greece
	Charu C. Aggarwal , Srinivasan Parthasarathy, Mining massively incomplete data sets by conceptual reconstruction, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.227-232, August 26-29, 2001, San Francisco, California
	Alessandra Alaniz Macedo , Maria da Graça Campos Pimentel , José Antonio Camacho Guerrero, Latent semantic linking over homogeneous repositories, Proceedings of the 2001 ACM Symposium on Document engineering, November 09-10, 2001, Atlanta, Georgia, USA
	R. Lempel , S. Moran, SALSA: the stochastic approach for link-structure analysis, ACM Transactions on Information Systems (TOIS), v.19 n.2, p.131-160, April 2001
	Xiaoying Tai , Fuji Ren , Kenji Kita, An information retrieval model based on vector space method by supervised learning, Information Processing and Management: an International Journal, v.38 n.6, p.749-764, November 2002
	Tao Li , Shenghuo Zhu , Mitsunori Ogihara, Efficient multi-way text categorization via generalized discriminant analysis, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA
	Ella Bingham , Ata Kabán , Mark Girolami, Topic Identification in Dynamical Text by Complexity Pursuit, Neural Processing Letters, v.17 n.1, p.69-83, 2003
	Ella Bingham , Heikki Mannila , Jouni K. Seppänen, Topics in 0--1 data, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada
	Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999
	Dimitris Achlioptas, Database-friendly random projections: Johnson-Lindenstrauss with binary coins, Journal of Computer and System Sciences, v.66 n.4, p.671-687, 1 June 2003
	A. Kabán , M. A. Girolami, Fast Extraction of Semantic Features from a Latent Semantic Indexed Text Corpus, Neural Processing Letters, v.15 n.1, p.31-43, February 2002
	Lars Engebretsen , Piotr Indyk , Ryan O'Donnell, Derandomized dimensionality reduction with applications, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.705-712, January 06-08, 2002, San Francisco, California
	Rodrigo B. Almeida , Virgilio A. F. Almeida, A community-aware search engine, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA
	Xiaofei He , Deng Cai , Haifeng Liu , Wei-Ying Ma, Locality preserving indexing for document representation, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom
	Fuji Ren , Shingo Kuroiwa, New advances on multi-lingual multi-function multi-media intelligent system, Focus on computational neurobiology, Nova Science Publishers, Inc., Commack, NY, 2004
	Krista Lagus , Samuel Kaski , Teuvo Kohonen, Mining massive document collections by the WEBSOM method, Information Sciences: an International Journal, v.163 n.1-3, p.135-156, 14 June 2004
	Chunqiang Tang , Sandhya Dwarkadas , Zhichen Xu, On scaling latent semantic indexing for large peer-to-peer systems, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom
	Deepayan Chakrabarti , Spiros Papadimitriou , Dharmendra S. Modha , Christos Faloutsos, Fully automatic cross-associations, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA
	Jia-Yu Pan , Hyung-Jeong Yang , Christos Faloutsos , Pinar Duygulu, Automatic multimedia cross-modal correlation discovery, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA
	Charu C. Aggarwal, An Efficient Subspace Sampling Framework for High-Dimensional Data Reduction, Selectivity Estimation, and Nearest-Neighbor Search, IEEE Transactions on Knowledge and Data Engineering, v.16 n.10, p.1247-1262, October 2004
	Alexei Vinokourov , Mark Girolami, A Probabilistic Framework for the Hierarchic Organisation and Classification of Document Collections, Journal of Intelligent Information Systems, v.18 n.2-3, p.153-172, March-May 2002
	Efficient Semantic-Based Content Search in P2P Network, IEEE Transactions on Knowledge and Data Engineering, v.16 n.7, p.813-826, July 2004
	Srinivasan Parthasarathy , Charu C. Aggarwal, On the Use of Conceptual Reconstruction for Mining Massively Incomplete Data Sets, IEEE Transactions on Knowledge and Data Engineering, v.15 n.6, p.1512-1521, November 2003
	Hanson Zhou , David Woodruff, Clustering via matrix powering, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France
	Mark Sandler, On the use of linear programming for unsupervised text classification, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
	Sameep Mehta , Srinivasan Parthasarathy , Hui Yang, Toward Unsupervised Correlation Preserving Discretization, IEEE Transactions on Knowledge and Data Engineering, v.17 n.9, p.1174-1185, September 2005
	Holger Bast , Debapriyo Majumdar, Why spectral retrieval works, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil
	Jacob G. Martin, Subproblem optimization by gene correlation with singular value decomposition, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA
	Ali Shokoufandeh , Diego Macrini , Sven Dickinson , Kaleem Siddiqi , Steven W. Zucker, Indexing Hierarchical Structures Using Graph Spectra, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.7, p.1125-1140, July 2005
	Bill B. Wang , R. I. Bob Mckay , Hussein A. Abbass , Michael Barlow, A comparative study for domain ontology guided feature extraction, Proceedings of the twenty-sixth Australasian conference on Computer science: research and practice in information technology, p.69-78, February 01, 2003, Adelaide, Australia
	Parry Husbands , Horst Simon , Chris Ding, Term norm distribution and its effects on latent semantic indexing, Information Processing and Management: an International Journal, v.41 n.4, p.777-787, July 2005
	Chris H. Q. Ding, A probabilistic model for Latent Semantic Indexing: Research Articles, Journal of the American Society for Information Science and Technology, v.56 n.6, p.597-608, April 2005
	Deng Cai , Xiaofei He, Orthogonal locality preserving indexing, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil
	Mikko Kurimo, Thematic indexing of spoken documents by using self-organizing maps, Speech Communication, v.38 n.1, p.29-45, September 2002
	Jimeng Sun , Dacheng Tao , Christos Faloutsos, Beyond streams and graphs: dynamic tensor analysis, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
	Ping Li , Trevor J. Hastie , Kenneth W. Church, Very sparse random projections, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
	Jieping Ye, Generalized Low Rank Approximations of Matrices, Machine Learning, v.61 n.1-3, p.167-191, November 2005
	Rada Mihalcea , Michel Simard, Parallel texts, Natural Language Engineering, v.11 n.3, p.239-246, September 2005
	M. Sahlgren , J. Karlgren, Automatic bilingual lexicon acquisition using random indexing of parallel corpora, Natural Language Engineering, v.11 n.3, p.327-341, September 2005
	Branko Horvat , Milan Ojsteršek, Towards the novel classification schemes in digital libraries, Proceedings of the 6th WSEAS International Conference on Distance Learning and Web Engineering, p.62-67, September 22-24, 2006, Lisbon, Portugal
	Odysseas Papapetrou, Full-text indexing and information retrieval in P2P systems, Proceedings of the 2008 EDBT Ph.D. workshop, March 25-25, 2008, Nantes, France
	Magnus Sahlgren , Rickard Cöster, Using bag-of-concepts to improve the performance of support vector machines in text categorization, Proceedings of the 20th international conference on Computational Linguistics, p.487-es, August 23-27, 2004, Geneva, Switzerland
	Noga Alon , Baruch Awerbuch , Yossi Azar , Boaz Patt-Shamir, Tell me who I am: an interactive recommendation system, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
	Stanley Loh , Leandro Krug Wives , José Palazzo M. de Oliveira, Concept-based knowledge discovery in texts extracted from the Web, ACM SIGKDD Explorations Newsletter, v.2 n.1, p.29-39, June, 2000
	Rabab Hayek , Guillaume Raschia , Patrick Valduriez , Noureddine Mouaddib, Summary management in P2P systems, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France
	Gianluigi Greco , Sergio Greco , Ester Zumpano, Web Communities: Models and Algorithms, World Wide Web, v.7 n.1, p.59-82, March 2004
	Tao Li , Shenghuo Zhu , Mitsunori Ogihara, Text categorization via generalized discriminant analysis, Information Processing and Management: an International Journal, v.44 n.5, p.1684-1697, September, 2008
	Deng Cai , Xiaofei He , Wei Vivian Zhang , Jiawei Han, Regularized locality preserving indexing via spectral regression, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal
	Darin Brezeale , Diane J. Cook, Learning video preferences from video content, Proceedings of the 8th international workshop on Multimedia data mining: (associated with the ACM SIGKDD 2007), p.1-9, August 12-12, 2007, San Jose, California
	Ping Li, Very sparse stable random projections for dimension reduction in lα (0 <α ≤ 2) norm, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA
	Christos Boutsidis , Jimeng Sun , Nikos Anerousis, Clustered subset selection and its applications on it service metrics, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA
	Yu-En Lu , Pietro Lió , Steven Hand, On low dimensional random projections and similarity search, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA
	Jingyu Hou, A Matrix-Based Model for Web Page Community Construction and More, Informatica, v.18 n.2, p.217-238, April 2007
	Heng Huang , Chris Ding , Dijun Luo , Tao Li, Simultaneous tensor subspace selection and clustering: the equivalence of high order svd and k-means clustering, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA
	Ioannis Antonellis , Hector Garcia Molina , Chi Chao Chang, Simrank++: query rewriting through link analysis of the click graph, Proceedings of the VLDB Endowment, v.1 n.1, August 2008
	Jimeng Sun , Dacheng Tao , Spiros Papadimitriou , Philip S. Yu , Christos Faloutsos, Incremental tensor analysis: Theory and applications, ACM Transactions on Knowledge Discovery from Data (TKDD), v.2 n.3, p.1-37, October 2008
	Aviv Nisgav , Boaz Patt-Shamir, Finding similar users in social networks: extended abstract, Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, August 11-13, 2009, Calgary, AB, Canada
	Deng Cai , Xiaofei He , Jiawei Han, Document Clustering Using Locality Preserving Indexing, IEEE Transactions on Knowledge and Data Engineering, v.17 n.12, p.1624-1637, December 2005