उत्पादन प्रणाली के लिए सिमहाश और मिनहाश के बीच चयन

Question

मैं सिमहाश और मिनहाश की एलएसएच (लोकैलिटी सेंसिटिव हैशिंग) तकनीकों से परिचित हूं। सिमहाश वास्तविक मूल्यवान डेटा पर कोसाइन समानता का उपयोग करता है। MinHash बाइनरी वैक्टर पर समानता समानता की गणना करता है। लेकिन मैं तय नहीं कर सकता कि कौन सा उपयोग करना बेहतर होगा।

मैं अर्ध-संरचित टेक्स्ट डेटा के डुप्लीकेट के पास खोजने के लिए वेबसाइट के लिए बैकएंड सिस्टम बना रहा हूं। उदाहरण के लिए, प्रत्येक रिकॉर्ड एक शीर्षक, स्थान, और एक संक्षिप्त पाठ विवरण (< 500 शब्द) होगा।

विशिष्ट भाषा कार्यान्वयन एक तरफ, कौन सा एल्गोरिदम ग्रीनफील्ड उत्पादन प्रणाली के लिए सबसे अच्छा होगा?

Answer 1

यह पेपर आपको दो एल्गोरिदम पर कुछ विचार दे सकता है।

http://jmlr.org/proceedings/papers/v33/shrivastava14.pdf

Answer 2

Simhash तेजी से (बहुत तेजी से) और आम तौर पर कम मेमोरी की आवश्यकता है, लेकिन कैसे भिन्न दो दस्तावेज़ों हो सकता है और अभी भी डुप्लिकेट के रूप में पता लगाया जा पर एक सख्त सीमा लगाता है। यदि आप 64-बिट सिमशैश (एक सामान्य पसंद) का उपयोग कर रहे हैं, और इस पर निर्भर करता है कि आप कितने अनुमत तालिकाओं को संग्रहित करने में सक्षम हैं, तो आप 3 या कम से कम 6 या 7 जितनी कम दूरी पर हैमिंग दूरी तक सीमित हो सकते हैं। छोटे हथौड़ा दूरी हैं! आप उन दस्तावेजों का पता लगाने तक ही सीमित रहेंगे जो अधिकतर समान हैं, और फिर भी आपको सिमशैश में जाने के लिए चुनने वाली सुविधाओं और आप उन्हें क्या वेटिंग देते हैं, इसके बारे में कुछ सावधानीपूर्वक ट्यूनिंग करने की आवश्यकता हो सकती है।

सिमशैश की पीढ़ी को Google द्वारा पेटेंट किया जाता है, हालांकि व्यवहार में वे कम से कम गैर-वाणिज्यिक उपयोग की अनुमति देते हैं।

Minhash के बाद आप आम तौर पर दस्तावेज़ प्रति 50-400 हैश भंडारण होगी, अधिक स्मृति का उपयोग करता है, और यह सीपीयू कुशल simhash के रूप में के रूप में नहीं है, लेकिन यह है, तो आप काफी दूर समानता खोजने की अनुमति देता उदा यदि आप चाहें तो 5% अनुमानित समानता के रूप में कम। सिमशैश की तुलना में यह समझना थोड़ा आसान है, खासकर टेबल के काम के तरीके के संदर्भ में। यह लागू करने के लिए काफी सरल है, आमतौर पर शिंगलिंग का उपयोग करते हुए, और अच्छे नतीजे पाने के लिए बहुत सारी ट्यूनिंग की आवश्यकता नहीं होती है। यह पेटेंट नहीं है (मेरे ज्ञान के लिए)।

यदि आप बड़े डेटा से निपट रहे हैं, तो मिशैश दृष्टिकोण का सबसे सीपीयू-गहन हिस्सा के बाद होगा, आपने अपने दस्तावेज़ के लिए मिन्हैश उत्पन्न किए हैं, जब आप अपनी तालिका के माध्यम से अन्य ढूंढने के लिए शिकार कर रहे हैं दस्तावेज जो इसके कुछ हैंश साझा करते हैं। दस या हजारों दस्तावेज हो सकते हैं जो कम से कम एक हैश साझा करते हैं, और आपको उन सभी को खोजने के लिए इन्हें खरपतवार करना होगा उदा। कम से कम आधा हैश। सिन्हाश यहां बहुत तेज है।

जैसा कि ओमर ने अपनी टिप्पणी में बताया है, मिन्हैश के अनुकूलन हैं जो आपको प्रति समान कम हैश के साथ समानता अनुमानों पर समान सटीकता प्राप्त करने की अनुमति देते हैं। यह आपके द्वारा किए जाने वाले खरपतवार की मात्रा को काफी हद तक कम कर सकता है।

संपादित करें:

मैं अब superminhash कोशिश की है। यह काफी तेज़ है, हालांकि मेरे उद्देश्यों के लिए मिन्हैश using a single hash function plus bit-transformations to produce all the other hashes का मेरा कार्यान्वयन तेजी से था। यह अधिक सटीक जैककार्ड अनुमान प्रदान करता है, मैंने परीक्षण की कुछ स्थितियों के तहत लगभग 15% बेहतर (हालांकि दूसरों के बीच लगभग कोई अंतर नहीं)। इसका मतलब यह चाहिए कि आप ही सटीकता प्राप्त करने के लिए एक तिहाई कम हैश के बारे में की जरूरत है। अपनी तालिका में कम हैश भंडारण का मतलब है कम "निराई" के पास डुप्लिकेट है, जो एक महत्वपूर्ण गति-अप उद्धार की पहचान करने की जरूरत है। मुझे सुपरमिंहश पर किसी भी पेटेंट से अवगत नहीं है।धन्यवाद ओमार!