Databases and Information Systems Commons^™

Counting And Sampling Small Structures In Graph And Hypergraph Data Streams, Themistoklis Haris

Dartmouth College Undergraduate Theses

In this thesis, we explore the problem of approximating the number of elementary substructures called simplices in large k-uniform hypergraphs. The hypergraphs are assumed to be too large to be stored in memory, so we adopt a data stream model, where the hypergraph is defined by a sequence of hyperedges.

First we propose an algorithm that (ε, δ)-estimates the number of simplices using O(m^1+1/k / T) bits of space. In addition, we prove that no constant-pass streaming algorithm can (ε, δ)- approximate the number of simplices using less than O( m ^1+1/k / T ) bits of space. Thus …

A Configurable Social Network For Running Irb-Approved Experiments, Mihovil Mandic

Dartmouth College Undergraduate Theses

Our world has never been more connected, and the size of the social media landscape draws a great deal of attention from academia. However, social networks are also a growing challenge for the Institutional Review Boards concerned with the subjects’ privacy. These networks contain a monumental variety of personal information of almost 4 billion people, allow for precise social profiling, and serve as a primary news source for many users. They are perfect environments for influence operations that are becoming difficult to defend against. Motivated to study online social influence via IRB-approved experiments, we designed and implemented a flexible, scalable, …

Boosting Video Representation Learning With Multi-Faceted Integration, Zhaofan Qiu, Yao Ting, Chong-Wah Ngo, Xiao-Ping Zhang, Dong Wu, Tao Mei

Research Collection School Of Computing and Information Systems

Video content is multifaceted, consisting of objects, scenes, interactions or actions. The existing datasets mostly label only one of the facets for model training, resulting in the video representation that biases to only one facet depending on the training dataset. There is no study yet on how to learn a video representation from multifaceted labels, and whether multifaceted information is helpful for video representation learning. In this paper, we propose a new learning framework, MUlti-Faceted Integration (MUFI), to aggregate facets from different datasets for learning a representation that could reflect the full spectrum of video content. Technically, MUFI formulates the …

How-To Present News On Social Media: A Causal Analysis Of Editing News Headlines For Boosting User Engagement, Kunwoo Park, Haewoon Kwak, Jisun An, Sanjay Chawla

Research Collection School Of Computing and Information Systems

To reach a broader audience and optimize traffic toward news articles, media outlets commonly run social media accounts and share their content with a short text summary. Despite its importance of writing a compelling message in sharing articles, the research community does not own a sufficient understanding of what kinds of editing strategies effectively promote audience engagement. In this study, we aim to fill the gap by analyzing media outlets' current practices using a data-driven approach. We first build a parallel corpus of original news articles and their corresponding tweets that eight media outlets shared. Then, we explore how those …

Minimizing The Regret Of An Influence Provider, Yipeng Zhang, Yuchen Li, Zhifeng Bao, Baihua Zheng

Research Collection School Of Computing and Information Systems

Influence maximization has been studied extensively from the perspective of the influencer. However, the influencer typically purchases influence from a provider, for example in the form of purchased advertising. In this paper, we study the problem from the perspective of the influence provider. Specifically, we focus on influence providers who sell Out-of-Home (OOH) advertising on billboards. Given a set of requests from influencers, how should an influence provider allocate resources to minimize regret, whether due to forgone revenue from influencers whose needs were not met or due to over-provisioning of resources to meet the needs of influencers? We formalize this …

Gpu-Accelerated Graph Label Propagation For Real-Time Fraud Detection, Chang Ye, Yuchen Li, Bingsheng He, Zhao Li, Jianling Sun

Research Collection School Of Computing and Information Systems

Fraud detection is a pressing challenge for most financial and commercial platforms. In this paper, we study the processing pipeline of fraud detection in a large e-commerce platform of TaoBao. Graph label propagation (LP) is a core component in this pipeline to detect suspicious clusters from the user-interaction graph. Furthermore, the run-time of the LP component occupies 75% overhead of TaoBao’s automated detection pipeline. To enable real-time fraud detection, we propose a GPU-based framework, called GLP, to support large-scale LP workloads in enterprises. We have identified two key challenges when integrating GPU acceleration into TaoBao’s data processing pipeline: (1) programmability …

On M-Impact Regions And Standing Top-K Influence Problems, Bo Tang, Kyriakos Mouratidis, Mingji Han

