एसक्यूएल कुशल निकटतम पड़ोसी क्वेरी

Question

मैं मुसीबत एक कुशल SQL क्वेरी निम्नलिखित स्थिति से निपटने के साथ आ रही है:

मान लें हम दो कॉलम

groupId : int 
value : float 

के साथ एक मेज है तालिका बहुत बड़ा है (कई मिलियन पंक्तियां)। "GroupId" प्रति "मूल्य" की एक अलग मात्रा है - 100 और 50.000 के बीच कुछ कहें। सभी फ्लोट मान शून्य से अधिक या बराबर होते हैं लेकिन अन्यथा असंबद्ध होते हैं।

किसी दिए गए समूह के लिए क्वेरी को समानता को कम करके क्रमबद्ध सभी अन्य समूहों को वापस करना चाहिए जहां "समान" को दो समूहों में 30 मूल्यों के सभी संभावित जोड़े के बीच न्यूनतम यूक्लिडियन दूरी के रूप में परिभाषित किया जाना चाहिए।

समानता की परिभाषा मुझे मार देती है। मुझे लगता है कि नैएव एल्गोरिदम के ऊपर परिभाषित समानता की गणना करने के लिए ओ (एन^2) है। अब मैं विचारों की तलाश कर रहा हूं या तो "समानता" या उपरोक्त के एक कुशल कार्यान्वयन को फिर से परिभाषित करने के लिए विचारों की तलाश कर रहा हूं। मैं एक के-निकटतम पड़ोसी से जुड़े एक समाधान की कल्पना कर सकता हूं, पोस्टगिस ज्यामितीय निकटतम पड़ोसियों या शायद सबसे बड़ा आम अनुवर्ती एल्गोरिदम (जैसे मुझे बाद में "अस्पष्ट" कार्यान्वयन की आवश्यकता होगी क्योंकि "मूल्य" शायद ही कभी बराबर बराबर तुलना करेगा) ।

वर्तमान में मामले में हम अपने एसक्यूएल पर हैं।

चियर्स,

Sören 

Answer 1

आपको यह सत्यापित किया जा सका है कि मैं सवाल का अधिकार मिल गया?

आपकी तालिका समूह आईडी द्वारा पहचाने गए वैक्टर का प्रतिनिधित्व करती है। प्रत्येक वेक्टर में 100 से 50,000 के बीच कुछ आयाम होता है, लेकिन आयाम पर कोई आदेश परिभाषित नहीं किया जाता है। यह तालिका से एक वेक्टर वास्तव में समकक्ष वर्ग का प्रतिनिधि है।

अब आप दो समकक्ष वर्गों की समानता को समानता वर्गों के किसी भी दो प्रतिनिधि के अनुमानों की न्यूनतम यूक्लिडियन दूरी के रूप में परिभाषित करते हैं, जो पहले 30 आयामों के उप-स्थान पर हैं। दो आयामों को प्रक्षेपण के लिए

उदाहरण:

A = <1, 2, 3, 4> 
B = <5, 6, 7, 8, 9, 10> 

एक वैक्टर की निम्नलिखित तुल्यता वर्ग का प्रतिनिधित्व करता है।

<1, 2, 3, 4> <2, 1, 2, 3> <3, 1, 2, 4> <4, 1, 2, 3> 
<1, 2, 4, 4> <2, 1, 3, 2> <3, 1, 4, 2> <4, 1, 3, 2> 
<1, 3, 2, 4> <2, 3, 1, 4> <3, 2, 1, 4> <4, 2, 1, 3> 
<1, 3, 4, 2> <2, 3, 4, 1> <3, 2, 4, 1> <4, 2, 3, 1> 
<1, 4, 2, 2> <2, 4, 1, 3> <3, 4, 1, 2> <4, 3, 1, 2> 
<1, 4, 3, 2> <2, 4, 3, 1> <3, 4, 2, 1> <4, 3, 2, 1> 

इस समकक्ष वर्ग के सभी प्रतिनिधिों के प्रक्षेपण को पहले दो आयामों में पैदा होता है।

<1, 2> <1, 3> <1, 4> 
<2, 1> <2, 3> <2, 4> 
<3, 1> <3, 2> <3, 4> 
<4, 1> <4, 2> <4, 3> 

बी 720 तत्वों के साथ समकक्ष वर्ग का प्रतिनिधित्व करता है। पहले दो आयामों के प्रक्षेपण से 30 तत्व उत्पन्न होते हैं।

