面向購物圖像搜索的哈希索引結(jié)構(gòu)算法研究.pdf

1、隨著電子商務(wù)的不斷發(fā)展，網(wǎng)絡(luò)購物因其快捷、方便等優(yōu)點而被越來越多的人所選擇，但隨之而來的是網(wǎng)絡(luò)圖像呈幾何增長。如何在這浩瀚的購物圖像數(shù)據(jù)集中快速有效地返回用戶需要的圖像商品，即圖像的相似性搜索問題，已成為學(xué)術(shù)界和工業(yè)界的最新研究熱點。目前，已有部分購物搜索系統(tǒng)出現(xiàn)，例如:淘淘搜、安圖搜等。而在這些系統(tǒng)中，當用戶上傳一張圖像時，系統(tǒng)返回的時間都相對較長，很難達到用戶的需求。為了提高查詢速度，需要對系統(tǒng)中的數(shù)據(jù)集進行索引結(jié)構(gòu)的建立，一個好的

2、索引結(jié)構(gòu)可以大幅度提高系統(tǒng)檢索速度。
　　 針對這個特點，最初人們提出了通過構(gòu)建樹形索引結(jié)構(gòu)等一系列方法來解決圖像的相似性搜索問題，但這些方法通常只適用于特征向量維度較低的情況。當特征向量維度較高時，這些方法的性能逐漸下降。為了解決該問題，一種基于近似最近鄰搜索算法—LSH（LocalitySensitiveHashing）被提出。該方法適用于高維數(shù)據(jù)且具有快速高效的搜索效果，因此被作為目前用于相似性搜索最為流行的一種方法。

3、r>　　 本文仍從哈希角度出發(fā)，提出了兩種快速有效的局部敏感哈希算法，其旨在保證系統(tǒng)能在一定搜索精確度的情況下減少查詢時間。本文的主要工作和貢獻總結(jié)如下:
　　 第一，提出了一種基于隨機的局部敏感哈希算法。該算法仍遵循LSH思想和框架，但針對現(xiàn)有LSH算法普遍存在的缺陷進行改進。在建立索引時，對于結(jié)構(gòu)中的每個哈希桶，其內(nèi)部特征向量按照與所屬哈希桶的桶中心距離進行升序排列存儲。查詢時，利用三角不等式原理對候選桶向量進行剪枝過濾，

4、減少距離計算次數(shù)，提高查詢速度。
　　 第二，提出了一種基于非隨機的局部敏感哈希算法。該算法針對隨機局部敏感哈希存在的性能不穩(wěn)定性提出改進。在原始數(shù)據(jù)集上根據(jù)分析維度信息量來建立哈希函數(shù)，由于一個固定的數(shù)據(jù)集維度信息量始終不變，因此哈希函數(shù)的選取不具有隨機性，從而保證了算法性能的穩(wěn)定。查詢時，利用多探測檢測思想，除了將與查詢點對應(yīng)哈希桶作為候選桶外，還將臨近桶也作為候選桶，同時，利用三角不等式進行剪枝過濾，提高查詢速度。