Research Collection School Of Computing and Information Systems

In this paper, we study the ��-impact region problem (mIR). In a context where users look for available products with top-�� queries, mIR identifies the part of the product space that attracts the most user attention. Specifically, mIR determines the kind of attribute values that lead a (new or existing) product to the top-�� result for at least a fraction of the user population. mIR has several applications, ranging from effective marketing to product improvement. Importantly, it also leads to (exact and efficient) solutions for standing top-�� impact problems, which were previously solved heuristically only, or whose current solutions face …

An Economic Analysis Of Rebates Conditional On Positive Reviews, Jianqing Chen, Zhiling Guo, Jian Huang

Research Collection School Of Computing and Information Systems

Strategic sellers on some online selling platforms have recently been using a conditional-rebate strategy to manipulate product reviews under which only purchasing consumers who post positive reviews online are eligible to redeem the rebate. A key concern for the conditional rebate is that it can easily induce fake reviews, which might be harmful to consumers and society. We develop a microbehavioral model capturing consumers’ review-sharing benefit, review-posting cost, and moral cost of lying to examine the seller’s optimal pricing and rebate decisions. We derive three equilibria: the no-rebate, organic-review equilibrium; the low-rebate, boosted-authentic-review equilibrium; and the high-rebate, partially-fake-review equilibrium. We …

Multi-View Collaborative Network Embedding, Sezin Kircali Ata, Yuan Fang, Min Wu, Jiaqi Shi, Chee Keong Kwoh, Xiaoli Li

Research Collection School Of Computing and Information Systems

Real-world networks often exist with multiple views, where each view describes one type of interaction among a common set of nodes. For example, on a video-sharing network, while two user nodes are linked, if they have common favorite videos in one view, then they can also be linked in another view if they share common subscribers. Unlike traditional single-view networks, multiple views maintain different semantics to complement each other. In this article, we propose Multi-view collAborative Network Embedding (MANE), a multi-view network embedding approach to learn low-dimensional representations. Similar to existing studies, MANE hinges on diversity and collaboration—while diversity enables …

Catch You With Cache: Out-Of-Vm Introspection To Trace Malicious Executions, Chao Su, Xuhua Ding, Qinghai Zeng

Research Collection School Of Computing and Information Systems

Out-of-VM introspection is an imperative part of security analysis. The legacy methods either modify the system, introducing enormous overhead, or rely heavily on hardware features, which are neither available nor practical in most cloud environments. In this paper, we propose a novel analysis method, named as Catcher, that utilizes CPU cache to perform out-of-VM introspection. Catcher does not make any modifications to the target program and its running environment, nor demands special hardware support. Implemented upon Linux KVM, it natively introspects the target's virtual memory. More importantly, it uses the cache-based side channel to infer the target control flow. To …

Spatially-Invariant Style-Codes Controlled Makeup Transfer, Han Deng, Chu Han, Hongmin Cai, Guoqiang Han, Shengfeng He

Research Collection School Of Computing and Information Systems

Transferring makeup from the misaligned reference image is challenging. Previous methods overcome this barrier by computing pixel-wise correspondences between two images, which is inaccurate and computational-expensive. In this paper, we take a different perspective to break down the makeup transfer problem into a two-step extraction-assignment process. To this end, we propose a Style-based Controllable GAN model that consists of three components, each of which corresponds to target style-code encoding, face identity features extraction, and makeup fusion, respectively. In particular, a Part-specific Style Encoder encodes the component-wise makeup style of the reference image into a style-code in an intermediate latent space …

Riding Through The Silver Tsunami: A Data Driven Approach To Improve Senior Citizens’ Engagement With Community Senior Activity Centres, Joshua Jie Feng Lam, Hwee-Pink Tan

Research Collection School Of Computing and Information Systems

In Singapore, 1 in 4 persons will be elderly by 2030 In preparation for the Silver Tsunami, the Singapore government and community care providers have collaborations to promote active, independent living amongst elders Current implementation of data driven population health is focused on well being indices using data collected from the general population There is no literature on the use of data analytics in assessing elder

Minimum Coresets For Maxima Representation Of Multidimensional Data, Yanhao Wang, Michael Mathioudakis, Yuchen Li, Kian-Lee Tan

Research Collection School Of Computing and Information Systems

