Search results

Title: Face search and clustering at scale
Creator: Otto, Charles
Date: 2016
Collection: Electronic Theses & Dissertations
Description: There has been a great deal of progress on the problem of unconstrained face recognition in recent years, particularly with the emergence of deep learning methods for generating face representations. Developing robust face representations is not only of great practical interest for classic biometric problems like face verification, but also for emerging large scale face search problems. In both social media, and law-enforcement applications, an extremely large volume of face data is becoming...
Show moreThere has been a great deal of progress on the problem of unconstrained face recognition in recent years, particularly with the emergence of deep learning methods for generating face representations. Developing robust face representations is not only of great practical interest for classic biometric problems like face verification, but also for emerging large scale face search problems. In both social media, and law-enforcement applications, an extremely large volume of face data is becoming commonplace. One emerging problem related to this high volume of data is to devise methods to search for persons of interest among the billions of shared photos on these websites. Another challenge is to group or cluster large collections of unlabeled face images by identity, for example as a prelude to manual examination of a collection of images in law-enforcement applications.Regarding the face search problem, we propose a face search system which combines a fast search procedure, coupled with a state-of-the-art commercial off the shelf (COTS) matcher, in a cascaded framework. Given a probe face, we first filter the large gallery of photos to find the top-k most similar faces using features learned by a convolutional neural network. The k retrieved candidates are re-ranked by combining similarities based on deep features and those output by the COTS matcher. We evaluate the proposed face search system on a gallery containing 80 million web-downloaded face images. Experimental results demonstrate that while the deep features perform worse than the COTS matcher on a mugshot dataset (93.7% vs. 98.6% TAR@FAR of 0.01%), fusing the deep features with the COTS matcher improves the overall performance (99.5% TAR@FAR of 0.01%). This shows that the learned deep features provide complementary information over representations used in state-of-the-art face matchers. On the unconstrained face image benchmarks, the performance of the learned deep features is competitive with reported accuracies. LFW database: 98.20% accuracy under the standard protocol and 88.03% TAR@FAR of 0.1% under the BLUFR protocol; IJB-A benchmark: 51.0% TAR@FAR of 0.1% (verification), rank 1 retrieval of 82.2% (closed-set search), 61.5% FNIR@FPIR of 1% (open-set search). The proposed face search system offers an excellent trade-off between accuracy and scalability on galleries with millions of images. Additionally, in a face search experiment involving photos of the Tsarnaev brothers, convicted of the Boston Marathon bombing, the proposed cascade face search system could find the younger brother's (Dzhokhar Tsarnaev) photo at rank 1 in 1 second on a 5M gallery and at rank 8 in 7 seconds on an 80M gallery, using a Intel Xeon processor clocked at 3.1 GHz.In terms of clustering, in social media, law enforcement, and other applications the number of unlabeled faces can be of the order of hundreds of million, while the number of identities (clusters) can range from a few thousand to millions. To address the challenges of run-time complexity and cluster quality, we present an approximate Rank-Order clustering algorithm that performs better than popular clustering algorithms (k-Means and Spectral). Our experiments include clustering up to 123 million face images into over 10 million clusters. Clustering results are analyzed in terms of external (known face labels) and internal (unknown face labels) cluster quality measures, and run-time. Our clustering algorithm achieves an F-measure of 0.87 on the LFW benchmark (13K faces of 5,749 individuals), which drops to 0.27 on the largest dataset considered (13K faces in LFW + 123M distractor images). Additionally, we show that frames in the YouTube benchmark can be clustered with an F-measure of 0.71. An internal per-cluster quality measure is developed to rank individual clusters for manual exploration of high quality clusters that are compact and isolated.Finally, we further develop our face representation, leveraging more advanced network architectures, and an order of magnitude more training data--attaining a verification rate of 92.22% at 0.1% FAR on the BLUFR verification protocol, using a single model.
Show less

Title: Fingerprint recognition : contributions to latent matching and 3D fingerprint target generation
Creator: Arora, Sunpreet Singh
Date: 2016
Collection: Electronic Theses & Dissertations
Description: Automatic fingerprint capture and comparison methods have led to the ubiquitous use of fingerprint-based person recognition in applications ranging from law enforcement and border control to national identification and smartphone unlock. However, despite tremendous advancements in the state-of-the-art, improvements are still needed in case of some challenging applications, e.g, to recognize poor quality and distorted fingerprints acquired from non-cooperative users, improve fingerprint reader...
Show moreAutomatic fingerprint capture and comparison methods have led to the ubiquitous use of fingerprint-based person recognition in applications ranging from law enforcement and border control to national identification and smartphone unlock. However, despite tremendous advancements in the state-of-the-art, improvements are still needed in case of some challenging applications, e.g, to recognize poor quality and distorted fingerprints acquired from non-cooperative users, improve fingerprint reader fidelity, and determine anti-spoofing capability of different fingerprint readers. In this thesis, we address two such impending challenges: (i) comparison of latent prints found at crime scenes to large collections of reference prints (rolled tenprints or slap fingerprints) in law enforcement databases, and (ii) operational evaluation of fingerprint recognition systems prior to large scale deployment.We develop a feedback paradigm that uses reference print features to dynamically select latent features during matching. The paradigm automatically determines if dynamic latent feature selection would improve recognition performance using a statistical hypothesis test and qualitatively decides the regions in latent and reference prints for applying feedback. The paradigm when used in conjunction with a state-of-the-art latent matcher demonstrates marked improvement (0.5-3.5%) in latent matching accuracy.Further, we develop a framework for crowdsourcing latent print feature markup to a pool of fingerprint examiners. The framework uses a statistical criterion to automatically determine when crowdsourcing is required, and a method to dynamically determine the number of examiners needed for latent feature markup. Significant recognition performance improvements (2.5-11.5%) are obtained using crowdsourced markups in conjunction with a state-of-the-art latent matcher.Finally, we design and fabricate single-finger and whole hand 3D targets for operational evaluation of optical and capacitive fingerprint readers as well as for end-to-end evaluation of fingerprint recognition systems. 2D calibration patterns with known characteristics (e.g. synthetic fingerprints with known features, sine gratings with known orientation and spacing) are projected onto electronic 3D finger and hand surfaces to create electronic 3D single-finger and whole hand targets. A high-resolution 3D printer is used to manufacture physical 3D single-finger and whole hand targets from electronic targets. Other contributions include: (i) a method to chemically clean the 3D printed targets without impacting the engraved target patterns, (ii) a procedure to apply conductive coating of metal/metal oxides on the surface of 3D targets using DC sputtering, (iii) fidelity measurement techniques using optical microscopy to assess the 3D target generation process, and (iv) methods to evaluate fingerprint readers using the fabricated 3D targets. We demonstrate that the 2D calibration pattern features are reproduced with high fidelity both on the electronic and physical 3D single-finger and whole hand targets and that the intra-class variations between images of the 3D targets do not degrade matching accuracy (at 0.01% false accept rate). We evaluate several commercially available single-finger and slap contact-based and contactless optical readers as well as capacitive readers using the generated 3D targets.
Show less

Title: Collaboration based spectrum sharing algorithms in cognitive radio networks
Creator: Hyder, Chowdhury Sayeed
Date: 2017
Collection: Electronic Theses & Dissertations
Description: Radio spectrum assignment to wireless providers using traditional fixed allocation policy will no longer be a viable technique to meet the growing spectrum demand of emerging wireless applications. This is because while the available pool of unassigned radio spectrum is low, the spectrum already assigned to existing applications is also often underutilized in time, frequency, and location. With features like transmission flexibility and adaptability cognitive radio (CR) provides auseful means...
Show moreRadio spectrum assignment to wireless providers using traditional fixed allocation policy will no longer be a viable technique to meet the growing spectrum demand of emerging wireless applications. This is because while the available pool of unassigned radio spectrum is low, the spectrum already assigned to existing applications is also often underutilized in time, frequency, and location. With features like transmission flexibility and adaptability cognitive radio (CR) provides auseful means of spectrum sharing among growing users as an alternative to the current fixed policy. The cognitive radio network (CRN), based on the functionality of CR, consists of two types of users — primary users (PU) and secondary users (SU). Primary users are licensed users who have exclusive access rights of a fixed spectrum range. Secondary users are unlicensed users who opportunistically exploit the spectrum holes or negotiate with primary users to earn transmissionaccess rights.The CRN based efficient spectrum sharing algorithms work on different forms of collaboration between the PUs and the SUs (inter-user collaboration) and among the SUs themselves (intra-user collaboration). In the sensing based collaboration model, the SUs sense licensed spectrum and collaboratively decide about its availability based on the sensing results without any involvements from the PUs. In the relay based collaboration model, the SUs coordinate with the PUs directly,relay primary packets in exchange for transmission opportunities, and thus build a win-win cooperative framework to attainmutual benefits. In the auction based collaborationmodel, the SUs bid for temporary or permanent usage rights of unused licensed spectrum bands that are put into auction for sale by the PUs. Each of these collaboration models faces different sets of challenges towardsachieving high spectrum utilization. In this dissertation, we address some of these challenges and present a set of efficient spectrum sharing algorithms based on these collaboration models.The first work in this dissertation addresses the spectrum sensing data falsification (SSDF) attack in IEEE 802.22 wireless regional area network (WRAN) under the sensing based collaboration model. We discuss different strategies of manipulating sensing reports by one or more malicious users and how these manipulation strategies may affect the spectrum utilization. To defend against such malicious attacks, we present an adaptive reputation based clustering algorithm. The algorithm combines the clustering technique with feedback based reputation adjustment to prevent independent and collaborative SSDF attacks and quarantines the attackers from the decision making process.Our next set of work in this dissertation falls under the relay based collaboration model. We investigate the feasibility of this collaboration model in the case of real-time applications. We quantify the impact of packet deadlines and cooperation overhead on the system performance. We discuss the impact of interference that may cause from secondary transmissions. Based on the analysis, we develop an interference aware reliable cooperative framework which improves the packet reception rate of both users with low overhead. We extend our investigation of this relay based collaboration model from single hop to multiple hops in the form of cooperative routing. We formulate the routing problem as an overlapping coalition formation game where each coalition represents a routing path between primary source and destination consisting of multiple SUs as intermediate relays. The proposed model allows SUs to participate in more than one coalitions and creates more transmission opportunities for them while achieving stable routing paths for PUs.Our final set of work in this dissertation deals with the challenges in the auction based collaboration model. We consider an online setting of spectrum auctions where participation and valuation of both bidders and sellers are stochastic. We analyze the behavior of bidders and sellers in such settings and develop truthful auction mechanisms with respect to bid and time, improving spectrum reuse, auction efficiency, and revenue. The findings from our research will help to understand the underlying challenges in future networks, build a better spectrum ecosystem, and encourage new spectrum sharing models in wireless broadband communications.
Show less

Title: Harnessing evolutionary computation for the design and generation of adaptive embedded controllers within the context of uncertainty
Creator: Byers, Chad Michael
Date: 2015
Collection: Electronic Theses & Dissertations
Description: A critical challenge for the design of embedded controllers is incorporating desirable qualities such as robustness, fault tolerance, and adaptability into the control process in order to respond to dynamic environmental conditions. An embedded controller governs the execution of a task-specific system by monitoring information from its environment via sensors and producing an appropriate response through the system's actuators, often independent of any supervisory control. For a human...
Show moreA critical challenge for the design of embedded controllers is incorporating desirable qualities such as robustness, fault tolerance, and adaptability into the control process in order to respond to dynamic environmental conditions. An embedded controller governs the execution of a task-specific system by monitoring information from its environment via sensors and producing an appropriate response through the system's actuators, often independent of any supervisory control. For a human developer, identifying the set of all possible combinations of conditions a system might experience and designing a solution to accommodate this set is burdensome, costly, and often, infeasible. To alleviate this burden, a variety of techniques have been explored to automate the generation of embedded controller solutions. In this dissertation, we focus on the bio-inspired technique referred to as evolutionary computation where we harness evolution's power as a population-based, global search technique to build up good behavioral components. In this way, evolution naturally selects for these desirable qualities in order for a solution to remain competitive over time in the population. Often, these search techniques operate in the context of uncertainty where aspects of the (1) problem domain, (2) solution space, and (3) search process itself are subject to variation and change. To mitigate issues associated with uncertainty in the problem domain, we propose the digital enzyme, a biologically-inspired model that maps the complexity of both the environment and the system into the space of values rather than instructions. To address uncertainty in the solution space, we remove constraints in our initial digital enzyme model to allow the genome structure to be dynamic and open-ended, accommodating a wider range of evolved solution designs. Finally, to help explore the inherent uncertainty that exists in the search process, we uncover a hidden feature interaction present between the diversity-preserving search operator of a popular evolutionary algorithm and propose a new way to use niching as a means to mitigate its unwanted effects and bias on search.
Show less

Title: Kernel-based clustering of big data
Creator: Chitta, Radha
Date: 2015
Collection: Electronic Theses & Dissertations
Description: There has been a rapid increase in the volume of digital data over the recent years. A study by IDC and EMC Corporation predicted the creation of 44 zettabytes (10^21 bytes) of digital data by the year 2020. Analysis of this massive amounts of data, popularly known as big data, necessitates highly scalable data analysis techniques. Clustering is an exploratory data analysis tool used to discover the underlying groups in the data. The state-of-the-art algorithms for clustering big data sets...
Show moreThere has been a rapid increase in the volume of digital data over the recent years. A study by IDC and EMC Corporation predicted the creation of 44 zettabytes (10^21 bytes) of digital data by the year 2020. Analysis of this massive amounts of data, popularly known as big data, necessitates highly scalable data analysis techniques. Clustering is an exploratory data analysis tool used to discover the underlying groups in the data. The state-of-the-art algorithms for clustering big data sets are linear clustering algorithms, which assume that the data is linearly separable in the input space, and use measures such as the Euclidean distance to define the inter-point similarities. Though efficient, linear clustering algorithms do not achieve high cluster quality on real-world data sets, which are not linearly separable. Kernel-based clustering algorithms employ non-linear similarity measures to define the inter-point similarities. As a result, they are able to identify clusters of arbitrary shapes and densities. However, kernel-based clustering techniques suffer from two major limitations: (i) Their running time and memory complexity increase quadratically with the increase in the size of the data set. They cannot scale up to data sets containing billions of data points. (ii) The performance of the kernel-based clustering algorithms is highly sensitive to the choice of the kernel similarity function. Ad hoc approaches, relying on prior domain knowledge, are currently employed to choose the kernel function, and it is difficult to determine the appropriate kernel similarity function for the given data set.In this thesis, we develop scalable approximate kernel-based clustering algorithms using random sampling and matrix approximation techniques. They can cluster big data sets containing billions of high-dimensional points not only as efficiently as linear clustering algorithms but also as accurately as classical kernel-based clustering algorithms.Our first contribution is based on the premise that the similarity matrices corresponding to big data sets can usually be well-approximated by low-rank matrices built from a subset of the data. We develop an approximate kernel-based clustering algorithm, which uses a low-rank approximate kernel matrix, constructed from a uniformly sampled small subset of the data, to perform clustering. We show that the proposed algorithm has linear running time complexity and low memory requirements, and also achieves high cluster quality, when provided with sufficient number of data samples. We also demonstrate that the proposed algorithm can be easily parallelized to handle distributed data sets. We then employ non-linear random feature maps to approximate the kernel similarity function, and design clustering algorithms which enhance the efficiency of kernel-based clustering, as well as label assignment for previously unseen data points. Our next contribution is an online kernel-based clustering algorithm that can cluster potentially unbounded stream data in real-time. It intelligently samples the data stream and finds the cluster labels using these sampled points. The proposed scheme is more effective than the current kernel-based and linear stream clustering techniques, both in terms of efficiency and cluster quality. We finally address the issues of high dimensionality and scalability to data sets containing a large number of clusters. Under the assumption that the kernel matrix is sparse when the number of clusters is large, we modify the above online kernel-based clustering scheme to perform clustering in a low-dimensional space spanned by the top eigenvectors of the sparse kernel matrix. The combination of sampling and sparsity further reduces the running time and memory complexity. The proposed clustering algorithms can be applied in a number of real-world applications. We demonstrate the efficacy of our algorithms using several large benchmark text and image data sets. For instance, the proposed batch kernel clustering algorithms were used to cluster large image data sets (e.g. Tiny) containing up to 80 million images. The proposed stream kernel clustering algorithm was used to cluster over a billion tweets from Twitter, for hashtag recommendation.
Show less

Title: Divide and Conquer : packet Classification by Smart Division
Creator: Daly, James Edward
Date: 2017
Collection: Electronic Theses & Dissertations
Description: Packet classifiers form the backbone of many networking and security devices. Most packet classifiers are defined by a list of rules that each match a subset of all packets. As new threats and vulnerabilities emerge, these rule lists are getting larger and thus taking longer to search. However, networks have very strict time constraints and delays classifying a packet at one stage can cascade and cause delays and congestion throughout the network. Additionally, with the advent of software...
Show morePacket classifiers form the backbone of many networking and security devices. Most packet classifiers are defined by a list of rules that each match a subset of all packets. As new threats and vulnerabilities emerge, these rule lists are getting larger and thus taking longer to search. However, networks have very strict time constraints and delays classifying a packet at one stage can cascade and cause delays and congestion throughout the network. Additionally, with the advent of software-defined networks, these rule lists are also constantly changing. Packet classifiers thus must support both fast classification time and fast updates.We present four methods to improve packet classification. Each method uses smart division to divide the problem into simpler subproblems that are more easily solved. Diplomat uses dimensional reduction to create a smaller rule list by dividing the problem into several lower dimensional problems and then combines them with as few rules as possible. ByteCuts uses rule list separation to partition the rule list into a small number of trees; this minimizes the rule replication that other tree-based methods such as HyperCuts and HyperSplit require. PartitionSort uses rule list separation to partition the rule list into parts that are sortable; each part can then be binary searched. Finally, TupleMerge uses rule list separation to partition the rule list into parts that are hashable; it requires fewer hash tables than Tuple Space Search which reduces search times.
Show less

Title: Novel Learning Algorithms for Mining Geospatial Data
Creator: Yuan, Shuai
Date: 2017
Collection: Electronic Theses & Dissertations
Description: Geospatial data have a wide range of applicability in many disciplines, including environmental science, urban planning, healthcare, and public administration. The proliferation of such data in recent years have presented opportunities to develop novel data mining algorithms for modeling and extracting useful patterns from the data. However, there are many practical issues remain that must be addressed before the algorithms can be successfully applied to real-world problems. First, the...
Show moreGeospatial data have a wide range of applicability in many disciplines, including environmental science, urban planning, healthcare, and public administration. The proliferation of such data in recent years have presented opportunities to develop novel data mining algorithms for modeling and extracting useful patterns from the data. However, there are many practical issues remain that must be addressed before the algorithms can be successfully applied to real-world problems. First, the algorithms must be able to incorporate spatial relationships and other domain constraints defined by the problem. Second, the algorithms must be able to handle missing values, which are common in many geospatial data sets. In particular, the models constructed by the algorithms may need to be extrapolated to locations with no observation data. Another challenge is to adequately capture the nonlinear relationship between the predictor and response variables of the geospatial data. Accurate modeling of such relationship is not only a challenge, it is also computationally expensive. Finally, the variables may interact at different spatial scales, making it necessary to develop models that can handle multi-scale relationships present in the geospatial data. This thesis presents the novel algorithms I have developed to overcome the practical challenges of applying data mining to geospatial datasets. Specifically, the algorithms will be applied to both supervised and unsupervised learning problems such as cluster analysis and spatial prediction. While the algorithms are mostly evaluated on datasets from the ecology domain, they are generally applicable to other geospatial datasets with similar characteristics. First, a spatially constrained spectral clustering algorithm is developed for geospatial data. The algorithm provides a flexible way to incorporate spatial constraints into the spectral clustering formulation in order to create regions that are spatially contiguous and homogeneous. It can also be extended to a hierarchical clustering setting, enabling the creation of fine-scale regions that are nested wholly within broader-scale regions. Experimental results suggest that the nested regions created using the proposed approach are more balanced in terms of their sizes compared to the regions found using traditional hierarchical clustering methods. Second, a supervised hash-based feature learning algorithm is proposed for modeling nonlinear relationships in incomplete geospatial data. The proposed algorithm can simultaneously infer missing values while learning a small set of discriminative, nonlinear features of the geospatial data. The efficacy of the algorithm is demonstrated using synthetic and real-world datasets. Empirical results show that the algorithm is more effective than the standard approach of imputing the missing values before applying nonlinear feature learning in more than 75% of the datasets evaluated in the study. Third, a multi-task learning framework is developed for modeling multiple response variables in geospatial data. Instead of training the local models independently for each response variable at each location, the framework simultaneously fits the local models for all response variables by optimizing a joint objective function with trace-norm regularization. The framework also leverages the spatial autocorrelation between locations as well as the inherent correlation between response variables to improve prediction accuracy. Finally, a multi-level, multi-task learning framework is proposed to effectively train predictive models from nested geospatial data containing predictor variables measured at multiple spatial scales. The framework enables distinct models to be developed for each coarse- scale region using both its fine-level and coarse-level features. It also allows information to be shared among the models through a common set of latent features. Empirical results show that such information sharing helps to create more robust models especially for regions with limited or no training data. Another advantage of using the multi-level, multi-task learning framework is that it can automatically identify potential cross-scale interactions between the regional and local variables.
Show less

Title: Improving Indoor Positioning Via Mobile Sensing
Creator: Qiu, Chen
Date: 2017
Collection: Electronic Theses & Dissertations
Description: Accurate indoor position and movement information of devices enables numerous opportunities for location based services. Services such as guiding users through buildings, highlighting nearby services within shopping malls, or tracking the number of steps taken are some of the opportunities available when accurate positioning information is computed by devices. GPS provides accurate localization results in an outdoor environment, such as navigation information for vehicles. Unfortunately, GPS...
Show moreAccurate indoor position and movement information of devices enables numerous opportunities for location based services. Services such as guiding users through buildings, highlighting nearby services within shopping malls, or tracking the number of steps taken are some of the opportunities available when accurate positioning information is computed by devices. GPS provides accurate localization results in an outdoor environment, such as navigation information for vehicles. Unfortunately, GPS cannot be applied indoors pervasively due to the various interferences.Indoor localization has been a challenging and significant topic in recent decades. Although extensive research has been dedicated to this field, accurate indoor location information remains a challenge without the incorporation of expensive devices or sophisticated infrastructures within buildings. We explored one practical approach for indoor map construction and four representative resolutions for indoor positioning.Considering most indoor localization approaches are based upon indoor maps, we develop techniques to construct indoor maps. Since indoor maps might be dynamic and updated regularly, we present iFrame, a dynamic approach that uses mobile sensing techniques for constructing 2-dimensional indoor maps. We abstract the unknown map as a matrix and use mobile devices that incorporate three mobile sensing technologies - accelerometers to support dead reckoning, Bluetooth RSSI detection, and WiFi RSSI detection. The layouts of rooms and hallways can be constructed automatically within 5-10 minutes.Based on the indoor map, we propose four indoor localization approaches by leveraging mobile sensing techniques. First, although GPS can not help indoor localization directly, we propose iLoom, which adopts a user's motion behaviors built by GPS information to enhance indoor localization. iLoom leverages an Acceleration Range Box to improve a user's acceleration value used for computing dead reckoning. By transfer learning the information from users' motion behaviors to the Acceleration Range Box, iLoom improves the Acceleration Range Box to achieve more accurate indoor positioning results. Second, we introduce CRISP - a prototype that leverages opportunities of the interaction of multiple smartphones to enhance indoor positioning. When mobile devices cooperate and share position information iteratively, the localization accuracies of mobile devices increases gradually. In addition, based upon the obtained location information, CRISP provide a pedometer that can avoid the accumulative errors caused by accelerometers. Third, we present SilentWhistle, a mobile prototype that incorporates acoustic information and motion traces on smartphones to locate users. When users encounter each other or related beacons, by measuring the relation between sound strength and distance, the initial location information obtained by dead reckoning can be enhanced by triangulations transferred from sound strength. Centralized and distributed models of SilentWhistle can avoid the incorrect location messages spreading based on the fault tolerance property. Finally, by employing mobile robots in indoor scenarios, we propose AirLoc to improve the indoor positioning accuracies on smartphones. When a robot is near a smartphone, the robot sends accurate location information to users' smartphones via Bluetooth. In AirLoc, we design dynamic programming algorithms to generate the optimal serving routes for a single robot. Then, we extend the single robot model to multi-robot model. In our simulation, the multi-robots are organized by an unbalanced tree and serve areas by the Distance/Density First Algorithm.
Show less

Title: Scalable Phylogenetic Analysis and Functional Interpretation of Genomes with Complex Evolutionary Histories
Creator: Hejase, Hussein El Abbass
Date: 2017
Collection: Electronic Theses & Dissertations
Description: Phylogenomics involves the inference of a genome-scale phylogeny. A phylogeny is typically inferred using sequences from multiple loci across a set of genomes of multiple organisms by reconstructing gene trees and then reconciling them into a species phylogeny. Many studies have shown that evolutionary processes such as gene flow, incomplete lineage sorting, recombination, selection, gene duplication and loss have shaped our genomes and played a major role in the evolution of a diverse array...
Show morePhylogenomics involves the inference of a genome-scale phylogeny. A phylogeny is typically inferred using sequences from multiple loci across a set of genomes of multiple organisms by reconstructing gene trees and then reconciling them into a species phylogeny. Many studies have shown that evolutionary processes such as gene flow, incomplete lineage sorting, recombination, selection, gene duplication and loss have shaped our genomes and played a major role in the evolution of a diverse array of metazoans, including humans and ancient hominins, mice, bacteria, and butterflies. The aforementioned evolutionary processes are primary causes of gene tree discordance, which introduce different loci in a genome that exhibit local genealogical variation (i.e. gene trees differing from each other and the species phylogeny in terms of topology and/or branch length).In this dissertation, we develop a method for fast and accurate inference of phylogenetic networks using large-scale sequence data. The advent of high-throughput sequencing technologies has brought about two main scalability challenges: (1) dataset size in terms of the number of taxa and (2) the evolutionary divergence of the taxa in a study. We explore the impact of both dimensions of scale on phylogenetic network inference and then introduce a new phylogenetic divide-and-conquer method which we call FastNet. We show using synthetic and empirical data spanning a range of evolutionary scenarios that FastNet outperforms the state-of-the-art in terms of accuracy and computational requirements.Furthermore, we develop methods that use better and more accurate phylogenies to functionally interpret genomes. One way to study and understand the biological function of genomes is through association mapping, which pinpoints statistical associations between genotypic and phenotypic characters while modeling the relatedness between samples to avoid generating spurious inferences. Many methods have been proposed to perform association mapping while accounting for sample relatedness. However, the state of the art predominantly utilizes the simplifying assumption that sample relatedness is effectively fixed across the genome. Recent studies have shown that sample relatedness can vary greatly across different loci within a genome where gene trees could differ from each other and the species phylogeny. Thus, there is an imminent need for methods to account for local genealogical variation in functional genomic analyses. We address this methodological gap by introducing two methods, Coal-Map and Coal-Miner, which account for sample relatedness locally within loci and globally across the entire genome. We show through simulated and empirical datasets that these newly introduced methods offer comparable or typically better statistical power and type I error control compared to the state-of-the-art.
Show less

Title: Balancing Convergence and Diversity in Evolutionary Single, Multi and Many Objectives
Creator: Seada, Haitham
Date: 2017
Collection: Electronic Theses & Dissertations
Description: Single objective optimization targets only one solution, that is usually the global optimum.On the other hand, the goal of multiobjective optimization is to represent the wholeset of trade-off Pareto-optimal solutions to a problem. For over thirty years, researchershave been developing Evolutionary Multiobjective Optimization (EMO) algorithms forsolving multiobjective optimization problems. Unfortunately, each of these algorithmswere found to work well on a specific range of objective...
Show moreSingle objective optimization targets only one solution, that is usually the global optimum.On the other hand, the goal of multiobjective optimization is to represent the wholeset of trade-off Pareto-optimal solutions to a problem. For over thirty years, researchershave been developing Evolutionary Multiobjective Optimization (EMO) algorithms forsolving multiobjective optimization problems. Unfortunately, each of these algorithmswere found to work well on a specific range of objective dimensionality, i.e. number ofobjectives. Most researchers overlooked the idea of creating a cross-dimensional algorithmthat can adapt its operation from one level of objective dimensionality to the other.One important aspect of creating such algorithm is achieving a careful balance betweenconvergence and diversity. Researchers proposed several techniques aiming at dividingcomputational resources uniformly between these two goals. However, in many situations,only either of them is difficult to attain. Also for a new problem, it is difficult totell beforehand if it will be challenging in terms of convergence, diversity or both. In thisstudy, we propose several extensions to a state-of-the-art evolutionary many-objectiveoptimization algorithm – NSGA-III. Our extensions collectively aim at (i) creating a unifiedoptimization algorithm that dynamically adapts itself to single, multi- and manyobjectives, and (ii) enabling this algorithm to automatically focus on either convergence,diversity or both, according to the problem being considered. Our approach augmentsthe already existing algorithm with a niching-based selection operator. It also utilizes therecently proposed Karush Kuhn Tucker Proximity Measure to identify ill-converged solutions,and finally, uses several combinations of point-to-point single objective local searchprocedures to remedy these solutions and enhance both convergence and diversity. Ourextensions are shown to produce better results than state-of-the-art algorithms over a setof single, multi- and many-objective problems.
Show less

Title: Evolution of cooperation in the light of information theory
Creator: Mirmomeni, Masoud
Date: 2015
Collection: Electronic Theses & Dissertations
Description: Cooperation is ubiquitous in different biological levels and is necessary for evolution to shape the life and create new forms of organization. Genes cooperate in controlling cells; cells efficiently collaborate together to produce cohesive multi-cellular organisms; members of insect colonies and animal clans cooperate in protecting the colony and providing food. Cooperation means that members of a group bear a cost, c, for another individuals to earn a benefit, b. While cooperators of the...
Show moreCooperation is ubiquitous in different biological levels and is necessary for evolution to shape the life and create new forms of organization. Genes cooperate in controlling cells; cells efficiently collaborate together to produce cohesive multi-cellular organisms; members of insect colonies and animal clans cooperate in protecting the colony and providing food. Cooperation means that members of a group bear a cost, c, for another individuals to earn a benefit, b. While cooperators of the group help others by paying a cost, defectors receive the benefits of this altruistic behavior without providing any service in return to the group. To address this dilemma, here we use a game theoretic approach to model and study evolutionary dynamics that can lead to unselfish behavior. Evolutionary game theory is an approach to study frequency-dependent systems. In evolutionary games the fitness of individuals depends on the relative abundance of the various types in the population. We explore different strategies and different games such as iterated games between players with conditional strategies, multi player games, and iterated games between fully stochastic strategies in noisy environments to find the necessity conditions that lead to cooperation. Interestingly, we see that in all of these games communication is the key factor for maintaining cooperation among selfish individuals. We show that communication and information exchange is necessary for the emergence of costly altruism, and to maintain cooperation in the group there should be minimum rate of communication between individuals. We quantify this minimum amount of information exchange, which is necessary for individuals to exhibit cooperative behavior, by defining a noisy communication channel between them in iterated stochastic games and measuring the communication rate (in bits) during the break down of cooperation.
Show less

Title: Multi-Task Learning and Its Application to Geospatio-Temporal Data
Creator: Xu, Jianpeng
Date: 2017
Collection: Electronic Theses & Dissertations
Description: Multi-task learning (MTL) is a data mining and machine learning approach for modeling multiple prediction tasks simultaneously by exploiting the relatedness among the tasks. MTL has been successfully applied to various domains, including computer vision, healthcare, genomics, recommender systems, and natural language processing. The goals of this thesis are: (1) to investigate the feasibility of applying MTL to geospatio-temporal prediction problems, particularly those encountered in the...
Show moreMulti-task learning (MTL) is a data mining and machine learning approach for modeling multiple prediction tasks simultaneously by exploiting the relatedness among the tasks. MTL has been successfully applied to various domains, including computer vision, healthcare, genomics, recommender systems, and natural language processing. The goals of this thesis are: (1) to investigate the feasibility of applying MTL to geospatio-temporal prediction problems, particularly those encountered in the climate and environmental science domains and (2) to develop novel MTL frameworks that address the challenges of building effective predictive models from geospatio-temporal data.The first contribution of this thesis is to develop an online temporal MTL framework called ORION for ensemble forecasting problems. Ensemble forecasting uses a numerical method to simulate the evolution of nonlinear dynamic systems, such as climate and hydrological systems. ORION aims to effectively aggregate the forecasts generated by different ensemble members for a future time window, where each forecast is obtained by perturbing the starting condition of the computer model or using a different model representation. ORION considers the prediction for each time point in the forecast window as a distinct prediction task, where the task relatedness is achieved by imposing temporal smoothness and mean regularization constraints. A novel, online update with restart strategy is proposed to handle missing observations in the training data. ORION can also be optimized for different objectives, such as ε -insensitive and quantile loss functions.The second contribution of this thesis is to propose a MTL framework named GSpartan that can perform inferences at multiple locations simultaneously while allowing the local models for different locations to be jointly trained. GSpartan assumes that the local models share a common, low-rank representation and employs a graph Laplacian regularization to enforce constraints due to the inherent spatial autocorrelation of the data. Sparsity and non-negativity constraints are also incorporated into the formulation to ensure interpretability of the models.GSpartan is a MTL framework that considers only the spatial autocorrelation of the data. It is also a batch learning algorithm, which makes it difficult to scale up to global-scale data. To address these limitations, a new framework called WISDOM is proposed, which can incorporate the task relatedness across both space and time. WISDOM encodes the geospatio-temporal data as a tensor and performs supervised tensor decomposition to identify the latent factors that capture the inherent spatial and temporal variabilities of the data as well as the relationship between the predictor and target variables. The framework is unique in that it trains distinct spatial and temporal prediction models from the latent factors of the decomposed tensor and aggregates the outputs of these models to obtain the final prediction. WISDOM also employs an incremental learning algorithm that can systematically update the models when training examples are available for a new time period or for a new location.Finally, the geospatio-temporal data for many scientific applications are often available at varying spatial scales. For example, they can be generated by computer models simulated at different grid resolutions (e.g., the global and regional models used in climate modeling). A simple way to handle the predictor variables generated from the multi-scale data is to concatenate them into a single feature vector and train WISDOM using the concatenated vectors. However, this strategy may not be effective as it ignores the inherent dependencies between variables at different scales. To overcome this limitation, this thesis presents an extension of WISDOM called MUSCAT for handling multi-scale geospatio-temporal data. MUSCAT considers the consistency of the latent factors extracted from the spatio-temporal tensors at different scales while inheriting the benefits of WISDOM. Given the massive size of the multi-scale spatio-temporal tensors, a novel, supervised, incremental multi-tensor decomposition algorithm is develop to efficiently learn the model parameters.
Show less

