Tez No	İndirme	Tez Künye	Durumu
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 Yazar:ERAY ÖZKURAL Danışman: PROF. DR. CEVDET AYKANAT Yer Bilgisi: İhsan Doğramacı Bilkent Üniversitesi / Mühendislik ve Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:	Onaylandı Doktora İngilizce 2013 143 s.
Seçilmiş temel veri madenciligi görevlerini iyileştirmek için bir çok yaklaşım üzerinde yoğunlaştık. Şu andaki tez büyük miktardaki veri için paralel işleme metodlarının iyileştirilmesiyle alakalıdır. Hem seyrek hem yoğun verikümeleri için yeni koşut veri madenciliği algoritmaları geliştirdik, ve bütün-çiftler benzerlik problemi için 1-B ve 2-B koşut algoritmalar önerdik. NoClique ve NoClique2 adında iki yeni koşut veri madenciliği algoritması bitdrill adındaki kendi ardışık dikey sık kalemkümesi madenciliği (SKM) algoritmamızı koşutlaştırmaktadır, ve düğüm ayracı ile çizge bölümleme (DAÇB) kullanan bir metodla kalemleri dağıtmakta ve seçici biçimde yinelemektedir. Metod düğümlerin sık kalemlere ve kenarların iki boyutundaki sık kalem kümelerine karşılık geldiği bir çizge üzerinde çalışmaktadır. Bu çizgenin düğüm ayracının bulunmasının kalem dagıtımı tarafından tespit edilen alt-veritabanlarının bağımsız bi ?çimde işlenmesi için yeterli olduğunu gösterdik. Bu dağıtım uygun ağırlıkların düğümlere verilmesiyle minimize edilen bir veri yinelemesine yol açmaktadır. Veri dağıtımı şeması iki yeni koşut sık kalemkümesi madenciliği algoritmasının tasarımında kullanılmaktadır. Iki algoritma da ayraca karşılık gelen kalemleri yineler. NoClique ayracın sebep olduğu işi yineler ve NoClique2 ayni işi kolektif olarak hesaplar. Hesapsal yük dengeleme ve yinelenen yahut kolektif işin minimizasyonu uygun yük tahminlerinin düğümlere atanmasıyla başarılabilir. Başarım bü ?tün kalemleri yineleyen başka bir koşutlaştırmayla ve ParDCI algoritmasıyla karşılaştırılır. Seçici kalem yinelemeyle kalem dağıtımını kullanan başka bir koşut SKM algoritması tanıtıyoruz. Daha önce önerdiğimiz koşut SKM için DACB modelini, bağımsız madencilik koşulunu gevşetme suretiyle genişletiyoruz. Bağımsız keşfedilen kalem kümeleri bulmak yerine, iletişim miktarını minimize edebiliriz ve adayları ince-gözenekli biçimde bölümleyebiliriz. Koşut hesaplamanın düğümlerin adaylara ve hiperkenarların kalemlere karşılık geldiği bir hiperçizge bölümleme modelini öneriyoruz. Her adaya düğüm ağırlıklarıyla bir yük tahmini atanır, ve kalem sıklıkları hiperkenar ağırlıkları olarak atanır. Modelin veri yinelemesini minimize ettiği ve yükleri yüksek kesinlikle dengelediği gösterilir. Aynı zamanda sadece belli bir sayıda seviyenin adaylarını u ?retebileceğimiz için, önceki kalem dağıtımını temsil eden sabit düğümlerin olduğu bir yeniden bölümleme modeli de tanıtıyoruz. Deneyler NoClique2?nin daha yüksek yük dengesizliğine göre aynı problem örnekleri için, ek koşut fazla hesaplama bedeliyle, hatırı sayılır iyileştirme elde ettiğimizi göstermektedir. Bütün-çiftler benzerlik problemi için, yakın zamandaki etkin ardışık algoritmaları koşut çerçeveye genişletiyoruz, ve hızlı bir ardışık algoritmanın vektör-başı ve boyut-başı koşutlaştırılmalarını, ve aynı zamanda iki algoritmanın 2-B bir algoritma üreten zarif bir birleşimini elde ediyoruz. Boyut-başı durumu için iki etkin algoritmik optimizasyonun boyut-başı koşutlaştırmayı yeterince etkin hale getirdiği gösterilmektedir. Bu optimizasyonlar iletişim bedellerini, aday sayısını ve hesaplama/iletişim dengesizliğini azaltmak için yerel budama ve belli bir sayıdaki vektörun blok işlemesini hedeflemektedir. Yerel budamanın doğruluğu ispatlanır. Ayrıca, özyinelemeli boyut-başı koşutlaştırma sunulur. Geniş deneylerde, algoritmaların başarımının olumlu çıktıgı, ve iki önemli optimizasyonun faydası gösterilmiştir. s¨ozc¨ukler: ko¸sut veri madencili?gi, d¨u?g¨um ayracı ile ¸cizge b¨ol¨umleme, hiper¸cizge b¨ol¨umleme, b¨ut¨un-¸ciftler benzerlik, veri da?gıtımı, veri yineleme.
We have embarked upon a multitude of approaches to improve the efficiency of selected fundamental tasks in data mining. The present thesis is concerned with improving the efficiency of parallel processing methods for large amounts of data. We have devised new parallel frequent itemset mining algorithms that work on both sparse and dense datasets, and 1-D and 2-D parallel algorithms for the all-pairs similarity problem. Two new parallel frequent itemset mining (FIM) algorithms named NoClique and NoClique2 parallelize our sequential vertical frequent itemset mining algorithm named bitdrill, and uses a method based on graph partitioning by vertex separator (GPVS) to distribute and selectively replicate items. The method operates on a graph where vertices correspond to frequent items and edges correspond to frequent itemsets of size two. We show that partitioning this graph by a vertex separator is sufficient to decide a distribution of the items such that the sub-databases determined by the item distribution can be mined independently. This distribution entails an amount of data replication, which may be reduced by setting appropriate weights to vertices. The data distribution scheme is used in the design of two new parallel frequent itemset mining algorithms. Both algorithms replicate the items that correspond to the separator. NoClique replicates the work induced by the separator and NoClique2 computes the same work collectively. Computational load balancing and minimization of redundant or collective work may be achieved by assigning appropriate load estimates to vertices. The performance is compared to another parallelization that replicates all items, and ParDCI algorithm. We introduce another parallel FIM method using a variation of item distribution with selective item replication. We extend the GPVS model for parallel FIM we have proposed earlier, by relaxing the condition of independent mining. Instead of finding independently mined item sets, we may minimize the amount of communication and partition the candidates in a fine-grained manner. We introduce a hypergraph partitioning model of the parallel computation where vertices correspond to candidates and hyperedges correspond to items. A load estimate is assigned to each candidate with vertex weights, and item frequencies are given as hyperedge weights. The model is shown to minimize data replication and balance load accurately. We also introduce a re-partitioning model since we can generate only so many levels of candidates at once, using fixed vertices to model previous item distribution/replication. Experiments show that we improve over the higher load imbalance of NoClique2 algorithm for the same problem instances at the cost of additional parallel overhead. For the all-pairs similarity problem, we extend recent efficient sequential algorithms to a parallel setting, and obtain document-wise and term-wise parallelizations of a fast sequential algorithm, as well as an elegant combination of two algorithms that yield a 2-D distribution of the data. Two effective algorithmic optimizations for the term-wise case are reported that make the term-wise parallelization feasible. These optimizations exploit local pruning and block processing of a number of vectors, in order to decrease communication costs, the number of candidates, and communication/computation imbalance. The correctness of local pruning is proven. Also, a recursive term-wise parallelization is introduced. The performance of the algorithms are shown to be favorable in extensive experiments, as well as the utility of two major optimizations. Key Words: parallel data mining, graph partitioning by vertex separator, hypergraph partitioning, all pairs similarity, data distribution, data replication.