Coresets are succinct summaries of large datasets such that, for a given problem, the solution obtained from a coreset is provably competitive with the solution obtained from the full dataset. As such, coreset-based data summarization techniques have been successfully applied to various problems, e.g., geometric optimization, clustering, and approximate query processing, for scaling them up to massive data. In this paper, we study coresets for the maxima representation of multidimensional data: Given a set �� of points in R �� , where �� is a small constant, and an error parameter �� ∈ (0, 1), a subset �� ⊆ �� …

Hierarchical Reinforcement Learning: A Comprehensive Survey, Shubham Pateria, Budhitama Subagdja, Ah-Hwee Tan, Chai Quek

Research Collection School Of Computing and Information Systems

Hierarchical Reinforcement Learning (HRL) enables autonomous decomposition of challenging long-horizon decision-making tasks into simpler subtasks. During the past years, the landscape of HRL research has grown profoundly, resulting in copious approaches. A comprehensive overview of this vast landscape is necessary to study HRL in an organized manner. We provide a survey of the diverse HRL approaches concerning the challenges of learning hierarchical policies, subtask discovery, transfer learning, and multi-agent learning using HRL. The survey is presented according to a novel taxonomy of the approaches. Based on the survey, a set of important open problems is proposed to motivate the future …

Efficient Conditional Gan Transfer With Knowledge Propagation Across Classes, Shahbazi. Mohamad, Zhiwu Huang, Huang, Danda Pani Paudel, Ajad Chhatkuli, Gool L. Van

Research Collection School Of Computing and Information Systems

Generative adversarial networks (GANs) have shown impressive results in both unconditional and conditional image generation. In recent literature, it is shown that pre-trained GANs, on a different dataset, can be transferred to improve the image generation from a small target data. The same, however, has not been well-studied in the case of conditional GANs (cGANs), which provides new opportunities for knowledge transfer compared to unconditional setup. In particular, the new classes may borrow knowledge from the related old classes, or share knowledge among themselves to improve the training. This motivates us to study the problem of efficient conditional GAN transfer …

On Predicting Personal Values Of Social Media Users Using Community-Specific Language Features And Personal Value Correlation, Amila Silva, Pei Chi Lo, Ee-Peng Lim

Research Collection School Of Computing and Information Systems

Personal values have significant influence on individuals’ behaviors, preferences, and decision making. It is therefore not a surprise that personal values of a person could influence his or her social media content and activities. Instead of getting users to complete personal value questionnaire, researchers have looked into a non-intrusive and highly scalable approach to predict personal values using user-generated social media data. Nevertheless, geographical differences in word usage and profile information are issues to be addressed when designing such prediction models. In this work, we focus on analyzing Singapore users’ personal values, and developing effective models to predict their personal …

Cache-Efficient Fork-Processing Patterns On Large Graphs, Shengliang Lu, Shixuan Sun, Johns Paul, Yuchen Li, Bingsheng He

Research Collection School Of Computing and Information Systems

As large graph processing emerges, we observe a costly fork-processing pattern (FPP) that is common in many graph algorithms. The unique feature of the FPP is that it launches many independent queries from different source vertices on the same graph. For example, an algorithm in analyzing the network community profile can execute Personalized PageRanks that start from tens of thousands of source vertices at the same time. We study the efficiency of handling FPPs in state-of-the-art graph processing systems on multi-core architectures, including Ligra, Gemini, and GraphIt. We find that those systems suffer from severe cache miss penalty because of …

Self-Adaptive Graph Traversal On Gpus, Mo Sha, Yuchen Li, Kian-Lee Tan

Research Collection School Of Computing and Information Systems

GPU’s massive computing power offers unprecedented opportunities to enable large graph analysis. Existing studies proposed various preprocessing approaches that convert the input graphs into dedicated structures for GPU-based optimizations. However, these dedicated approaches incur significant preprocessing costs as well as weak programmability to build general graph applications. In this paper, we introduce SAGE, a self-adaptive graph traversal on GPUs, which is free from preprocessing and operates on ubiquitous graph representations directly. We propose Tiled Partitioning and Resident Tile Stealing to fully exploit the computing power of GPUs in a runtime and self-adaptive manner. We also propose Sampling-based Reordering to further …

Reciprocal Transformations For Unsupervised Video Object Segmentation, Sucheng Ren, Wenxi Liu, Yongtuo Liu, Haoxin Chen, Guoqiang Han, Shengfeng He

