संख्या पुनर्प्राप्ति

Question

के लिए स्पेस-कुशल संभाव्य डेटा संरचनाएं मान लें कि हमारे पास एक एल्गोरिदम है जो कुंजी की एक अनुमानित लंबी धारा प्राप्त करता है। इसके बाद यह प्रत्येक कुंजी के लिए 0 और 1 के बीच एक मान उत्पन्न करता है, जैसा कि हम इसे पूर्ववर्ती पुनर्प्राप्ति के लिए संसाधित करते हैं। इनपुट सेट इतना बड़ा है कि हम प्रत्येक कुंजी के लिए एक मान स्टोर नहीं कर सकते हैं। मूल्य उत्पन्न करने वाला नियम कुंजी भर में स्वतंत्र है।

अब, मान लेते हैं कि हम पीछे देखने में त्रुटि बर्दाश्त कर सकते हैं, लेकिन हम अभी भी लिया गया और मूल मूल्यों में अंतर कम करना चाहते हैं (अर्थात asymptotically कई यादृच्छिक retrievals से अधिक)।

उदाहरण के लिए, यदि किसी दिए गए कुंजी के लिए मूल मान 0.008 था, तो 0.06 को पुनर्प्राप्त करना 0.6 पुनर्प्राप्त करने से कहीं बेहतर है।

इस समस्या को हल करने के लिए हम किस डेटा संरचना या एल्गोरिदम का उपयोग कर सकते हैं?

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

मैं आदर्श रूप से ऐसे समाधान की तलाश कर रहा हूं जो पैरामीटर को स्थान और त्रुटि दरों के बीच पैरामीटर कर सकता है।

Answer 1

शायद ब्लूम फ़िल्टर का एक संस्करण Compact Approximator कहा जाता है: एक ब्लूम फ़िल्टर की तरह लेकिन सामान्यीकृत इसलिए प्रविष्टियां जाली से मूल्य हैं। वह जाली यहां केवल 0 और 1 के बीच तैरती है (इसमें जाली होने की तुलना में अधिक संरचना होती है लेकिन यह आवश्यकताओं को पूरा करती है) या फिर आप उन नंबरों को संग्रहित कर रहे हैं।

एक अद्यतन प्रासंगिक प्रविष्टियों को इसके बीच अधिकतम और मूल्य याद रखने के द्वारा प्रतिस्थापित करता है, एक क्वेरी न्यूनतम सभी प्रासंगिक प्रविष्टियों (नीचे उदाहरण) की गणना करती है। परिणाम केवल वास्तविक मूल्य को अधिक महत्व दे सकते हैं। ऑर्डरिंग को उलटकर (न्यूनतम और अधिकतम स्वैपिंग और 0 के बजाय 1 से प्रारंभ करना) आप एक अनुमान लगा सकते हैं, जिसमें अंतराल दिया जा सकता है जिसमें वास्तविक मूल्य होता है।

index1 = hash1(key) 
data[index1] = max(data[index1], value); 
index2 = hash2(key) 
data[index2] = max(data[index2], value); 
... etc 

और overestimation हो रही की तरह दिखता है:

result = 1 
index1 = hash1(key) 
result = min(data[index1], result); 
index2 = hash2(key) 
result = min(data[index2], result); 
... etc