匹配400萬行數據並按相似性對結果進行排序的最佳方法？

我們使用libpuzzle（http://www.pureftpd.org/project/libpuzzle/doc）比較400萬張圖片的相似度。匹配400萬行數據並按相似性對結果進行排序的最佳方法？

它工作得很好。

但是，而不是使用libpuzzle函數做圖像與圖像比較，還有另一種比較圖像的方法。

下面是一些背景知識：

Libpuzzle產生任何給定的圖像的相當小（544字節）的哈希值。這個散列可以反過來用來比較使用libpuzzles函數的其他散列。有幾個API ...... PHP，C等等......我們正在使用PHP API。

比較圖像的另一種方法是通過從給定的散列創建矢量，這裏是從文檔的糊劑：

切割成固定長度的字的矢量。例如，讓我們考慮以下矢量：

[ABCDEFGHIJKLMNOPQRSTU VWXYZ]

隨着字長（K）的10，就可以得到下面的話：

[ABCDEFGHIJ]在位置0找到 [bcdefghijk]發現在1位 [cdefghijkl]在2位等發現直到位置N-1

然後，索引你以（字的化合物索引向量+ p osition）。

即使有數百萬的圖像，K = 10和N = 100也應該足以讓只有很少的條目共享相同的索引。

所以，我們有矢量法工作。它實際上比圖像與圖像比較好一些，因爲當我們進行圖像與圖像比較時，我們使用其他數據來減少我們的樣本大小。它與我們用來減少樣本大小的其他數據有些不相關，也沒有特定應用，但是使用矢量方法...我們不必這樣做，我們可以對400萬個哈希中的每一個進行真實測試。

我們的問題是：

400萬倍的圖像，每幅圖像100個向量，這成爲4個億行。我們發現MySQL在大約60000個圖像（60000 x 100 = 600萬行）之後往往會窒息。

我們使用的查詢如下：

SELECT isw.itemid, COUNT(isw.word) as strength 
FROM vectors isw 
JOIN vectors isw_search ON isw.word = isw_search.word 
WHERE isw_search.itemid = {ITEM ID TO COMPARE AGAINST ALL OTHER ENTRIES} 
GROUP BY isw.itemid;

如前所述，即使有正確的索引，上面是相當緩慢的，當涉及到400萬行。

那麼，任何人都可以提出任何其他技術/算法來測試這些相似性？

我們願意付出一切。

有些事情值得一提：

哈希是二進制的。
哈希總是長度相同，544字節。

我們已經能夠拿出的最好的是：從二進制

轉換圖像的哈希值，以ASCII碼。
創建載體。
創建一個字符串如下：VECTOR1 VECTOR2 VECTOR3等等
使用sphinx進行搜索。

我們還沒有嘗試過上述內容，但是這可能會產生比mysql查詢更好的結果。

任何想法？如前所述，我們願意安裝任何新服務（postgresql？hadoop？）。

最後要說明的是，該矢量+比較方法的工作原理可以在Libpuzzle Indexing millions of pictures?問題中找到。我們實際上使用Jason提供的確切方法（目前是最後一個答案，授予200+以上的分數）。

來源

2013-03-30 anonymous-one

我對hadhaop集羣和Hadoop上的Mahout有很好的體驗。也許你想嘗試一下。 –

使用全文搜索引擎應該工作得很好。只有確保使用正確的排名方法。你可能不想使用TF-IDF之類的東西。 – nwellnhof

另一個問題是'相同的序列在同一個位置上具有相同的值'，這意味着您可能只需要存儲每10個字節，並將其與輸入圖像進行異或運算。如果你得到幾個字節xor = 0，那麼做一個完整的比較。 400萬個55byte的短哈希將適合220Mb，並且您可以在一個好的系統上掃描所有這一秒。取決於你想要走多快。無法找到任何樣本哈希來測試這個理論，雖然...並不想回答沒有測試的可靠性 – rlb

不要在數據庫中這樣做，只需使用簡單的文件。下面我已經示出的一些詞的文件從所述兩個vectores [abcdefghijklmnopqrst]（圖像1）和[xxcdefghijklxxxxxxxx]（圖像2）

<index>  <image> 
0abcdefghij  1 
1bcdefghijk  1 
2cdefghijkl  1 
3defghijklm  1 
4efghijklmn  1 
... 
... 
0xxcdefghij  2 
1xcdefghijk  2 
2cdefghijkl  2 
3defghijklx  2 
4efghijklxx  2 
...

現在排序的文件：

<index>  <image> 
0abcdefghij  1 
0xxcdefghij  2 
1bcdefghijk  1 
1xcdefghijk  2 
2cdefghijkl  1  
2cdefghijkl  2  <= the index is repeated, those we have a match 
3defghijklm  1 
3defghijklx  2 
4efghijklmn  1 
4efghijklxx  2

當文件已經排序很容易找到具有相同索引的記錄。寫一個小程序或一些可以運行經過排序的列表並找到重複的東西。

來源

2013-03-30 13:58:58

我選擇'回答我自己'的問題，因爲我們發現了一個很好的解決方案。

在最初的問題中，我提到我們正在考慮通過獅身人面像搜索來做到這一點。

好吧，我們繼續做下去，結果更好，然後通過mysql來做到這一點。

所以，本質上的過程是這樣的：

一個）從生成圖像的哈希值。 b）將這個散列向量化爲100個部分。 c）binhex（二進制到十六進制），因爲它們是二進制格式，所以這些向量中的每一個都是二進制的。

d）在sphinx中搜索如下所示：

itemid | 0_vector0 1_vector1 2_vec ...等等

e）使用sphinx搜索進行搜索。

最初......一旦我們擁有了這個充滿400萬條記錄的獅身人面像庫，每次搜索仍然需要大約1秒。

然後，我們爲8個核心上的sphinxbase啓用了分佈式索引，現在每秒鐘將會查詢大約10次以上的搜索結果。這對我們來說已經足夠了。

最後一步是將這個sphinxbase進一步分發到我們擁有的多個服務器上，進一步利用我們可用的未使用的cpu週期。

但是暫且不夠好。我們每天增加大約1000-2000個'物品'，因此通過'只是新的'搜索會很快發生......在我們進行初步掃描之後。

來源

2013-03-31 15:03:36

匹配400萬行數據並按相似性對結果進行排序的最佳方法？

回答

相關問題