Doctor of Philosophy, The Ohio State University, 2015, Computer Science and Engineering

Making sense of, analyzing, and extracting useful information from large and complex data is a grand challenge. A user tasked with meeting this challenge is often befuddled with questions on where and how to begin to understand the relevant characteristics of such data. Recent advances in relational analytics, in particular network analytics, offer key tools for insight into connectivity structure and relationships at both local ("guilt by association") and global (clustering and pattern matching) levels. These tools form the basis of recommender systems, ranking, and learning algorithms of great importance to research and industry alike. However, complex data rarely originate in a format suitable for network analytics, and the transformation of large and typically high-dimensional non-network data to a network is rife with parameterization challenges, as an under- or over-connected network will lead to poor subsequent analysis. Additionally, both network formation and subsequent network analytics become very computationally expensive as network size increases, especially if multiple networks with different connectivity levels are formed in the previous step; scalable approximate solutions are thus a necessity. I present an interactive system called PLASMA-HD to address these challenges. PLASMA-HD builds on recent progress in the fields of locality sensitive hashing, knowledge caching, and graph visualization to provide users with the capability to probe and interrogate the intrinsic structure of data. For an arbitrary dataset (vector, structural, or mixed), and given a similarity or distance measure-of-interest, PLASMA-HD enables an end user to interactively explore the intrinsic connectivity or clusterability of a dataset under different threshold criteria. PLASMA-HD employs and enhances the recently proposed Bayesian Locality Sensitive Hashing (BayesLSH), to efficiently estimate connectivity structure among entities. Unlike previous efforts which operate at (open full item for complete abstract)

Committee: Srinivasan Parthasarathy (Advisor); Arnab Nandi (Committee Member); P Sadayappan (Committee Member); Michael Barton (Committee Member) Subjects: Computer Science

Doctor of Philosophy, The Ohio State University, 2019, Computer Science and Engineering

Graphic Processing Units (GPUs) have become popular in the last decade due to their high memory bandwidth and powerful computing capacity. Nevertheless, achieving high-performance on GPUs is not trivial. It generally requires significant programming expertise and understanding of details of low-level execution mechanisms in GPUs. This dissertation introduces approaches for optimizing regular and irregular applications. To optimize regular applications, it introduces a novel approach to GPU kernel optimization by identifying and alleviating bottleneck resources. This approach, however, is not effective in irregular applications because of data-dependent branches and memory accesses. Hence, tailored approaches are developed for two popular domains of irregular applications: graph algorithms and sparse matrix primitives. Performance modeling for GPUs is carried out by abstract kernel emulation along with latency/gap modeling of resources. Sensitivity analysis with respect to resource latency/gap parameters is used to predict the bottleneck resource for a given kernel's execution. The utility of the bottleneck analysis is demonstrated in two contexts: i) Enhancing the OpenTuner auto-tuner with the new bottleneck-driven optimization strategy. Effectiveness is demonstrated by experimental results on all kernels from the Rodinia suite and GPU tensor contraction kernels from the NWChem computational chemistry suite. ii) Manual code optimization. Two case studies illustrate the use of a bottleneck analysis to iteratively improve the performance of code from state-of-the-art DSL code generators. However, the above approach is ineffective for irregular applications such as graph algorithms and sparse linear systems. Graph algorithms are used in various applications, and high-level GPU graph processing frameworks are an attractive alternative for achieving both high productivity and high-performance. This dissertation develops an approach to graph processing on GPUs (open full item for complete abstract)

Committee: Ponnuswamy Sadayappan (Advisor); Rountev Atanas (Committee Member); Teodorescu Radu (Committee Member) Subjects: Computer Science

Master of Science, Miami University, 2024, Computer Science

Causal maps are graphical models that are well-understood in small scales. When created through a participatory modeling process, they become a strong asset in decision making. Furthermore, those who participate in the modeling process may seek to understand the problem from various perspectives. However, as causal maps increase in size, the information they contain becomes clouded, which results in the map being unusable. In this thesis, we transform causal maps into various mediums to improve the usability and accessibility of large causal models; our proposed algorithms can also be applied to small-scale causal maps. In particular, we transform causal maps into meaningful paragraphs using GPT and network traversal algorithms to attain full-coverage of the map. Then, we compare automatic text summarization models with graph reduction algorithms to reduce the amount of text to a more approachable size. Finally, we combine our algorithms into a visual analytics environment to provide details-on-demand for the user by displaying the summarized text, and interacting with summaries to display the detailed text, causal map, and even generate images in an appropriate manner. We hope this research provides more tools for decision-makers and allows modelers to give back to participants the final result of their work.

Committee: Philippe Giabbanelli (Advisor); Daniela Inclezan (Committee Member); Garrett Goodman (Committee Member) Subjects: Computer Science

Master of Sciences (Engineering), Case Western Reserve University, 2017, EECS - System and Control Engineering

