S3-TM: Scalable streaming short text matching
Ölçeklenebilir akan kısa metin eşleme
- Tez No: 379570
- Danışmanlar: DOÇ. DR. HAKAN FERHATOSMANOĞLU, YRD. DOÇ. DR. BUĞRA GEDİK
- 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: 2014
- 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ı: 61
Özet
Mikroblog hizmetleri bilginin üretilmesi ve yayılmasında temel araçlar haline gelmiştir. Dolayısıyla, bu hizmetlerin gözlemlenmesi, gerekli bilgiye ulaşmada kritik bir yetenektir. Bu izleme genelde mikroblog hizmetlerine içerik tabanlı abonelikler kaydedilmesi sayesinde yapılmaktadır. Abonelikler, akan yayınlar üzerinde sürekli çalışan sorgular olarak düşünülebilinir. Bu aboneliklerin değerlendirilmesi, Twitter ve Weibo gibi sistemlerin popülerliği ve ölçeği düşünüldüğünde, oldukça önemli bir sorundur. Bu sorunu aşmak için biz, akan kısa metin eşleme sistemi olan S3-TM'i sunuyoruz. S3-TM akan veri işleme uygulaması olarak organize edilmiş ve veri merkezi ortamında çalışacak şekilde, veri paralelliği sağlayan bir akış ağı olarak tasarlanmıştır. Yayınların ve aboneliklerin yapısını avantaja çevirerek eşlemeyi ölçeklenebilir olarak yapan S3-TM, yayınları ve abonelikleri tüm uçlara aktarmamakta, yayınları birden fazla uca aktarırken, abonelikleri sadece bir uca aktarmaktadır. Ayrıca, sunduğumuz algoritmalar, verimliliği daha da artırmak için, yayınların aktarıldığı uç sayısını minimuma indirmektedir. Tezde önerdiğimiz ilk algoritmalar, kelimelerin ortak görünme grafiklerini bölümlere ayırarak ortak kelimelerin sıkça geçtiği yayınları tüm eşleme operatörlerinin küçük bir kümesine yollamayı hedeflemektedir. Bu algoritmalar verimli olmalarına rağmen yükü eşitlemede yetersiz kalmışlardır. Bu problemi aşmak için, kelime ve yayınların çift taraflı grafiğini verimli bir şekilde bölümleyerek modelleme yapan ve daha dengeli yük dağılımı sağlayan SALB algoritmasını geliştirdik. Aynı zamanda, benzer abonelikleri aynı uçlara yönlendirerek gruplayan ve eşleme işleminin yükünü minimuma indiren LASP algoritmasını ekledik. Ayrıca, artan uç sayısında daha iyi bir ölçeklenebilirliğe ulaşmak için iş yükündeki çarpıklıkları çözen basit ama verimli teknikler geliştirdik. Son olarak eşleme doğruluğu üzerinde çok az bir etki yapan yük azaltma teknikleriyle, beklenmeyen yük artışlarını çözdük. Deneysel sonuçlarımız S3-TM algoritmasının ölçeklenebilir olduğunu göstermektedir. Buna ek olarak, SALB algoritması temel algoritmadan 2.5 kat olmak üzere, kelimelerin ortak görünme grafiği bölümleme algoritmalarından da daha yüksek performanslı olduğu gözlemlenmektedir.
Özet (Çeviri)
Micro-blogging services have become major venues for information creation, as well as channels of information dissemination. Accordingly, monitoring them for relevant information is a critical capability. This is typically achieved by reg- istering content-based subscriptions with the micro-blogging service. Such sub- scriptions are long running queries that are evaluated against the stream of posts. Given the popularity and scale of micro-blogging services like Twitter and Weibo, building a scalable infrastructure to evaluate these subscriptions is a challenge. To address this challenge, we present the S3-TM system for streaming short text matching. S3-TM is organized as a stream processing application, in the form of a data parallel flow graph designed to be run on a data center environment. It takes advantage of the structure of the publications (posts) and subscriptions to perform the matching in a scalable manner, without broadcasting publications or subscriptions to all of the matcher instances. The basic design of S3-TM uses a scoped multicast for publications and scoped anycast for subscriptions. To fur- ther improve throughput, we introduce publication routing algorithms that aim at minimizing the scope of the multicasts. The first set of algorithms we de- velop are based on partitioning the word co-occurrence frequency graph, with the aim of routing posts that include commonly co-occurring words to a small set of matchers. While effective, these algorithms fell short in balancing the load. To address this, we develop the SALB algorithm, which provides better load balance by modeling the load more accurately using the word-to-post bipartite graph. We also develop a subscription placement algorithm, called LASP, to group together similar subscriptions, in order to minimize the subscription matching cost. Fur- thermore, to achieve good scalability for increasing number of nodes, we introduce simple yet effective techniques to handle workload skew. Finally, we introduce load shedding techniques for handling unexpected load spikes with small impact on the accuracy. Our experimental results show that S3-TM is scalable. Further- more, the SALB algorithm provides more than 2.5× throughput compared to the baseline multicast and outperforms the graph partitioning based approaches.
Benzer Tezler
- Kenar ağlarında nokta yatay konumu inceliği
The Precission for the horizontal position of the point in trilateration net
ALİ RIZA YURDAKUL
- Büyük Menderes havzası topraklarında fosfor ve potasyum fiksasyonu ve buna etki eden etmenlerin incelenmesi
Phosphorus and potassium fixation Büyük Menderes basin soils and the factors influencing
ŞAFAK KIRMIZI
- Hazar havzası (Kazakistan) güneyindeki petrollü jura-triyas yaşlı kayaçların organik jeokimyasal özellikleri
Organic geochemical properties of jura-triassic aging rocks in the south part of Caspian basin (Kazakhstan)
TOLGANAY JARASSOVA
Doktora
Türkçe
2020
Jeoloji MühendisliğiAkdeniz ÜniversitesiJeoloji Mühendisliği Ana Bilim Dalı
PROF. DR. MEHMET ALTUNSOY
- Üç serbestlik dereceli silindirik bir manipulatörün tasarımı, simülasyonu ve kontrolu
Design simulation and control of a cylindirical 3dof manipulator
S.HAYDAR İÇLİ