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

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

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

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