लगातार सबस्ट्रक्चर्स की खोज में आमतौर पर दो चरण होते हैं। पहले चरण में, यह लगातार सबस्ट्रक्चर उम्मीदवार बना सकता है। हर उम्मीदवार की आवृत्ति का परीक्षण दूसरे चरण में किया जाता है। लगातार सबस्ट्रक्चर खोज पर अधिकांश अध्ययन पहले चरण के अनुकूलन पर ध्यान केंद्रित करते हैं क्योंकि दूसरे चरण में एक सबग्राफ आइसोमॉर्फिज्म परीक्षण शामिल होता है जिसकी कम्प्यूटेशनल जटिलता अत्यधिक उच्च होती है (यानी, NP-complete)।
लगातार सबस्ट्रक्चर माइनिंग के विभिन्न तरीके
एप्रोरी-आधारित दृष्टिकोण
एप्रोरी-आधारित लगातार सबस्ट्रक्चर माइनिंग एल्गोरिदम एप्रोरी-आधारित लगातार आइटमसेट माइनिंग एल्गोरिदम के समान सुविधाएँ भेजते हैं। छोटे "आकार" के ग्राफ़ के साथ लगातार ग्राफ़ की खोज शुरू होती है, और एक अतिरिक्त वर्टेक्स, एज, या पथ वाले उम्मीदवार बनाकर बॉटम-अप तरीके से आगे बढ़ती है। ग्राफ़ आकार का प्रतिनिधित्व उपयोग किए गए एल्गोरिदम पर आधारित होता है।
एप्रोरी-आधारित सबस्ट्रक्चर माइनिंग एल्गोरिदम की मुख्य डिज़ाइन जटिलता उम्मीदवार उत्पादन चरण है। लगातार आइटमसेट माइनिंग में उम्मीदवार उत्पादन सीधा है। उदाहरण के लिए, मान लें कि हमारे पास आकार-3 के दो लगातार आइटमसेट हैं: (abc) और (bcd)। उनसे उत्पन्न आकार-4 का लगातार आइटमसेट उम्मीदवार आसानी से (abcd) है, जो एक जॉइन से बदला गया है। हालांकि, लगातार सबस्ट्रक्चर माइनिंग में उम्मीदवार उत्पादन समस्या लगातार आइटमसेट माइनिंग की तुलना में कठिन है, क्योंकि दो सबस्ट्रक्चर्स को जोड़ने के कई तरीके हैं।
पैटर्न-ग्रोथ दृष्टिकोण
एप्रोरी-आधारित दृष्टिकोण को अपने लेवल-वाइज़ उम्मीदवार उत्पादन के कारण ब्रेडथ-फर्स्ट सर्च (BFS) रणनीति का उपयोग करना पड़ता है। यह निर्धारित करने के लिए कि क्या आकार-(k+1) ग्राफ़ लगातार है, इसे इसकी सभी संबंधित आकार-k सबग्राफ़ की जांच करनी होगी ताकि इसकी आवृत्ति की ऊपरी सीमा प्राप्त हो सके। इस प्रकार, किसी भी आकार-(k+1) सबग्राफ़ की माइनिंग से पहले, एप्रोरी-जैसा दृष्टिकोण आमतौर पर आकार-k सबग्राफ़ की माइनिंग पूरी करनी होती है।
इसके विपरीत, पैटर्न-ग्रोथ विधि अपनी खोज विधि के संबंध में अधिक गतिशील है। यह ब्रेडथ-फर्स्ट सर्च के साथ-साथ डेप्थ-फर्स्ट सर्च (DFS) का उपयोग कर सकती है, जिसमें कम मेमोरी खपत होती है।
पैटर्न ग्रोथ ग्राफ़ सरल है, लेकिन कुशल नहीं है। बॉटलनेक ग्राफ़ को विस्तारित करने की अक्षमता पर है। वही ग्राफ़ कई बार पाया जा सकता है। उदाहरण के लिए, n अलग-अलग (n-1)-एज ग्राफ़ हो सकते हैं जिन्हें उसी n-एज ग्राफ़ तक विस्तारित किया जा सकता है। उसी ग्राफ़ की बार-बार खोज कम्प्यूटेशनली अक्षम है। हम एक ग्राफ़ जिसे दूसरी बार खोजा जाता है, डुप्लिकेट ग्राफ़ कहते हैं।
डुप्लिकेट ग्राफ़ की पीढ़ी को कम करने के लिए, प्रत्येक लगातार ग्राफ़ को यथासंभव रूढ़िवादी रूप से विस्तारित किया जाना चाहिए। यह सिद्धांत कई नए एल्गोरिदम के डिज़ाइन की ओर ले जाता है। स्पैनिंग एल्गोरिदम को डुप्लिकेट ग्राफ़ की पीढ़ी को कम करने के लिए डिज़ाइन किया गया है। इसे डुप्लिकेट डिटेक्शन के लिए पहले से खोजे गए लगातार ग्राफ़ की खोज करने की आवश्यकता नहीं है। यह किसी भी डुप्लिकेट ग्राफ़ का विस्तार नहीं करता, फिर भी लगातार ग्राफ़ के पूर्ण सेट की खोज की गारंटी देता है।
