高维空间中的最近邻搜索

基于摘要分析。该学位论文研究通用高维空间中的精确与近似最近邻搜索（NNS），贡献包括基于距离下界的精确检索、面向外存 I/O 的学习型近似检索，以及近似 NNS 算法的系统评估；研究对象不是 EEG 或 BCI。 精确 NNS 部分提出 compounded embedding，将高维点映射到低维空间，并使嵌入后两点的距离成为原空间欧氏距离的下界。在 filter-and-verify 框架下，算法利用该下界剪除候选，再进行验证。作者报告，在多种真实数据上的实验显示该方法具有有效性与效率优势；摘要未给出具体数据集、加速倍数及基线配置。 近似 NNS 部分面向外存检索，通过学习哈希函数构建数据敏感索引，重点优化 I/O，尤其是顺序 I/O。索引由多个点 ID 列表组成，按学习函数的输出值排序，以近似保留高维空间中的次序关系；作者考虑了线性与非线性两种函数，并分别设计学习目标，但摘要未提供目标函数形式。作者报告，在六个大规模高维数据集上，学习型索引相较所比较的外存近似 NNS 方法具有更好的 I/O 效率与搜索准确性，具体指标定义及数值尚未验证。 系统评估涵盖来自不同领域及实践实现的 19 种算法、20 个数据集、多种指标与查询负载。作者另提出一种方法，并报告其在多数数据集的广泛设置下兼具较高查询效率与召回率；摘要不足以核对该方法与前述索引的关系。实验协议、消融及统计信息尚未验证。 平台推测（待验证）：若 EEG 应用需要检索大规模固定长度特征向量，上述机制可能用于加速相似片段查询，而非直接提升解码性能。可复用距离下界剪枝与索引模块，但需先确定特征表示、距离及索引更新策略；精确检索的保证依赖原方法的欧氏距离下界条件。低信噪比与跨被试分布变化可能使近邻缺乏任务意义，小数据规模也可能无法抵消建索引成本。可在同一批 EEG 特征和固定查询集上，以穷举欧氏距离检索为参照，检验精确结果一致性，并比较近似检索的召回率、延迟和 I/O 开销。已有 EEG 相关工作尚未检索确认。