Subspace Exploration: Bounds on Projected Frequency Estimation

Summary: Characterizes space for frequency/norm/heavy-hitter estimation under unknown column projections of n×d data, proving 2^Ω(d) lower bounds when subspaces are revealed post-data. Gives coding-theory constructions and combinatorial reductions achieving N^{c'}-approx in min(N^{c'},n) space, improving on naive 2^d. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1839
Venue: PODS
Year: 2021
Pagerank: 5.5181056e-05
Overall Rank: 7,918 | 45.68%
DOI: 10.1145/3452021.3458312

Incoming Non-self Citations Over Time

Authors

1. Graham Cormode (University of Warwick)
2. Charlie Dickens (University of Warwick)
3. David P. Woodruff (Carnegie Mellon University)

BibTeX Citation

@inproceedings{cormode_pods21,
        address = {New York, NY, USA},
        series = {{PODS} '21},
        title = {{Subspace Exploration: Bounds on Projected Frequency Estimation}},
        url = {https://dl.acm.org/doi/10.1145/3452021.3458312},
        doi = {10.1145/3452021.3458312},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Cormode, Graham and Dickens, Charlie and Woodruff, David P.},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,368	Towards Better Bounds for Finding Quasi-Identifiers *	2023	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
482	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00017772185
6,275	BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory	2017	PODS	5.9299343e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,899	Minimum Coresets for Maxima Representation of Multidimensional Data	2021	PODS
2	1,600	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS
3	11,529	Lower Bounds for Sparse Oblivious Subspace Embeddings	2022	PODS
4	1,646	Fast Algorithms for Projected Clustering	1999	SIGMOD
5	1,833	Finding Generalized Projected Clusters in High Dimensional Spaces	2000	SIGMOD
6	5,963	Hierarchical Subspace Sampling: A Unified Framework for High Dimensional Data Reduction, Selectivity Estimation and Nearest Neighbor Search	2002	SIGMOD
7	10,162	On Sketching Trimmed Statistics	2026	PODS
8	8,106	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB
9	13,287	Sparsity-Dimension Trade-Offs for Oblivious Subspace Embeddings	2026	PODS
10	7,926	Space Lower Bounds for Itemset Frequency Sketches	2016	PODS