Theory and Algorithms Commons^™

Efficient Algorithms For Solving Aggregate Keyword Routing Problems, Qize Jiang, Weiwei Sun, Baihua Zheng, Kunjie Chen

Research Collection School Of Computing and Information Systems

With the emergence of smart phones and the popularity of GPS, the number of point of interest (POIs) is growing rapidly and spatial keyword search based on POIs has attracted significant attention. In this paper, we study a more sophistic type of spatial keyword searches that considers multiple query points and multiple query keywords, namely Aggregate Keyword Routing (AKR). AKR looks for an aggregate point m together with routes from each query point to m. The aggregate point has to satisfy the aggregate keywords, the routes from query points to the aggregate point have to pass POIs in order to …

Maximizing Multifaceted Network Influence, Yuchen Li, Ju Fan, George V. Ovchinnikov, Panagiotis Karras

Research Collection School Of Computing and Information Systems

An information dissemination campaign is often multifaceted, involving several facets or pieces of information disseminating from different sources. The question then arises, how should we assign such pieces to eligible sources so as to achieve the best viral dissemination results? Past research has studied the problem of Influence Maximization (IM), which is to select a set of k promoters that maximizes the expected reach of a message over a network. However, in this classical IM problem, each promoter spreads out the same unitary piece of information. In this paper, we propose the Optimal Influential Pieces Assignment (OIPA) problem, which is …

Mirai Bot Scanner Summation Prototype, Charles V. Frank Jr.

Masters Theses & Doctoral Dissertations

The Mirai botnet deploys a distributed mechanism with each Bot continually scanning for a potential new Bot Victim. A Bot continually generates a random IP address to scan the network for discovering a potential new Bot Victim. The Bot establishes a connection with the potential new Bot Victim with a Transmission Control Protocol (TCP) handshake. The Mirai botnet has recruited hundreds of thousands of Bots. With 100,000 Bots, Mirai Distributed Denial of Service (DDoS) attacks on service provider Dyn in October 2016 triggered the inaccessibility to hundreds of websites in Europe and North America (Sinanović & Mrdovic, 2017). A month …

Semantic And Influence Aware K-Representative Queries Over Social Streams, Yanhao Wang, Yuchen Li, Kianlee Tan

Research Collection School Of Computing and Information Systems

Massive volumes of data continuously generated on social platforms have become an important information source for users. A primary method to obtain fresh and valuable information from social streams is social search. Although there have been extensive studies on social search, existing methods only focus on the relevance of query results but ignore the representativeness. In this paper, we propose a novel Semantic and Influence aware k-Representative (k-SIR) query for social streams based on topic modeling. Specifically, we consider that both user queries and elements are represented as vectors in the topic space. A k-SIR query retrieves a set of …

Send Hardest Problems My Way: Probabilistic Path Prioritization For Hybrid Fuzzing, Lei Zhao, Yue Duan, Jifeng Xuan

Research Collection School Of Computing and Information Systems

Hybrid fuzzing which combines fuzzing and concolic execution has become an advanced technique for software vulnerability detection. Based on the observation that fuzzing and concolic execution are complementary in nature, the state-of-the-art hybrid fuzzing systems deploy ``demand launch'' and ``optimal switch'' strategies. Although these ideas sound intriguing, we point out several fundamental limitations in them, due to oversimplified assumptions. We then propose a novel ``discriminative dispatch'' strategy to better utilize the capability of concolic execution. We design a novel Monte Carlo based probabilistic path prioritization model to quantify each path's difficulty and prioritize them for concolic execution. This model treats …

Dish: Democracy In State Houses, Nicholas A. Russo

Master's Theses

In our current political climate, state level legislators have become increasingly impor- tant. Due to cuts in funding and growing focus at the national level, public oversight for these legislators has drastically decreased. This makes it difficult for citizens and activists to understand the relationships and commonalities between legislators. This thesis provides three contributions to address this issue. First, we created a data set containing over 1200 features focused on a legislator’s activity on bills. Second, we created embeddings that represented a legislator’s level of activity and engagement for a given bill using a custom model called Democracy2Vec. Third, we …

