किसी दिए गए वेक्टर में वेक्टर शब्दकोश के लिए फास्ट लुकअप। उच्च आयाम

Question

मैं ऐसे उत्तरों की तलाश कर रहा हूं जो स्केल करते हैं, लेकिन मेरे विशिष्ट उद्देश्य के लिए, मेरे पास 48 वां आयाम वेक्टर है। इसे 0 और 255 के बीच 48 पूर्णांक की सरणी के रूप में दर्शाया जा सकता है।

मेरे पास इन वैक्टरों का एक बड़ा शब्दकोश है, उनमें से लगभग 25 हजार।

मुझे अपने वेक्टर लेने में सक्षम होना चाहिए जो मेरे डेटाबेस में हो सकता है या नहीं, और जल्दी से पता चलता है कि डेटाबेस से कौन सा वेक्टर निकटतम है। निकटतम से, मेरा मतलब पारंपरिक दूरी सूत्र के संदर्भ में है।

मेरा कोड पायथन में समाप्त होगा लेकिन यह एक सामान्य प्रश्न है।

ब्रूट फोर्स बहुत धीमी है। मुझे एक करीबी शब्दकोश स्पीड लुकअप चाहिए। किसी के पास कोई विचार है?

Answer 1

एक और तकनीक है कि उपयोगी साबित होगा इलाके संवेदनशील हैशिंग है। यदि आप एक वेक्टर लौटने से खुश हैं जो लगभग निकटतम पड़ोसी है, तो तेज समाधान हैं। यहां देखें (http://www.cs.umd.edu/~mount/ANN/)

Answer 2

मैं kd-tree को लागू करने का सुझाव दूंगा जिस पर आप Nearest neighbour search कर सकते हैं। के आयामों में एन बिंदुओं के लिए सबसे खराब मामला खोज समय O(k.N^(1-1/k)) है, इसलिए इसे एन

में समय-समय पर स्केल करना चाहिए यदि मेरे पास समय है तो मैं इस उत्तर पर वापस आऊंगा और विकिपीडिया के बारे में कम जानकारी प्रदान करूंगा।

चूंकि आप पाइथन में काम कर रहे हैं क्योंकि kdtrees पर इस सिसिकी कुकबुक प्रविष्टि में मदद करनी चाहिए। http://en.wikipedia.org/wiki/Locality_sensitive_hashing

इसके अपने प्रश्न से स्पष्ट नहीं है कि आप निकटतम पड़ोसियों -exact- की जरूरत है: