Master of Science, The Ohio State University, 2020, Computer Science and Engineering

As the number of data sources and dynamic datasets grows so does the need for efficient online algorithms to process them. Clustering is a very important data exploration tool used in various fields from data science to machine learning. Clustering finds structure unsupervised among indecipherable collections of data. Online clustering is the process of grouping samples in a data stream into meaningful collections as they appear over time. As more data is collected in these streams online clustering becomes more important than ever. Unfortunately, the number of available efficient online clustering algorithms is limited due to the difficulty of their design that often requires significant trade-offs in clustering performance for efficiency. Those that do exist require expert domain knowledge of the data space to set hyperparameters for the algorithm such as the desired number of clusters. This domain knowledge is often unavailable, so resources must be spent tuning hyperparameters to get acceptable performance. In this thesis we present an online modification to FINCH, the recent state-of-the-art parameter-free clustering algorithm by Sarfraz et al. called Stream FINCH (S-FINCH). We examine the stages of the FINCH algorithm and leverage key insights to produce an algorithm which reduces the online update complexity of FINCH. We then compare the performance of S-FINCH and FINCH over several toy and real-world datasets. We show theoretically and empirically that our S-FINCH algorithm is more efficient than the FINCH algorithm in the online domain and has reasonable real-time update performance. We also present several alternative cluster representatives which can be used to build different agglomerative cluster hierarchies using the S-FINCH algorithm. We compare the cluster quality and clustering time performance of these new representatives with the original FINCH algorithm. The S-FINCH algorithm presented in this thesis allows for fast and efficient online (open full item for complete abstract)

Committee: James Davis PhD. (Advisor); Juan Vasquez PhD. (Committee Member); Kyle Tarplee PhD. (Committee Member); Wei-Lun Chao PhD. (Committee Member) Subjects: Computer Science; Information Science; Information Technology

Doctor of Philosophy, The Ohio State University, 2021, Physics

The discovery of ultra-high energy (UHE) neutrinos provides a promising tool to probe the highly energetic hadronic accelerators at the far reaches of our universe with little deflection or interaction in their travels through the cosmos. However, detecting these neutrinos is rare and requires expansive detectors and medium, optimized hardware, and extensive analysis. This thesis explores potential applications for evolutionary algorithms to improve the experimental design and analysis of UHE neutrino experiments. The first project describes the use of genetic algorithms for designing antennas with better sensitivities to ultra-high energy neutrino-induced radio pulses than current designs. This thesis describes the history and work of the Genetically Evolving NEuTrIno TeleScopes (GENETIS) project. First, initial projects and exploratory GAs are described. Second, a discussion is given on the evolution of increasingly complex antenna designs optimized to improve the detection of UHE neutrinos. Finally, a project to optimize antenna response patterns are evolved for a given array geometry is presented. The second project described is an investigation using genetic programming to distinguish signals from instrumental or environmental noise triggers. Using Karoo GP, a genetic programming software suite, we present a study using genetic programming to classify signal and background in ARA data. In addition to variable exploration and feature extraction, coherently summed waveforms (CSWs) are also analyzed. Evolutionary algorithms are powerful techniques that are underutilized in astrophysics. With the potential to improve experimental design and analysis techniques, these algorithms could help lead the search in UHE neutrino detection and the field of multi-messenger astronomy.

Committee: Amy Connolly (Advisor); Chistopher Hirata (Committee Member); Richard Furnstahl (Committee Member); Antonio Boveia (Committee Member) Subjects: Astrophysics; Physics

Master of Computing and Information Systems, Youngstown State University, 2018, Department of Computer Science and Information Systems

The research presented is focused on the development of algorithms targeted towards analyzing data in the form of categorical time series or sequences. The wide availability of mobile devices and sensors connected to the Internet, makes it easier to collect datasets to model long-term user behavior. Nevertheless, performing fundamental analytical operations, such as clustering for grouping these data based on similarity patterns, has proved challenging due to the categorical nature of the data, the multiple variables to consider and their corruption by missing values. The classical metric type similarity distances have to be replaced with "edit" type distances, such as Optimal Matching. We developed this approach with the aim of studying the effect of similarity measure choice on clustering and dimensionality reduction methods applied to long-term life cycle trajectories. The discovered patterns can help providing better decision making and public policy design.

Committee: Alina Lazar PhD (Advisor); Bonita Sharif PhD (Committee Member); John Sullins PhD (Committee Member) Subjects: Computer Science; Information Systems; Information Technology

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

Geometric routing is navigating the message on the basis of node coordinates. In ad hoc wireless networks, geometric routing allows stateless message navigation with minimum routing tables and constant message size. Concurrent geometric routing improves message delivery latency and reliability at the expense of greater message cost. In this dissertation, we study concurrent geometric routing solutions to geocasting, multicasting and multisource broadcast. For each solution, we present theoretical performance bounds as well as performance comparison through abstract and concrete simulation.

Committee: Mikhail Nesterenko (Advisor); Gokarna Sharma (Committee Member); Hassan Peyravi (Committee Member); Volodymyr Andriyevskyy (Committee Member); Andrew Tonge (Committee Member) Subjects: Computer Science

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

