本文選題：相似性檢索 + 位置敏感哈希��； 參考：《中山大學(xué)》2017年博士論文

【摘要】：高維空間中的相似性檢索(High-Dimensional Similarity Search)問題在數(shù)據(jù)庫(kù)、數(shù)據(jù)挖掘以及計(jì)算幾何等領(lǐng)域有著廣泛的應(yīng)用。給定一個(gè)相似性函數(shù),相似性檢索問題是指在數(shù)據(jù)庫(kù)找到一個(gè)數(shù)據(jù)對(duì)象,使得它與一個(gè)給定的查詢對(duì)象的相似度最大。根據(jù)度量函數(shù)的不同,相似性檢索問題有不同的形式。本文著重研究相似性檢索在歐氏空間中三個(gè)非常重要的問題:最近鄰檢索、最遠(yuǎn)鄰檢索和最大內(nèi)積檢索。由于受到維度災(zāi)難的影響,在高維空間中找到精確的結(jié)果代價(jià)非常大,因此近似相似性檢索在近20年得到了廣泛的關(guān)注。然而,目前近似相似性檢索問題仍然存在一些挑戰(zhàn):(1)對(duì)于高維c-近似最近鄰問題,位置敏感哈希(Locality Sensitive Hashing,簡(jiǎn)稱LSH)及其變體是目前最有影響的方法。然而,當(dāng)前LSH函數(shù)由于采用查詢無(wú)關(guān)的分桶策略,容易導(dǎo)致誤分桶,并限制了業(yè)界領(lǐng)先的外存方法LSBForest和C2LSH只能支持c≥2的近似最近鄰檢索;(2)對(duì)于高維c-近似最遠(yuǎn)鄰問題,目前尚沒有一個(gè)高效的外存算法可以處理高維空間中的近似最遠(yuǎn)鄰檢索;(3)對(duì)于高維c-近似最大內(nèi)積問題,業(yè)界領(lǐng)先的方法Sign-ALSH和Simple-LSH沒有充分利用數(shù)據(jù)的分布和查詢的信息,導(dǎo)致檢索的精度和效率偏低。針對(duì)上述這些問題,本文以LSH函數(shù)族和LSH機(jī)制為切入點(diǎn),對(duì)高維歐氏空間中的c-近似最近鄰檢索、c-近似最遠(yuǎn)鄰檢索和c-近似最大內(nèi)積檢索做了深入的研究�？偟膩碚f,本文的主要工作有以下幾點(diǎn):對(duì)于高維c-近似最近鄰問題,本文首先提出了一種針對(duì)lp距離的查詢引導(dǎo)的LSH函數(shù),其中p∈(0,2]。與傳統(tǒng)的LSH函數(shù)相比,該函數(shù)使用查詢的哈希值作為錨點(diǎn),臨時(shí)的對(duì)數(shù)據(jù)對(duì)象進(jìn)行分桶,可以有效避免誤分桶操作�；诓樵円龑�(dǎo)的LSH函數(shù),本文提出了基于外存的新型的查詢引導(dǎo)的位置敏感哈希機(jī)制(QueryAware LSH,簡(jiǎn)稱QALSH)。本文通過理論證明,QALSH對(duì)于近似最近鄰檢索有理論保證,并且可以支持任意的近似比例c1。本文的實(shí)驗(yàn)結(jié)果表明,QALSH勝過業(yè)界領(lǐng)先的LSB-Forest,C2LSH和SRS算法,并且在高維空間中表現(xiàn)尤其出色。對(duì)于高維c-近似最遠(yuǎn)鄰問題,本文首先提出了反轉(zhuǎn)LSH函數(shù)族的概念,并設(shè)計(jì)了一個(gè)切實(shí)有效的反轉(zhuǎn)查詢引導(dǎo)的位置敏感哈希函數(shù)族�；谶@個(gè)新的函數(shù)族,本文提出了兩個(gè)針對(duì)近似最遠(yuǎn)鄰的外存算法RQALSH和RQALSH*。本文通過理論分析表明,RQALSH對(duì)于近似最遠(yuǎn)鄰檢索有理論保證。本文的實(shí)驗(yàn)結(jié)果表明,RQALSH和RQALSH*的性能,要明顯優(yōu)于業(yè)界領(lǐng)先的QDAFN和DrusillaSelect算法。對(duì)于高維c-近似最大內(nèi)積問題,本文通過利用數(shù)據(jù)的分布和查詢的位置信息,提出了一個(gè)基于同心超球的非對(duì)稱的位置敏感哈希機(jī)制(Asymmetric LSH scheme based on Homocentric Hypersphere,簡(jiǎn)稱H2-ALSH)。H2-ALSH機(jī)制對(duì)于近似最大內(nèi)積檢索具有理論保證,并且支持任意近似比例0c1。本文的實(shí)驗(yàn)結(jié)果表明,H2-ALSH機(jī)制可以有效提升查詢的精度,并且H2-ALSH機(jī)制的效率明顯勝過業(yè)界領(lǐng)先的Sign-ALSH和Simple-LSH算法。
[Abstract]:For high - dimensional c - approximate nearest neighbor problem , there is still no efficient external memory algorithm which can handle approximate nearest neighbor retrieval in high - dimensional space . In this paper , we prove that QALSH is better than the industry ' s leading LSB - Forest , C2LSH and SRS algorithms . The experimental results show that RQALSH is superior to the industry ' s leading LSB - Forest , C2LSH and SRS algorithms . The H2 - ALSH mechanism has a theoretical guarantee for the approximate maximum internal product retrieval , and supports any approximate proportion 0c1 . The experimental results show that the H2 - ALSH mechanism can effectively improve the accuracy of the query , and the efficiency of the H2 - ALSH mechanism is obviously better than the industry - leading Sign - ALSH and Simple - LSH algorithm .

【學(xué)位授予單位】：中山大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2017
【分類號(hào)】：TP391.3
，

本文編號(hào)：1791960