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: hc876059c80ff9ea1
Venue: PODS
Year: 1998
Pagerank: 0.00011852572
Overall Rank: 1,141 | 92.34%
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
788	Simrank++: Query Rewriting through Link Analysis of the Click Graph	2008	VLDB	0.00013980547
1,988	SANTOS: Relationship-based Semantic Table Union Search	2023	SIGMOD	9.2482448e-05
3,784	Database-friendly Random Projections	2001	PODS	7.0223112e-05
5,259	Using taxonomy, discriminants, and signatures for navigating in text databases	1997	VLDB	6.2061655e-05
6,237	Clustering via Matrix Powering	2004	PODS	5.8388788e-05
6,740	On the Effects of Dimensionality Reduction on High Dimensional Similarity Search	2001	PODS	5.6916981e-05
9,011	Applications of linear algebra in information retrieval and hypertext analysis	1999	PODS	5.238062e-05
12,762	Parsimonious Linear Fingerprinting for Time Series	2010	VLDB	4.9793485e-05
13,152	Self-similarity in the web	2001	VLDB	4.9793485e-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
172	Combining Fuzzy Information from Multiple Systems	1996	PODS	0.00026835705

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,020	Querying Probabilistic Information Extraction	2010	VLDB
2	4,567	Structured Annotations of Web Queries	2010	SIGMOD
3	9,042	Measuring the Structural Similarity of Semistructured Documents Using Entropy	2007	VLDB
4	464	An Architecture for Parallel Topic Models	2010	VLDB
5	6,740	On the Effects of Dimensionality Reduction on High Dimensional Similarity Search	2001	PODS
6	9,741	LES3: Learning-based Exact Set Similarity Search	2021	VLDB
7	280	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB
8	8,110	Efficient and Tunable Similar Set Retrieval	2001	SIGMOD
9	4,439	Incremental Maintenance of Length Normalized Indexes for Approximate String Matching	2009	SIGMOD
10	9,011	Applications of linear algebra in information retrieval and hypertext analysis	1999	PODS