Search results

Title: Some contributions to semi-supervised learning
Creator: Mallapragada, Paven Kumar
Date: 2010
Collection: Electronic Theses & Dissertations

Title: Semi=supervised learning with side information : graph-based approaches
Creator: Liu, Yi
Date: 2007
Collection: Electronic Theses & Dissertations

Title: Estimating covariance structure in high dimensions
Creator: Maurya, Ashwini
Date: 2016
Collection: Electronic Theses & Dissertations
Description: Many of scientific domains rely on extracting knowledge from high-dimensional data set to provide insights into complex mechanisms underlying these data. Statistical modeling hasbecome ubiquitous in the analysis of high dimensional data for exploring the large-scale gen regulatory networks in hope of developing better treatments for deadly diseases, in search o better understanding of cognitive systems, and in prediction of volatility in stock market in the hope of averting the potential risk...
Show moreMany of scientific domains rely on extracting knowledge from high-dimensional data set to provide insights into complex mechanisms underlying these data. Statistical modeling hasbecome ubiquitous in the analysis of high dimensional data for exploring the large-scale gen regulatory networks in hope of developing better treatments for deadly diseases, in search o better understanding of cognitive systems, and in prediction of volatility in stock market in the hope of averting the potential risk. Statistical analysis in these high-dimensional data set yields better results only if an estimation procedure exploits hidden structures underlying the data. This thesis develops flexible estimation procedures with provable theoretical guarantees for estimating the unknown covariance structures underlying data generating process. Of particular interest are procedures that can be used on high dimensional data sets where the number of samples n is much smaller than the ambient dimension p. Due to the importance of structure estimation, the methodology is developed for the estimation of both covariance and its inverse in parametric and as well in non-parametric framework.
Show less

Title: Contributions to Machine Learning in Biomedical Informatics
Creator: Baytas, Inci Meliha
Date: 2019
Collection: Electronic Theses & Dissertations
Description: With innovations in digital data acquisition devices and increased memory capacity, virtuallyall commercial and scientific domains have been witnessing an exponential growth in the amountof data they can collect. For instance, healthcare is experiencing a tremendous growth in digitalpatient information due to the high adaptation rate of electronic health record systems in hospitals.The abundance of data offers many opportunities to develop robust and versatile systems, as longas the...
Show moreWith innovations in digital data acquisition devices and increased memory capacity, virtuallyall commercial and scientific domains have been witnessing an exponential growth in the amountof data they can collect. For instance, healthcare is experiencing a tremendous growth in digitalpatient information due to the high adaptation rate of electronic health record systems in hospitals.The abundance of data offers many opportunities to develop robust and versatile systems, as longas the underlying salient information in data can be captured. On the other hand, today’s data,often named big data, is challenging to analyze due to its large scale and high complexity. For thisreason, efficient data-driven techniques are necessary to extract and utilize the valuable informationin the data. The field of machine learning essentially develops such techniques to learn effectivemodels directly from the data. Machine learning models have been successfully employed to solvecomplicated real world problems. However, the big data concept has numerous properties that poseadditional challenges in algorithm development. Namely, high dimensionality, class membershipimbalance, non-linearity, distributed data, heterogeneity, and temporal nature are some of the bigdata characteristics that machine learning must address.Biomedical informatics is an interdisciplinary domain where machine learning techniques areused to analyze electronic health records (EHRs). EHR comprises digital patient data with variousmodalities and depicts an instance of big data. For this reason, analysis of digital patient data isquite challenging although it provides a rich source for clinical research. While the scale of EHRdata used in clinical research might not be huge compared to the other domains, such as socialmedia, it is still not feasible for physicians to analyze and interpret longitudinal and heterogeneousdata of thousands of patients. Therefore, computational approaches and graphical tools toassist physicians in summarizing the underlying clinical patterns of the EHRs are necessary. Thefield of biomedical informatics employs machine learning and data mining approaches to provide the essential computational techniques to analyze and interpret complex healthcare data to assistphysicians in patient diagnosis and treatment.In this thesis, we propose and develop machine learning algorithms, motivated by prevalentbiomedical informatics tasks, to analyze the EHRs. Specifically, we make the following contributions:(i) A convex sparse principal component analysis approach along with variance reducedstochastic proximal gradient descent is proposed for the patient phenotyping task, which is definedas finding clinical representations for patient groups sharing the same set of diseases. (ii)An asynchronous distributed multi-task learning method is introduced to learn predictive modelsfor distributed EHRs. (iii) A modified long-short term memory (LSTM) architecture is designedfor the patient subtyping task, where the goal is to cluster patients based on similar progressionpathways. The proposed LSTM architecture, T-LSTM, performs a subspace decomposition on thecell memory such that the short term effect in the previous memory is discounted based on thelength of the time gap. (iv) An alternative approach to T-LSTM model is proposed with a decoupledmemory to capture the short and long term changes. The proposed model, decoupled memorygated recurrent network (DM-GRN), is designed to learn two types of memories focusing on differentcomponents of the time series data. In this study, in addition to the healthcare applications,behavior of the proposed model is investigated for traffic speed prediction problem to illustrate itsgeneralization ability. In summary, the aforementioned machine learning approaches have beendeveloped to address complex characteristics of electronic health records in routine biomedical informaticstasks such as computational patient phenotyping and patient subtyping. Proposed modelsare also applicable to different domains with similar data characteristics as EHRs.
Show less

