ঘন ঘন সাবস্ট্রাকচারের আবিষ্কার সাধারণত দুটি ধাপ নিয়ে গঠিত। প্রথম ধাপে, এটি ঘন ঘন সাবস্ট্রাকচার প্রার্থী তৈরি করতে পারে। দ্বিতীয় ধাপে প্রত্যেক প্রার্থীর ফ্রিকোয়েন্সি পরীক্ষা করা হয়। ঘন ঘন সাবস্ট্রাকচার আবিষ্কারের বেশিরভাগ গবেষণা প্রথম ধাপের অপ্টিমাইজেশানের উপর ফোকাস করে কারণ দ্বিতীয় ধাপে একটি সাবগ্রাফ আইসোমরফিজম পরীক্ষা জড়িত যার কম্পিউটেশনাল জটিলতা অত্যধিক বেশি (যেমন, এনপি-সম্পূর্ণ)।
ঘন ঘন সাবস্ট্রাকচার মাইনিংয়ের জন্য বিভিন্ন পদ্ধতি রয়েছে যা নিম্নরূপ -
Apriori-ভিত্তিক পদ্ধতি - Apriori-ভিত্তিক ঘন ঘন সাবস্ট্রাকচার মাইনিং অ্যালগরিদমগুলি Apriori-ভিত্তিক ঘন ঘন আইটেমসেট মাইনিং অ্যালগরিদমগুলির সাথে একই বৈশিষ্ট্যগুলি পাঠায়। ঘন ঘন গ্রাফের জন্য অনুসন্ধান ছোট "আকার" এর গ্রাফ দিয়ে শুরু হয় এবং প্রার্থীদের একটি অতিরিক্ত শীর্ষ, প্রান্ত বা পথ তৈরি করে নীচের দিকে এগিয়ে যায়। গ্রাফ আকারের উপস্থাপনা ব্যবহৃত অ্যালগরিদমের উপর ভিত্তি করে।
Apriori-ভিত্তিক সাবস্ট্রাকচার মাইনিং অ্যালগরিদমের প্রধান নকশা জটিলতা হল প্রার্থী তৈরির ধাপ। ঘন ঘন আইটেমসেট খনির প্রার্থী উত্পাদন সত্যবাদী. উদাহরণস্বরূপ, ধরুন আমাদের দুটি ঘন ঘন আইটেমসেট আছে সাইজ-3:(abc) এবং (bcd)।
তাদের থেকে তৈরি করা সাইজ-4-এর ঘন ঘন আইটেমসেট প্রার্থী সহজেই (abcd), যোগদান থেকে পরিবর্তিত হয়। যাইহোক, ঘন ঘন সাবস্ট্রাকচার মাইনিংয়ে প্রার্থী জেনারেশন সমস্যা ঘন ঘন আইটেমসেট মাইনিংয়ের চেয়ে কঠিন, কারণ দুটি সাবস্ট্রাকচারে যোগ দেওয়ার অনেক উপায় রয়েছে।
প্যাটার্ন-গ্রোথ অ্যাপ্রোচ - Apriori-ভিত্তিক পন্থাকে ব্রেডথ-ফার্স্ট সার্চ (BFS) কৌশলটি ব্যবহার করতে হবে কারণ এর স্তর-ভিত্তিক প্রার্থী প্রজন্ম। একটি আকার-(k + 1) গ্রাফ ঘন ঘন হয় কিনা তা নির্ধারণ করতে, এটির ফ্রিকোয়েন্সির একটি উপরের সীমা পেতে এটির সমস্ত সংশ্লিষ্ট আকার-কে সাবগ্রাফগুলি পরীক্ষা করতে হবে। এইভাবে, যেকোন সাইজ-(k +1) সাবগ্রাফ খনির আগে, Apriori-এর মত পদ্ধতিতে সাধারণত সাইজ-k সাবগ্রাফের মাইনিং সম্পূর্ণ করতে হয়।
অতএব, Apriori-এর মত পদ্ধতির জন্য BFS প্রয়োজনীয়। বিপরীতে, প্যাটার্ন-বৃদ্ধি পদ্ধতিটি তার অনুসন্ধান পদ্ধতি সম্পর্কিত আরও গতিশীল। এটি প্রস্থ-প্রথম অনুসন্ধানের পাশাপাশি গভীরতা-প্রথম অনুসন্ধান (DFS) ব্যবহার করতে পারে, যার পরবর্তীটি কম মেমরি ব্যবহার করে।
প্যাটার্ন গ্রোথ গ্রাফ সহজ, কিন্তু দক্ষ নয়। বাধা একটি গ্রাফ প্রসারিত অদক্ষতা হয়. একই গ্রাফ বেশ কয়েকবার পাওয়া যাবে। উদাহরণস্বরূপ, n ভিন্ন (n − 1)-এজ গ্রাফ থাকতে পারে যেগুলি একই n-এজ গ্রাফে বাড়ানো যেতে পারে। একই গ্রাফের বারবার আবিষ্কার গণনাগতভাবে অদক্ষ। দ্বিতীয়বার আবিষ্কৃত গ্রাফকে আমরা ডুপ্লিকেট গ্রাফ বলি।
এটি ডুপ্লিকেট গ্রাফের প্রজন্মকে কমাতে পারে, প্রতিটি ঘন ঘন গ্রাফ যতটা সম্ভব রক্ষণশীলভাবে প্রসারিত করা উচিত। এই নীতিটি বেশ কয়েকটি নতুন অ্যালগরিদমের নকশার দিকে নিয়ে যায়। স্প্যানিং অ্যালগরিদমটি ডুপ্লিকেট গ্রাফের প্রজন্ম কমাতে ডিজাইন করা হয়েছে। ডুপ্লিকেট সনাক্তকরণের জন্য পূর্বে আবিষ্কৃত ঘন ঘন গ্রাফ অনুসন্ধানের প্রয়োজন নেই। এটি কোনো ডুপ্লিকেট গ্রাফ প্রসারিত করে না, তবুও ঘন ঘন গ্রাফের সম্পূর্ণ সেট আবিষ্কারের নিশ্চয়তা দেয়।