Delaunay refinement is a useful tool for sampling and meshing. Pioneered by Ruppert and Chew for piecewise-linear complexes in R^2, Delaunay refinement has been extended to myriad classes of shapes including smooth 1- and 2-manifolds, volumes bounded by smooth 2-manifolds, and piecewise-smooth complexes. Delaunay refinement algorithms often carry certain guarantees regarding the geometric and topological closeness of output to input, as well as guarantees of the quality of mesh elements, making meshes generated via Delaunay refinement a natural choice for simulation and rendering. A major shortcoming of Delaunay refinement is its scalability: as the size of the mesh grows, the data structures necessary to carry out Delaunay refinement efficiently (such as the Delaunay triangulation and its dual, the Voronoi diagram) also grow, and this incurs memory thrashing when generating dense meshes. In this dissertation, we improve Delaunay refinement in two main capacities: (1) we improve the memory scalability of Delaunay refinement to allow for the generation of truly huge meshes, and (2) we improve the time scalability of Delaunay refinement by developing a novel parallel algorithm. To address the issue of memory scalability, we developed a localized refinement method embodying a divide-and-conquer paradigm for meshing smooth surfaces. The algorithm divides the sampling of the input domain via octree and meshes one node of the octree at a time, thus reducing memory requirements. Our theoretical results show that the algorithm terminates, and that the output is not only consistent, but also is geometrically close to the input and is a subcomplex of the Delaunay triangulation of the sampling restricted to the input surface. Our initial work nicely addresses the aforementioned shortcoming of Delaunay refinement, but only for smooth 2-manifolds. In later work, we extended this technique to another important input class: volumes bounded by smooth 2-manifolds. It is not im (open full item for complete abstract)

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

MS, University of Cincinnati, 2001, Engineering : Computer Science and Engineering

Knowledge discovery from large datasets to extract meaningful and predictive information has gained immense importance. The approaches for analyzing large datasets should assist in interpreting the complex relationships between the data samples, in addition to providing an experimental platform where new experiments can be performed and suggested. A parameter driven, deterministic, unsupervised, agglomerative clustering approach based on the notion of context dependent divergence between multi-attribute data samples is described in this work. An explicit way of cluster structure is proposed along with criteria that measure cluster properties and guide cluster expansion. A user adjustable fuzzy inference mechanism controls cluster expansion and makes the approach suitable for experimentation by changing a few parameters. To support the results obtained by such an unsupervised approach, a general validation method based on necessary and possible support is described. The results on real data sets and their validation lend a strong support to this work.

Committee: DR. ANCA RALESCU (Advisor) Subjects: Computer Science

MS, University of Cincinnati, 2001, Engineering : Computer Science

The goal of this thesis is to make good science easier to do by promoting and facilitating the comparison of algorithms. Algorithms for solving difficult problems, and in particular heuristic algorithms for intractable problems, often do not lend themselves to standard methods of theoretical analysis: thus a researcher must make an empirical, statistical argument for or against an algorithm's quality. This thesis discusses the design and evaluation of experiments in this sometimes slippery area of study. We contend that a contribution to science requires more than the reporting of an algorithm's optimal results: researchers should choose sample sizes rationally; they should then report, at minimum, both the distribution of results overall and the distribution of a set of optimal values, which may involve further sampling to reach desired goals; they should account for sampling itself by including confidence intervals for their claims; and if they compare results of different algorithms, then their comparisons should be statistically sound and rigorous. We offer an experimental procedure with guidelines for each of these steps, and within the procedure, we offer a new method for sampling and comparing sets of optimal values, which we call k% optima. We also present a demonstration experiment in which we apply our procedure to report and compare the performance of three heuristic algorithms for VLSI circuit partitioning.

Committee: Dr. Carla Purdy (Advisor) Subjects:

Doctor of Philosophy, The Ohio State University, 2008, Computer and Information Science

This dissertation addresses several performance optimization issues in the context of the Tensor Contraction Engine (TCE), a domain-specific compiler to synthesize parallel, out-of-core programs for a class of scientific computations encountered in computational chemistry and physics. The domain of our focus is electronic structure calculations, where many computationally intensive components are expressible as a set of tensor contractions. These scientific applications are extremely compute-intensive and consume significant computer resources at national supercomputer centers. The manual development of high-performance parallel programs for them is usually very tedious and time consuming. The TCE system is targeted at reducing the burden on application scientists, by having them specify computations in a high-level form, from which efficient parallel programs are automatically synthesized. The goal of this research is to develop an optimization framework to derive high-performance implementations for a set of given tensor contractions. In particular, the issues investigated include: 1) Development of an efficient in-memory parallel algorithm for a tensor contraction. 2) Design of a performance-model driven framework for a parallel out-of-core tensor contraction. 3) Design of an integrated optimization framework, which incorporating multiple high-level program transformation techniques to improve locality and parallelism for a set of tensor contractions. This subject includes the following three topics: 3.1) Modeling interactions between different transformations and assess their impact on the overall performance, 3.2) Using a search-based strategy to explore the combined space of transformations, and provide efficient pruning methods to reduce the search space, 3.3) Using performance-driven models to identify the best combination and generate high-performance code. 4) Incorporation of domain-specific optimizations, such as sparse and symmetry. We have implemented a (open full item for complete abstract)

