大規模資料庫之索引學習

10.29428/9789860544169.201801.0181

王正賢；邱志義

最近鄰居 ； 量化流失 ； 深度神經網路 ； nearest neighbor ； quantization loss ； deep neural networks

NCS 2017 全國計算機會議

2017（2018 / 01 / 01）

968 - 972

繁體中文

本論文中，我們提出一種新穎的方法，透過學習最近鄰居（近鄰）關係，重新定義索引結構（重新排序）。給予一個查詢值，如要找出有那些群離查詢值最相近，最直接的方法就是利用歐幾里得距離，算出每群與查詢值的距離後排序。然而資料進行量化後所產生的資訊流失而影響準確率是無法避免的。為了解決這個問題，我們使用了近鄰概率來取代原先以歐幾里得距離來排名的方式。我們提出了兩種演算法，離線訓練與在線索引，仍是基於深度神經網路(deep neural networks，簡稱DNN)的架構下學習近鄰關係。實驗結果顯示，使用我們提出的方法重新排序檢索表後，在一百萬及十億筆資料裡都有著令人滿意的成果。

In this paper, we present a novel ranking scheme that learns the nearest neighbor relation embedded in the index structure. Given a query point, a direct way to rank clusters of the index structure is based on their Euclidean distances to the query from near to far. However, the data quantization loss will inevitably impair the index accuracy. To address this problem, the proposed method ranks clusters based on the nearest neighbor probabilities of clusters rather than their Euclidean distances. We present two algorithms for offline training and online indexing that leverage the deep neural networks to learn the neighborhood relation. Experiments on one million and one billion datasets demonstrate a promising result of the proposed ranking scheme.