Latent Semantic Indexing: A Probabilistic Analysis

Summary: Gives a rigorous probabilistic analysis proving LSI recovers latent semantics and improves retrieval under specific generative conditions. Proposes random-projection acceleration and frames results as theoretical justification for spectral methods (e.g., collaborative filtering). (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1140
Venue: PODS
Year: 1998
Pagerank: 0.00012097985
Overall Rank: 1,119 | 92.33%
DOI: 10.1145/275487.275505

Incoming Non-self Citations Over Time

Authors

1. Christos H. Papadimitriou (University of California Berkeley)
2. Prabhakar Raghavan (IBM)
3. Hisao Tamaki (Meiji University)
4. Santosh Vempala (Massachusetts Institute of Technology)

BibTeX Citation

@inproceedings{papadimitriou_pods98,
        address = {New York, NY, USA},
        series = {{PODS} '98},
        title = {{Latent Semantic Indexing: A Probabilistic Analysis}},
        url = {https://dl.acm.org/doi/10.1145/275487.275505},
        doi = {10.1145/275487.275505},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Papadimitriou, Christos H. and Raghavan, Prabhakar and Tamaki, Hisao and Vempala, Santosh},
        year = {1998}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
758	Simrank++: Query Rewriting through Link Analysis of the Click Graph	2008	VLDB	0.00014277369
2,315	SANTOS: Relationship-based Semantic Table Union Search	2023	SIGMOD	8.7605101e-05
3,721	Database-friendly Random Projections	2001	PODS	7.1736703e-05
5,145	Using taxonomy, discriminants, and signatures for navigating in text databases	1997	VLDB	6.3472692e-05
6,110	Clustering via Matrix Powering	2004	PODS	5.9728946e-05
6,646	On the Effects of Dimensionality Reduction on High Dimensional Similarity Search	2001	PODS	5.8148791e-05
8,847	Applications of linear algebra in information retrieval and hypertext analysis	1999	PODS	5.3579487e-05
12,471	Parsimonious Linear Fingerprinting for Time Series	2010	VLDB	5.093636e-05
12,862	Self-similarity in the web	2001	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
170	Combining Fuzzy Information from Multiple Systems	1996	PODS	0.00027376361

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,587	An Efficient Indexing Technique for Full-Text Database Systems	1992	VLDB
2	4,494	Structured Annotations of Web Queries	2010	SIGMOD
3	8,882	Measuring the Structural Similarity of Semistructured Documents Using Entropy	2007	VLDB
4	452	An Architecture for Parallel Topic Models	2010	VLDB
5	6,646	On the Effects of Dimensionality Reduction on High Dimensional Similarity Search	2001	PODS
6	11,702	LES3: Learning-based Exact Set Similarity Search	2021	VLDB
7	287	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB
8	7,942	Efficient and Tunable Similar Set Retrieval	2001	SIGMOD
9	4,359	Incremental Maintenance of Length Normalized Indexes for Approximate String Matching	2009	SIGMOD
10	8,847	Applications of linear algebra in information retrieval and hypertext analysis	1999	PODS