Committee: Ponnuswamy Sadayappan (Advisor) Subjects: Computer Science

Master of Science (MS), Ohio University, 1989, Electrical Engineering & Computer Science (Engineering and Technology)

Two methods for filtering aircraft positions and predicting the range and bearing between aircraft for the Collision Warning System (CWS), which utilizes the present Air Traffic Control Radar Beacon System (ATCRBS), are developed. The extended Kalman filters required for the tracking algorithms are developed and implemented, and simulation results are presented. The first method assumes that the CWS equipped aircraft (Own) position is a known quantity by utilizing an area navigational aid. In such a case, the threatening aircraft (Target) position and velocity become state-variables of the extended Kalman filter used for prediction and tracking. The second method requires both the Own and Target aircraft to be estimated by the extended Kalman filter since Own position is not available. The filters are expected to obtain relative range accuracies of at least 0.5 nautical miles and bearing accuracies of at least 3.0 degrees for suitable Own/Target/Radar geometries.

Committee: Frank van Graas (Advisor) Subjects:

Doctor of Philosophy (PhD), Ohio University, 2000, Electrical Engineering & Computer Science (Engineering and Technology)

Existing deadlock prevention and avoidance methods for flexible manufacturing systems have either restricted the class of systems they apply to, or are conservative so that the approach has polynomial complexity. The problem with these restrictions is that the system is not allowed to enter many safe states that contribute to high resource utilization. This work has developed two deadlock avoidance algorithms for flexible manufacturing systems that allow both single capacity and multiple capacity resources. The model further allows choices in part routing; that is, there can be several resources to choose from to visit next at any step of a process plan. Process plans need not be sequential and fixed, but must be finite. Two types of choices have been considered: free choice, where the system controller can pick one of several possibilities; and conditional choice, where factors external to the system influence the choice. An example of conditional choice is routing based on the results of an inspection. The first algorithm developed allows free choices only. The second allows both types of choices. The main strategy of both algorithms is to analyze a potential part movement to determine whether such a move is safe, unsafe, or undetermined. This classification is linear in complexity. A part movement that is classified as undetermined is further analyzed using another procedure, which attempts to empty the system (virtually) to decide whether or not the original move is safe. In this case, the complexity involved in determining the final classification of the proposed part move increases to the cube of the system size L, that is,O( L 3). The methods are proved to be correct, that is, they will not allow a live system to enter a deadlock state. The first method is compared to other popular deadlock detection and avoidance algorithms in the literature. The proposed method is less conservative than the existing algorithms. In addition, the system does not require any p (open full item for complete abstract)

Committee: Robert Judd (Advisor) Subjects:

Master of Science (MS), Ohio University, 2004, Industrial and Manufacturing Systems Engineering (Engineering)

Scheduling problems arise in diverse areas such as flexible manufacturing systems, logistics, and network systems and so on. A job shop scheduling problem (JSP) is among the toughest scheduling problems due to the huge number of possible solutions for every problem. There is no efficient conventional optimization algorithm that can guarantee an optimal solution in polynomial time. Due to this inherent intractability, heuristic procedures such as genetic algorithms offer an attractive way of solving these problems. Even with genetic algorithms, larger job shop problems lead to highly time consuming computations due to the vast solution space. This research tries to use the principles of distributed computing to improve solution time in case of such large problems. This document proposes software developed in Java programming language to solve job shop scheduling problems using genetic algorithms by simultaneously utilizing the processing capabilities of several networked computers. The software is based on the client-server model, where the server distributes the computationally intensive task of crossover, mutation and makespan calculation for chromosomes to remote clients. Testing has been done to determine whether this approach is useful in reducing computation time in case of different sizes of job shop scheduling problems and different types of hardware configuration. Results of the testing are discussed at the end of the document.

Committee: David Koonce (Advisor) Subjects: Engineering, Industrial

Master of Science, The Ohio State University, 1971, Graduate School

Committee: Not Provided (Other) Subjects:

Master of Science, The Ohio State University, 1969, Graduate School

Committee: Not Provided (Other) Subjects:

Master of Science, The Ohio State University, 1964, Graduate School

Committee: Not Provided (Other) Subjects:

Master of Science, The Ohio State University, 1966, Graduate School

Committee: Not Provided (Other) Subjects:

Master of Science, The Ohio State University, 1971, Graduate School

Committee: Not Provided (Other) Subjects:

Master of Science, The Ohio State University, 1971, Graduate School

Committee: Not Provided (Other) Subjects:

Master of Science, The Ohio State University, 1970, Graduate School

Committee: Not Provided (Other) Subjects:

Master of Science, The Ohio State University, 1970, Graduate School

Committee: Not Provided (Other) Subjects:

Master of Science, The Ohio State University, 2005, Graduate School

Committee: Not Provided (Other) Subjects: