基于汉明距离预测矩阵的二进制向量检索
本文提出了一种利用概率多项式计算对数域上任意对称布尔函数并控制误差的低阶多项式方案,借此算法可在超对数维度中在真正的亚二次时间内求解汉明距离,并且能够对内积最大的向量,有最近的 ell1 对和杰卡德系数最大的向量对进行计算。
Jul, 2015
本文提出了一种基于量化的快速 Johnson-Lindenstrauss 嵌入法,该方法使用有界正交系统和部分循环集合进行快速的嵌入,并利用噪声整形实现积极的降噪机制,该方法的误差多项式和指数衰减,是当前二进制嵌入和汉明距离所能达到的巅峰效果;此外,本文还提出了一种基于噪声整形机制的量化压缩感知度量方法,该方法在测量值的数量和比特数上实现了误差的多项式和指数衰减,是目前处理有限正交系统的最优表现。
Jan, 2018
本论文提出一种使用基于多索引哈希表(multi-index hash tables)方法的加权二进制编码查询算法,通过引入加权汉明距离和表格查找算法及表格合并算法,成功提高了查询的搜索效率和准确性。
Nov, 2019
本文介绍了一种新的量子算法,以解决预定大小的已知集合中的未知 N 位字符串的甄别问题,还在量子学习理论中应用该算法并改进了其复杂度,并且提出一种新的组合定理,使我们能够编写没有错误降低的具有依赖性查询复杂度的量子算法,最后用此方法消除了布尔矩阵乘法的最优量子算法中所有的对数因子。
Nov, 2013
复杂模型的查询通常需要复杂的计算和长时间的响应,因此弱模型能够快速提供不准确的结果,在使用少量查询到更强大的模型解决不准确性时具有优势。本文设计和分析了实用的算法,仅使用少量准确查询来处理低质量的不准确模型,接近于给定问题的经典算法性能,并且在许多方面证明了我们的算法是最佳的。此外,我们还概述了拓展至其他类型的 matroid oracle、非自由的 dirty oracle 以及其他 matroid 问题。
Feb, 2024
该研究探讨了分布式协议用于在大型数据集中查找所有相似向量对的方法,重点关注 Hamming 距离,提出了一种新型组合优化问题来捕捉分析上的核心,展示了边等周形状的设计方法和新的距离相关性界限。
Nov, 2016
本文提出了一种基于二进制编码的非线性降维方法,能够在保留原始空间结构的同时,将高维数据嵌入到汉明立方体中,实现对任意集合中点的编码,并在理论上证明了该方法的最优位数下界及哈明距离下的非遗忘式编码,同时针对一般点集甚至无限点集提供了分析结果,并通过实验验证了理论结论的有效性。
Feb, 2015
使用互不偏基的基向量作为寻味向量,以估计矩阵迹,要求生成每个向量仅需 O (log (n)) 个随机比特,从而显著地提高了单次采样方差,同时也改进了传统方法。
Jul, 2016