Improving Vix Futures Forecasts Using Machine Learning Methods, James Hosker, Slobodan Djurdjevic, Hieu Nguyen, Robert Slater

SMU Data Science Review

The problem of forecasting market volatility is a difficult task for most fund managers. Volatility forecasts are used for risk management, alpha (risk) trading, and the reduction of trading friction. Improving the forecasts of future market volatility assists fund managers in adding or reducing risk in their portfolios as well as in increasing hedges to protect their portfolios in anticipation of a market sell-off event. Our analysis compares three existing financial models that forecast future market volatility using the Chicago Board Options Exchange Volatility Index (VIX) to six machine/deep learning supervised regression methods. This analysis determines which models provide best …

The Global Disinformation Order: 2019 Global Inventory Of Organised Social Media Manipulation, Samantha Bradshaw, Philip N. Howard

Copyright, Fair Use, Scholarly Communication, etc.

Executive Summary

Over the past three years, we have monitored the global organization of social media manipulation by governments and political parties. Our 2019 report analyses the trends of computational propaganda and the evolving tools, capacities, strategies, and resources.

1. Evidence of organized social media manipulation campaigns which have taken place in 70 countries, up from 48 countries in 2018 and 28 countries in 2017. In each country, there is at least one political party or government agency using social media to shape public attitudes domestically.

2.Social media has become co-opted by many authoritarian regimes. In 26 countries, computational propaganda …

Learning To Map The Visual And Auditory World, Tawfiq Salem

Theses and Dissertations--Computer Science

The appearance of the world varies dramatically not only from place to place but also from hour to hour and month to month. Billions of images that capture this complex relationship are uploaded to social-media websites every day and often are associated with precise time and location metadata. This rich source of data can be beneficial to improve our understanding of the globe. In this work, we propose a general framework that uses these publicly available images for constructing dense maps of different ground-level attributes from overhead imagery. In particular, we use well-defined probabilistic models and a weakly-supervised, multi-task training …

Building Recommendation Systems, Orion Davis

Williams Honors College, Honors Research Projects

Recommendation systems are pieces of software that suggest new items to a user. There are many moving parts to these systems including data, the actual recommendation model, processing data and finally displaying data. This project explores the role each part plays in the overall system and how to develop a recommendation system for beer from scratch. This project highlights the algorithm behind the recommendations and a user facing Android application.

Absorption Calculator: A Cross-Platform Application For Portable Data Analysis, Annmarie Kolbl

Williams Honors College, Honors Research Projects

Traditional spectrometers are expensive and non-portable, making them inaccessible to the public. This application will be used in conjunction with spectrometer hardware developed by Erie Open Systems. The hardware itself is 3D printed and, in addition to being portable, enables data to be collected easily. The purpose of this project is to create a cross-platform application capable of reading the output from the spectrometer hardware, calculating the absorbance levels of the sample against the control, and recording the data in tables stored on the cloud. The end result will be an application that runs on iOS and Android, and is …

Large Scale Online Multiple Kernel Regression With Application To Time-Series Prediction, Doyen Sahoo, Steven C. H. Hoi, Bin Lin

Research Collection School Of Computing and Information Systems

Kernel-based regression represents an important family of learning techniques for solving challenging regression tasks with non-linear patterns. Despite being studied extensively, most of the existing work suffers from two major drawbacks as follows: (i) they are often designed for solving regression tasks in a batch learning setting, making them not only computationally inefficient and but also poorly scalable in real-world applications where data arrives sequentially; and (ii) they usually assume that a fixed kernel function is given prior to the learning task, which could result in poor performance if the chosen kernel is inappropriate. To overcome these drawbacks, this work …

Unsupervised User Identity Linkage Via Factoid Embedding, Wei Xie, Xin Mu, Roy Ka Wei Lee, Feida Zhu, Ee-Peng Lim

