高维区间搜索的输出敏感工具

Dec, 2013

Output-Sensitive Tools for Range Searching in Higher Dimensions

Micha Sharir, Shai Zaban

TL;DR论文提出一种基于半空间的点集划分技术及相关算法，能在高维空间中构建浅点集的跨度树并实现半空间范围计数，并在空间和查询时间上具有较好的复杂度。

Abstract

Let $P$ be a set of $n$ points in ${\mathbb R}^{d}$. A point $p \in P$ is $k$\emph{-shallow} if it lies in a halfspace which contains at most $k$ points of $P$ (including $p$). We show that if all points of $P$ are $k$-shallow, then $P$ can be partitioned into $\Theta(n/k)$ subsets, so

halfspace partitioning spanning tree dimension range counting

发现论文，激发创造

半空间深度的精确计算

提出了一种基于理论框架的计算点相对于任意维数的数据云的半空间深度的方法，该方法可导出一整个算法类。这些算法中的深度是在数据云的适当投影相对于有限数量的深度值中最小的计算。对该类算法的三种变体进行了更详细的研究。模拟结果表明，所有的算法都能非常高效地处理不处于一般位置甚至包含平局的数据。

Nov, 2014

学习半空间交集的改进难度结果

通过与半空间和所谓的并行煎饼分布的新颖联系，我们以统一的方式获得了较强（而且令人惊讶地简单）的在不适当的情况下学习半空间交集的下界，这是过去几年强大的高维统计学中许多下界构造的核心，我们还给出了统计查询框架下的无条件难度结果。

Feb, 2024

非凸支持数据的快速核半空间深度

通过在再生核希尔伯特空间中扩展半空间深度来处理分布的多模态性，并证明了该深度的一致性和可靠的浓度界限，从而实现了快速计算半空间深度数倍数量级的性能。

Dec, 2023

私密中心点与半空间的学习

介绍了针对任意有限域的高维半空间私有学习器，其样本复杂度为 poly (d,2^log*|X|)。其构造是基于在 m 个点中找到近似中心点的差分隐私算法，可用于设计差分隐私算法，并提供了在凸包中查找点的样本复杂度的下界。

Feb, 2019

针对核范围空间，查询常数数量即可

介绍了核范围空间的 ε- 覆盖概念，研究了它在数据分析中的作用和在高维机器学习中的降维效果，并证明了基于核范围空间的 ε- 覆盖大小不受输入维度和大小的影响，从而揭示了松弛的边界范围查询概念能够消除维度诅咒的奥秘。

Jun, 2023

k-SUM 和相关问题的近似最优线性决策树

本文研究了求解离散几何和组合问题中的线性决策树，提出了一种基于推理维度的新方法来构造线性决策树，并通过比较查询来解决 $K$-SUM 问题、排序 sumsets $A+B$ 以及解决子集 - SUM 问题，与统计学习和离散几何的研究有着密切联系。

May, 2017

子线性时间下的谱聚类预测器

本研究的主要贡献是提出了一种使用子线性时间的谱聚类算法，该算法可以将图按照展开器分簇，并可以提高聚类的准确性，同时通过估计图中节点的随机游走的分布，实现对谱嵌入的点积访问，并使用谱嵌入进行超平面划分，从而实现聚类。

Jan, 2021

随机超平面镶嵌的降维

研究了如何利用随机超平面对区域进行均匀的镶嵌，并利用超平面将欧氏空间中的有界集嵌入哈明空间中，从而实现对欧氏空间中集合的离散化降维。

Nov, 2011

k-means 在平面上甚至需要指数次迭代

证明了 k-means 算法存在关于维数的指数下界，并以平面上的简单构造为例给出了指数下界的证明。

Dec, 2008

关于 Tukey 深度随机近似的质量

图基深度（或半空间深度）是多变量数据的广泛使用的中心度量。然而，精确计算图基深度已知在高维度中是一个难题。作为补救措施，已提出了图基深度的随机近似。在本文中，我们研究了这种随机算法何时能够很好地近似图基深度。我们研究了从对数凹面各向同性分布中抽样的情况。我们证明，如果要求算法在维度上以多项式时间运行，则随机算法正确近似了最大深度 1/2 和接近零的深度。另一方面，对于任何中间深度的点，任何良好的近似都需要指数复杂度。

Sep, 2023