Title: Hybrid Structural and Behavioral Diversity Techniques for Effective Genetic Programming
Creator: Burks, Armand Rashad
Date: 2017
Collection: Electronic Theses & Dissertations
Description: Sustaining the diversity of evolving populations is a fundamental issue in genetic programming. We describe a novel measure of structural diversity for tree-based genetic programming, and we demonstrate its utility compared to other diversity techniques. We demonstrate our technique on the real-world application of tuberculosis screening from X-ray images. We then introduce a new paradigm of genetic programming that involves simultaneously maintaining structural and behavioral diversity in...
Show moreSustaining the diversity of evolving populations is a fundamental issue in genetic programming. We describe a novel measure of structural diversity for tree-based genetic programming, and we demonstrate its utility compared to other diversity techniques. We demonstrate our technique on the real-world application of tuberculosis screening from X-ray images. We then introduce a new paradigm of genetic programming that involves simultaneously maintaining structural and behavioral diversity in order to further improve the efficiency of genetic programming.Our results show that simultaneously promoting structural and behavioral diversity improves genetic programming by leveraging the benefits of both aspects of diversity while overcoming the shortcomings of either technique in isolation. The hybridization increases the behavioral diversity of our structural diversity technique, and increases the structural diversity of the behavioral diversity techniques. This increased diversity leads to performance gains compared to either technique in isolation.We found that in many cases, our structural diversity technique provides significant performance improvement compared to other state-of-the-art techniques. Our results from the experiments comparing the hybrid techniques indicate that the largest performance gain was typically attributed to our structural diversity technique. The incorporation of the behavioral diversity techniques provide additional improvement in many cases.
Show less

