Geri Dön

Efficient parallel frequency mining based on a novel top-down partitioning scheme for transactional data

Yeni bir işlem verisi parçalama şeması tabanlı etkin paralel frekans tarama

  1. Tez No: 129214
  2. Yazar: ERAY ÖZKURAL
  3. Danışmanlar: PROF. DR. CEVDET AYKANAT
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Paralel Veri Tarama, Frekans Tarama, Parallel Data Mining, Frequency Mining
  7. Yıl: 2002
  8. Dil: İngilizce
  9. Üniversite: İhsan Doğramacı Bilkent Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 123

Özet

ÖZET YENİ BİR İŞLEM VERİSİ PARÇALAMA ŞEMASI TABANLI ETKİN PARALEL FREKANS TARAMA Eray Özkural Bilgisayar Mühendisliği, Yüksek Lisans Tez Yöneticisi: Prof. Cevdet Ay kanat Ocak, 2002 Son yıllarda, gelişen veri toplama yetenekleriyle birlikte büyük miktarlarda veri toplanmıştır. Bilimsel ve iş alanlarından elde edilen çok geniş veriler için yararlı bilgilerin otomatik olarak bulunmasi gerekmektedir. Veri tarama bu tarz bilgi keşfi için etkin algoritmik çözümlerin değişik büyük veriler üzerinde uygu lanmasıdır. Frekans tarama bir işlem ya da ilişkisel veri tabanındaki bütün sık desenleri keşfeder ve ilişki kuralı tarama ve dizi kurali tarama gibi bir çok veri tarama algoritmalarının özünü oluşturur. Sık desen keşfi paralel programlama için dev veriler üzerinde karmaşık bir işlem olması itibariyle önemli bir problem haline gelmiştir. Bu tezde, yeni bir sınıf paralel frekans tarama algoritması öneriyoruz. Frekans tarama işini tepeden aşağı bölmek için kullanılabilecek bir işlem verisi parçalama şeması takdim ediyoruz. Yöntemimiz iki uzunluğundaki sık desenlerin çizgesi [Gp2) üzerinde çalışmakta olup, bu çizgenin köşe ayracıyla parçalanması (GPVS) işlem kümesi üzerinde iki-yollu bir parçalamaya eşlenmektedir. Elde edilen iki parça bağımsız olarak taranabilir ve bu sayede eş zamanlılık için kullanilabilir. Bu özelliğin tutması için Gf2 'deki ayraç tarafından belirlenen ve GPVS tarafından minimize edilen bir yineleme bulunmaktadır. Genel bir paralel frekans taramasi algoritmasında kullanılan bir k-yollu parçalama iki-yollu parçalama şemasından türetilmektedir. İlk olarak Gf2'yi paralel olarak hesaplarız ve ertesinde veri tabanının k-yollu bir parçalaması k işlemci için paralel kendini çağıran bir yöntemle belirlenir. Veri tabanı her işlemciye bir parça düşecek şekilde yeniden dağıtılır, izleyen tarama her işlemcide verilen seri bir tarama algoritmasıyla eş vıvıı zamanlı biçimde devam eder. FP~Growth'u seri algoritma olarak kullandiğımız tam bir program gerçekleştirilmiştir. Bir Beowulf sistemi üzerinde yapılan per formans çalışması sentetik veritabanları için iyi hızlanma kaydettiğimizi göster mektedir. Problemin zor örneklerinde gelişmiş bir algoritmanın yaklaşık iki katı hızlanma kazanmış bulunmaktayız. Ayrıca FP-Growth için bir düzeltme ve hızlandırma sunuyoruz.

Özet (Çeviri)

