A distributed graph mining framework based on mapreduce
Eşle/indirge yöntemi üzerine kurulu dağıtık bir ağ madenciliği gerçeklemesi
- Tez No: 268842
- Danışmanlar: YRD. DOÇ. DR. TOLGA CAN
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2010
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Bölümü
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 62
Özet
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.
Özet (Çeviri)
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.
Benzer Tezler
- Differential privacy in financial distributed ledger applications
Finansal dağıtık defter uygulamalarında diferansiyel mahremiyet
MERVE CAN KUŞ
Doktora
İngilizce
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSabancı ÜniversitesiBilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
PROF. DR. ALBERT LEVİ
- Structural scene analysis of remotely sensed images using graph mining
Uydu görüntülerinin çizge madenciliği ile yapısal sahne analizi
BAHADIR ÖZDEMİR
Yüksek Lisans
İngilizce
2010
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. SELİM AKSOY
- Çoklu bölümlenmelerin birleştirilmesinde yeni verimli ve ölçeklenebilir yöntemler
Novel efficient and scalable methods for combining multiple clusterings
ARİF MURAT YAĞCI
Yüksek Lisans
İngilizce
2010
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBahçeşehir ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. SELİM NECDET MİMAROĞLU
- Kural tabanlı şüpheli işlem önleme sistemlerinde kullanılmak üzere çizge veritabanı modeli önerisi
A graph database model proposal for use in rule based fraud transaction prevention systems
BAHADIR ESAD DEMİR
Yüksek Lisans
Türkçe
2024
BankacılıkSakarya ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ VEYSEL HARUN ŞAHİN
- Akıllı çiftlikler için büyük veri analizi
Big data analysis for smart farming
DUYGU NAZİFE ZARALI
Yüksek Lisans
Türkçe
2018
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolGazi ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. HACER KARACAN