ফ্রিকোয়েন্ট সাবস্ট্রাকচার আবিষ্কার সাধারণত দুটি ধাপে সম্পন্ন হয়। প্রথম ধাপে, ফ্রিকোয়েন্ট সাবস্ট্রাকচার ক্যান্ডিডেট তৈরি করা হয়। দ্বিতীয় ধাপে, প্রতিটি ক্যান্ডিডেটের ফ্রিকোয়েন্সি পরীক্ষা করা হয়। ফ্রিকোয়েন্ট সাবস্ট্রাকচার আবিষ্কারের অধিকাংশ গবেষণা প্রথম ধাপের অপ্টিমাইজেশনের ওপর ফোকাস করে কারণ দ্বিতীয় ধাপে সাবগ্রাফ আইসোমরফিজম টেস্ট জড়িত যার কম্পিউটেশনাল কমপ্লেক্সিটি অত্যধিক বেশি (NP-complete)।
ফ্রিকোয়েন্ট সাবস্ট্রাকচার মাইনিংয়ের পদ্ধতিগুলো
এপ্রিয়োরি-ভিত্তিক পদ্ধতি (Apriori-based Approach)
এপ্রিয়োরি-ভিত্তিক ফ্রিকোয়েন্ট সাবস্ট্রাকচার মাইনিং অ্যালগরিদমগুলো এপ্রিয়োরি-ভিত্তিক ফ্রিকোয়েন্ট আইটেমসেট মাইনিং অ্যালগরिदমের মতো বৈশিষ্ট্য ধারণ করে। ছোট "সাইজ"ের গ্রাফ থেকে সার্চ শুরু করে এবং বটম-আপ পদ্ধতিতে ক্যান্ডিডেট তৈরি করে যেগুলো একটি অতিরিক্ত ভার্টেক্স, এজ, বা পাথ ধারণ করে। গ্রাফ সাইজের রিপ্রেজেন্টেশন অ্যালগরিদমের ওপর নির্ভর করে।
এপ্রিয়োরি-ভিত্তিক সাবস্ট্রাকচার মাইনিং অ্যালগরিদমের মূল ডিজাইন কমপ্লেক্সিটি হলো ক্যান্ডিডেট জেনারেশন ধাপ। ফ্রিকোয়েন্ট আইটেমসেট মাইনিং-এ ক্যান্ডিডেট প্রোডাকশন সোজা। উদাহরণস্বরূপ, যদি আমাদের দুটি সাইজ-৩ ফ্রিকোয়েন্ট আইটেমসেট থাকে: (abc) এবং (bcd)। তাহলে সেগুলো থেকে জেনারেট হওয়া সাইজ-৪ ফ্রিকোয়েন্ট আইটেমসেট ক্যান্ডিডেট সহজেই (abcd), একটি জয়েন থেকে রূপান্তরিত। কিন্তু ফ্রিকোয়েন্ট সাবস্ট্রাকচার মাইনিং-এ ক্যান্ডিডেট জেনারেশন সমস্যা ফ্রিকোয়েন্ট আইটেমসেট মাইনিং-এর চেয়ে কঠিন, কারণ দুটি সাবস্ট্রাকচার জয়েন করার অনেক উপায় থাকে।
প্যাটার্ন-গ্রোথ পদ্ধতি (Pattern-Growth Approach)
এপ্রিয়োরি-ভিত্তিক পদ্ধতিতে লেভেল-ওয়াইজ ক্যান্ডিডেট জেনারেশনের কারণে ব্রেডথ-ফার্স্ট সার্চ (BFS) কৌশল ব্যবহার করতে হয়। একটি সাইজ-(k+1) গ্রাফ ফ্রিকোয়েন্ট কিনা নির্ধারণ করতে, এর সকল সংশ্লিষ্ট সাইজ-k সাবগ্রাফ চেক করতে হয় এর ফ্রিকোয়েন্সির একটি আপার বাউন্ড পেতে। তাই যেকোনো সাইজ-(k+1) সাবগ্রাফ মাইন করার আগে, এপ্রিয়োরি-সদৃশ পদ্ধতিতে সাধারণত সাইজ-k সাবগ্রাফ মাইনিং সম্পূর্ণ করতে হয়।
অতএব, এপ্রিয়োরি-সদৃশ পদ্ধতিতে BFS আবশ্যক। বিপরীতে, প্যাটার্ন-গ্রোথ মেথড তার সার্চ কৌশলে আরও ডাইনামিক। এটি ব্রেডথ-ফার্স্ট সার্চ এবং ডেপথ-ফার্স্ট সার্চ (DFS) দুটোই ব্যবহার করতে পারে, যেটি কম মেমরি খরচ করে।
প্যাটার্ন গ্রোথ গ্রাফ সহজ, কিন্তু দক্ষ নন। বটলनेक হলো গ্রাফ এক্সটেন্ড করার অদক্ষতা। একই গ্রাফ একাধিক বার পাওয়া যেতে পারে। উদাহরণস্বরূপ, nটি ভিন্ন (n-1)-এজ গ্রাফ থাকতে পারে যেগুলো একই n-এজ গ্রাফে এক্সটেন্ড করা যায়। একই গ্রাফ বারবার আবিষ্কার হওয়া কম্পিউটেশনালি অদক্ষ। আমরা এক גרাফ যেটি দ্বিতীয়বার আবিষ্কার হয় তাকে ডুপ্লিকেট গ্রাফ বলে।
ডুপ্লিকেট গ্রাফ জেনারেশন কমানোর জন্য, প্রতিটি ফ্রিকোয়েন্ট গ্রাফ যতটা সম্ভব সংরক্ষণশীলভাবে এক্সটেন্ড করা উচিত। এই নীতিটি বেশ কিছু নতুন অ্যালগরিদমের ডিজাইনে নিয়ে এসেছে। স্প্যানিং অ্যালগরिदম ডুপ্লিকেট গ্রাফ জেনারেশন কমানোর জন্য ডিজাইন করা হয়েছে। এটি পূর্বে আবিষ্কৃত ফ্রিকোয়েন্ট গ্রাফ সার্চ করতে হয় না ডুপ্লিকেট ডিটেকশনের জন্য। এটি কোনো ডুপ্লিকেট গ্রাফ এক্সটেন্ড করে না, তবুও সম্পূর্ণ ফ্রিকোয়েন্ট গ্রাফ সেট আবিষ্কার করার গ্যারান্টি দেয়।