Research Collection School Of Computing and Information Systems

User identity linkage (UIL), the problem of matching user account across multiple online social networks (OSNs), is widely studied and important to many real-world applications. Most existing UIL solutions adopt a supervised or semisupervised approach which generally suffer from scarcity of labeled data. In this paper, we propose Factoid Embedding, a novel framework that adopts an unsupervised approach. It is designed to cope with different profile attributes, content types and network links of different OSNs. The key idea is that each piece of information about a user identity describes the real identity owner, and thus distinguishes the owner from other …

Influence Maximization On Social Graphs: A Survey, Yuchen Li, Ju Fan, Yanhao Wang, Kian-Lee Tan

Research Collection School Of Computing and Information Systems

Influence Maximization (IM), which selects a set of k users (called seed set) from a social network to maximize the expected number of influenced users (called influence spread), is a key algorithmic problem in social influence analysis. Due to its immense application potential and enormous technical challenges, IM has been extensively studied in the past decade. In this paper, we survey and synthesize a wide spectrum of existing studies on IM from an algorithmic perspective, with a special focus on the following key aspects (1) a review of well-accepted diffusion models that capture information diffusion process and build the foundation …

An Outlier Detection Algorithm Based On Cross-Correlation Analysis For Time Series Dataset, Hui Lu, Yaxian Liu, Zongming Fei, Chongchong Guan

Computer Science Faculty Publications

Outlier detection is a very essential problem in a variety of application areas. Many detection methods are deficient for high-dimensional time series data sets containing both isolated and assembled outliers. In this paper, we propose an Outlier Detection method based on Cross-correlation Analysis (ODCA). ODCA consists of three key parts. They are data preprocessing, outlier analysis, and outlier rank. First, we investigate a linear interpolation method to convert assembled outliers into isolated ones. Second, a detection mechanism based on the cross-correlation analysis is proposed for translating the high-dimensional data sets into 1-D cross-correlation function, according to which the isolated outlier …

Question-Guided Hybrid Convolution For Visual Question Answering, Peng Gao, Pan Lu, Hongsheng Li, Shuang Li, Yikang Li, Steven C. H. Hoi, Xiaogang Wang

Research Collection School Of Computing and Information Systems

In this paper, we propose a novel Question-Guided Hybrid Convolution (QGHC) network for Visual Question Answering (VQA). Most state-of-the-art VQA methods fuse the high-level textual and visual features from the neural network and abandon the visual spatial information when learning multi-modal features.To address these problems, question-guided kernels generated from the input question are designed to convolute with visual features for capturing the textual and visual relationship in the early stage. The question-guided convolution can tightly couple the textual and visual information but also introduce more parameters when learning kernels. We apply the group convolution, which consists of question-independent kernels and …

Expected Length Of The Longest Chain In Linear Hashing, Pongthip Srivarangkul, Hemanta K. Maji

The Summer Undergraduate Research Fellowship (SURF) Symposium

Hash table with chaining is a data structure that chains objects with identical hash values together with an entry or a memory address. It works by calculating a hash value from an input then placing the input in the hash table entry. When we place two inputs in the same entry, they chain together in a linear linked list. We are interested in the expected length of the longest chain in linear hashing and methods to reduce the length because the worst-case look-up time is directly proportional to it.

The linear hash function used to calculate hash value is defined …

Exact Processing Of Uncertain Top-K Queries In Multi-Criteria Settings, Kyriakos Mouratidis, Bo Tang

Research Collection School Of Computing and Information Systems

Traditional rank-aware processing assumes a dataset that contains available options to cover a specific need (e.g., restaurants, hotels, etc) and users who browse that dataset via top-k queries with linear scoring functions, i.e., by ranking the options according to the weighted sum of their attributes, for a set of given weights. In practice, however, user preferences (weights) may only be estimated with bounded accuracy, or may be inherently uncertain due to the inability of a human user to specify exact weight values with absolute accuracy. Motivated by this, we introduce the uncertain top-k query (UTK). Given uncertain preferences, that is, …