Title: A framework for verification of transaction level models in systemc
Creator: Hajisheykhi, Reza
Date: 2016
Collection: Electronic Theses & Dissertations
Description: Due to their increasing complexity, today's SoC (System on Chip) systems are subject to a variety of faults (e.g., single-event upset, component crash, etc.), thereby their verification a highly important task of such systems. However, verification is a complex task in part due to the large scale of integration of SoC systems and different levels of abstraction provided by modern system design languages such as SystemC.To facilitate the verification of SoC systems, this dissertation proposes...
Show moreDue to their increasing complexity, today's SoC (System on Chip) systems are subject to a variety of faults (e.g., single-event upset, component crash, etc.), thereby their verification a highly important task of such systems. However, verification is a complex task in part due to the large scale of integration of SoC systems and different levels of abstraction provided by modern system design languages such as SystemC.To facilitate the verification of SoC systems, this dissertation proposes an approach for verifying inter-component communication protocols in SystemC Transaction Level Modeling (TLM) programs. SystemC is a widely accepted language and an IEEE standard. It includes a C++ library of abstractions and a run-time kernel that simulates the specified system, thereby enabling the early development of embedded software for the system that is being designed. To enable and facilitate the communication of different components in SystemC, the Open SystemC Initiative (OSCI) has proposed an interoperability layer (on top of SystemC) that enables transaction-based interactions between the components of a system, called Transaction Level Modeling (TLM).In order to verify SystemC TLM programs, we propose a method that includes five main steps, namely defining formal semantics, model extraction, fault modeling, model slicing, and model checking. In order to extract a formal model from the given SystemC TLM program, first we need to specify the requirements of developing a formal semantics that can capture the SystemC TLM programs while still benefiting from automation techniques for verification and/or synthesis. Based on this intuition, we utilize two model extraction approaches that consider the architecture of the given program too.In the first approach, we propose a set of transformation rules that helps us to extract a Promela model from the SystemC TLM program. In the second approach, we discuss how to extract a timed automata model from the given program.When we have the formal model, we model and inject several types of faults into the formal models extracted from the SystemC TLM programs. For injecting faults, we have developed a tool, called UFIT, that takes a formal model and a desirable fault type, and injects the faults into the model accordingly.The models extracted from the SystemC TLM program are usually very complex. Additionally, when we inject faults into these models they become even more complex. Hence, we utilize a model slicing technique to slice the models in the presence or absence of faults. We have developed a tool, called USlicer that takes a formal model along with a set of properties that needs to be verified, and generate a sliced model based on the given properties. The results show that verification time and the memory usage of the sliced version of the model is significantly smaller than that of the original model. Subsequently, in some cases where the verification of the original formal models is not even possible, using our model slicing technique makes the verification possible in a reasonable time and space.We demonstrate the proposed approach using several SystemC transaction level case studies. In each case study, we explain each step of our approach in detail and discuss the results and improvements in each of them.
Show less

