Geometric data structures have been extensively studied in the regime where the dimension is much smaller than the number of input points. But in many scenarios in Machine Learning, the dimension can be much higher than the number of points and can be so high that the data structure might be unable to read and store all coordinates of the input and query points. Inspired by these scenarios and related studies in feature selection and explainable clustering, we initiate the study of geometric data structures in this ultra-high dimensional regime. Our focus is the approximate nearest neighbor problem. In this problem, we are given a set of n points C ⊆ ℝ^d and have to produce a small data structure that can quickly answer the following query: given q ∈ ℝ^d, return a point c ∈ C that is approximately nearest to q, where the distance is under 𝓁₁, 𝓁₂, or other norms. Many groundbreaking (1+ε)-approximation algorithms have recently been discovered for 𝓁₁- and 𝓁₂-norm distances in the regime where d≪ n. The main question in this paper is: Is there a data structure with sublinear (o(nd)) space and sublinear (o(d)) query time when d≫ n? This question can be partially answered from the machine-learning literature: - For 𝓁₁-norm distances, an Õ(log(n))-approximation data structure with Õ(n log d) space and O(n) query time can be obtained from explainable clustering techniques [Dasgupta et al. ICML'20; Makarychev and Shan ICML'21; Esfandiari, Mirrokni, and Narayanan SODA'22; Gamlath et al. NeurIPS'21; Charikar and Hu SODA'22]. - For 𝓁₂-norm distances, a (√3+ε)-approximation data structure with Õ(n log(d)/poly(ε)) space and Õ(n/poly(ε)) query time can be obtained from feature selection techniques [Boutsidis, Drineas, and Mahoney NeurIPS'09; Boutsidis et al. IEEE Trans. Inf. Theory'15; Cohen et al. STOC'15]. - For 𝓁_p-norm distances, a O(n^{p-1}log²(n))-approximation data structure with O(nlog(n) + nlog(d)) space and O(n) query time can be obtained from the explainable clustering algorithms of [Gamlath et al. NeurIPS'21]. An important open problem is whether a (1+ε)-approximation data structure exists. This is not known for any norm, even with higher (e.g. poly(n)⋅ o(d)) space and query time. In this paper, we answer this question affirmatively. We present (1+ε)-approximation data structures with the following guarantees. - For 𝓁₁- and 𝓁₂-norm distances: Õ(n log(d)/poly(ε)) space and Õ(n/poly(ε)) query time. We show that these space and time bounds are tight up to poly (log n/ε) factors. - For 𝓁_p-norm distances: Õ(n² log(d) (log log(n)/ε)^p) space and Õ (n(log log(n)/ε)^p) query time. Via simple reductions, our data structures imply sublinear-in-d data structures for some other geometric problems; e.g. approximate orthogonal range search (in the style of [Arya and Mount SoCG'95]), furthest neighbor, and give rise to a sublinear O(1)-approximate representation of k-median and k-means clustering. We hope that this paper inspires future work on sublinear geometric data structures.

In this article, we show that the algorithm of maintaining expander decompositions in graphs undergoing edge deletions directly by removing sparse cuts repeatedly can be made efficient. Formally, for an m-edge undirected graph G, we say a cut is ϕ-sparse if . A ϕ-expander decomposition of G is a partition of V into sets X1,X2,…, Xk such that each cluster G[X1] contains no ϕ-sparse cut (meaning it is a ϕ-expander) with Õ(ϕm) edges crossing between clusters. A natural way to compute a ϕ-expander decomposition is to decompose clusters by ϕ-sparse cuts until no such cut is contained in any cluster. We show that even in graphs undergoing edge deletions, a slight relaxation of this meta-algorithm can be implemented efficiently with amortized update time mo(1)/ϕ2. Our approach naturally extends to maintaining directed ϕ-expander decompositions and ϕ-expander hierarchies and thus gives a unifying framework while having simpler proofs than previous state-of-the-art work. In all settings, our algorithm matches the run-times of previous algorithms up to subpolynomial factors. Moreover, our algorithm provides stronger guarantees for ϕ-expander decompositions. For example, for graphs undergoing edge deletions, our approach is the first to maintain a dynamic expander decomposition where each updated decomposition is a refinement of the previous decomposition, and our approach is the first to guarantee a sublinear ϕm1+ο(1) bound on the total number of edges that cross between clusters across the entire sequence of dynamic updates. Our techniques also give by far the simplest, deterministic algorithms for maintaining Strongly-Connected Components (SCCs) in directed graphs undergoing edge deletions, and for maintaining connectivity in undirected fully-dynamic graphs, both matching the current state-of-the art run-times up to subpolynomial factors. * The full version of the paper can be accessed at https://arxiv.org/abs/2204.02519