< 5, 6> < 5, 7> < 5, 8> < 5, 9> < 5, 10> 
< 6, 5> < 6, 7> < 6, 8> < 6, 9> < 6, 10> 
< 7, 5> < 7, 6> < 7, 8> < 7, 9> < 7, 10> 
< 8, 5> < 8, 6> < 8, 7> < 8, 9> < 8, 10> 
< 9, 5> < 9, 6> < 9, 7> < 9, 8> < 9, 10> 
<10, 5> <10, 6> <10, 7> <10, 8> <10, 9> 

तो ए और बी की दूरी, क्योंकि इस अनुमानों से दो वैक्टर की न्यूनतम दूरी है 8 का वर्गमूल है। उदाहरण के लिए < 3, 4> और < 5, 6> इस दूरी को उत्पन्न करें।

तो, क्या मैं समस्या की मेरी समझ के साथ सही हूं?

एम घटकों के साथ एन वैक्टरों के लिए वास्तव में बेवकूफ एल्गोरिदम प्रत्येक को गणना (एन -1) दूरी की गणना करनी होगी।प्रत्येक दूरी के लिए एल्गोरिदम एम की दूरी की गणना करेगा!/(एम - 30)! प्रत्येक वेक्टर के लिए प्रक्षेपण। इसलिए 100 आयामों (आपकी निचली बाउंड) के लिए वेक्टर के लिए 2.65 * 10^32 संभावित प्रोजेक्शन हैं। इसके लिए अनुमानों के बीच लगभग 7 * 10^64 दूरी की गणना करना और दो वैक्टरों की दूरी को खोजने के लिए न्यूनतम खोजना आवश्यक है। और फिर इस बार दोहराएं।

मुझे उम्मीद है कि मैंने आपको गलत समझा है या गलती की है। अन्यथा यह वास्तव में चुनौतीपूर्ण और व्यवहार्य नहीं है के बीच कुछ लगता है।

कुछ ऐसा जो मैंने सोचा था वेक्टर घटकों को ऑर्डर करने और उनसे मिलान करने का प्रयास कर रहा है। मैनहट्टन दूरी का उपयोग करना - यदि संभव हो - समाधान को सरल बनाने में मदद कर सकता है।

आप प्रत्येक समूह के द्रव्यमान का केंद्र गणना कर सकते हैं और फिर बड़े पैमाने पर से प्रत्येक समूह केन्द्र की दूरी के आधार पर की तुलना करें:

Answer 2

यहाँ कुछ अच्छा अनुमान आधारित हैं।

एक और तरीका यह है कि आप इसे कर सकते हैं हैश द्वारा प्रत्येक पंक्ति और पंक्तियों के निर्देशांक हैं जो उसी स्थान पर हैश समान मानते हैं और इस प्रकार दो समूह समानता अपडेट की जाती है।

जानकारी लगातार अद्यतन किया जा रहा है और क्या अंतराल पर यदि ऐसा है तो:

कुछ अधिक जानकारी जैसे उपयोगी होगा। कितना अद्यतित है और इसे कितना सटीक होना चाहिए?

Answer 3

अनुभवहीन संस्करण कुछ इस तरह होगा: फिर (नहीं क्वेरी विश्लेषक के माध्यम से चलाने)

select groupid, min(distance) as mindist 
from 
    (select other.groupid as groupid, 
      min(abs(other.value - us.value)) as distance 
    from g us 
    join g other on other.groupid != us.groupid 
    where us.groupid = ?) 
order by mindist 
group by groupid 

, indicies का लाभ लेने के:

select groupid, min(abs(value - usvalue)) as mindist 
from 
    (select other.groupid as groupid, 
      max(other.value) as value, 
      us.value as usvalue 
    from g us 
    join g other on other.groupid != us.groupid and other.value <= us.value 
    where us.groupid = ? 

    union 

    select other.groupid as groupid, 
      min(other.value) as value, 
      us.value as usvalue 
    from g us 
    join g other on other.groupid != us.groupid and other.value >= us.value 
    where us.groupid = ?) 
order by mindist 
group by groupid 

यह उम्मीद है कि mysql एक का उपयोग करने के लिए अनुमति चाहिए इंडेक्स को शामिल होने पर निकटतम पड़ोसियों को तुरंत ढूंढने के लिए।

इसमें त्रुटियां हो सकती हैं, लेकिन उम्मीद है कि विचार की इस पंक्ति में मदद मिलेगी।