Research Collection School Of Computing and Information Systems

Unsupervised video object segmentation (UVOS) aims at segmenting the primary objects in videos without any human intervention. Due to the lack of prior knowledge about the primary objects, identifying them from videos is the major challenge of UVOS. Previous methods often regard the moving objects as primary ones and rely on optical flow to capture the motion cues in videos, but the flow information alone is insufficient to distinguish the primary objects from the background objects that move together. This is because, when the noisy motion features are combined with the appearance features, the localization of the primary objects is …

Learning From The Master: Distilling Cross-Modal Advanced Knowledge For Lip Reading, Sucheng Ren, Yong Du, Jianming Lv, Guoqiang Han, Shengfeng He

Research Collection School Of Computing and Information Systems

Lip reading aims to predict the spoken sentences from silent lip videos. Due to the fact that such a vision task usually performs worse than its counterpart speech recognition, one potential scheme is to distill knowledge from a teacher pretrained by audio signals. However, the latent domain gap between the cross-modal data could lead to a learning ambiguity and thus limits the performance of lip reading. In this paper, we propose a novel collaborative framework for lip reading, and two aspects of issues are considered: 1) the teacher should understand bi-modal knowledge to possibly bridge the inherent cross-modal gap; 2) …

Discovering Interpretable Latent Space Directions Of Gans Beyond Binary Attributes, Huiting Yang, Liangyu Chai, Qiang Wen, Shuang Zhao, Zixun Sun, Shengfeng He

Research Collection School Of Computing and Information Systems

Generative adversarial networks (GANs) learn to map noise latent vectors to high- fidelity image outputs. It is found that the input latent space shows semantic correlations with the output image space. Recent works aim to interpret the latent space and discover meaningful directions that correspond to human interpretable image transformations. However, these methods either rely on explicit scores of attributes (e.g., memorability) or are restricted to binary ones (e.g., gender), which largely limits the applicability of editing tasks, especially for free- form artistic tasks like style/anime editing. In this paper, we propose an adversarial method, AdvStyle, for discovering interpretable directions …

Ganmut: Learning Interpretable Conditional Space For A Gamut Of Emotions, S. D'Apolito, D.P. Paundel, Zhiwu Huang, A.R. Vergara, Gool L. Van

Research Collection School Of Computing and Information Systems

Humans can communicate emotions through a plethora of facial expressions, each with its own intensity, nuances and ambiguities. The generation of such variety by means of conditional GANs is limited to the expressions encoded in the used label system. These limitations are caused either due to burdensome labeling demand or the confounded label space. On the other hand, learning from inexpensive and intuitive basic categorical emotion labels leads to limited emotion variability. In this paper, we propose a novel GAN-based framework which learns an expressive and interpretable conditional space (usable as a label space) of emotions, instead of conditioning on …

Iquant: Interactive Quantitative Investment Using Sparse Regression Factors, Xuanwu Yue, Qiao Gu, Deyun Wang, Huamin Qu, Yong Wang

Research Collection School Of Computing and Information Systems

The model-based investing using financial factors is evolving as a principal method for quantitative investment. The main challenge lies in the selection of effective factors towards excess market returns. Existing approaches, either hand-picking factors or applying feature selection algorithms, do not orchestrate both human knowledge and computational power. This paper presents iQUANT, an interactive quantitative investment system that assists equity traders to quickly spot promising financial factors from initial recommendations suggested by algorithmic models, and conduct a joint refinement of factors and stocks for investment portfolio composition. We work closely with professional traders to assemble empirical characteristics of “good” factors …

Knowledge And Anxiety About Covid-19 In The State Of Qatar, And The Middle East And North Africa Region—A Cross Sectional Study, Sathyanarayanan Doraiswamy, Sohaila Cheema, Maisonneuve Patrick, Amit Abraham, Ingmar Weber, Jisun An, Albert B. Lowenfels, Ravinder Mamtani

Research Collection School Of Computing and Information Systems

