LEMP: Fast Retrieval of Large Entries in a Matrix Product

Summary: LEMP retrieves large entries in the product of two tall-and-skinny matrices without full matrix computation. It reduces large-entry retrieval to multiple cosine similarity searches and introduces tailored cosine search algorithms, achieving up to 10x speedups. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5042
Venue: SIGMOD
Year: 2015
Pagerank: 6.2211271e-05
Overall Rank: 4,401 | 69.39%
DOI: 10.1145/2723372.2747647

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,940	SliceLine: Fast, Linear-Algebra-based Slice Finding for ML Model Debugging	2021	SIGMOD	0.00010020173
3,772	FEXIPRO: Fast and Exact Inner Product Retrieval in Recommender Systems	2017	SIGMOD	6.7761705e-05
4,353	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD	6.263585e-05
4,808	On the Complexity of Inner Product Similarity Join	2016	PODS	5.908896e-05
8,485	Maximum Inner Product is Query-Scaled Nearest Neighbor	2025	VLDB	4.4999394e-05
10,090	Integrating Vector Databases across Embedding Models	2026	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
7	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015496097
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076637636
1,305	Bayesian Locality Sensitive Hashing for Fast Similarity Search	2012	VLDB	0.00012687101

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,670	On Efficient Large Sparse Matrix Chain Multiplication	2024	SIGMOD	4.3066148e-05
6,018	Relative Lempel-Ziv Factorization for Efficient Storage and Retrieval of Web Collections	2012	VLDB	5.2415551e-05
10,180	LM-Tree: A Hybrid Learned Index for Similarity Search in Metric Spaces	2026	SIGMOD	4.1945683e-05
7,522	Efficient and Tunable Similar Set Retrieval	2001	SIGMOD	4.7180617e-05
3,609	Similarity search in the blink of an eye with compressed indices	2023	VLDB	6.9215236e-05
8,397	LCS-TRIM: Dynamic Programming Meets XML Indexing and Querying	2007	VLDB	4.527474e-05
8,485	Maximum Inner Product is Query-Scaled Nearest Neighbor	2025	VLDB	4.4999394e-05
8,647	A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases	2006	SIGMOD	4.4768766e-05
3,425	Efficient EMD-based Similarity Search in Multimedia Databases via Flexible Dimensionality Reduction	2008	SIGMOD	7.1077107e-05
11,504	LES3: Learning-based Exact Set Similarity Search	2021	VLDB	4.1945683e-05