Title: Example-Based Parameterization of Linear Blend Skinning for Skinning Decomposition (EP-LBS
Creator: Hopkins, Kayra M.
Date: 2017
Collection: Electronic Theses & Dissertations
Description: This thesis presents Example-based Parameterization of Linear Blend Skinning for Skinning Decomposition (EP-LBS), a unified and robust method for using example data to simplify and improve the development and parameterization of high quality 3D models for animation. Animation and three-dimensional (3D) computer graphics have quickly become a popular medium for education, entertainment and scientific simulation. In addition to film, gaming and research applications, recent advancements in...
Show moreThis thesis presents Example-based Parameterization of Linear Blend Skinning for Skinning Decomposition (EP-LBS), a unified and robust method for using example data to simplify and improve the development and parameterization of high quality 3D models for animation. Animation and three-dimensional (3D) computer graphics have quickly become a popular medium for education, entertainment and scientific simulation. In addition to film, gaming and research applications, recent advancements in augmented reality (AR) and virtual reality (VR) are driving additional demand for 3D content. However, the success of graphics in these arenas depends greatly on the efficiency of model creation and the realism of the animation or 3D image.A common method for figure animation is skeletal animation using linear blend skinning (LBS). In this method, vertices are deformed based on a weighted sum of displacements due to an embedded skeleton. This research addresses the problem that LBS animation parameter computation, including determining the rig (the skeletal structure), identifying influence bones (which bones influence which vertices), and assigning skinning weights (amounts of influence a bone has on a vertex), is a tedious process that is difficult to get right. Even the most skilled animators must work tirelessly to design an effective character model and often find themselves repeatedly correcting flaws in the parameterization. Significant research, including the use of example-data, has focused on simplifying and automating individual components of the LBS deformation process and increasing the quality of resulting animations. However, constraints on LBS animation parameters makes automated analytic computation of the values equally as challenging as traditional 3D animation methods. Skinning decomposition is one such method of computing LBS animation LBS parameters from example data. Skinning decomposition challenges include constraint adherence and computationally efficient determination of LBS parameters.The EP-LBS method presented in this thesis utilizes example data as input to a least-squares non-linear optimization process. Given a model as a set of example poses captured from scan data or manually created, EP-LBS institutes a single optimization equation that allows for simultaneous computation of all animation parameters for the model. An iterative clustering methodology is used to construct an initial parameterization estimate for this model, which is then subjected to non-linear optimization to improve the fitting to the example data. Simultaneous optimization of weights and joint transformations is complicated by a wide range of differing constraints and parameter interdependencies. To address interdependent and conflicting constraints, parameter mapping solutions are presented that map the constraints to an alternative domain more suitable for nonlinear minimization. The presented research is a comprehensive, data-driven solution for automatically determining skeletal structure, influence bones and skinning weights from a set of example data. Results are presented for a range of models that demonstrate the effectiveness of the method.
Show less

Title: Capturing Bluetooth Traffic in the Wild : Practical Systems and Privacy Implications
Creator: ALBAZRQAOE, WAHHAB
Date: 2018
Collection: Electronic Theses & Dissertations
Description: Bluetooth wireless technology is today present in billions of smartphones, mobile devices, and portable electronics. With the prevalence of personal Bluetooth devices, a practical Bluetooth traffic sniffer is of increasing interest due to the following. First, it has been reported that a traffic sniffer is an essential, day-to-day tool for Bluetooth engineers and applications developers; and second, as the communication between Bluetooth devices is privacy-sensitive in nature, exploring the...
Show moreBluetooth wireless technology is today present in billions of smartphones, mobile devices, and portable electronics. With the prevalence of personal Bluetooth devices, a practical Bluetooth traffic sniffer is of increasing interest due to the following. First, it has been reported that a traffic sniffer is an essential, day-to-day tool for Bluetooth engineers and applications developers; and second, as the communication between Bluetooth devices is privacy-sensitive in nature, exploring the possibility of Bluetooth traffic sniffing in practical settings sheds lights into potential user privacy leakage. To date, sniffing Bluetooth traffic has been widely considered an extremely intricate task due to wideband spread spectrum of Bluetooth, pseudo-random frequency hopping adopted by Bluetooth at baseband, and the interference in the open 2.4 GHz band.This thesis addresses these challenges by introducing novel traffic sniffers that capture Bluetooth packets in practical environments. In particular, we present the following systems. (i) BlueEar, the first practical Bluetooth traffic sniffing system only using general, inexpensive wireless platforms. BlueEar features a novel dual-radio architecture where two inexpensive, Bluetooth-compliant radios coordinate with each other to eavesdrop on hopping subchannels in indiscoverable mode. Statistic models and lightweight machine learning tools are integrated to learn the adaptive hopping behavior of the target. Our results show that BlueEar maintains a packet capture rate higher than 90% consistently in dynamic settings. In addition, we discuss the implications of the BlueEar approach on Bluetooth LE sniffing and present a practical countermeasure that effectively reduces the packet capture rate of sniffer by 70%, which can be easily implemented on the Bluetooth master while requiring no modification to slave devices like keyboards and headsets.
Show less

Title: Convolutional neural networks for automated cell detection in magnetic resonance imaging data
Creator: Afridi, Muhammad Jamal
Date: 2017
Collection: Electronic Theses & Dissertations
Description: Cell-based therapy (CBT) is emerging as a promising solution for a large number of serious health issues such as brain injuries and cancer. Recent advances in CBT, has heightened interest in the non-invasive monitoring of transplanted cells in in vivo MRI (Magnetic Resonance Imaging) data. These cells appear as dark spots in MRI scans. However, to date, these spots are manually labeled by experts, which is an extremely tedious and a time consuming process. This limits the ability to conduct...
Show moreCell-based therapy (CBT) is emerging as a promising solution for a large number of serious health issues such as brain injuries and cancer. Recent advances in CBT, has heightened interest in the non-invasive monitoring of transplanted cells in in vivo MRI (Magnetic Resonance Imaging) data. These cells appear as dark spots in MRI scans. However, to date, these spots are manually labeled by experts, which is an extremely tedious and a time consuming process. This limits the ability to conduct large scale spot analysis that is necessary for the long term success of CBT. To address this gap, we develop methods to automate the spot detection task. In this regard we (a) assemble an annotated MRI database for spot detection in MRI; (b) present a superpixel based strategy to extract regions of interest from MRI; (c) design a convolutional neural network (CNN) architecture for automatically characterizing and classifying spots in MRI; (d) propose a transfer learning approach to circumvent the issue of limited training data, and (e) propose a new CNN framework that exploits labeling behavior of the expert in the learning process. Extensive experiments convey the benefits of the proposed methods.
Show less

Title: Hidden Markov model-based homology search and gene prediction in NGS ERA
Creator: Techa-angkoon, Prapaporn
Date: 2017
Collection: Electronic Theses & Dissertations
Description: The exponential cost reduction of next-generation sequencing (NGS) enabled researchers to sequence a large number of organisms in order to answer various questions in biology, ecology, health, etc. For newly sequenced genomes, gene prediction and homology search against characterized protein sequence databases are two fundamental tasks for annotating functional elements in the genomes. The main goal of gene prediction is to identify the gene locus and their structures. As there is...
Show moreThe exponential cost reduction of next-generation sequencing (NGS) enabled researchers to sequence a large number of organisms in order to answer various questions in biology, ecology, health, etc. For newly sequenced genomes, gene prediction and homology search against characterized protein sequence databases are two fundamental tasks for annotating functional elements in the genomes. The main goal of gene prediction is to identify the gene locus and their structures. As there is accumulating evidence showing important functions of RNAs (ncRNAs), comprehensive gene prediction should include both protein-coding genes and ncRNAs. Homology search against protein sequences can aid identification of functional elements in genomes. Although there are intensive research in the fields of gene prediction, ncRNA search, and homology search, there are still unaddressed challenges. In this dissertation, I made contributions in these three areas. For gene prediction, I designed an HMM-based ab initio gene prediction tool that considers G+C gradient in grass genomes. For homology search, I designed a method that can align short reads against protein families using profile HMMs. For ncRNA search, I designed a ncRNA alignment tool that can align highly structured ncRNAs using only sequence similarity. Below I summarize my contributions.Despite decades of research about gene prediction, existing gene prediction tools are not carefully designed to deal with variant G+C content and 5'-3' changing patterns inside coding regions. Thus, these tools can miss genes with positive or negative G+C gradient in grass genomes such as rice, maize, sorghum, etc. I implemented a tool named AUGUSTUS-GC that accounts for 5'-3' G+C gradient. Our tool can accurately predict protein-coding genes in plant genomes especially grass genomes.A large number of sequencing projects produced short reads from the whole genomes or transcriptomic data. I designed a short reads homology search tool that employs paired-end reads to improve homology search sensitivity. The experimental results show that our tool can achieve significantly better sensitivity and accuracy in aligning short reads that are part of remote homologs.Despite the extensive studies of ncRNA search, the existing tools that heavily depend on the secondary structure in homology search cannot efficiently handle RNA-seq data that is accumulating rapidly. It will be ideal if we can have a faster ncRNA homology search tool with similar accuracy as those adopting secondary structure. I implemented an accurate ncRNA alignment tool called glu-RNA that can achieve similar accuracy to structural alignment tools while keeping the same running time complexity as sequence alignment tools. The experimental results demonstrate that our tool can achieve more accurate alignments than the popular sequence alignment tools and a well-known structural alignment program.
Show less

Title: Discrete vector and 2-tensor analyses and applications
Creator: Liu, Beibei
Date: 2015
Collection: Electronic Theses & Dissertations
Description: We present novel analysis methods for vector fields and an intrinsic representation of 2-tensor fields on meshes, and show the benefits they bring to discrete calculus, geometry processing, texture synthesis and fluid simulation. For instance, such vector fields and tensor fields in flat 2D space are necessary for example-based texture synthesis. However, many existing methods cannot ensure the continuity automatically or control the singularities accurately. Moreover, extending such analyses...
Show moreWe present novel analysis methods for vector fields and an intrinsic representation of 2-tensor fields on meshes, and show the benefits they bring to discrete calculus, geometry processing, texture synthesis and fluid simulation. For instance, such vector fields and tensor fields in flat 2D space are necessary for example-based texture synthesis. However, many existing methods cannot ensure the continuity automatically or control the singularities accurately. Moreover, extending such analyses to curved surfaces involves several known challenges. First, vectors at different surface points are defined in different tangent planes, so their comparison necessarily involves a concept calledconnection to transport vectors from one tangent plane to another in a parallel way. The few existing approaches for discrete connections offer neither a globally optimal principled definition nor a consistent disretization of differential operators. Second, symmetric 2-tensors, which play a crucial role in geometry processing, are often discretized as components stored in the predefined local frames. There is no convenient way to perform coordinate-independent computations with arbitrary 2-tensor fields on triangulated surface meshes. Finally, the persistent pursue for efficiency in the processing of vector fields in applications such as incompressible fluid simulation often results in undesired artifacts such as numerical viscosity, which prevents a predictive preview for the fine-resolution simulation at coarse spatial and temporal resolutions.We offer solutions to address these issues using our novel representation and analysis tools.First, we present a framework for example-based texture synthesis with feature alignment to vector fields with two way rotational symmetry, also known as orientation fields. Our contribution is twofold: a design tool for orientation fields with a natural boundary condition and singularity control, and a parallel texture synthesis adapted specifically for such fields in feature alignment.Second, we define discrete connection on triangle meshes, which involves closed-form expressions within edges and triangles and finite rotations between pairs of incident vertices, edges, or triangles. The finite set of parameters of this connection can be optimally computed by minimizing a quadratic measure of the deviation from the connection induced by the embedding of the input triangle mesh. Local integrals of other first-order derivatives as well as the L2-based energies can also be computed.Third, we offer a coordinate-free representation of arbitrary 2-tensor fields on triangle meshes, where we leverage a decomposition of continuous 2-tensors in the plane to construct a finite-dimensional encoding of tensor fields through scalar values on oriented pieces of a manifold triangulation. We also provide closed-form expressions of common operators for tensor fields, including pairing, inner product, and trace for this discrete representation, and formulate a discrete covariant derivative induced by the 2-tensors instead of the metric of the surface. Other operators, such as discrete Lie bracket, can be constructed based on these operators. This approach extends computational tools for tensor fields and offers a numerical framework for discrete tensor calculus on triangulations.Finally, a spectral vector field calculus on embeded irregular shape is introduced to build a model-reduced variational Eulerian integrator for incompressible fluid. The resulting simulation combines the efficiency gains of dimension reduction, the qualitative robustness to coarse spatial and temporal resolutions of geometric integrators, and the simplicity of sub-grid accurate boundary conditions on regular grids to deal with arbitrarily-shaped domains. A functional map approach to fluid simulation is also proposed, where scalar-valued and vector-valued eigenfunctions of the Laplacian operator can be easily used as reduced bases. Using a variational integrator in time topreserve liveliness and a simple, yet accurate embedding of the fluid domain onto a Cartesian grid, our model-reduced fluid simulator can achieve realistic animations in significantly less computation time than full-scale non-dissipative methods but without the numerical viscosity from which current reduced methods suffer.
Show less

Title: Hardware Algorithms for High-Speed Packet Processing
Creator: Norige, Eric
Date: 2017
Collection: Electronic Theses & Dissertations
Description: The networking industry is facing enormous challenges of scaling devices to support theexponential growth of internet traﬃc as well as increasing number of features being implemented inside the network. Algorithmic hardware improvements to networking componentshave largely been neglected due to the ease of leveraging increased clock frequency and compute power and the risks of implementing complex hardware designs. As clock frequencyslows its growth, algorithmic solutions become important to...
Show moreThe networking industry is facing enormous challenges of scaling devices to support theexponential growth of internet traﬃc as well as increasing number of features being implemented inside the network. Algorithmic hardware improvements to networking componentshave largely been neglected due to the ease of leveraging increased clock frequency and compute power and the risks of implementing complex hardware designs. As clock frequencyslows its growth, algorithmic solutions become important to ﬁll the gap between currentgeneration capability and next generation requirements. This paper presents algorithmicsolutions to networking problems in three domains: Deep Packet Inspection(DPI), ﬁrewall(and other) ruleset compression and non-cryptographic hashing. The improvements in DPIare two-pronged: ﬁrst in the area of application-level protocol ﬁeld extraction, which allowssecurity devices to precisely identify packet ﬁelds for targeted validity checks. By usingcounting automata, we achieve precise parsing of non-regular protocols with small, constantper-ﬂow memory requirements, extracting at rates of up to 30gbps on real traﬃc in softwarewhile using only 112 bytes of state per ﬂow. The second DPI improvement is on the longstanding regular expression matching problem, where we complete the HFA solution to theDFA state explosion problem with eﬃcient construction algorithms and optimized memorylayout for hardware or software implementation. These methods construct automata toocomplex to be constructed by previous methods in seconds, while being capable of 29gbpsthroughput with an ASIC implementation. Firewall ruleset compression enables more ﬁrewall entries to be stored in a ﬁxed capacity pattern matching engine, and can also be usedto reorganize a ﬁrewall speciﬁcation for higher performance software matching. A novelrecursive structure called TUF is given to unify the best known solutions to this problemand suggest future avenues of attack. These algorithms, with little tuning, achieve a 13.7%improvement in compression on large, real-life classiﬁers, and can achieve the same results asexisting algorithms while running 20 times faster. Finally, non-cryptographic hash functionscan be used for anything from hash tables to track network ﬂows to packet sampling fortraﬃc characterization. We give a novel approach to generating hardware hash functionsin between the extremes of expensive cryptographic hash functions and low quality linearhash functions. To evaluate these mid-range hash functions properly, we develop new evaluation methods to better distinguish non-cryptographic hash function quality. The hashfunctions described in this paper achieve low-latency, wide hashing with good avalanche anduniversality properties at a much lower cost than existing solutions.
Show less

Title: Suicide, Signals, and Symbionts : evolving Cooperation in Agent-Based Systems
Creator: Vostinar, Anya E.
Date: 2017
Collection: Electronic Theses & Dissertations
Description: Cooperation is ubiquitous in nature despite the constant pressure for organisms to cheat by receiving a benefit from cooperators, while not cooperating themselves. The continued evolution and persistence of countless forms of cooperation is a central topic in evolutionary theory. Extensive research has been done on the theoretical dynamics of cooperation through game theory and the natural examples of cooperation. However, it remains difficult to understand thoroughly the evolution of many...
Show moreCooperation is ubiquitous in nature despite the constant pressure for organisms to cheat by receiving a benefit from cooperators, while not cooperating themselves. The continued evolution and persistence of countless forms of cooperation is a central topic in evolutionary theory. Extensive research has been done on the theoretical dynamics of cooperation through game theory and the natural examples of cooperation. However, it remains difficult to understand thoroughly the evolution of many cooperative systems, due in part to the ancient origins of these systems and the long time scales required to see cooperation evolve in any natural populations. I have systematically analyzed the evolution of three broad types of cooperation: programmed cell death, quorum sensing, and mutualisms (cooperation across species). I have provided evidence that programmed cell death can originate due to kin selection. I have also created two new systems to enable the extensive exploration of factors that affect the evolution of public goods cooperation and mutualism. Using these systems, I determine the effects of environmental factors on the evolution of public goods cooperation and mutualism. By uniting the expansive theoretical work on these forms of cooperation with a fully-controlled experimental system, I contributed to our understanding of how these forms of cooperation can emerge and be maintained in industrial and medical applications that rely on bacterial cooperation.
Show less

MSU Libraries

Digital Repository

Pages

Pages

MSU Libraries

Digital Repository

You are here

Search results

Pages

Pages