Embedding Wordnet Knowledge For Textual Entailment, Yunshi Lan, Jing Jiang

Research Collection School Of Computing and Information Systems

In this paper, we study how we can improve a deep learning approach to textual entailment by incorporating lexical entailment relations from WordNet. Our idea is to embed the lexical entailment knowledge contained in WordNet in specially-learned word vectors, which we call “entailment vectors.” We present a standard neural network model and a novel set-theoretic model to learn these entailment vectors from word pairs with known lexical entailment relations derived from WordNet. We further incorporate these entailment vectors into a decomposable attention model for textual entailment and evaluate the model on the SICK and the SNLI dataset. We find that …

Machine Learning To Predict College Course Success, Anthony R.Y. Dalton, Justin Beer, Sriharshasai Kommanapalli, James S. Lanich Ph.D.

SMU Data Science Review

In this paper, we present an analysis of the predictive ability of machine learning on the success of students in college courses in a California Community College. The California Legislature passed assembly bill 705 in order to place students in non-remedial coursework, based on high school transcripts, to increase college completion. We utilize machine learning methods on de-identified student high school transcript data to create predictive algorithms on whether or not the student will be successful in college-level English and Mathematics coursework. To satisfy the bill’s requirements, we first use exploratory data analysis on applicable transcript variables. Then we use …

A Bayesian Latent Variable Model Of User Preferences With Item Context, Aghiles Salah, Hady W. Lauw

Research Collection School Of Computing and Information Systems

Personalized recommendation has proven to be very promising in modeling the preference of users over items. However, most existing work in this context focuses primarily on modeling user-item interactions, which tend to be very sparse. We propose to further leverage the item-item relationships that may reflect various aspects of items that guide users’ choices. Intuitively, items that occur within the same “context” (e.g., browsed in the same session, purchased in the same basket) are likely related in some latent aspect. Therefore, accounting for the item’s context would complement the sparse user-item interactions by extending a user’s preference to other items …

Distributed K-Nearest Neighbor Queries In Metric Spaces, Xin Ding, Yuanliang Zhang, Lu Chen, Yunjun Gao, Baihua Zheng

Research Collection School Of Computing and Information Systems

Metric k nearest neighbor (MkNN) queries have applications in many areas such as multimedia retrieval, computational biology, and location-based services. With the growing volumes of data, a distributed method is required. In this paper, we propose an Asynchronous Metric Distributed System (AMDS), which uniformly partitions the data with the pivot-mapping technique to ensure the load balancing, and employs publish/subscribe communication model to asynchronously process large scale of queries. The employment of asynchronous processing model also improves robustness and efficiency of AMDS. In addition, we develop an efficient estimation based MkNN method using AMDS to improve the query efficiency. Extensive experiments …

Efficient Representative Subset Selection Over Sliding Windows, Yanhao Wang, Yuchen Li, Kian-Lee Tan

Research Collection School Of Computing and Information Systems

Representative subset selection (RSS) is an important tool for users to draw insights from massive datasets. Existing literature models RSS as submodular maximization to capture the "diminishing returns" property of representativeness, but often only has a single constraint, which limits its applications to many real-world problems. To capture the recency issue and support various constraints, we formulate dynamic RSS as maximizing submodular functions subject to general d -knapsack constraints (SMDK) over sliding windows. We propose a KnapWindow framework (KW) for SMDK. KW utilizes KnapStream (KS) for SMDK in append-only streams as a subroutine. It maintains a sequence of checkpoints and …

Online Active Learning With Expert Advice, Shuji Hao, Peiying Hu, Peilin Zhao, Steven C. H. Hoi, Chunyan Miao

Research Collection School Of Computing and Information Systems

In literature, learning with expert advice methods usually assume that a learner always obtain the true label of every incoming training instance at the end of each trial. However, in many real-world applications, acquiring the true labels of all instances can be both costly and time consuming, especially for large-scale problems. For example, in the social media, data stream usually comes in a high speed and volume, and it is nearly impossible and highly costly to label all of the instances. In this article, we address this problem with active learning with expert advice, where the ground truth of an …

