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

1、隨著以互聯(lián)網(wǎng)技術為代表的計算機技術的普及，世界步入了大數(shù)據(jù)時代。相似性查詢是日常生活中是人們獲取信息的常見手段，更是大數(shù)據(jù)時代至關重要的需求。大數(shù)據(jù)在給人們帶來豐富資訊和高質(zhì)量體驗的同時，也對很多傳統(tǒng)領域產(chǎn)生了挑戰(zhàn)。維度災難使得基于空間劃分和數(shù)據(jù)劃分的索引方式不再能有效解決查詢問題，為此研究者提出近似相似性查詢的理念，以少量查詢精度為代價大大減少查詢耗時。
　　局部敏感哈希技術(Locality Sensitive Hashing

2、,LSH)作為近似相似性查詢的最新技術，逐漸成為研究熱點，其基本思想可以概括為過濾-驗證框架(Filter-and-Refine Framework)，即先過濾掉低概率相似的數(shù)據(jù)對象，然后精確計算候選數(shù)據(jù)對象和查詢項之間的相似度，這就大大減少了查詢所需的精確計算，從而可以快速得出查詢結果。局部敏感哈希使用大量哈希表以高概率保證計算的準確性，這造成了基于LSH的算法空間開銷過大的缺陷。
　　本文提出一種分布式和集中式的LSH近似近鄰

3、查找算法，即基于Multi-probe的分布式LSH近似近鄰查找方案和基于海明距離的LSH近似近鄰查找算法。分布式方案側重于通過Multi-probe技術，在Chord環(huán)上構建分布式索引的方法，在保證召回率的情況下顯著減少哈希表數(shù)量；集中式算法利用哈希結果產(chǎn)生的特征指紋，用隨機抽取的方式產(chǎn)生指紋子串并構建索引表，通過比較查詢項和數(shù)據(jù)項的項指紋子串的海明距離，對數(shù)據(jù)項賦予權值以減少候選數(shù)據(jù)集大小?？傊?，通過分布式和集中式兩種方法，分別對應