Theory and Algorithms Commons^™

Generating Combinatorial Objects- A New Perspective, Alexander Chizoma Nwala

Computer Science Theses & Dissertations

Combinatorics is the science of "possibilities." This definition, while not formal is a fair statement because all too often, in order to gain insight into the solution of many counting problems, we explore the possibilities. In some cases we seek to know how many options, while in other cases we seek to enumerate or list the options. Irrespective of the scenario, combinatorics plays a vital role today. In many instances such as exploring the options for choosing a new password for a combination lock, we employ combinatorics. In considering the possible license plate permutations for a state, or to see …

Mechanisms For Arranging Ride Sharing And Fare Splitting For Last-Mile Travel Demands, Shih-Fen Cheng, Duc Thien Nguyen, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

A great challenge of city planners is to provide efficient and effective connection service to travelers using public transportation system. This is commonly known as the last-mile problem and is critical in promoting the utilization of public transportation system. In this paper, we address the last-mile problem by considering a dynamic and demand-responsive mechanism for arranging ride sharing on a non-dedicated commercial fleet (such as taxis or passenger vans). Our approach has the benefits of being dynamic, flexible, and with low setup cost. A critical issue in such ride-sharing service is how riders should be grouped and serviced, and how …

Didn’T You See My Message?: Predicting Attentiveness To Mobile Instant Messages, Martin Pielot, Rodrigo De Oliveira, Haewoon Kwak, Nuria. Oliver

Research Collection School Of Computing and Information Systems

Mobile instant messaging (e.g., via SMS or WhatsApp) often goes along with an expectation of high attentiveness, i.e., that the receiver will notice and read the message within a few minutes. Hence, existing instant messaging services for mobile phones share indicators of availability, such as the last time the user has been online. However, in this paper we not only provide evidence that these cues create social pressure, but that they are also weak predictors of attentiveness. As remedy, we propose to share a machine-computed prediction of whether the user will view a message within the next few minutes or …

Persistent Community Detection In Dynamic Social Networks, Siyuan Liu, Shuhui Wang, Ramayya Krishnan

Research Collection School Of Computing and Information Systems

While community detection is an active area of research in social network analysis, little effort has been devoted to community detection using time-evolving social network data. We propose an algorithm, Persistent Community Detection (PCD), to identify those communities that exhibit persistent behavior over time, for usage in such settings. Our motivation is to distinguish between steady-state network activity, and impermanent behavior such as cascades caused by a noteworthy event. The results of extensive empirical experiments on real-life big social networks data show that our algorithm performs much better than a set of baseline methods, including two alternative models and the …

Automatic Objects Removal For Scene Completion, Jianjun Yang, Yin Wang, Honggang Wang, Kun Hua, Wei Wang, Ju Shen

Computer Science Faculty Publications

With the explosive growth of Web-based cameras and mobile devices, billions of photographs are uploaded to the Internet. We can trivially collect a huge number of photo streams for various goals, such as 3D scene reconstruction and other big data applications. However, this is not an easy task due to the fact the retrieved photos are neither aligned nor calibrated. Furthermore, with the occlusion of unexpected foreground objects like people, vehicles, it is even more challenging to find feature correspondences and reconstruct realistic scenes. In this paper, we propose a structure-based image completion algorithm for object removal that produces visually …

Multi-Threaded Automatic Integration Using Openmp And Cuda, Rida Assaf

Masters Theses

Problems in many areas give rise to computationally expensive integrals that beg the need of efficient techniques to solve them, e.g., in computational finance for the modeling of cash flows; for the computation of Feynman loop integrals in high energy physics; and in stochastic geometry with applications to computer graphics.

We demonstrate feasible numerical approaches in the framework of the PARINT multivariate integration package. The parallel environment is provided by the cluster of the High Performance Computational Science (HPCS) laboratory, with 22 (16- or 32-core) nodes, NVIDIA GPUs, and Intel Xeon Phi coprocessors.

Monte Carlo integration is implemented in CUDA …

Are Timed Automata Bad For A Specification Language? Language Inclusion Checking For Timed Automata, Ting Wang, Jun Sun, Yang Liu, Xinyu Wang, Shanping Li

Research Collection School Of Computing and Information Systems

Given a timed automaton P modeling an implementation and a timed automaton S as a specification, language inclusion checking is to decide whether the language of P is a subset of that of S. It is known that this problem is undecidable and “this result is an obstacle in using timed automata as a specification language” [2]. This undecidability result, however, does not imply that all timed automata are bad for specification. In this work, we propose a zone-based semi-algorithm for language inclusion checking, which implements simulation reduction based on Anti-Chain and LU-simulation. Though it is not guaranteed to terminate, …

A Hamming Embedding Kernel With Informative Bag-Of-Visual Words For Video Semantic Indexing, Feng Wang, Wen-Lei Zhao, Chong-Wah Ngo, Bernard Merialdo

Research Collection School Of Computing and Information Systems

In this article, we propose a novel Hamming embedding kernel with informative bag-of-visual words to address two main problems existing in traditional BoW approaches for video semantic indexing. First, Hamming embedding is employed to alleviate the information loss caused by SIFT quantization. The Hamming distances between keypoints in the same cell are calculated and integrated into the SVM kernel to better discriminate different image samples. Second, to highlight the concept-specific visual information, we propose to weight the visual words according to their informativeness for detecting specific concepts. We show that our proposed kernels can significantly improve the performance of concept …

Machine Learning In Wireless Sensor Networks: Algorithms, Strategies, And Applications, Mohammad Abu Alsheikh, Shaowei Lin, Dusit Niyato, Hwee-Pink Tan

Research Collection School Of Computing and Information Systems

Wireless sensor networks (WSNs) monitor dynamic environments that change rapidly over time. This dynamic behavior is either caused by external factors or initiated by the system designers themselves. To adapt to such conditions, sensor networks often adopt machine learning techniques to eliminate the need for unnecessary redesign. Machine learning also inspires many practical solutions that maximize resource utilization and prolong the lifespan of the network. In this paper, we present an extensive literature review over the period 2002-2013 of machine learning methods that were used to address common issues in WSNs. The advantages and disadvantages of each proposed algorithm are …

Data Supply Chains, Tamara Kneese

Media Studies

As data moves between actors and organizations, what emerges is a data supply chain. Unlike manufacturing supply chains, transferred data is often duplicated in the process, challenging the essence of ownership. What does ethical data labor look like? How are the various stakeholders held accountable for being good data guardians? What does clean data transfer look like? What kinds of best practices can business and government put into place? What upstream rights to data providers have over downstream commercialization of their data?

Predicting Human Behavior, Tamara Kneese

Media Studies

Countless highly accurate predictions can be made from trace data, with varying degrees of personal or societal consequence (e.g., search engines predict hospital admission, gaming companies can predict compulsive gambling problems, government agencies predict criminal activity). Predicting human behavior can be both hugely beneficial and deeply problematic depending on the context. What kinds of predictive privacy harms are emerging? And what are the implications for systems of oversight and due process protections? For example, what are the implications for employment, health care and policing when predictive models are involved? How should varied organizations address what they can predict?

Advances In Piecewise Smooth Image Reconstruction, Ralf Juengling

Dissertations and Theses

Advances and new insights into algorithms for piecewise smooth image reconstruction are presented. Such algorithms fit a piecewise smooth function to image data without prior knowledge of the number of regions or the location of region boundaries in the best fitting function. This is a difficult model selection problem since the number of parameters of possible solutions varies widely.

The approach followed in this work was proposed by Yvan Leclerc. It uses the Minimum Description Length principle to make the reconstruction problem well-posed: the best fitting function yields the shortest encoding of the image data. In order to derive a …

L-Opacity: Linkage-Aware Graph Anonymization, Sadegh Nobari, Panagiotis Karras, Hwee Hwa Pang, Stephane Bressan

Research Collection School Of Computing and Information Systems

The wealth of information contained in online social networks has created a demand for the publication of such data as graphs. Yet, publication, even after identities have been removed, poses a privacy threat. Past research has suggested ways to publish graph data in a way that prevents the re-identification of nodes. However, even when identities are effectively hidden, an adversary may still be able to infer linkage between individuals with sufficiently high confidence. In this paper, we focus on the privacy threat arising from such link disclosure. We suggest L-opacity, a sufficiently strong privacy model that aims to control an …

Unstructured P2p Link Lifetimes Redux, Zhongmei Yao, Daren B. H. Cline

Computer Science Faculty Publications

We revisit link lifetimes in random P2P graphs under dynamic node failure and create a unifying stochastic model that generalizes the majority of previous efforts in this direction. We not only allow nonexponential user lifetimes and age-dependent neighbor selection, but also cover both active and passive neighbor-management strategies, model the lifetimes of incoming and outgoing links, derive churn-related message volume of the system, and obtain the distribution of transient in/out degree at each user. We then discuss the impact of design parameters on overhead and resilience of the network.