Title: A collaborative software toolchain for automatic collection and comparative analysis of sensor characterization data
Creator: Boling, Charles Samuel
Date: 2016
Collection: Electronic Theses & Dissertations
Description: Reproducible research has been recognized as a growing concern in most areas of science. To achieve widespread adoption of repeatable, transparent research practices, some commentators have identified a need for better software for authoring reproducible digital publications. Complicating this goal, scientific investigations increasingly involve interdisciplinary teams, sophisticated workflows for acquiring and analyzing data, and huge datasets that rely on considerable metadata to interpret....
Show moreReproducible research has been recognized as a growing concern in most areas of science. To achieve widespread adoption of repeatable, transparent research practices, some commentators have identified a need for better software for authoring reproducible digital publications. Complicating this goal, scientific investigations increasingly involve interdisciplinary teams, sophisticated workflows for acquiring and analyzing data, and huge datasets that rely on considerable metadata to interpret. Computational scientists have begun to adopt tools for managing the complex histories of their data and procedures, but software which simultaneously allows researchers to specify experiments, remotely control equipment, and capture and organize data remains immature. This thesis demonstrates a software architecture for programmable remote control of custom and commercial lab equipment, automatic annotation and queryable storage of data sets, and provenance-aware specification of experiment and analysis procedures. The design consists of a suite of small, single-purpose software services which may be controlled remotely from a web browser, including a graphical programming tool, an abstraction layer for interfacing with commercial and custom embedded systems, and a hybrid document/table database for persistent storage of annotated experimental data. The software implementation embraces modern web technologies and best practices to produce a modular, user-extensible framework that is well-suited for helping to integrate computer-controlled research labs with the emerging Internet of Things.
Show less

Title: ON DESIGN AND IMPLEMENTATION OF FAST & SECURE NETWORK PROTOCOLS FOR DATACENTERS
Creator: Munir, Ali
Date: 2019
Collection: Electronic Theses & Dissertations
Description: My PhD work focuses on improving the performance and security of networked systems. For network performance, my research focuses on scheduling and transport in datacenter networks. For network security, my research focuses on multipath TCP security.To improve the performance of datacenter transport, I proposed PASE, a near-optimal and deployment friendly transport protocol. To this end, I first identified the underlying strategies used by existing datacenter transports. Next, I showed that...
Show moreMy PhD work focuses on improving the performance and security of networked systems. For network performance, my research focuses on scheduling and transport in datacenter networks. For network security, my research focuses on multipath TCP security.To improve the performance of datacenter transport, I proposed PASE, a near-optimal and deployment friendly transport protocol. To this end, I first identified the underlying strategies used by existing datacenter transports. Next, I showed that these strategies are complimentary to each other, rather than substitutes, as they have different strengths and can address each other’s limitations. Unfortunately, prior datacenter transports use only one of these strategies and as a result they either achieve near-optimal performance or deployment friendliness but not both. Based on this insight, I designed a datacenter transport protocol called PASE, which carefully synthesizes these strategies by assigning different transport responsibility to each strategy. To further improve the performance of datacenter transport in multi-tenant networks, I proposed Stacked Congestion Control (SCC), to achieve performance isolation and objective scheduling simultaneously. SCC is a distributed host-based bandwidth allocation framework, where an underlay congestion control layer handles contention among tenants, and a private congestion control layer for each tenant optimizes its performance objective. To my best knowledge, no prior work supported performance isolation and objective scheduling simultaneously. To improve task scheduling performance in datacenters, I proposed NEAT, a task scheduling framework that leverages information from the underlying network scheduler to make task placement decisions. Existing datacenter schedulers optimize either the placement of tasks or the scheduling of network flows. Inconsistent assumptions of the two schedulers can compromise the overall application performance. The core of NEAT is a task completion time predictor that estimates the completion time of a task under given network condition and a given network scheduling policy. Next, a distributed task placement framework leverages the predicted task completion times to make task placement decisions and minimize the average completion time of active tasks.To improve multipath TCP (MPTCP) security, I reported vulnerabilities in MPTCP that arise because of cross-path interactions between MPTCP subflows. MPTCP allows two endpoints to simultaneously use multiple paths between them. An attacker eavesdropping one MPTCP subflow can infer throughput of other subflows and also can inject forged MPTCP packets to change priorities of any MPTCP subflow. Attacker can exploit these vulnerabilities to launch the connection hijack attack on the paths he has no access to, or to divert traffic from one path to other paths. My proposed vulnerabilities fixes, changes to MPTCP specification, provide the guarantees that MPTCP is at least as secure as TCP and the original MPTCP. And has been adopted by IETF.
Show less

