Tez No İndirme Tez Künye Durumu
268842
A distributed graph mining framework based on mapreduce / Eşle/indirge yöntemi üzerine kurulu dağıtık bir ağ madenciliği gerçeklemesi
Yazar:SERTAN ALKAN
Danışman: YRD. DOÇ. DR. TOLGA CAN
Yer Bilgisi: Orta Doğu Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Bölümü
Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin:Dağıtık programlama = Distributed programming
Onaylandı
Yüksek Lisans
İngilizce
2010
62 s.
Bir ağ içinde saklı olan ve sık geçen desenler incelenen bu ağ için önemli bilgiler sunar. Bir ağ veritabanındaki sık geçen daha küçük ağları bulmak için varolan teknikler genelde tüm verinin tek bir makina belleğine sığacağını göz önüne alarak tasarlanmışlardır. Her ne kadar belli bir miktara kadar oldukça eniyilenmiş yöntemler olsa da, ölçeklenebilme problemine çözüm geliştirememişlerdir. Bu tez çalışmasında, amacımız verilen bir ağ içinde en az daha önceden belirlenen eşik değerde tekrarlanan küçük ağları bulmaktır. Burda, sık geçen desenleri bulabilmek için, çalıştırılan küme boyutu ile orantılı biçimde ölçeklenebilen dağıtık bir yöntem sunuyoruz. Bu yöntemin merkezinde, dağıtık dosya sistemi üzerine veriyi bölmek için ve hesaplanan desenleri bilgi kaybetmeden birleştirmek için varolan bir ağ parçalama yöntemini kullanır. Sık desenlerin her parçada bulunması bilinen bir başka yöntemi kullanarak yapılır. Bilinen diğer yöntemler sık geçen desenleri bulabildikleri halde, veriyi parçalasalar bile tek bir makinada çalışmak üzere tasarlandıklarından dağıtık yöntemler değillerdir. Üstelik, bu yöntemler hesaplama yoğunluklu olmalarına rağmen hata toleransları yoktur ve hiçbiri dağıtık bir dosya sistemi üzerinde çalışmak üzere tasarlanmamıştır. Sunulan yöntemde ise, Eşle/İndirge yöntemini kullanarak, desenlerin hesaplanması kümedeki her makina üzerine dağıtılmaktadır. Yöntem; önce, ardışık gönderilen ve her seferinde veriyi birbirine en az bağlı olan iki düğüm setine ayıran eşle/indirge işleriyle veriyi böler, bir başka eşle/indirge işiyle her bir parçadaki desenleri hesaplar ve bulunan desenleri birleştirip tüm ağ içindeki desenleri bulabilmek için ardışık eşle/indirge işleri gönderir. Gerçekleme için açık kaynak kodlu bir eşle/indirge ortamı, Hadoop, kullanıldı. Deneylerde, yöntemin büyük ağlara ölçeklenebildiği ve veri miktarı büyüdükçe varolan yöntemlerden daha yüksek başarımla çalıştığı gözlemlendi.
The frequent patterns hidden in a graph can reveal crucial information about the network the graph represents. Existing techniques to mine the frequent subgraphs in a graph database generally rely on the premise that the data can be fit into main memory of the device that the computation takes place. Even though there are some algorithms that are designed using highly optimized methods to some extent, many lack the solution to the problem of scalability. In this thesis work, our aim is to find and enumerate the subgraphs that are at least as frequent as the designated threshold in a given graph. Here, we propose a new distributed algorithm for frequent subgraph mining problem that can scale horizontally as the computing cluster size increases. The method described here, uses a partitioning method and Map/Reduce programming model to distribute the computation of frequent subgraphs. In the core of this algorithm, we make use of an existing graph partitioning method to split the given data in the distributed file system and to merge and join the computed subgraphs without losing information. The frequent subgraph computation in each split is done using another known method which can enumerate the frequent patterns. Although current algorithms can efficiently find frequent patterns, they are not parallel or distributed algorithms in that even when they partition the data, they are designed to work on a single machine. Furthermore, these algorithms are computationally expensive but not fault tolerant and are not designed to work on a distributed file system. Using the Map/Reduce paradigm, we distribute the computation of frequent patterns to every machine in a cluster. Our algorithm, first bi-partitions the data via successive Map/Reduce jobs, then invokes another Map/Reduce job to compute the subgraphs in partitions using CloseGraph, recovers the whole set by invoking a series of Map/Reduce jobs to merge-join the previously found patterns. The implementation uses an open source Map/Reduce environment, Hadoop. In our experiments, our method can scale up to large graphs, as the graph data size gets bigger, this method performs better than the existing algorithms.