Digital Certificate Management: Optimal Pricing And Crl Releasing Strategies, Jie Zhang, Nan Hu, M. K. Raka

Research Collection School Of Computing and Information Systems

The fast growth of e-commerce and online activities places increasing needs for authentication and secure communication to enable information exchange and online transactions. The public key infrastructure (PKI) provides a promising foundation for meeting such demand, in which certificate authorities (CAs) provide digital certificates. In practice, it is critical to understand consumer purchasing and revocation behaviors so that CAs can better manage the digital certificates and its CRL releasing process. To address this problem, we analytically model a CA's pricing and revocation releasing strategies taking into consideration the users' rational decisions. The model provides solutions two main research questions: (1) …

A Fast Algorithm For The Inversion Of Quasiseparable Vandermonde-Like Matrices, Sirani M. Perera, Grigory Bonik, Vadim Olshevsky

Publications

The results on Vandermonde-like matrices were introduced as a generalization of polynomial Vandermonde matrices, and the displacement structure of these matrices was used to derive an inversion formula. In this paper we first present a fast Gaussian elimination algorithm for the polynomial Vandermonde-like matrices. Later we use the said algorithm to derive fast inversion algorithms for quasiseparable, semiseparable and well-free Vandermonde-like matrices having O(n2) complexity. To do so we identify structures of displacement operators in terms of generators and the recurrence relations(2-term and 3-term) between the columns of the basis transformation matrices for quasiseparable, semiseparable and well-free polynomials. Finally we …

Fast Algorithms For Analyzing Partially Ranked Data, Matthew Mcdermott

HMC Senior Theses

Imagine your local creamery administers a survey asking their patrons to choose their five favorite ice cream flavors. Any data collected by this survey would be an example of partially ranked data, as the set of all possible flavors is only ranked into subsets of the chosen flavors and the non-chosen flavors. If the creamery asks you to help analyze this data, what approaches could you take? One approach is to use the natural symmetries of the underlying data space to decompose any data set into smaller parts that can be more easily understood. In this work, I describe …

A Distributed Greedy Algorithm For Constructing Connected Dominating Sets In Wireless Sensor Networks, Akshaye Dhawan, Nicholas A. Scoville, Michelle Tanco

Mathematics, Computer Science & Statistics Faculty Publications

A Connected Dominating Set (CDS) of the graph representing a Wireless Sensor Network can be used as a virtual backbone for routing in the network. Since sensor nodes are constrained by limited on-board batteries, it is desirable to have a small CDS for the network. However, constructing a minimum size CDS has been shown to be a NP-hard problem. In this paper we present a distributed greedy algorithm for constructing a CDS that we call Greedy Connect. Our algorithm operates in two phases, first constructing a dominating set and then connecting the nodes in this set. We evaluate our algorithm …

Data Mining Based Hybridization Of Meta-Raps, Fatemah Al-Duoli, Ghaith Rabadi

Engineering Management & Systems Engineering Faculty Publications

Though metaheuristics have been frequently employed to improve the performance of data mining algorithms, the opposite is not true. This paper discusses the process of employing a data mining algorithm to improve the performance of a metaheuristic algorithm. The targeted algorithms to be hybridized are the Meta-heuristic for Randomized Priority Search (Meta-RaPS) and an algorithm used to create an Inductive Decision Tree. This hybridization focuses on using a decision tree to perform on-line tuning of the parameters in Meta-RaPS. The process makes use of the information collected during the iterative construction and improvement phases Meta-RaPS performs. The data mining algorithm …

Detection Of Seagrass Scars Using Sparse Coding And Morphological Filter, Ender Oguslu, Sertan Erkanli, Victoria J. Hill, W. Paul Bissett, Richard C. Zimmerman, Jiang Li, Charles R. Bostater Jr. (Ed.), Stelios P. Mertikas (Ed.), Xavier Neyt (Ed.)

OES Faculty Publications

We present a two-step algorithm for the detection of seafloor propeller seagrass scars in shallow water using panchromatic images. The first step is to classify image pixels into scar and non-scar categories based on a sparse coding algorithm. The first step produces an initial scar map in which false positive scar pixels may be present. In the second step, local orientation of each detected scar pixel is computed using the morphological directional profile, which is defined as outputs of a directional filter with a varying orientation parameter. The profile is then utilized to eliminate false positives and generate the final …