Title: Network Reachability : Quantification, Verification, Troubleshooing, and Optimization
Creator: Khakpour, Amir Reza
Date: 2011
Collection: Electronic Theses & Dissertations
Description: Quantifying, verifying, troubleshooting, and optimizing the network reachability is essential for network management and network security monitoring as well as various aspects of network auditing, maintenance, and design. Although attempts to model network reachability have been made, feasible solutions for computing, maintaining and optimally designing network reachability have remained unknown. Network reachability control is very critical because, on one hand, reachability errors can cause...
Show moreQuantifying, verifying, troubleshooting, and optimizing the network reachability is essential for network management and network security monitoring as well as various aspects of network auditing, maintenance, and design. Although attempts to model network reachability have been made, feasible solutions for computing, maintaining and optimally designing network reachability have remained unknown. Network reachability control is very critical because, on one hand, reachability errors can cause network security breaches or service outages, leading to millions of dollars of revenue loss for an enterprise network. On the other hand, network operators suffer from lack of tools that thoroughly examine network access control configurations and audit them to avoid such errors. Besides, finding reachability errors is by no means easy. The access control rules, by which network reachability is restricted, are often very complex and manually troubleshooting them is extremely difficult. Hence, having a tool that finds the reachability errors and fix them automatically can be very useful. Furthermore, flawed network reachability design and deployment can degrade the network performance significantly. Thus, it is crucial to have a tool that designs the network configurations such that they have the least performance impact on the enterprise network.In this dissertation, we first present a network reachability model that considers connectionless and connection-oriented transport protocols, stateless and stateful routers/firewalls, static and dynamic NAT, PAT, IP tunneling, etc. We then propose a suite of algorithms for quantifying reachability based on network configurations (mainly access control lists (ACLs)) as well as solutions for querying network reachability. We further extend our algorithms and data structures for detecting reachability errors, pinpointing faulty access control lists, and fixing them automatically and efficiently. Finally, we propose algorithms to place rules on network devices optimally so that they satisfy the networks central access policies. To this end, we define correctness and performance criteria for rule placement and in turn propose cost-based algorithms with adjustable parameters (for the network operators) to place rules such that the correctness and performance criteria are satisfied.We implemented the algorithms in our network reachability tool called Quarnet and conducted experiments on a university network. Experimental results show that the offline computation of reachability matrices takes a few hours and the online processing of a reachability query takes 75 milliseconds on average. We also examine our reachability error detection and correction algorithms on a few real-life networks to examine their performance and ensure that Quarnet is efficient enough to be practically useful. The results indicate that we can find reachability errors in order of minutes and fix them in order of seconds depending on the size of network and number of ACLs. Finally, we added the rule placement suite of algorithms to Quarnet, which can design a network ACL in based on the network central policies in order of tens of minutes for an enterprise network. We compare it with Purdue ACL placement, the state-of-the-art access policy design technique, and explain its pros and cons.
Show less

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: A robust method for addressing pupil dilation in iris recognition
Creator: Pasula, Raghunandan
Date: 2016
Collection: Electronic Theses & Dissertations
Description: The rich texture of the iris is being used as a biometric cue in several human recognition systems. Iris recognition systems are fairly robust to small changes in illumination and pose. However there are a number of factors that still adversely affect the performance of an iris matcher. These include occlusion, large deviation in gaze, low image resolution, long acquisition distance and pupil dilation. Large differences in pupil size increases thedissimilarity between iris images of the same...
Show moreThe rich texture of the iris is being used as a biometric cue in several human recognition systems. Iris recognition systems are fairly robust to small changes in illumination and pose. However there are a number of factors that still adversely affect the performance of an iris matcher. These include occlusion, large deviation in gaze, low image resolution, long acquisition distance and pupil dilation. Large differences in pupil size increases thedissimilarity between iris images of the same eye.In this work, the degradation of match scores due to pupil dilation is systematically studied using Hamming Distance histograms. A novel rule-based fusion technique based on the aforementioned study is proposed to alleviate the effect of pupil dilation. The proposed method computes a new distance score at every pixel location based on the similarities between IrisCode bits that were generated using Gabor Filters at different resolutions.Experiments show that the proposed method increases the genuine accept rate from 76% to 90% at 0.0001% false accept rate when comparing images with large differences in pupil sizes in the WVU-PLR dataset. The proposed method is also shown to improve the performance of iris recognition on other non-ideal iris datasets. In summary, the use of multi-resolution Gabor Filters in conjunction with a rule-based integration of decisions at the pixel (bit) level is observed to improve the resilience of iris recognition to differences in pupil size.
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: 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: Robust Global Motion Compensation and Its Applications
Creator: Safdarnejad, Seyed Morteza
Date: 2017
Collection: Electronic Theses & Dissertations
Description: This thesis presents algorithms for robust global motion compensation (GMC). GMC algorithms are used to remove camera motion and transform the video such that in the resultant video, the background appears static and the only motion rises from foreground objects. Many computer vision algorithms are tailored for static camera, and using GMC, it is possible to apply these algorithms on videos from moving cameras. For instance, motion-based video analysis is strongly affected by camera motion....
Show moreThis thesis presents algorithms for robust global motion compensation (GMC). GMC algorithms are used to remove camera motion and transform the video such that in the resultant video, the background appears static and the only motion rises from foreground objects. Many computer vision algorithms are tailored for static camera, and using GMC, it is possible to apply these algorithms on videos from moving cameras. For instance, motion-based video analysis is strongly affected by camera motion. If camera motion is not compensated, it interferes with the motion of interest, such as motion of human, and renders the analysis problem to be more challenging.Generally, in sequential schemes, GMC estimates the homography transformation between two consecutive frames by matching keypoints on the frames, and maps the second frame to a global coordinate. Then, by accumulating these transformations, a composite transformation is calculated which maps each frame to the global coordinate. However, existing GMC algorithms are sensitive to existence of foreground motion and fail easily in the case of considerable foreground motion or ambiguous and low texture background.To address the challenges in GMC, first, we propose a Robust Global Motion Compensation (RGMC) algorithm which explicitly suppresses the foreground effect and utilizes a comprehensive probabilistic verification model to find the best mappings between consecutive frames. Despite the robustness offered by RGMC, we further identified the problem of temporal drift of the estimation, due to accumulation of errors in estimation of mappings between consecutive coordinates. Furthermore, to address the issues of sequential GMC, we propose a Temporally Robust Global Motion Compensation (TRGMC) algorithm which by joint alignment of input frames, estimates accurate and temporally consistent transformations to the global coordinates. Joint alignment not only leads to the temporal consistency of GMC, but also improves GMC stability by using redundancy of the information.Many applications can benefit from a reliable and accurate GMC algorithm. We first briefly look into these applications. Then, among the many applications, we further investigate the problem of sequence alignment, and propose an alignment algorithm for non-overlapping sequences, enabled by performance of TRGMC. Given the transformation to a global coordinate, offered by TRGMC, and capability of background reconstruction using TRGMC result, we are able to align sequences even if the spatial overlap between the sequences is minimal or nonexistent. To this end, we first spatially align the sequences such that extrapolated backgrounds are aligned well and trajectory of moving objects are spatially smooth in the global coordinate. Next, we temporally align the sequences based on the smoothness of spatio-temporal trajectory of moving objects across field of view of different cameras.
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: TRADE-OFFS AMONG DATA SECURITY, USABILITY AND COMPLEXITY IN MOBILE CLOUD COMPUTING
Creator: Zhou, Kai
Date: 2018
Collection: Electronic Theses & Dissertations
Description: The proliferation of mobile cloud computing changes the way that data is utilized. Huge volume of data is collected at the network edge, transmitted through the network, gathered in the cloud, and utilized by various end-users. Data security, usability, and complexity are among the most important design issues in mobile computing environment. Trade- offs generally exist among these issues. While data encryption is a primary mechanism to ensure data security, it will inevitably introduce some...
Show moreThe proliferation of mobile cloud computing changes the way that data is utilized. Huge volume of data is collected at the network edge, transmitted through the network, gathered in the cloud, and utilized by various end-users. Data security, usability, and complexity are among the most important design issues in mobile computing environment. Trade- offs generally exist among these issues. While data encryption is a primary mechanism to ensure data security, it will inevitably introduce some computational overhead to the data owners. Also, data encryption will reduce data usability since typically it is hard to conduct computations over encrypted data.In this thesis, we focus on designing secure, efficient and versatile protocols that can achieve trade-offs among data security, data usability, and computational complexity, featuring the mobile cloud computing environment. In particular, we explore the trade-offs from two aspects. First, we design secure computation outsourcing schemes for a wide variety of computational problems such as general scientific computation and cryptographic computation, trying to alleviate the computational overhead at the user side while preserving the security of the outsourced data. Our proposed scheme is cost-aware in that it provides different levels of security protection for the outsourced problem with different computational overhead. Second, we design a specific encryption scheme that enables certain computations to be conducted directly over encrypted data. In this way, data users can directly utilize encrypted data to meet the demands of various applications without compromising datasecurity. More specifically, our proposed encryption scheme encrypts two vectors in such a manner that the inner product of the vectors can be evaluated and compared to a pre-defined threshold. We show that an encryption scheme can be utilized as an essential building block to construct various privacy-preserving applications such as an online biometric authentication system. Our proposed schemes are highly efficient and suitable for resource-constrained devices in the mobile cloud computing environment to greatly expand the computational capacity and/or extend battery life.
Show less

