Geri Dön

BB-Graph: A new subgraph isomorphism algorithm for querying big graph databases

BB-Graph: büyük çizge veritabanlarını sorgulamak için yeni bir altçizge eşyapılılık algoritması

PDF İndir

  1. Tez No: 441943
  2. Yazar: MERVE ASİLER
  3. Danışmanlar: PROF. DR. ADNAN YAZICI
  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: 2016
  8. Dil: İngilizce
  9. Üniversite: Orta Doğu Teknik Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: Belirtilmemiş.

Özet

Büyük veri kavramının doğmasıyla, ilişkisel veritabanı yönetim sisteminde masraflı birleştirme operasyonları gerektiren durumlarda daha esnek ve hızlı sorgulama sağladığı için büyük çizge veritabanı modeli çok popüler olmuştur. Ancak, altçizge eşyapılılık problemi olarak bilinen, bir çizgesel sorgunun bir veritabanı çizgesindeki tüm tam eşleşmelerini bulmak oldukça zordur. Literatürde ilgili birçok çalışma olmasına rağmen, bu NP-hard bir problem olduğundan, tüm sorgu tipleri için verimli çalışan kusursuz bir algoritma bulunmamaktadır. Ullmann'ın fikri üzerine kurulan şu anki altçizge eşyapılılık yaklaşımları, ilgisiz adayları budama stratejisine odaklanmaktadır. Yine de, bazı veritabanları ve sorgular için, bu algoritmaların kullandıkları budama teknikleri yetersiz kalmaktadır. O yüzden, zayıf performansa yol açarlar. Ayrıca, bu algoritmalardan bazıları ek hafıza tüketimine sebep olan dizinlere gereksinim duyar. Bunlardan motivasyon alarak, büyük veritabanı çizgelerini ek veri yapılarına ihtiyaç olmadan verimlice sorgulamak için yeni bir altçizge eşyapılılık algoritması BB-Graph'ı geliştirdik. Algoritmamızı çok büyük bazı çizge veritabanı uygulamalarında var olan algoritmalarla, GraphQL ve Neo4j'nin Cypher'ı ile, karşılaştırarak test ettik ve BB-Graph'ın çoğu sorgu tipi için daha iyi performans sergilediğini gösterdik.

Özet (Çeviri)

With the emergence of the big data concept, the big graph database model has become very popular since it provides very flexible and quick querying for the cases that require costly join operations in RDBMs. However, it is a big challenge to find all exact matches of a query graph in a big database graph, which is known as the subgraph isomorphism problem. Although many related studies exist in literature, there is not a perfect algorithm that works for all types of queries efficiently since it is an NP-hard problem. The current subgraph isomorphism approaches built on Ullmann's idea focus on the strategy of pruning out the irrelevant candidates. Nevertheless, for some databases and queries, their pruning techniques are inadequate. Therefore, they result in poor performance. Moreover, some of those algorithms need large indices that cause extra memory consumption. Motivated by these, we introduce a new subgraph isomorphism algorithm, namely BB-Graph, for querying big database graphs in an efficient manner without requiring large data structures. We test and compare our algorithm with the existing ones, GraphQL and Cypher of Neo4j, on some very big graph database applications and show that our algorithm performs better for most of the query types.

Benzer Tezler

  1. Tez No

    572187

    BB-PLUS: An efficient approach for subgraph isomorphism problem in big graph databases

    BB-PLUS: Büyük çizge veritabanlarında altçizge eşyapılılık problemine etkin bir yaklaşım

    EZGİ TAŞKOMAZ

    Yüksek Lisans

    İngilizce

    İngilizce

    2019

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. ADNAN YAZICI

  2. Tez No

    66838

    GT yöntemlerinin sınıflandırması, performans ölçütleri, üretimle ilgili verileri kullanan yeni yöntemlere örnekler ve genetik algoritmalar

    Taxonomy of GT methods, performance measures,some new GT methods that is able to incorporate pertinent manufacturing data and genetic algorithms

    HATİCE DERİCİ

    Yüksek Lisans

    Türkçe

    Türkçe

    1997

    Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesi

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

    DOÇ. DR. M. BÜLENT DURMUŞOĞLU

  3. Tez No

    39313

    Veri akış denklemlerinin çözümü ile kod optimizasyonu

    Code optimization by solving data flow equations

    EROL AKARSU

    Yüksek Lisans

    Türkçe

    Türkçe

    1993

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    DOÇ.DR. NADİA ERDOĞAN

  4. Tez No

    19265

    Aktif tüm-geçiren anahtarlı kapasite filtrelerinin kaskad kafes yapılarla gerçeklenmesi

    Cascaded lattice realization of active all-pass switched capacitor filters

    DOĞAN ALKAN

    Yüksek Lisans

    Türkçe

    Türkçe

    1991

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    PROF.DR. CEVDET ACAR

  5. Tez No

    75589

    Demiryolu ağında trafik sayımlarından O-D matrisi tahmini

    Başlık çevirisi yok

    ZEYNEP AĞCI

    Yüksek Lisans

    Türkçe

    Türkçe

    1998

    İnşaat Mühendisliğiİstanbul Teknik Üniversitesi

    Ulaştırma Ana Bilim Dalı

    PROF. DR. HALUK GERÇEK

Geri Dön