Frequent subgraph mining over dynamic graphs
Abuzayed, Nourhan N.I., author.

Frequent subgraph mining over dynamic graphs

Abuzayed, Nourhan N.I., author.

Yazar Ek Girişi
Abuzayed, Nourhan N.I., author.

Fiziksel Tanımlama
xii, 94 leaves: charts;+ 1 computer laser optical disc.

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

Konu Başlığı
Data mining
Graph theory

Yazar Ek Girişi
Ergenç Bostanoğlu, Belgin,

Tüzel Kişi Ek Girişi
İzmir Institute of Technology. Computer Engineering.

Tek Biçim Eser Adı
Thesis (Doctoral)--İzmir Institute of Technology:Computer Engineering.
İzmir Institute of Technology: Computer Engineering--Thesis (Doctoral).

Elektronik Erişim
Access to Electronic Versiyon.

KütüphaneMateryal TürüDemirbaş NumarasıYer NumarasıDurumu/İade Tarihi
IYTETezT002583QA76.9.D343 A16 2022Tez Koleksiyonu