- This event has passed.
PhD Defense – Abdullah Al-Mamun
April 12, 2018 @ 2:00 pm - 3:00 pm UTC-5
Title: Novel Algorithms for Some Fundamental Big Data Problems
Major Advisor: Dr. Sanguthevar Rajasekaran
Associate Advisors: Dr. Reda Ammar, Dr. Ion Mandoiu
Date/Time: Thursday, Apr 12th, 2018 at 2:00 pm
Location: Moved! to HBL Heritage Room 4118
Abstract:
In this digital era data sets are growing rapidly. Storing, processing, and analyzing large volume of data require efficient techniques. These techniques deal with big data problems by providing time efficient methods, external memory algorithms, distributed processing and so on. This thesis studies three important areas of big data problems and presents state of the art approaches to address them.
The first part of this thesis discusses k-mer counting problem. A massive number of bioinformatics applications require counting of k-length substrings in genetically important long strings. Genome assembly, repeat detection, multiple sequence alignment, error detection, and many other related applications use a k-mer counter as a building block. Very fast and efficient algorithms are necessary to count k-mers in large data sets to be useful in such applications. We propose a novel trie-based algorithm for this k-mer counting problem.
In the second part, we present algorithms on record linkage problems. Integrating data from multiple sources is a crucial and challenging problem. Here we have come up with efficient sequential and parallel algorithms for record linkage which can handle any number of datasets. Our methods employ single linkage as well as complete linkage hierarchical clustering to address this problem.
The last part explains three problems with algorithmic challenges. The first one is minimum spanning tree problem. Finding minimum spanning trees (MST) in various types of networks is a well-studied problem in theory and practical applications. We have devised a very efficient algorithm which combines ideas from randomized selection, Kruskal’s algorithm and Prim’s algorithm. The second problem is closest l-mers problem. Algorithms for finding the closest l-mers have been used in solving the (l, d)-motif search problem. We describe exact as well as very fast approximate algorithms for computing a group of three l-mers having minimum combined distance among all possible such combinations. The third problem is higher order spectra analysis of nonlinear time series. It has applications in biomedical signal processing, communications, geophysics, speech processing, etc. We address this problem by providing space and time efficient sequential and parallel algorithms.
