# Speeding Up Sparsification using Inner Product Search Data Structures

arXiv: https://arxiv.org/abs/2204.03209 · HTML: https://mlsanity.com/paper/2204.03209/

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Apr 2022.

## Built on by (most cited first, 22 of 22)

- [Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension](https://mlsanity.com/paper/2304.04397/) (2023)
- [A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time](https://mlsanity.com/paper/2309.07418/) (2023)
- [GradientCoin: A Peer-to-Peer Decentralized Large Language Models](https://mlsanity.com/paper/2308.10502/) (2023)
- [A Sublinear Adversarial Training Algorithm](https://mlsanity.com/paper/2208.05395/) (2022)
- [Solving Attention Kernel Regression Problem via Pre-conditioner](https://mlsanity.com/paper/2308.14304/) (2023)
- [Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summations](https://mlsanity.com/paper/2212.11408/) (2022)
- [A Nearly-Optimal Bound for Fast Regression with ℓ_∞ Guarantee](https://mlsanity.com/paper/2302.00248/) (2023)
- [Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Acceleration](https://mlsanity.com/paper/2305.08367/) (2023)
- [Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation](https://mlsanity.com/paper/2306.04169/) (2023)
- [Faster Robust Tensor Power Method for Arbitrary Order](https://mlsanity.com/paper/2306.00406/) (2023)
- [Sublinear Time Algorithm for Online Weighted Bipartite Matching](https://mlsanity.com/paper/2208.03367/) (2022)
- [Fast and Efficient Matching Algorithm with Deadline Instances](https://mlsanity.com/paper/2305.08353/) (2023)
- [Fast John Ellipsoid Computation with Differential Privacy Optimization](https://mlsanity.com/paper/2408.06395/) (2024)
- [Dynamic Maintenance of Kernel Density Estimation Data Structure: From Practice to Theory](https://mlsanity.com/paper/2208.03915/) (2022)
- [Structured and Fast Optimization: The Kronecker SGD Algorithm](https://mlsanity.com/paper/2305.08001/) (2023)
- [Query Complexity of Active Learning for Function Family With Nearly Orthogonal Basis](https://mlsanity.com/paper/2306.03356/) (2023)
- [When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?](https://mlsanity.com/paper/2502.16912/) (2025)
- [Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decoding](https://mlsanity.com/paper/2503.11108/) (2025)
- [Quantum Speedup for Spectral Approximation of Kronecker Products](https://mlsanity.com/paper/2402.07027/) (2024)
- [Accept More, Reject Less: Reducing up to 19% Unnecessary Desk-Rejections over 11 Years of ICLR Data](https://mlsanity.com/paper/2506.20141/) (2025)
- [Towards Sampling Data Structures for Tensor Products in Turnstile Streams](https://mlsanity.com/paper/2510.03678/) (2025)
- [Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Training](https://mlsanity.com/paper/2311.11429/) (2023)

## Abstract (arXiv)

We present a general framework that utilizes different efficient data structures to improve various sparsification problems involving an iterative process. We also provide insights and characterization for different iterative process, and answer that when should we use which data structures in what type of problem. We obtain improved running time for the following problems. * For constructing linear-sized spectral sparsifier (Batson, Spielman and Srivastava, 2012), all the existing deterministic algorithms require Omega(d4) time. In this work, we provide the first deterministic algorithm that breaks that barrier which runs in O(dω+1) time, where ω is the exponent of matrix multiplication. * For one-sided Kadison-Singer-typed discrepancy problem, we give fast algorithms for both small and large number of iterations. * For experimental design problem, we speed up a key swapping process. In the heart of our work is the design of a variety of different inner product search data structures that have efficient initialization, query and update time, compatible to dimensionality reduction and robust against adaptive adversary.