Geri Dön

Discovery of frequent item set in peer-to-peer networks

Görevdeş ağlarda sık bulunan öğe setinin bulunması

  1. Tez No: 270058
  2. Yazar: EMRAH ÇEM
  3. Danışmanlar: DOÇ. DR. ÖZNUR ÖZKASAP
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2010
  8. Dil: İngilizce
  9. Üniversite: Koç Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Elektrik ve Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. 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

    İngilizce

    2015

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMarmara Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. MELİH KIRLIDOĞ

  2. 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

    Türkçe

    2024

    Endüstri ve Endüstri MühendisliğiYıldız Teknik Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. SERKAN ALTUNTAŞ

    PROF. DR. TÜRKAY DERELİ

  3. 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

    İngilizce

    2018

    İstatistikAnadolu Üniversitesi

    İstatistik Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ ATİLLA ASLANARGUN

  4. Privacy preserving data analysis for information systems

    Bilgi sistemleri için gizliliği koruyan veri analizi

    BARIŞ YILDIZ

    Doktora

    İngilizce

    İngilizce

    2022

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolDokuz Eylül Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. RECEP ALP KUT

  5. 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

    İ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