CSE Honors Competition

Join Us to Celebrate Exceptional Graduate Research at CSE!
Ganesh Dasika, Hardware: GPGPU, M.D. – A Low-power Supercomputer for Portable Medical Imaging

Medical imaging provides physicians with the ability to generate 3D images of the human body to detect and diagnose a wide variety of medical ailments. However, supercomputer levels of performance are required to construct these images from large datasets. Graphics processing units (GPUs) have emerged as the supercomputer-on-the-desktop solution as they are low cost and achieve tera-FLOP levels of performance. However, GPUs are not well matched to medical imaging due to the relatively low memory bandwidth to compute ratio that they support. Further, the power consumption of GPUs makes them impractical to operate in newer, untethered imaging devices. This work presents the GPGPU, MD architecture – a domain-specific architecture designed specifically for medical imaging applications, but with sufficient generality to make it programmable.

Ran Duan, Theory: Fast Algorithms for (max,min) – Matrix Multiplication and Bottleneck Paths

Given a directed graph with a capacity on each edge, the all-pairs
bottleneck paths (APBP) problem is to determine, for all vertices s
and t, the maximum flow that can be routed from s to t. For dense
graphs this problem is equivalent to that of computing the
(max,min)-transitive closure of a real-valued matrix. In this paper,
we give a (max,min)-matrix multiplication algorithm running in time
O(n^{(3+\omega)/2}), which is roughly O(n^{2.688}), where \omega is
the exponent of boolean matrix multiplication. Although our algorithm
is slower than the best APBP algorithm on vertex capacitated graphs,
running in O(n^{2.575}) time, it is just as efficient as the best
algorithm for computing the dominance product, a problem closely
related to (max,min)-matrix multiplication.

Ahmed Hassan, Intelligent Systems: Mining Language Networks

Link analysis techniques are very popular both in Web search and in network analysis. They have been successfully applied to several domains including web page ranking, community finding and several other applications. Those techniques rely on explicit links between textual entities which limits their applicability to domains where explicit links are available. I will present text mining methods that adapt link analysis techniques to corpora in which explicit links between documents do not exist. To do that, I rely on natural language processing techniques to come up with implicit links between documents that could replace or extend explicit link based networks. This idea can be used in several application including: community finding in non hyperlinked environments, blog feed ranking and recommendation, determining speaker salience in discussions, identifying how individuals in groups influence other participants, and tracking how speaker salience evolves over time.

Xin Hu, Software: Large-Scale Malware Indexing Using Function-Call Graphs

A major challenge of the anti-virus (AV) industry is how to effectively process the huge influx of malware samples they receive every day. One possible solution to this problem is to quickly determine if a new malware sample is similar to any previously-seen malware program. In this paper, we design, implement and evaluate a malware database management system called SMIT (Symantec Malware Indexing Tree) that can efficiently make such determination based on malware’s function-call graphs, which is a structural representation known to be less susceptible to instruction-level obfuscations commonly employed by malware writers to evade detection of AV software. Because each malware program is represented as a graph, the problem of searching for the most similar malware program in a database to a given malware sample is cast into a nearest-neighbor search problem in a graph database. To speed up this search, we have developed an efficient method to compute graph similarity that exploits structural and instruction-level information in the underlying malware programs, and a multi-resolution indexing scheme that uses a computationally economical feature vector for early pruning and resorts to a more accurate but computationally more expensive graph similarity function only when it needs to pinpoint the most similar neighbors. Results of a comprehensive performance study of the SMIT prototype using a database of more than 100,000 malware demonstrate the effective pruning power and scalability of its nearest neighbor search mechanisms.