基于局部敏感哈希的近似最近鄰查詢研究.pdf

1、高維空間中的近似最近鄰(Approximate Nearest Neighbor, A N N)查詢問題是一個基本的查詢范式,尤其是在多媒體數(shù)據的相似性查詢上有重要的應用價值。近來,局部敏感哈希(Locality Sensitive Hashing, L S H)方法及其改進方法被視為最有希望解決近似最近鄰查詢問題的方法。然而,當前的LSH方法存在一個缺陷,即需要大量的隨機I/O操作來訪問侯選點。同時,為了保證返回結果的準確性,需要訪問

2、足夠多的候選點,從而導致龐大的I/O開銷。
　　為了克服這個缺陷,本文提出一個新的方法,SortingKeys-LSH￡SK-LSH)。該方法通過提高候選集存儲的局部性來減少頁面訪問次數(shù)。本文首先定義了一個新的距離度量方式來估算兩個數(shù)據點的合成哈希值之間的距離。接著,提出一種在合成哈希值集合上的線序關系。這種線序關系可以用來對合成哈希值的集合以及對應的數(shù)據集進行排序。因此,在一個索引文件中,在本文的距離定義下距離相近的數(shù)據點可以被