Title: An Analysis of Fitness in Long-Term Asexual Evolution Experiments
Creator: Wiser, Michael J.
Date: 2015
Collection: Electronic Theses & Dissertations
Description: Evolution is the central unifying concept of modern biology. Yet it can be hard to study in natural system, as it unfolds across generations. Experimental evolution allows us to ask questions about the process of evolution itself: How repeatable is the evolutionary process? How predictable is it? How general are the results? To address these questions, my collaborators and I carried out experiments both within the Long-Term Evolution Experiment (LTEE) in the bacteria Escherichia coli, and the...
Show moreEvolution is the central unifying concept of modern biology. Yet it can be hard to study in natural system, as it unfolds across generations. Experimental evolution allows us to ask questions about the process of evolution itself: How repeatable is the evolutionary process? How predictable is it? How general are the results? To address these questions, my collaborators and I carried out experiments both within the Long-Term Evolution Experiment (LTEE) in the bacteria Escherichia coli, and the digital evolution software platform Avida. In Chapter 1, I focused on methods. Previous research in the LTEE has relied on one particular way of measuring fitness, which we know becomes less precise as fitness differentials increase. I therefore decided to test whether two alternate ways of measuring fitness would improve precision, using one focal population. I found that all three methods yielded similar results in both fitness and coefficient of variation, and thus we should retain the traditional method.In Chapter 2, I turned to measuring fitness in each of the populations. Previous work had considered fitness to change as a hyperbola. A hyperbolic function is bounded, and predicts that fitness will asymptotically approach a defined upper bound; however, we knew that fitness in these populations routinely exceeded the asymptotic limit calculated from a hyperbola fit to the earlier data. I instead used to a power law, a mathematical function that does not have an upper bound. I found that this function substantially better describes fitness in this system, both among the whole set of populations, and in most of the individual populations. I also found that the power law models fit on just early subsets of the data accurately predict fitness far into the future. This implies that populations, even after 50,000 generations of evolution in consistent environment, are so far from the tops of fitness peaks that we cannot detect evidence of those peaks.In Chapter 3, I examined to how variance in fitness changes over long time scales. The among-population variance over time provides us information about the adaptive landscape on which the populations have been evolving. I found that among-population variance remains significant. Further, competitions between evolved pairs of populations reveal additional details about fitness trajectories than can be seen from competitions against the ancestor. These results demonstrate that our populations have been evolving on a complex adaptive landscape.In Chapter 4, I examined whether the patterns found in Chapter 2 apply to a very different evolutionary system, Avida. This system incorporates many similar evolutionary pressures as the LTEE, but without the details of cellular biology that underlie nearly all organic life. I find that in both the most complex and simplest environments in Avida, fitness also follows the same power law dynamics as seen in the LTEE. This implies that power law dynamics may be a general feature of evolving systems, and not dependent on the specific details of the system being studied.
Show less

MSU Libraries

Digital Repository

Pages

Pages

MSU Libraries

Digital Repository

You are here

Search results

Pages

Pages