一种基于学习的高维数据c-近似最近邻查询算法

• 作者: 周傲英 沙朝锋 王晓玲 袁培森
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 随机投影 c-近似最近邻查询 支持向量机分类器 高维数据 熵最大化准则 位置敏感哈希
• 年，卷（期）: 2012,（8）
• 所属期刊栏目: 数据库技术
• 页码范围: 2018-2031
• 分类号: TP311
• 字数: 10534字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2012.04166

摘要

针对高维数据近似最近邻查询,在过滤-验证框架下提出了一种基于学习的数据相关的c-近似最近邻查询算法.证明了数据经过随机投影之后,满足语义哈希技术所需的熵最大化准则.把经过随机投影的二进制数据作为数据的类标号,训练一组分类器用来预测查询的类标号.在此基础上,计算查询与数据集中数据对象的海明距离.最后,在过滤后的候选数据集上计算查询的最近邻与现有方法相比,该方法对空间需求更小,编码长度更短,效率更高.模拟数据集和真实数据集上的实验结果表明,该方法不仅能够提高查询效率,而且方便调控在查询质量和查询处理时间方面的平衡问题.