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: 1807
Venue: PODS
Year: 2021
Pagerank: 4.7180617e-05
Overall Rank: 7,496 | 47.86%
DOI: 10.1145/3452021.3458312

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,162	Towards Better Bounds for Finding Quasi-Identifiers *	2023	PODS	4.1945683e-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
383	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00024820873
2,884	BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory	2017	PODS	7.9620506e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,168	Evaluating Clustering in Subspace Projections of High Dimensional Data	2009	VLDB	4.5701004e-05
13,800	Design and Analysis of Subspace Clustering Algorithms and their Applicability	2002	VLDB	-
9,772	Minimum Coresets for Maxima Representation of Multidimensional Data	2021	PODS	4.2856106e-05
1,629	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS	0.00011085267
11,330	Lower Bounds for Sparse Oblivious Subspace Embeddings	2022	PODS	4.1945683e-05
1,595	Fast Algorithms for Projected Clustering	1999	SIGMOD	0.00011222442
2,019	Finding Generalized Projected Clusters in High Dimensional Spaces	2000	SIGMOD	9.7707059e-05
5,065	Hierarchical Subspace Sampling: A Unified Framework for High Dimensional Data Reduction, Selectivity Estimation and Nearest Neighbor Search	2002	SIGMOD	5.7247716e-05
8,203	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB	4.5596344e-05
7,504	Space Lower Bounds for Itemset Frequency Sketches	2016	PODS	4.7180617e-05