Parallel sequence mining on distributed memory systems
Dağıtık bellekli sistemlerde paralel dizi madenciliği
- Tez No: 112335
- Danışmanlar: YRD. DOÇ. DR. ATİLLA GÜRSOY
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Kafes, eşdeğer sınıf, yatay veritabanı parçalama metodu iv, Lattice, equivalence class, horizontal database partitioning method. 111 igggSSSSS
- Yıl: 2001
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 56
Özet
ÖZET DAĞITIK BELLEKLİ SİSTEMLERDE PARALEL DİZİ MADENCİLİĞİ Embiya KARAPINAR Bilgisayar Mühendisliği, Yüksek Lisans Tez Yöneticisi: Yrd. Doç. Dr. Atilla Gürsoy Şubat, 2001 Çok büyük veritabanlarında tüm sık dizileri bulmak çok zaman alan bir görevdir. Bununla birlikte, çok büyük veritabanları orjinal veritabanını birden çok veri yığınına parçalayarak ana bellekte işlemeyi zorunlu kılar. Çoğu güncel algoritmalar en uzun sık dizinin uzunluğu adedince veritabanını okumayı gerektirir. Spade, kafes-kuramı yaklaşımını kullanarak orjinal problemi ana hafızada işlenebilen küçük parçalara ( eşdeğer sınıflara) ayıran ve vertabanını üç kere okuyan çok hızlı bir algoritmadır. Bu tez çalışmasında, dağıtık bellekli sistemler için sık diziler kümesinin tamamını bulan ve Spade algoritmasını baz alan dSpade adlı paralel algoritmayı öneriyoruz. dSpade algoritması her işlemcinin eşit miktarda müşteri hareketi sakladığı yatay veritabanı parçalama metodunu kullanır. dSpade birli ve ikili sık dizileri bulan Fi ve Fi fazları süresince anauyumlu bir algorit madır. Her işlemci F1 ve F2 fazları süresince yerel verileri üzerinde yerel destek sayılarını bulur ve genel birli ve ikili sık dizileri bulmak için bu destek sayılarını diğer işlemcilere yayımlar. Birli ve ikili sik dizileri bulduktan sonra tüm sık diziler kafes içine yerleştirilir ve orjinal problemi küçük parçalara bölmek amacıyle kafes eşdeğer sınıflara ayrıştırılır. Eşdeğer sınıflar açgözlü kurami yöntemiyle en az görev yükü olan işlemciye döngüsel bir sırayla eşleştirilir. Bu aşamadan sonra, her işlemci zaman uyumsuz olarak kendisine eşleştirilen eşdeğer sınıfları üzerindeki tüm artan uzunluktaki sık dizileri, Fk, bulur. Sonuçlarını açıkladığımız başarım deneylerini 32-düğümlü Beowulf kümesinde yürüttük. Deneyler gösterdi ki, dSpade iyi bir hız oranı ve veritabanı boyutuna bağlı olarak lineer ölçekle artan sonuçlar verir.
Özet (Çeviri)
ABSTRACT PARALLEL SEQUENCE MINING ON DISTRIBUTED-MEMORY SYSTEMS Embiya KARAPINAR M.S. in Computer Engineering Supervisor: Asst. Prof. Dr. Atilla Gürsoy February, 2001 Discovering all the frequent sequences in very large databases is a time consuming task. However, large databases forces to partition the original database into chunks of data to process in main-memory. Most current algorithms require as many database scans as the longest frequent sequences. Spade is a fast algorithm which reduces the number of database scans to three by using lattice-theoretic approach to decompose origional problem into small pieces (equivalence classes) which can be processed in main-memory independently. In this thesis work, we present dSpade, a parallel algorithm, based on Spade, for discov ering the set of all frequent sequences, targeting distributed-memory systems. In dSpade, horizontal database partitioning method is used, where each processor stores equal number of customer transactions. dSpade is a synchronous algorithm for discovering frequent 1-sequences (F1) and frequent 2-sequences ( F%). Each processor performs the same computation on its local data to get local support counts and broadcasts the results to other processors to find global frequent sequences during F1 and F2 computation. After discovering all F1 and F2, all frequent sequences are inserted into lattice to decompose the original problem into equivalence classes. Equivalence classes are mapped in a greedy heuristic to the least loaded processors in a round- robin manner. Finally, each processor asynchronously begins to compute Fk on its mapped equivalence classes to find all frequent sequences. We present results of performance experiments conducted on a 32-node Beowulf Cluster. Experiments show that dSpade delivers good speedup and scales linearly in the database size.
Benzer Tezler
- Apache spark tabanlı destek vektör makıneleri ile akan büyük veri sınıflandırma
Apache spark based distributed svm algorithm for stream data classification
BARIŞ AKGÜN
Yüksek Lisans
Türkçe
2016
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. ŞULE GÜNDÜZ ÖĞÜDÜCÜ
- İstanbul Metro tünellerinin flac bilgisayar programı ile modellenmesi
Modelling of tunnels of İstanbul subway with flac computer software
OKAN ÖZBAKIR
Yüksek Lisans
Türkçe
1997
Maden Mühendisliği ve Madencilikİstanbul Teknik ÜniversitesiYeraltı Maden İşletmeciliği Ana Bilim Dalı
PROF. DR. ERGİN NASUF
- Bomlu kazı makinalarında kesici kafa tasarım parametrelerinin incelenmesi
Başlık çevirisi yok
ÖMÜR ACAROĞLU
Yüksek Lisans
Türkçe
1996
Maden Mühendisliği ve Madencilikİstanbul Teknik ÜniversitesiPROF.DR. ŞİNASİ ESKİKAYA
- Controlled release system including nanoparticles that can be used for hypothyroidism treatment
Hipotiroidi tedavisinde kullanılabilecek nanopartikül içerikli kontrollü salım sistemi
CEREN KUTLU KAYA
Doktora
İngilizce
2020
Biyomühendislikİstanbul Teknik ÜniversitesiNanobilim ve Nanomühendislik Ana Bilim Dalı
PROF. DR. FATMA NEŞE KÖK
- 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
ERAY ÖZKURAL
Yüksek Lisans
İngilizce
2002
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT