提出两种轻量级数据流压缩方法，实现近似最近邻与核密度估计的高效查询。
Sublinear Sketches for Approximate Nearest Neighbor and Kernel Density Estimation
- 通过子线性存储策略，仅保留部分输入数据构建紧凑索引。
- 在动态数据流中实现近似最近邻查询，内存占用为 n^(1+ρ-η)，查询时间亚线性。
- 首次在滑动窗口模型下给出核密度估计的理论子线性压缩保证，适合大规模实时分析。
近似最近邻（ANN）搜索和近似核密度估计（A-KDE）是现代机器学习的核心问题，广泛应用于数据分析、信息系统与大规模决策。在海量动态数据流中，核心挑战在于设计紧凑的摘要（sketch），在保留数据关键结构的同时支持高效查询。本文提出新的压缩算法，首次在动态数据流中实现ANN与A-KDE的子线性空间与查询时间保证。对于流式模型下的ANN，假设合理条件下，所提方法仅需 $\mathcal{O}(n^{1+ρ-η})$ 内存，仅存储总输入的 $n^{-η}$ 分数，支持亚线性查询时间、批量查询，并可扩展至更通用的Turnstile模型；此前工作多关注精确最近邻，本工作首次实现近似场景下内存与误差间的近最优权衡。对于滑动窗口模型下的A-KDE，提出大小为 $\mathcal{O}\left(RW \cdot \frac{1}{\sqrt{1+ε} - 1} \log^2 N\right)$ 的压缩结构，其中 $R$ 为行数，$W$ 为LSH范围，$N$ 为窗口大小，$ε$ 为近似误差；据我们所知，这是首个在该模型下具备理论子线性压缩保证的A-KDE方案。我们在多个真实数据集上进行了实验，结果表明所提方法轻量且实际误差低。
原文摘要 · Abstract (English)
Approximate Nearest Neighbor (ANN) search and Approximate Kernel Density Estimation (A-KDE) are fundamental problems at the core of modern machine learning, with broad applications in data analysis, information systems, and large-scale decision making. In massive and dynamic data streams, a central challenge is to design compact sketches that preserve essential structural properties of the data while enabling efficient queries. In this work, we develop new sketching algorithms that achieve sublinear space and query time guarantees for both ANN and A-KDE for a dynamic stream of data. For ANN in the streaming model, under natural assumptions, we design a sublinear sketch that requires only $\mathcal{O}(n^{1+ρ-η})$ memory by storing only a sublinear ($n^{-η}$) fraction of the total inputs, where $ρ$ is a parameter of the LSH family, and $0<η<1$. Our method supports sublinear query time, batch queries, and extends to the more general Turnstile model. While earlier works have focused on Exact NN, this is the first result on ANN that achieves near-optimal trade-offs between memory size and approximation error. Next, for A-KDE in the Sliding-Window model, we propose a sketch of size $\mathcal{O}\left(RW \cdot \frac{1}{\sqrt{1+ε} - 1} \log^2 N\right)$, where $R$ is the number of sketch rows, $W$ is the LSH range, $N$ is the window size, and $ε$ is the approximation error. This, to the best of our knowledge, is the first theoretical sublinear sketch guarantee for A-KDE in the Sliding-Window model. We complement our theoretical results with experiments on various real-world datasets, which show that the proposed sketches are lightweight and achieve consistently low error in practice.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。