更快速且空间高效的局部敏感哈希索引构建

基于摘要分析。本文研究欧氏距离与余弦相似度下局部敏感哈希（LSH）的索引构建，提出以 count sketch 和 higher-order count sketch 替代传统随机高斯投影的哈希码生成算法，目标是降低高维数据、多维哈希码场景中的计算与存储开销。其主要研究对象是通用近似相似性检索，并非 EEG 或 BCI 解码。 传统 ELSH 与 SRP 根据数据点的哈希码将其分配到哈希表的桶中。摘要指出，为 d 维向量生成 m 维哈希码时，传统方法的时间与空间复杂度均为 O(md)。作者提出面向欧氏距离的 CSELSH、HCSELSH，以及面向余弦相似度的 CSSRP、HCSSRP：其中 CSELSH、CSSRP 使用 count sketch，另外两种使用 higher-order count sketch。 作者报告，这些方案将哈希码计算时间降至 O(d)；CSELSH、CSSRP 将空间复杂度降至 O(d)，HCSELSH、HCSSRP 则降至 O(N·d^(1/N))。摘要将 N≥1 描述为输入或重塑后张量的大小，其精确定义及复杂度成立条件需核对全文。这些复杂度针对哈希码生成环节，不宜直接解释为完整索引构建或检索流程的端到端成本。作者称提供了数学保证，并在多个真实数据集上进行模拟验证，但摘要未列出数据集名称、检索质量、运行时间或内存测量；实验协议、消融及统计信息尚未验证。 平台推测（待验证）：若 EEG 应用需要对大量固定维度特征向量进行近邻检索，可假设这些 sketch 哈希方法能够降低检索索引的构建开销。可复用部分是哈希码生成，仍需确定 EEG 特征表示、距离度量及张量重塑方式；低信噪比、跨被试分布变化和通道差异可能使欧氏距离或余弦相似度失去任务意义，小样本下索引收益也可能有限。一个可检验的小实验是固定 EEG 特征与检索集合，在相同哈希码长度和哈希表设置下，对比传统 ELSH/SRP 与相应变体的构建时间、峰值内存及相对于精确近邻的召回率。相关 EEG 工作尚未检索确认，这一迁移假设不代表已验证的 BCI 效果。