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: 5043
Venue: SIGMOD
Year: 2015
Pagerank: 6.215279e-05
Overall Rank: 4,396 | 69.45%
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,942	SliceLine: Fast, Linear-Algebra-based Slice Finding for ML Model Debugging	2021	SIGMOD	0.00010010569
3,780	FEXIPRO: Fast and Exact Inner Product Retrieval in Recommender Systems	2017	SIGMOD	6.7703467e-05
4,350	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD	6.2576191e-05
4,808	On the Complexity of Inner Product Similarity Join	2016	PODS	5.9040739e-05
8,484	Maximum Inner Product is Query-Scaled Nearest Neighbor	2025	VLDB	4.4956257e-05
10,090	Integrating Vector Databases across Embedding Models	2026	SIGMOD	4.1905499e-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
8	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015436578
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076824554
1,299	Bayesian Locality Sensitive Hashing for Fast Similarity Search	2012	VLDB	0.00012712766

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,670	On Efficient Large Sparse Matrix Chain Multiplication	2024	SIGMOD	4.3024878e-05
6,022	Relative Lempel-Ziv Factorization for Efficient Storage and Retrieval of Web Collections	2012	VLDB	5.2365238e-05
10,180	LM-Tree: A Hybrid Learned Index for Similarity Search in Metric Spaces	2026	SIGMOD	4.1905499e-05
7,521	Efficient and Tunable Similar Set Retrieval	2001	SIGMOD	4.7135369e-05
3,541	Similarity search in the blink of an eye with compressed indices	2023	VLDB	6.9910982e-05
8,374	LCS-TRIM: Dynamic Programming Meets XML Indexing and Querying	2007	VLDB	4.5282277e-05
8,484	Maximum Inner Product is Query-Scaled Nearest Neighbor	2025	VLDB	4.4956257e-05
8,645	A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases	2006	SIGMOD	4.4725847e-05
3,427	Efficient EMD-based Similarity Search in Multimedia Databases via Flexible Dimensionality Reduction	2008	SIGMOD	7.1016046e-05
11,508	LES3: Learning-based Exact Set Similarity Search	2021	VLDB	4.1905499e-05