डिस्कवर में समय-समय पर पैटर्न के एक बड़े डेटा-सेट

Question

मैं रूप में डिस्क पर tuples की एक बड़ी अनुक्रम (t1, k1) (टी 2, k2) ... (तमिलनाडु, केएन)

टीआई एक monotonically बढ़ती टाइमस्टैम्प है और की एक कुंजी है (यदि आवश्यक हो तो एक निश्चित लंबाई स्ट्रिंग मान लें)। न तो टीआई और न ही अद्वितीय होने की गारंटी है। हालांकि, अद्वितीय टीआईएस और किस की संख्या बहुत बड़ी है (लाखों)। n स्वयं बहुत बड़ा है (100 मिलियन +) और के आकार (लगभग 500 बाइट्स) स्मृति में सब कुछ स्टोर करना असंभव बनाता है।

मैं इस अनुक्रम में कुंजी की आवधिक घटनाओं को जानना चाहता हूं।

उदाहरण के लिए

, अगर मैं अनुक्रम (1, क) (2, ख) (3, ग) (4, ख) (5, क) (6, ख) है (7, घ) (8, ख) (9, क) (10, ख)

एल्गोरिथ्म फेंकना चाहिए (क, 4) और (ख, 2)। यह 4 और बी की अवधि के साथ होता है 2.

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

Answer 1

यह Fourier transforms (Fast Fourier Transforms इत्यादि) का आविष्कार किया गया था।

आप अनिवार्य रूप से समय (या कुछ समान आयाम) डोमेन से frequency domain पर अनुक्रम को बदल रहे हैं। यह कंप्यूटर की अनुप्रयोग की भविष्यवाणी करने वाली एक बहुत पुरानी समस्या है, और विषय पर सिद्धांत का एक विशाल शरीर है। discrete fourier transform भी देखें।

संपादित करें: आपको अपने मूल्य k1, k2, ... को किसी भी तरह बदलना होगा, लेकिन यह मानना ​​है कि यह संभव है, यह दृष्टिकोण भी होना चाहिए।

Answer 2

आप अवधि खोजने के लिए अलग autocorrelation का उपयोग कर सकते हैं, फिर कुंजी के लिए खोजें। ऑटोकॉर्पोरेशन के फायदे यह हैं कि यह समझना थोड़ा आसान है कि अलग डोमेन में क्या हो रहा है, और आपको — पर चाबियों को मैप करने के बारे में चिंता करने की ज़रूरत नहीं है, केवल दो चाबियों के एक विशेष कार्य का उपयोग करें जो 1 के बराबर हैं और 0 जब वे असमान हैं।

Answer 3

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

व्यक्तिगत रूप से, मुझे लगता है कि यह शायद सबसे अच्छा है जब तक कि आप समस्या के लिए अधिक संरचना की पहचान नहीं कर लेते।

Answer 4

आइए लेबल एक (टाइमस्टैम्प, स्ट्रिंग) के रूप में टपल ( कुंजी, मूल्य)। कुछ बाधाएं: 1. मान का एक अलग सेट है, यानी इन मानों की आवधिक उपस्थिति के बीच का मिलान सटीक है: aaabb ... aaabb, aaab ... aaabc। 2. किसी मान के सभी उदाहरणों का सेट स्मृति में लगाया जा सकता है।

एल्गोरिदम: 1. सभी अद्वितीय मूल्यों की एक पूरी सूची प्राप्त करें 2. प्रत्येक अद्वितीय मूल्य के लिए, सभी टुपल्स प्राप्त करें, टाइमस्टैम्प की ऑर्डर सूची बनाएं। 3. इस डेटा में पैटर्न देखने के लिए एल्गोरिदम लागू करें। आदर्श रूप से एक गैर वर्दी असतत फूरियर परिवर्तन, या autocorrelation।

Answer 5

आप वास्तव में दो अलग-अलग समस्याएं हैं:

1. आप अपने डेटा, m अद्वितीय कुंजी द्वारा परिभाषित में m अलग संकेत है। आपको प्रत्येक सिग्नल को अलग करने की आवश्यकता है और स्टोर अलग से है।

2. इन अद्वितीय संकेतों में से एक को देखते हुए, आपको यह निर्धारित करना होगा कि यह आवधिक है या नहीं, यह स्वत: सहसंबंध या असतत फूरियर ट्रांसफॉर्म का एक आवेदन है, जो भी आप चाहें। उदाहरण के लिए, डीएफटी आपको अपने डेटा के इंटरपोलेशन आवधिक कार्यों के गुणांक देता है। यदि डीएफटी में केवल एक गुणांक शून्य है, तो स्पष्ट अवधि होती है।

आप संकेतों को अलग करने के बिना डेटा को एफ टी या ऑटो सहसंबंध लागू होते हैं आप एक जटिल समस्या है जहाँ आप अगर मिला "समय-समय पर" संकेतों के एक के बाद एक अद्वितीय संकेत या कई से बना है पता नहीं होगा मिल जाएगा ।