發(fā)布時間：2021-01-20 07:12

　　隨著海量信息檢索技術(shù)的發(fā)展,對文本、圖片和視頻等高維數(shù)據(jù)對象的相似性檢索要求不斷提高。局部敏感哈希（LSH）是解決高維數(shù)據(jù)近鄰檢索的主要方法之一,但存在索引存儲代價(jià)高及查詢效率低等問題。提出了一種基于二級混合索引模型構(gòu)造方法,先利用溢出樹（Spill tree）對數(shù)據(jù)集進(jìn)行劃分,再對每個部分構(gòu)建基于LSH的哈希表,形成混合索引,支撐高維數(shù)據(jù)檢索。試驗(yàn)表明,該方法縮小了高維數(shù)據(jù)對象的索引存儲空間,提高了查詢效率和查詢質(zhì)量。 

【文章來源】：指揮信息系統(tǒng)與技術(shù). 2019,10(06)

【文章頁數(shù)】：5 頁

【部分圖文】：

LSS tree算法分層索引結(jié)構(gòu)

圖2(c)中,若查詢半徑r取值較大,則易于找到滿足條件的k個近鄰點(diǎn),但是會犧牲查詢質(zhì)量;反之,若查詢半徑r取值較小,則需耗費(fèi)更多時間進(jìn)行檢索,影響查詢效率。除了查詢時間指標(biāo)外,對算法性能評估還需考慮查詢質(zhì)量指標(biāo)。暴力搜索屬于精確查詢,而Spill tree算法在葉節(jié)點(diǎn)同樣采用暴力搜索,只要劃分的數(shù)據(jù)點(diǎn)中有k個點(diǎn)置于該葉節(jié)點(diǎn),即可精確滿足近鄰查詢,因此本文不對暴力搜索和Spill tree算法進(jìn)行比較分析。本文僅對LSB和LSS tree 2種算法在不同k值情況下的查準(zhǔn)率Ratio進(jìn)行對比,其對比結(jié)果如表1所示�？梢�,k值選擇對查準(zhǔn)率有一定影響,這是由于LSH算法存在一定的隨機(jī)性,而LSB和LSS算法均基于LSH算法,因此k值上升會導(dǎo)致查準(zhǔn)率Ratio下降。LSB和LSS算法的查準(zhǔn)率較接近,均達(dá)到了較高水平。在查準(zhǔn)率接近情況下,由于LSS算法的查詢消耗時間較短,因此LSS算法的性能相比其他算法有顯著提升。

【參考文獻(xiàn)】：
期刊論文
[1]基于搜索引擎日志的用戶查詢意圖分類[J]. 楊杰,徐越,余建橋,蔣建華.  指揮信息系統(tǒng)與技術(shù). 2019(02)
[2]一種基于主成分的多表圖像哈希檢索方法[J]. 鄧清文,林志賢,郭太良.  計(jì)算機(jī)工程與應(yīng)用. 2018(03)
[3]一種基于LSH面向二元混合類型數(shù)據(jù)的相似性查詢方法[J]. 朱命冬,申德榮,寇月,聶鐵錚,于戈.  計(jì)算機(jī)學(xué)報(bào). 2018(08)

碩士論文
[1]基于位置敏感哈希的近似kNN查詢算法研究[D]. 邱文明.大連理工大學(xué) 2014



本文編號：2988624