While the coronavirus disease 2019 (COVID-19) pandemic wreaked havoc across the globe, we have witnessed substantial mis- and disinformation regarding various aspects of the disease. We conducted a cross-sectional study using a self-administered questionnaire for the general public (recruited via social media) and healthcare workers (recruited via email) from the State of Qatar, and the Middle East and North Africa region to understand the knowledge of and anxiety levels around COVID-19 (April–June 2020) during the early stage of the pandemic. The final dataset used for the analysis comprised of 1658 questionnaires (53.0% of 3129 received questionnaires; 1337 [80.6%] from the …

Prediction Of Sleep Quality In Live-Alone Diabetic Seniors Using Unobtrusive In-Home Sensors, Barry Nuqoba, Hwee-Pink Tan

Research Collection School Of Computing and Information Systems

Diabetes, a chronic disease that occurs when the pancreas does not produce enough insulin or when the body cannot effectively utilize its insulin, is increasingly recognized as a significant health burden and affects many older adults. Poor sleep quality in diabetic seniors worsens the diabetes condition, but most seniors are tend to regard poor sleep quality as a usual event and do not seek treatment. This study aims to detect poor sleep quality in diabetic seniors through passive in-home monitoring to inform intervention (e.g., seeking diagnosis and treatment) to improve the physical and mental health of diabetic seniors. We derive …

Virtual Reality For Hazard Mitigation And Community Resilience: An Interdisciplinary Collaboration With Community Engagement To Enhance Risk Awareness, N. J. Stone, G. Yan, Fiona Fui-Hoon Nah, C. Sabharwal, K. Angle, F. E. Hatch, S. Runnels, V. Brown, G. M. Schoor, C. Engelbrecht

Research Collection School Of Computing and Information Systems

To achieve community resilience and mitigate the consequences of natural hazards, community officials must balance competing priorities for local resources and funding. Besides the challenge of dealing with multiple competing priorities, community officials face another challenge: low risk awareness of natural hazards by the public and other stakeholders. Considering that virtual reality (VR) has been used to enhance learning and to change attitudes and behaviors, animating natural hazards in VR has the potential to enhance stakeholders’ (e.g., the public, local/state/federal governments, insurance agencies, and property owners) risk awareness. Informed stakeholders make better decisions related to protective action. Therefore, we propose …

Marrying Top-K With Skyline Queries: Relaxing The Preference Input While Producing Output Of Controllable Size, Kyriakos Mouratidis, Keming Li, Bo Tang

Research Collection School Of Computing and Information Systems

The two most common paradigms to identify records of preference in a multi-objective setting rely either on dominance (e.g., the skyline operator) or on a utility function defined over the records’ attributes (typically, using a top-�� query). Despite their proliferation, each of them has its own palpable drawbacks. Motivated by these drawbacks, we identify three hard requirements for practical decision support, namely, personalization, controllable output size, and flexibility in preference specification. With these requirements as a guide, we combine elements from both paradigms and propose two new operators, ORD and ORU. We perform a qualitative study to demonstrate how they …

Soarnet, Deep Learning Thermal Detection For Free Flight, Jake T. Tallman

Master's Theses

Thermals are regions of rising hot air formed on the ground through the warming of the surface by the sun. Thermals are commonly used by birds and glider pilots to extend flight duration, increase cross-country distance, and conserve energy. This kind of powerless flight using natural sources of lift is called soaring. Once a thermal is encountered, the pilot flies in circles to keep within the thermal, so gaining altitude before flying off to the next thermal and towards the destination. A single thermal can net a pilot thousands of feet of elevation gain, however estimating thermal locations is not …

Impact Of User Traversal On Performance Of Stem Learners In Immersive Virtual Environments, Eric W. Nersesian

Dissertations

The emerging technologies of augmented and virtual reality (AR/VR) may have vast implications to societal communication and representation of information. AR/VR computer interfaces are unique in that they may be placed spatially around the user in three-dimensional (3D) space; this affords new methods of both presentation and user interaction with the target information.

This may be especially impactful in the education of science, technology, engineering, and mathematics (STEM) professionals. Prior research has shown that simulations and visualizations improve the performance of STEM learners compared to live instruction and textbook reading. Yet, research into AR/VR as a learning environment for widespread …

Translating Natural Language Queries To Sparql, Shreya Satish Bhajikhaye

Master's Projects

The Semantic Web is an extensive knowledge base that contains facts in the form of RDF
triples. These facts are not easily accessible to the average user because to use them requires
an understanding of ontologies and a query language like SPARQL. Question answering systems
form a layer of abstraction on linked data to overcome these issues. These systems allow the
user to input a question in a natural language and receive the equivalent SPARQL query. The
user can then execute the query on the database to fetch the desired results. The standard
techniques involved in translating natural language questions …