标题： 近似最近邻和核密度估计的次线性草图 显示英文标题

标题： Sublinear Sketches for Approximate Nearest Neighbor and Kernel Density Estimation

摘要： 近似最近邻（ANN）搜索和近似核密度估计（A-KDE）是现代机器学习核心的基本问题，在数据分析、信息系统和大规模决策中有着广泛的应用。在大规模和动态的数据流中，一个中心挑战是设计紧凑的摘要，这些摘要能够保留数据的本质结构特性，同时支持高效的查询。在本工作中，我们开发了新的摘要算法，对于动态数据流，这两种ANN和A-KDE都能实现次线性空间和查询时间保证。对于流模型中的ANN，在自然假设下，我们设计了一个仅需$\mathcal{O}(n^{1+\rho-\eta})$内存的次线性摘要，通过仅存储总输入的次线性（$n^{-\eta}$）比例，其中$\rho$是LSH族的一个参数，且$0<\eta<1$。我们的方法支持次线性查询时间、批量查询，并扩展到更一般的Turnstile模型。虽然之前的研究集中在精确NN上，但这是第一个在内存大小和近似误差之间实现接近最优权衡的ANN结果。 接下来，在滑动窗口模型中，我们提出一个大小为$\mathcal{O}\left(RW \cdot \frac{1}{\sqrt{1+\epsilon} - 1} \log^2 N\right)$的概要，其中$R$是概要的行数，$W$是 LSH 范围，$N$是窗口大小，$\epsilon$是近似误差。 据我们所知，这是在滑动窗口模型中针对 A-KDE 的第一个理论上的次线性概要保证。 我们通过在各种真实数据集上的实验来补充我们的理论结果，这些实验表明所提出的概要轻量级且在实践中始终表现出较低的误差。 显示英文摘要

摘要： 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+\rho-\eta})$ memory by storing only a sublinear ($n^{-\eta}$) fraction of the total inputs, where $\rho$ is a parameter of the LSH family, and $0<\eta<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+\epsilon} - 1} \log^2 N\right)$, where $R$ is the number of sketch rows, $W$ is the LSH range, $N$ is the window size, and $\epsilon$ 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.