RPA：一种内存高效的度量空间recall@R近似最近邻搜索索引（英文）

现有的度量空间的近似最近邻搜索（approximate nearest neighbor search, ANNS）方法通常依赖于预选择的支撑点构成的序列，序列中的支撑点按照到数据元素的距离升序排列．然而，大多数现有的度量空间ANNS方法由于索引结构复杂、支撑点过多或者未能充分利用距离信息导致搜索时内存开销巨大．为此，提出精简排列阵（reduced permutation array, RPA）的度量空间recall@R近似最近邻搜索方法．对于全体数据元素，RPA预先选择k个支撑点，对每个数据元素仅存储离该数据元素最近的l个（l?k），并将所有元素的支撑点序列构建为一个数组结构．在搜索过程中，利用一种得分函数，该函数基于查询对象到各个支撑点的距离来近似计算数据元素到查询对象的距离．同时，维护一个有界最小堆，以保存R个候选结果数据元素．RPA具有结构简单、内存效率高和可扩展性强等特点．实验结果表明，在相同召回率的情况下，与排列索引（permutation-based index, P-index）相比，RPA平均具有高达3倍的内存压缩比．研究结果可在内存资源有限的单机环境下提供一种有效的...