A disk-based graph database system with incremental storage layout optimization
Artımlı depolama düzen optimizasyonlu disk tabanlı çizge veritabanı
- Tez No: 418737
- Danışmanlar: 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: 2016
- 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
Artık insanların, yazılım sistemlerinin ve fiziksel dünyanın daha önce hiç olmadığı kadar büyük bir hızda, hacimde ve çeşitlilikte veri ürettikleri, herşeyin bağlı ve daha erişilebilir olduğu bir dünyada yaşıyoruz. Telekomünikasyon, sosyal medya ve canlı veri kaydı gibi bir çok uygulama alanında insanlar, sistemler ve bulundukları ortamlar arasında kolayca bir ilişki bulunabilir. Bu ilişkiler çoğunlukla, varlıkları düğümler, aralarındaki ilişkilerde kenarları gösterecek şekilde zamanla gelisen bir çizge olarak karşımıza çıkabilmektedir. Bu yüzden, bir çizge yapısı içinde dinamik değişebilen ilişkileri yönetmek, modern veri işleme sistemlerinin ortak gereksinimlerinden biri olmuştur. Veri işleme sistemlerinin yaygınlaşması da çizge veritabanlarının önem kazanmasına sebep olmuştur. Bu çalışmada, artımlı güncellemeleri destekleyen, disk tabanlı bir çizge veritabanı geliştirdik. Veritabanına çizge güncelleştirmeleri (ekleme/çıkarma) bir akış şeklinde gelir, sistem gelen veriye göre bir depolama düzeni oluşturur ve en optimize olacak şekilde bu düzeni yönetir. Böylece, optimize depolama düzeni üzerinde düşürülen disk girdi-çıktısı, gezinme tipi algoritmaların daha verimli olarak koşulabilmesini sağlar. Geliştirdiğimiz depolama düzeni optimizasyonları, artımlı biçimde çizge güncellemeleri gelirken oluşan çizge kenarlarının boyutsal lokalitelerini hesaba katarak, çizge üzerinde gezinme sırasında oluşan disk girdi-çıktı sayısını düşürmeyi amaçlamaktadır.
Özet (Çeviri)
The world has become ever more connected, where the data generated by people, software systems, and the physical world is more accessible than before and is much larger in volume, variety, and velocity. In many application domains, such as telecommunications and social media, live data recording the relationships between people, systems, and the environment is available. This data often takes the form of a temporally evolving graph, where entities are the vertices and the relationships between them are the edges. For this reason, managing dynamic relationships represented by a graph structure has been a common requirement for modern data processing applications. Graph databases gained importance with the proliferation of such data processing applications. In this work, we developed a disk-based graph database system, which is able to manage incremental updates on the graph structure. The updates arrive in a streaming manner and the system creates and maintains an optimized storage layout for the graph in an incremental way. This optimized storage layout enables the database to support traversal based graph algorithms more efficiently, by minimizing the disk I/O required to execute them. The storage layout optimizations we develop aim at taking advantage of spatial locality of edges to minimize the traversal I/O cost, but achieves this in an incremental way as new edges/vertices get added and removed.
Benzer Tezler
- Scalable layout of large graphs on disk
Büyük çizgeler için ölçeklenebilir disk yerleşimi
ABDURRAHMAN YAŞAR
Yüksek Lisans
İngilizce
2015
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. BUĞRA GEDİK
- Hypergraph based declustering of multi-disk databases
Çok diskli veritabanlarının hiperçizge tabanlı ayrıştırılması
MEHMET KOYUTÜRK
Yüksek Lisans
İngilizce
2000
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. CEVDET AYKANAT
- Sahada programlanabilir kapı dizileri ile lojik devre tasarımı
Başlık çevirisi yok
VOLKAN SEZER
Yüksek Lisans
Türkçe
1996
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. AHMET DERVİŞOĞLU
- Unit disk graph coloring and its reoptimization
Birim disk çizge boyama ve yeniden eniyilenmesi
ARMAN BOYACI
Yüksek Lisans
İngilizce
2009
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Bölümü
YRD. DOÇ. TINAZ EKİM AŞICI
- Exploiting cluster-skipping inverted index structure for semantic place retrieval
Anlamsal mekan getirimi için küme atlamalı ters dizin yapısından yararlanma
ENES RECEP ÇINAR
Yüksek Lisans
İngilizce
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. İSMAİL SENGÖR ALTINGÖVDE