基于乘积量化的近似最近邻算法

摘要

多媒体数据平台难以应付海量数据高效索引和搜索数据的问题,提出了一种解决近似最近邻问题的乘积量化算法。首先,根据海量数据索引和搜索问题的特性,采用近似最近邻思想建立数学模型;然后通过将数据的高维特征分段进行单独k最近邻编码得到数据的压缩编码;其次,根据编码方式建立解码器使得压缩编码可以近似地还原成原始特征。最后利用非对称距离计算的方式,计算出原始向量与压缩编码的距离,根据该距离来判断数据之间的相似程度达到搜索的目的。理论分析表明,与传统的基于局部哈希敏感的数据搜索算法相比,采用非对称距离计算的乘积量化算法在同等时间和召回率的条件下,搜索速度提高了约1 000倍。