Please use this identifier to cite or link to this item: https://hdl.handle.net/11147/12616
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorErgenç Bostanoğlu, Belgintr
dc.contributor.authorAbuzayed, Nourhan N. I.tr
dc.date.accessioned2022-11-30T11:57:44Z-
dc.date.available2022-11-30T11:57:44Z-
dc.date.issued2022-07en_US
dc.identifier.urihttps://hdl.handle.net/11147/12616-
dc.identifier.urihttps://tez.yok.gov.tr/UlusalTezMerkezi/TezGoster?key=_F5QEpayDXGqGZlp9XiFtChGsy4KR4vZL9u_PvKLMYULAYkJCb9MFPlheea2FvI8-
dc.descriptionThesis (Doctoral)--Izmir Institute of Technology, Computer Engineering, Izmir, 2022en_US
dc.descriptionIncludes bibliographical references (leaves. 90-93)en_US
dc.descriptionText in English; Abstract: Turkish and Englishen_US
dc.description.abstractFrequent subgraph mining (FSM) is an essential and challenging graph mining task used in several applications. Modern applications employ evolving graphs, so FSM is more challenging with evolving graphs due to the streaming nature of the input, and the exponential time complexity of the algorithms. Sampling schemes are used if approximate results serve the purpose. This thesis introduces three approximate frequent subgraph mining algorithms in evolving graphs. those algorithms use novel controlled reservoir sampling. A sample reservoir of the evolving graph and an auxiliary heap reservoir data structure are kept together in a fixed sized reservoir. When the whole reservoir is full, and space has required the edges of lower degree or higher nodes are deleted. This selection is done by utilizing the heap data structure as a heap reservoir, which keeps the node degrees. By keeping the edges of higher degree nodes in the sample reservoir, accuracy is maximized without sacrificing time and space, in contrast, keeping the edges of lower degree nodes in the sample reservoir, accuracy is minimized with higher time and space. The first algorithm is Controlled Reservoir Sampling with Unlimited heap size (UCRS), where the used heap reservoir size is unlimited. The second algorithm is Controlled Reservoir Sampling with Limited heap size (LCRS). It is a modified version of UCRS, but the heap reservoir size is limited, as a result; sample reservoir size in the whole reservoir increases since the total number of nodes dedicated for the whole reservoir includes the nodes of the heap reservoir also. The third algorithm is Maximum Controlled Reservoir Sampling (MCRS). It is a modified version of UCRS, but the candidate edge for deletion is an edge with maximum node degrees. Experimental evaluations to measure scalability and recall performances of the three algorithms in comparison to state of art algorithms are performed on dense and sparse evolving graphs. Findings show that UCRS and LCRS algorithms are scalable and achieve better recall than edge based reservoir algorithms. LCRS achieves the best recall in comparison to edge or subgraph based reservoir algorithms. MCRS has the worst speed-up and recall among the other proposed and competitor algorithms.en_US
dc.description.abstractSık alt çizgeler madenciliği bir çok veri madenciliği uygulaması için temel ve zorlu bir iştir. Modern uygulamalar devingen çizgelerle çalışmakta olup, girdilerindeki veri akışı, sık alt çizge madenciliği algoritmalarının karmaşıklığını arttırmaktadır. Yaklaşık sonuçların yeterli olduğu durumlarda örneklemeye dayalı yaklaşımlar kullanılmaktadır. Bu tez kapsamında üç adet yaklaşık sık alt çizge madenciliği algoritması önerilmektedir. Önerilen algoritmalarda yenilikçi olarak, kontrollü depolama ile örneklem oluşturma yaklaşımı kullanılmıştır. Devingen çizgeye ilişkin örneklem sabit boyutlu depoda tutulmakta ve yardımcı bir yığın veri yapısı kullanılmaktadır. Bu yığın veri yapısında depodaki çizge düğümlerinin bağlantı dereceleri tutulmaktadır. Sabit boyutlu depo dolduğunda ve yeni alan gereksinimi ortaya çıktığında bu depodan çizgenin en düşük dereceli düğümleri çıkarılmaktadır. Devingen çizge örneklemini tutan sabit depoda yüksek dereceli düğümlerin kalması sağlanarak sonuçlardaki doğruluk, yer ve zaman maliyetini artırmadan yükseltebilmektedir. İlk olarak limitsiz boyutlu kontrollü depo örneklemesine dayalı “Controlled Reservoir Sampling with Unlimited heap size (UCRS)” algoritması önerilmiştir; adından da anlaşılacağı üzere kullanılan yardımcı yığının boyutu kısıtlanmamıştır. İkinci algoritma “Controlled Reservoir Sampling with Limited heap size (LCRS)” da büyüyen depo ile büyüyen yığının boyutuna sınır getirilmektedir. Üçüncü algoritma “Maximum Controlled Reservoir Sampling (MCRS)” ilk algoritmaya benzemektedir; yığın boyutu sınırlandırılmamıştır ancak depodan düğüm silmek gerektiğinde en düşük dereceli düğüm yerine en yüksek dereceli düğüm çıkarılmaktadır. Her üç algoritmanın başarım değerlendirmeleri zaman, ölçeklenebilirlik ve doğruluk ölçütleri ile yapılmıştır. Başarım değerlendirmelerinde önerilen algoritmalar iki güncel rakip algoritma ile yoğun ve seyrek veri setleri üzerinde karşılaştırılmıştır. Bulgular UCRS ve LCRS algorithmalarının ölçeklenebilir olduğunu, rakip kenar tabanlı algoritmadan daha doğru sonuçlar verdiğini göstermiştir. LCRS tüm rakip algoritmalardan daha iyi başarım elde etmiştir. MCRS algoritmasının sonuçları tüm algoritmalar arasında en kötüdür.tr
dc.format.extentxii, 94 leavesen_US
dc.language.isoenen_US
dc.publisherIzmir Institute of Technologyen_US
dc.rightsinfo:eu-repo/semantics/openAccessen_US
dc.subjectFrequent subgraph miningen_US
dc.subjectGraph miningen_US
dc.subjectAlgorithmsen_US
dc.titleFrequent subgraph mining over dynamic graphsen_US
dc.title.alternativeDeğişken veri üzerine sık alt çizge madenciliğien_US
dc.typeDoctoral Thesisen_US
dc.authorid0000-0002-0688-5511-
dc.departmentThesis (Doctoral)--İzmir Institute of Technology, Computer Engineeringen_US
dc.relation.publicationcategoryTezen_US
dc.identifier.yoktezid631054en_US
item.grantfulltextopen-
item.openairecristypehttp://purl.org/coar/resource_type/c_18cf-
item.cerifentitytypePublications-
item.openairetypeDoctoral Thesis-
item.languageiso639-1en-
item.fulltextWith Fulltext-
Appears in Collections:Phd Degree / Doktora
Files in This Item:
File Description SizeFormat 
10147615.pdfDoctoral Thesis3.11 MBAdobe PDFView/Open
Show simple item record



CORE Recommender

Page view(s)

178
checked on Apr 15, 2024

Download(s)

146
checked on Apr 15, 2024

Google ScholarTM

Check





Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.