With the rise of social media and big data, graph analytics are increasingly being called upon to provide insights based on network connectivity and the concept of "centrality." While many graph centrality measures are computed solely from topology, Percolation Centrality simultaneously addresses network percolation by incorporating into its calculation individual nodal states. This allows for the modeling of network infection, and can be applied to use cases such as disease transmission and viral marketing campaigns. While useful across a variety of domains, Percolation Centrality has not yet been scaled to run on multi-genre distributed computing platforms. This thesis develops a vertex-centric, platform-independent logic for scaling the computation of Percolation Centrality, presents a solution built on Teradata Aster's bulk synchronous parallel graph engine, validates the function's results, tests its scalability against a variety of generated sample networks, and demonstrates its ability to handle and generate insights from real-world data.

Committee: Vira Chankong Ph.D. (Committee Chair); Narasingarao Sreenath Ph.D. (Committee Member); Evren Gurkan-Cavusoglu Ph.D. (Committee Member) Subjects: Systems Science

PHD, Kent State University, 2016, College of Arts and Sciences / Department of Computer Science

Graph models can represent a variety of data types such as social media, cyber business and security, web, urban networks, and more. They are extensively studied and widely used in data management, mining, and analysis in many important application areas. On the other hand, graph visualization has been a major topic in information visualization to manifest graph structure and features for effective and intuitive data exploration. In this thesis, we present a set of visual analytics solutions for several important applications by integrating graph models with visualization tools, including the visualization systems of urban trajectory data, text stream data, and categorical data. Our approaches utilize graphs to abstract and manage various data, to discover hidden knowledge with graph algorithms, and to help users gain insights from graph-based visualizations and interaction. Our research widens the horizon and enhances the capability of visual analytics methodologies. First, we propose a new visual analytics method, TrajGraph, for studying urban mobility patterns. In particular, a graph model represents taxi trajectories traveling over road networks. Then graph computation is applied to identify graph centralities that find the time varying hubs and backbones of road networks from massive taxi trajectories. The graph is further visualized and interacted for users to explore the important roles of city streets and regions. Second, we employed a parallel-graph model to enhance visual analytics of the large-scale urban trajectory datasets. Specifically, we designed a novel, scalable parallel-graph model for trajectory data management. It supports fast computation over various information queries in distributed environments. A new visualization tool that allows users to get statistics information, and relationship of cars and roads in the big trajectory data by employing the functionalities of the parallel-graph model. Third, we develop a dynamic visualizati (open full item for complete abstract)

Committee: Ye Zhao (Advisor); Ruoming Jin (Committee Member); Chengchang Lu (Committee Member); Xinyue Ye (Committee Member); Donald White (Committee Member) Subjects: Computer Science

Doctor of Philosophy, The Ohio State University, 2015, Computer Science and Engineering

Today's networks are massive and dynamic; Facebook with a billion of users and a trillion of connections and Twitter with ~600 millions of users tweeting ~9,000 times in a second are just a few examples. Making sense of these graphs in static and dynamic scenarios is essential. Most of the existing algorithms assume that the graph is static and it does not change. Today, these assumptions are no more valid. Fast algorithms for streaming and parallel scenarios are necessary to process graphs of massive sizes. Compression techniques are also quite necessary to deal with the size. In our work, we provide compression, streaming, and parallel algorithms for three important graph analytics problems: centrality computation, dense subgraph discovery and community detection. In addition, we introduce new dense subgraph discovery algorithms to better model the cohesion in real-world networks.

Committee: Umit V. Catalyurek (Advisor); Arnab Nandi (Committee Member); Srinivasan Parthasarathy (Committee Member) Subjects: Computer Science

Doctor of Philosophy, The Ohio State University, 2012, Computer Science and Engineering

Scalar functions are virtually ubiquitous in scientific research. A vast amount of research has been conducted in visualization and exploration of low-dimensional data during the last few decades, but adapting these techniques to high-dimensional, topologically-complex data remains challenging. Traditional metric-preserving dimensionality reduction techniques suffer when the intrinsic dimension of data is high, as the metric cannot generally survive projection into low dimensions. The metric distortion can be arbitrarily large, and preservation of topological structure is not guaranteed, resulting in a misleading view of the data. When preservation of geometry is not possible, topological analysis provides a promising alternative. As an example, simplicial homology characterizes the structure of a topological space (i.e. a simplicial complex) via its intrinsic topological features of various dimensions. Unfortunately, this information can be abstract and difficult to comprehend. The ranks of these homology groups (the Betti numbers) offer a simpler, albeit coarse, interpretation as the number of voids of each dimension. In high dimensions, these approaches suffer from exponential time complexity, which can render them impractical for use with real data. In light of these difficulties, we turn to an alternative type of topological characterization. We investigate the Reeb graph as a visualization and analysis tool for such complex data. The Reeb graph captures the topology of the set of level sets of a scalar function, providing a simple, intuitive, and informative topological representation. We present the first sub-quadratic expected time algorithm for computing the Reeb graph of an arbitrary simplicial complex, opening up the possibility of using the Reeb graph as a tool for understanding high-dimensional data. While the Reeb graph effectively captures some topological structure, it is still somewhat terse. The Morse-Smale complex summarizes a scalar function by b (open full item for complete abstract)

Committee: Yusu Wang PhD (Advisor); Tamal Dey PhD (Committee Member); Rephael Wenger PhD (Committee Member) Subjects: Bioinformatics; Computer Science