Discovery of frequent item set in peer-to-peer networks
Görevdeş ağlarda sık bulunan öğe setinin bulunması
- Tez No: 270058
- Danışmanlar: DOÇ. DR. ÖZNUR ÖZKASAP
- 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: Koç Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Elektrik ve Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 77
Özet
Bir çok görevdeş ağ uygulaması sistemdeki düğümlerde kısmi olarak bulunan veri erişim sıklığı, öğe sıklığı, sorgu ve olay sayısı gibi sistem genelindeki bilgiye ihtiyaç duyarlar. Dağıtık bir sistemde sık bulunan öğelerin belirlenmesi problemi sistem genelindeki bir bilginin hesaplanmasını gerektiren yaygın bir problemdir. Sistem genelindeki sıklığı belirli bir eşik değerinin üstünde bulunan öğelere sık bulunan veya yaygın öğeler denir. Günümüz P2P ağlarında, sistem genelindeki sık öğelerin bilgisine ihtiyaç duyan uygulamaların sayısı hızla artmaktadır. Bu yüzden, sık bulunan öğelerin verimli bir şekilde tespit edilmesi, bir çok görevdeş ağ uygulamalarında, düğümler için değerli bir servistir. Ayrıca, bu servis dağıtık veri tabanı uygulamalarında, önbellek yönetiminde, veri yineleme yöntemlerinde, algılayıcı ağlarda ve güvenlik mekanizmalarının önemli olduğu sistemlerde de kullanılabilir.Bu tezde, ProFID olarak adlandırdığımız, yapılandırılmamış görevdeş ağlarda sık bulu-nan öğelerin belirlenmesi için epidemik tabanlı yöntemi kullanan dağıtık bir yöntem sunulmuştur. Ortalama yönteminin epidemik tabanlı yöntem ile birlikte sık bulunan öğelerin tespit edilmesinde kullanılması ve pratik yakınsama yöntemi önerdiğimiz yöntemin yenilikçi ve yararlı özellikleridir. Bu konudaki çalışmalara katkılarımızı şu şekilde sıralayabiliriz. İlk olarak, sık bulunan öğe setinin bütün düğümlerde hesaplandığı tam dağıtık bir yöntem önerisi sunulmuştur. Bu yöntem yapılandırılmamış ağlarda ikili gruplar halinde ortalama yöntemi ile ağ boyutu tahminini kullanarak sık öğeleri tespit eden ilk yöntemdir. İkinci olarak, algoritmanın sonlandırılması için pratik yakınsama yöntemi sunulmuştur. Bu yöntem ile düğümler yerel durumlarındaki değişimleri değerlendirerek, diğer düğümlerden bağımsız olarak yakınsama kararı alırlar. Ayrıca, PeerSim simülatörü ile elde edilen kapsamlı sonuçlar kullanılarak önerilen yöntemin verimliliği, ölçeklenebilirliği ve uygulanabilirliği ölçülmüştür. Son olarak, ProFID ile uyarlanmış Push-Sum yöntemleri karşılaştırılmıştır. Bu karşılaştırma sonuçlarında, ProFID hem doğruluk hem de ölçeklenebilirlik açısındanuyarlanmış Push-Sum yöntemine göre daha iyi sonuçlar vermiştir.
Özet (Çeviri)
Several P2P applications require a global view of system information such as data access frequencies, item frequencies, query and event counts, that are available locally and partially at peers. Frequent item set discovery (FID) in a distributed environment is a common problem requiring global information computation. Items that globally occur more than a threshold value are referred as frequent or popular and the number of diverse applications that need globally frequent items is increasing expeditiously in today's P2P networks. Therefore, efficiently discovering frequent items would be a valuable service for peers. Being significant for P2P systems, FID problem is also applicable to distributed database applications, cache management, data replication, sensor networks, and security mechanisms in which identifying frequently occurring items in the entire system is useful.In this thesis, we propose and develop a gossip-based distributed approach, namely ProFID, for discovering frequent items in unstructured P2P networks. In contrast to the prior studies, our solution progresses in a fully distributed manner using an atomic averaging function to discover frequent items. Utilizing averaging function with gossip-based aggregation in frequent item set discovery problem and a practical convergence rule are novel and beneficial features of our approach. We make the following contributions to the current state of the art. First, we propose a fully distributed Protocol for Frequent Item Discovery (ProFID) where the result is produced at every peer. ProFID uses a novel pairwise averaging function and network size estimation together to discover frequent items in an unstructured P2P network. We also propose a practical rule for convergence of the algorithm. In contrast to previous works, each peer gives local decision for convergence based on the change of updated local state. Moreover, we developed a model of ProFID in PeerSim and performed various experiments to compare and evaluate its efficiency, scalability, applicability. Finally, we compared the accuracy and scalability of ProFID with adaptive Push-Sum algorithm. The comparison results show that ProFID outperforms adaptive Push-sum in terms of accuracy, convergence speed and message overhead.
Benzer Tezler
- An efficient mining approach of frequent data item sets on large uncertain databases
An efficient mining approach of frequent data item sets on large uncertain databases
ISSE HASSAN SHEIKH NUR
Yüksek Lisans
İngilizce
2015
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMarmara ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. MELİH KIRLIDOĞ
- Teknoloji fırsat keşfi için veri odaklı çözüm yaklaşımlarının geliştirilmesi
Development of data-driven solution approaches for technology opportunity discovery
ZÜLFİYE ERDOĞAN
Doktora
Türkçe
2024
Endüstri ve Endüstri MühendisliğiYıldız Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. SERKAN ALTUNTAŞ
PROF. DR. TÜRKAY DERELİ
- Data mining and an application in the open education system of Anadolu University
Veri madenciliği ve Anadolu Üniversitesi açıköğretim sisteminde bir uygulama
BILAL AL-RUBAIEE
Yüksek Lisans
İngilizce
2018
İstatistikAnadolu Üniversitesiİstatistik Ana Bilim Dalı
DR. ÖĞR. ÜYESİ ATİLLA ASLANARGUN
- Privacy preserving data analysis for information systems
Bilgi sistemleri için gizliliği koruyan veri analizi
BARIŞ YILDIZ
Doktora
İngilizce
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolDokuz Eylül ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. RECEP ALP KUT
- Parallelization of a novel frequent itemset hiding algorithm on a CPU-GPU platform
Yeni bir sık kümeleri gizleme algoritmasının CPU-GPU plaformu üzerinde parallelleştirilmesi
SAMUEL BACHA HEYE
Yüksek Lisans
İngilizce
2014
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİzmir Yüksek Teknoloji EnstitüsüBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. TOLGA AYAV