ABSTRACT EFFICIENT PARALLEL FREQUENCY MINING BASED ON A NOVEL TOP-DOWN PARTITIONING SCHEME FOR TRANSACTIONAL DATA Eray Ozkural M.S. in Computer Engineering Supervisor: Prof. Cevdet Aykanat January, 2002 In recent years, large quantities of data have been amassed with advances in data acquisition capabilities. Automated detection of useful information is required for vast data obtained from scientific and business domains. Data Mining is the application of efficient algorithmic solutions on a variety of immense data for such knowledge discovery. Frequency mining discovers all frequent patterns in a transaction or relational database and it comprises the core of several data mining algorithms such as association rule mining and sequence mining. Frequent pattern discovery has become a challenge for parallel programming since it is a highly complex operation on huge datasets demanding efficient and scalable algorithms. In this thesis, we propose a new family of parallel frequency mining algo rithms. We introduce a novel transaction set partitioning scheme that can be used to divide the frequency mining task in a top-down fashion. The method op erates on the graph of frequent patterns with length two (Gp2) from which a graph partitioning by vertex separator (GPVS) is mapped to a two-way partitioning on the transaction set. The two parts obtained can be mined independently and therefore can be utilized for concurrency. In order for this property to hold, there is an amount of replication dictated by the separator in Gp2 which is minimized by the GPVS algorithm. A k-way partitioning is derived from recursive applica tion of 2- way partitioning scheme which is used in the design of a generic parallel frequency mining algorithm. First we compute Gp2 in parallel, succeeding that we designate a k-way partitioning of the database for k processors with a parallel IVrecursive procedure. The database is redistributed such, that each processor is as signed one part. Subsequent mining proceeds simultaneously and independently at each processor with a given serial mining algorithm. A complete implemen tation in which we employ FP- Growth as the sequential algorithm has been achieved. The performance study of the algorithm on a Beowulf system demon strates favorable performance for synthetic databases. For hard instances of the problem, we have gained approximately twice the speedup of a state-of-the-art algorithm. We also present a correction and optimization to FP- Growth algorithm.

Benzer Tezler

  1. Tez No

    350528

    Bor ve mineral katkılı selülozik yalıtım malzemesi üretimi ve karakterizasyonu

    Production of boron and mineral reinforced cellulosic insulation material and its characterization

    İBRAHİM ETHEM KARAAĞAÇLIOĞLU

    Doktora

    Türkçe

    Türkçe

    2012

    Maden Mühendisliği ve Madencilikİstanbul Teknik Üniversitesi

    Maden Mühendisliği Ana Bilim Dalı

    PROF. DR. MEHMET SABRİ ÇELİK

  2. Tez No

    66390

    Bir benzinli motorun türbülanslı akış alanlarının incelenmesi

    The Investigation of the turblent flow fields in the motored S.1. engine

    AHMET ERDİL

    Doktora

    Türkçe

    Türkçe

    1997

    Uçak Mühendisliğiİstanbul Teknik Üniversitesi

    Uçak Mühendisliği Ana Bilim Dalı

    PROF. DR. OĞUZ BORAT

  3. Tez No

    856752

    Computational analyses of die-embedded microchannels for high electron mobility transistors considering thermal, hydrodynamic and structural behavior

    Yüksek elektron mobiliteli transistorlara uygulanmış gömülü mikrokanal yapılarının ısıl, hidrodinamik ve yapısal davranışlarının hesaplamalı analizleri

    ORÇUN YILDIZ

    Yüksek Lisans

    İngilizce

    İngilizce

    2023

    Makine Mühendisliğiİstanbul Teknik Üniversitesi

    Makine Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ ALAEDDİN BURAK İREZ

    PROF. DR. LÜTFULLAH KUDDUSİ

  4. Tez No

    336855

    Data distribution and performance optimization models for parallel data mining

    Koşut veri madenciliği için veri dağıtımı ve başarım optimizasyon modelleri

    ERAY ÖZKURAL

    Doktora

    İngilizce

    İngilizce

    2013

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. CEVDET AYKANAT

  5. Tez No

    601299

    Garp linyit işletmelerinde kullanılan çekme kepçeli yerkazarların güvenirlik analizleri

    Reliability analysis of dragline systems used in G.L.İ

    CAN DURU

    Yüksek Lisans

    Türkçe

    Türkçe

    2019

    Maden Mühendisliği ve Madencilikİstanbul Teknik Üniversitesi

    Maden Mühendisliği Ana Bilim Dalı

    DOÇ. DR. HAKAN TUNÇDEMİR

Geri Dön