Algorithms
在具有稀疏向量的非常高維空間中查找緊密對
我有（約一百萬）個特徵向量。有（約一百萬）個二元特徵，但僅在每個向量中（〜一千）他們將是，其餘的是. 我正在尋找至少具有（〜一百）共同特徵（同時）。這種對的數量與（約一百萬）。
我認為這可以被視為在一個非常高維的空間中尋找接近點對。距離函數可能是這樣的，它基於兩個向量有多少共同特徵。但它也可能對更傳統的距離度量（例如歐幾里得）有用。
哪些著名的算法可用於解決此問題？任何二次方的或者將不實用。
問題的一個示例現實世界公式是考慮人們在多個地點之間移動。如果兩個人同時在同一地點，我們就說他們相遇了。（至少有 1 人在場的位置-時間組合的數量為.) 我們正在尋找朋友：至少見過面的人次。
看起來您正在尋找的方法是 minhash 簽名和 Locality Sensitive Hashing (LSH) 的組合；Mining Massive Datasets的（免費）pdf在第 3 章中詳細描述了這種方法（和其他相似性度量），但簡要說明：
minhash簽名是原始矩陣的濃縮表示，它是通過對特徵應用一定數量的n個哈希函數來構造的，從而減少每次觀察的特徵數量。這會減少數據的大小，但是您可能會注意到這仍然會給您留下一個問題。
為了解決這個問題，MMDS 建議，如果您只想找到高於某個相似度閾值的配對（這似乎適用於您的情況），那麼您可以只關注那些最有可能相似的配對 - 這種方法稱為Locality Sensitive Hashing，在第 3.4 節中，他們介紹瞭如何將 minhash 簽名方法與 LSH 相結合的示例。
除了課文，Coursera 課程也有同名講座。