The Effect Of Endgame Tablebases On Modern Chess Engines, Christopher D. Peterson

Computer Engineering

Modern chess engines have the ability to augment their evaluation by using massive tables containing billions of positions and their memorized solutions. This report examines the importance of these tables to better understand the circumstances under which they should be used. The analysis conducted in this paper empirically examines differences in size and speed of memorized positions and their impacts on engine strength. Using this technique, situations where memorized tables improve play (and situations where they do not) are discovered.

Efficient Reduced Bias Genetic Algorithm For Generic Community Detection Objectives, Aditya Karnam Gururaj Rao

Theses

The problem of community structure identification has been an extensively investigated area for biology, physics, social sciences, and computer science in recent years for studying the properties of networks representing complex relationships. Most traditional methods, such as K-means and hierarchical clustering, are based on the assumption that communities have spherical configurations. Lately, Genetic Algorithms (GA) are being utilized for efficient community detection without imposing sphericity. GAs are machine learning methods which mimic natural selection and scale with the complexity of the network. However, traditional GA approaches employ a representation method that dramatically increases the solution space to be searched by …

Modular Scheduling System For Westside School District, Tyler Bienhoff

Honors Program: Senior Projects (Public)

Westside School district offers a modular scheduling system for their high school that is more similar to a college schedule than the typical high school system. Due to the complexity of their master schedule each semester, there are no commercially available products that can assist in creating a schedule. Hence, this thesis discusses a scheduling algorithm and management system that was built specifically for Westside High School with the potential to be expanded for use by other interested schools. The first part of the paper is focused on gathering input from students and faculty for which courses and how many …

A Sliding-Window Framework For Representative Subset Selection, Yanhao Wang, Yuchen Li, Kian-Lee Tan

Research Collection School Of Computing and Information Systems

Representative subset selection (RSS) is an important tool for users to draw insights from massive datasets. A common approach is to model RSS as the submodular maximization problem because the utility of extracted representatives often satisfies the "diminishing returns" property. To capture the data recency issue and support different types of constraints in real-world problems, we formulate RSS as maximizing a submodular function subject to a d-knapsack constraint (SMDK) over sliding windows. Then, we propose a novel KnapWindow framework for SMDK. Theoretically, KnapWindow is 1-ε/1+d - approximate for SMDK and achieves sublinear complexity. Finally, we evaluate the efficiency and effectiveness …

Distributed Multi-Task Classification: A Decentralized Online Learning Approach, Chi Zhang, Peilin Zhao, Shuji Hao, Yeng Chai Soh, Bu Sung Lee, Chunyan Miao, Steven C. H. Hoi

Research Collection School Of Computing and Information Systems

Although dispersing one single task to distributed learning nodes has been intensively studied by the previous research, multi-task learning on distributed networks is still an area that has not been fully exploited, especially under decentralized settings. The challenge lies in the fact that different tasks may have different optimal learning weights while communication through the distributed network forces all tasks to converge to an unique classifier. In this paper, we present a novel algorithm to overcome this challenge and enable learning multiple tasks simultaneously on a decentralized distributed network. Specifically, the learning framework can be separated into two phases: (i) …

Cora: Commingled Remains And Analytics – An Open Community Ecosystem, Nicole Mcelroy, Ryan Ernst

UNO Student Research and Creative Activity Fair

Anthropologists at organizations such as the DPAA (Defense POW/MIA Accounting Agency) have the tough job of sorting through commingled remains of fallen soldiers. Under the direction of Professor Pawaskar at the College of IS&T, Ryan Ernst and I are currently developing a web application for the DPAA that will help them inventory the bones and record all the appropriate associations. After the inventory web application is built we will begin the analysis process using graph theory and other mathematical algorithms. This will ultimately help organizations like the DPAA get closer to the end goal of identifying fallen soldiers from commingled …