ارائه روشی جهت یافتن الگوهای درختی تکراری با استفاده از شاخص معکوس

در سالهای اخیر افزایش سرعت ایجاد پایگاه دادههای درختی موجب شده است که توجه فراوانی به داده کاوی میان درخت ها یا درخت کاوی جلب شود. در میان الگوهای متفاوتی که در پایگاه دادهی درختی وجود دارد، کاوش زیردرخت های تکراری از اهمیت زیادی برخوردار است. زیردرخت های تکراری نه تنها به خودی خود ارزشمند میباشند، بلکه در سایر زمینه داده کاوی نیز قابل استفاده هستند. از جمله ی این زمینه ها میتوان خوشه بندی، دسته بندی و داده شناسی زیستی را نام برد. در این مقاله، روشی جدید مبتنی بر شاخص معکوس جهت کاوش الگوهای درختی تکراری پیشنهاد شده است. این روش در دو فاز غیرفعال و فعال انجام میشود. در فاز غیرفعال ابتدا زیردرختهای موجود در مجموعه درختان را یافته، سپس آنها را به رشته تبدیل کرده و در شاخص معکوس ذخیره مینماییم. در فاز فعال به راحتی از شاخص معکوس زیردرخت های تکراری موردنظر را در سریعترین زمان ممکن استخراج میکنیم. در روش پیشنهادی از زمان هایی که سیستم بیکار است حداکثر استفاده را مینماییم به طوری که در ارزیابی ها، بهره وری CPU در بالاترین حد می باشد. یکی دیگر از قابلیت های روش پیشنهادی این است که برخلاف روش های قبلی با افزودن یک درخت به مجموعه درختان،لازم نیست مراحل قبلی مجدداً تکرار شود.

کلیدواژه ها:

الگوهای درختی تکراری ، جستجوی زیردرختهای تکراری ، شاخص معکوس ، Inverted Index ، Tree Mining