Numerical Analysis and Scientific Computing Commons^™

Two-View Transductive Support Vector Machines, Guangxia Li, Steven C. H. Hoi, Kuiyu Chang

Research Collection School Of Computing and Information Systems

Obtaining high-quality and up-to-date labeled data can be difficult in many real-world machine learning applications, especially for Internet classification tasks like review spam detection, which changes at a very brisk pace. For some problems, there may exist multiple perspectives, so called views, of each data sample. For example, in text classification, the typical view contains a large number of raw content features such as term frequency, while a second view may contain a small but highly-informative number of domain specific features. We thus propose a novel two-view transductive SVM that takes advantage of both the abundant amount of unlabeled data …

Mixed Operators In Compressed Sensing, Matthew A. Herman, Deanna Needell

CMC Faculty Publications and Research

Applications of compressed sensing motivate the possibility of using different operators to encode and decode a signal of interest. Since it is clear that the operators cannot be too different, we can view the discrepancy between the two matrices as a perturbation. The stability of L1-minimization and greedy algorithms to recover the signal in the presence of additive noise is by now well-known. Recently however, work has been done to analyze these methods with noise in the measurement matrix, which generates a multiplicative noise term. This new framework of generalized perturbations (i.e., both additive and multiplicative noise) extends the prior …

Pretty Lights, Nicholas (Nick) Delmas, Matthew (Matt) Maniaci

Computer Engineering

Digital media players often include a visualization component that allows a user to watch a visualization synchronized to their music or videos. This project uses the visualization plugin API of an existing media playback program (WinAmp) but it displays its visuals using physical LED lights. Instead of outputting visuals to the computer screen, data is sent over USB to a micro controller that runs the LED lights. This project aims to give users a more visceral visual experience than traditional visualizations on the computer screen.

A Genetic Algorithm Approach For Optimized Routing, Pavithra Gudur

Electrical & Computer Engineering Theses & Dissertations

Genetic Algorithms find several applications in a variety of fields, such as engineering, management, finance, chemistry, scheduling, data mining and so on, where optimization plays a key role. This technique represents a numerical optimization technique that is modeled after the natural process of selection based on the Darwinian principle of evolution. The Genetic Algorithm (GA) is one among several optimization techniques and attempts to obtain the desired solution by generating a set of possible candidate solutions or populations. These populations are then compared and the best solutions from the set are retained. Subsequently, new candidate solutions are produced, and the …

Continuous Spatial Assignment Of Moving Users, Hou U Leong, Kyriakos Mouratidis, Nikos Mamoulis

Research Collection School Of Computing and Information Systems

Consider a set of servers and a set of users, where each server has a coverage region (i.e., an area of service) and a capacity (i.e., a maximum number of users it can serve). Our task is to assign every user to one server subject to the coverage and capacity constraints. To offer the highest quality of service, we wish to minimize the average distance between users and their assigned server. This is an instance of a well-studied problem in operations research, termed optimal assignment. Even though there exist several solutions for the static case (where user locations are fixed), …

Information Search Patterns In E-Commerce Product Comparison Services, Fiona Fui-Hoon Nah, Weiyin Hong, Liqiang Chen, Hong-Hee Lee

Research Collection School Of Computing and Information Systems

To facilitate product selection and purchase decisions on e-commerce Web sites, the presentation of product information is very important. In this research, the authors study how disposition styles influence users’ search patterns in product comparison services of e-commerce Web sites. The results show that people use relatively more feature paths and less product paths in vertical disposition style than horizontal disposition style. The findings also indicate that there are relatively more feature paths and less product paths in the first half than second half of the information search paths. This is consistent with Gensch’s two-stage choice model which suggests that …

Optimal Matching Between Spatial Datasets Under Capacity Constraints, Hou U Leong, Kyriakos Mouratidis, Man Lung Yiu, Nikos Mamoulis

Research Collection School Of Computing and Information Systems

Consider a set of customers (e.g., WiFi receivers) and a set of service providers (e.g., wireless access points), where each provider has a capacity and the quality of service offered to its customers is anti-proportional to their distance. The capacity constrained assignment (CCA) is a matching between the two sets such that (i) each customer is assigned to at most one provider, (ii) every provider serves no more customers than its capacity, (iii) the maximum possible number of customers are served, and (iv) the sum of Euclidean distances within the assigned provider-customer pairs is minimized. Although max-flow algorithms are applicable …

What Is Twitter, A Social Network Or A News Media?, Haewoon Kwak, Changhyun Lee, Hosung: Moon Park

Research Collection School Of Computing and Information Systems

Twitter, a microblogging service less than three years old, commands more than 41 million users as of July 2009 and is growing fast. Twitter users tweet about any topic within the 140-character limit and follow others to receive their tweets. The goal of this paper is to study the topological characteristics of Twitter and its power as a new medium of information sharing.We have crawled the entire Twitter site and obtained 41.7 million user profiles, 1.47 billion social relations, 4,262 trending topics, and 106 million tweets. In its follower-following topology analysis we have found a non-power-law follower distribution, a short …

Mining Diversity On Networks, Lu Liu, Feida Zhu, Chen Chen, Xifeng Yan, Jiawei Han, Philip Yu, Shiqiang Yang

Research Collection School Of Computing and Information Systems

Despite the recent emergence of many large-scale networks in different application domains, an important measure that captures a participant’s diversity in the network has been largely neglected in previous studies. Namely, diversity characterizes how diverse a given node connects with its peers. In this paper, we give a comprehensive study of this concept. We first lay out two criteria that capture the semantic meaning of diversity, and then propose a compliant definition which is simple enough to embed the idea. An efficient top-k diversity ranking algorithm is developed for computation on dynamic networks. Experiments on both synthetic and real datasets …

Algorithms For Constrained K-Nearest Neighbor Queries Over Moving Object Trajectories, Yunjun Gao, Baihua Zheng, Gencai Chen, Qing Li, Chun Chen

Research Collection School Of Computing and Information Systems

An important query for spatio-temporal databases is to find nearest trajectories of moving objects. Existing work on this topic focuses on the closest trajectories in the whole data space. In this paper, we introduce and solve constrained k-nearest neighbor (CkNN) queries and historical continuous CkNN (HCCkNN) queries on R-tree-like structures storing historical information about moving object trajectories. Given a trajectory set D, a query object (point or trajectory) q, a temporal extent T, and a constrained region CR, (i) a CkNN query over trajectories retrieves from D within T, the k (≥ 1) trajectories that lie closest to q and …

Do You Trust To Get Trust? A Study Of Trust Reciprocity Behaviors And Reciprocal Trust Prediction, Viet-An Nguyen, Ee Peng Lim, Hwee Hoon Tan, Jing Jiang, Aixin Sun

Research Collection School Of Computing and Information Systems

Trust reciprocity, a special form of link reciprocity, exists in many networks of trust among users. In this paper, we seek to determine the extent to which reciprocity exists in a trust network and develop quantitative models for measuring reciprocity and reciprocity related behaviors. We identify several reciprocity behaviors and their respective measures. These behavior measures can be employed for predicting if a trustee will return trust to her trustor given that the latter initiates a trust link earlier. We develop for this reciprocal trust prediction task a number of ranking method and classification methods, and evaluated them on an …

Policy-Driven Distributed And Collaborative Demand Response In Multi-Domain Commercial Buildings, Archan Misra, Henning Schulzrinne

Research Collection School Of Computing and Information Systems

Enabling a sophisticated Demand Response (DR) framework, whereby individual consumers adapt their electricity consumption in response to price variations, is a major objective of the emerging Smart Grid. We first point out why the current model, of EMS-based centralized control of a static repository of high load appliances, is inappropriate for supporting DR in future commercial buildings and campuses, where the consuming appliances are controlled by multiple users. To enable DR in such multi-domain environments, we envision a more collaborative and autonomous model, where a large set of heterogeneous smart electrical devices autonomously self-organize and negotiate their collective DR. Enabling …

Data Mining Based Predictive Models For Overall Health Indices, Ridhima Rajkumar, Kyong Jin Shim, Jaideep Srivastava

Research Collection School Of Computing and Information Systems

In this study, we infer health care indices of individuals using their pharmacy medical and prescription claims. Specifically, we focus on the widely used Charlson Index. We use data mining techniques to formulate the problem of classifying Charlson Index (CI) and build predictive models to predict individual health index score. First, we present comparative analyses of several classification algorithms. Second, our study shows that certain ensemble algorithms lead to higher prediction accuracy in comparison to base algorithms. Third, we introduce cost-sensitive learning to the classification algorithms and show that the inclusion of cost-sensitive learning leads to improved prediction accuracy. The …

Finding Influentials Based On The Temporal Order Of Information Adoption In Twitter, Changhyun Lee, Haewoon Kwak, Hosung Park, Sue Moon

Research Collection School Of Computing and Information Systems

Twitter offers an explicit mechanism to facilitate information diffusion and has emerged as a new medium for communication. Many approaches to find influentials have been proposed, but they do not consider the temporal order of information adoption. In this work, we propose a novel method to find influentials by considering both the link structure and the temporal order of information adoption in Twitter. Our method finds distinct influentials who are not discovered by other methods.

Time Dependent Channel Packet Calculation Of Two Nucleon Scattering Matrix Elements, Brian S. Davis

Theses and Dissertations

A new approach to calculating nucleon-nucleon scattering matrix elements using a proven atomic time-dependent wave packet technique is investigated. Wave packets containing centripetal barrier information are prepared in close proximity to nuclear well. This is accomplished by first using an analytic equation to determine the wave packets in a suitable intermediate asymptotic state where the centripetal barrier is negligible. Then, the split operator technique is used to propagate the wave packets back to their original positions under the full Hamiltonian. Here, one wave packet is held stationary while the other is allowed to evolve and explore the nuclear well. Scattering …

Software Internationalization: A Framework Validated Against Industry Requirements For Computer Science And Software Engineering Programs, John Huân Vũ

Master's Theses

View John Huân Vũ's thesis presentation at http://youtu.be/y3bzNmkTr-c.

In 2001, the ACM and IEEE Computing Curriculum stated that it was necessary to address "the need to develop implementation models that are international in scope and could be practiced in universities around the world." With increasing connectivity through the internet, the move towards a global economy and growing use of technology places software internationalization as a more important concern for developers. However, there has been a "clear shortage in terms of numbers of trained persons applying for entry-level positions" in this area. Eric Brechner, Director of Microsoft Development Training, suggested …

Top-K Aggregation Queries Over Large Networks, Xifeng Yan, Bin He, Feida Zhu, Jiawei Han

Research Collection School Of Computing and Information Systems

Searching and mining large graphs today is critical to a variety of application domains, ranging from personalized recommendation in social networks, to searches for functional associations in biological pathways. In these domains, there is a need to perform aggregation operations on large-scale networks. Unfortunately the existing implementation of aggregation operations on relational databases does not guarantee superior performance in network space, especially when it involves edge traversals and joins of gigantic tables. In this paper, we investigate the neighborhood aggregation queries: Find nodes that have top-k highest aggregate values over their h-hop neighbors. While these basic queries are common in …

Preference Queries In Large Multi-Cost Transportation Networks, Kyriakos Mouratidis, Yimin Lin, Man Lung Yiu

Research Collection School Of Computing and Information Systems

Research on spatial network databases has so far considered that there is a single cost value associated with each road segment of the network. In most real-world situations, however, there may exist multiple cost types involved in transportation decision making. For example, the different costs of a road segment could be its Euclidean length, the driving time, the walking time, possible toll fee, etc. The relative significance of these cost types may vary from user to user. In this paper we consider such multi-cost transportation networks (MCN), where each edge (road segment) is associated with multiple cost values. We formulate …

Local Coordination Under Bounded Rationality: Coase Meets Simon, Finds Hayek, C. Jason Woodard

Research Collection School Of Computing and Information Systems

This paper explores strategic behavior in a network of firms using an agent-based model. The model exhibits a tension between economic efficiency and the stability of the network in the face of incentives to change its configuration. This tension is to be expected because the conditions of the Coase theorem are violated: the boundedly rational firms in the model lack the ability to discover efficient network configurations or achieve them through collective action. In computational experiments, as predicted by theory, firms frequently became locked into inefficient outcomes or endless cycles of mutual frustration. However, simple institutional innovations such as property …

Fuzzy Matching Of Web Queries To Structured Data, Tao Cheng, Hady W. Lauw, Stelios Paparizos

Research Collection School Of Computing and Information Systems

Recognizing the alternative ways people use to reference an entity, is important for many Web applications that query structured data. In such applications, there is often a mismatch between how content creators describe entities and how different users try to retrieve them. In this paper, we consider the problem of determining whether a candidate query approximately matches with an entity. We propose an off-line, data-driven, bottom-up approach that mines query logs for instances where Web content creators and Web users apply a variety of strings to refer to the same Web pages. This way, given a set of strings that …

Homophily In The Digital World: A Livejournal Case Study, Hady W. Lauw, John C. Shafer, Rakesh Agrawal, Alexandros Ntoulas

Research Collection School Of Computing and Information Systems

Are two users more likely to be friends if they share common interests? Are two users more likely to share common interests if they're friends? The authors study the phenomenon of homophily in the digital world by answering these central questions. Unlike the physical world, the digital world doesn't impose any geographic or organizational constraints on friendships. So, although online friends might share common interests, a priori there's no reason to believe that two users with common interests are more likely to be friends. Using data from LiveJournal, the authors show that the answer to both questions is yes.

Efficient Verification Of Shortest Path Search Via Authenticated Hints, Man Lung Yiu, Yimin Lin, Kyriakos Mouratidis

Research Collection School Of Computing and Information Systems

Shortest path search in transportation networks is unarguably one of the most important online search services nowadays (e.g., Google Maps, MapQuest, etc), with applications spanning logistics, spatial optimization, or everyday driving decisions. Often times, the owner of the road network data (e.g., a transport authority) provides its database to third-party query services, which are responsible for answering shortest path queries posed by their clients. The issue arising here is that a query service might be returning sub-optimal paths either purposely (in order to serve its own purposes like computational savings or commercial reasons) or because it has been compromised by …

K-Anonymity In The Presence Of External Databases, Dimitris Sacharidis, Kyriakos Mouratidis, Dimitris Papadias

Research Collection School Of Computing and Information Systems

The concept of k-anonymity has received considerable attention due to the need of several organizations to release microdata without revealing the identity of individuals. Although all previous k-anonymity techniques assume the existence of a public database (PD) that can be used to breach privacy, none utilizes PD during the anonymization process. Specifically, existing generalization algorithms create anonymous tables using only the microdata table (MT) to be published, independently of the external knowledge available. This omission leads to high information loss. Motivated by this observation we first introduce the concept of k-join-anonymity (KJA), which permits more effective generalization to reduce the …

Symphony: A Platform For Search-Driven Applications, John C. Shafer, Rakesh Agrawal, Hady W. Lauw

Research Collection School Of Computing and Information Systems

We present the design of Symphony, a platform that enables non-developers to build and deploy a new class of search-driven applications that combine their data and domain expertise with content from search engines and other web services. The Symphony prototype has been built on top of Microsoft's Bing infrastructure. While Symphony naturally makes use of the customization capabilities exposed by Bing, its distinguishing feature is the capability it provides to the application creator to combine their proprietary data and domain expertise with content obtained from Bing. They can also integrate specialized data obtained from web services to enhance the richness …

Efficient Valid Scope For Location-Dependent Spatial Queries In Mobile Environments, Ken C. K. Lee, Wang-Chien Lee, Hong Va Leong, Brandon Unger, Baihua Zheng

Research Collection School Of Computing and Information Systems

In mobile environments, mobile clients can access information with respect to their locations by submitting Location-Dependent Spatial Queries (LDSQs) to Location-Based Service (LBS) servers. Owing to scarce wireless channel bandwidth and limited client battery life, frequent LDSQ submission from clients must be avoided. Observing that LDSQs issued from a client located at nearby positions would likely return the same query results, we explore the idea of valid scope, which represents a spatial area in which a set of LDSQs will retrieve exactly the same set of query results. With a valid scope derived and an LDSQ result cached, a client …

Twitterrank: Finding Topic-Sensitive Influential Twitterers, Jianshu Weng, Ee Peng Lim, Jing Jiang, Qi He

Research Collection School Of Computing and Information Systems

This paper focuses on the problem of identifying influential users of micro-blogging services. Twitter, one of the most notable micro-blogging services, employs a social-networking model called "following", in which each user can choose who she wants to "follow" to receive tweets from without requiring the latter to give permission first. In a dataset prepared for this study, it is observed that (1) 72.4% of the users in Twitter follow more than 80% of their followers, and (2) 80.5% of the users have 80% of users they are following follow them back. Our study reveals that the presence of "reciprocity" can …

Estimating The Quality Of Postings In The Real-Time Web, Hady W. Lauw, Alexandros Ntoulas, Krishnaram Kenthapadi

Research Collection School Of Computing and Information Systems

Millions of users are posting their status updates, interesting findings, news, ideas and observations in real-time on microblogging services such as Twitter, Jaiku and Plurk. This real-time Web can be a great resource of valuable timely information. Since the real-time Web is completely open and decentralized and anyone may post information at whim, distinguishing interesting and popular postings from the mundane ones is a challenging task. In this paper we study the problem of estimating the quality (or “interestingness”) of postings in the real-time Web. We identify several important factors that are indicative of the quality of postings, and present …

Privacy-Preserving Similarity-Based Text Retrieval, Hwee Hwa Pang, Jialie Shen, Ramayya Krishnan

Research Collection School Of Computing and Information Systems

Users of online services are increasingly wary that their activities could disclose confidential information on their business or personal activities. It would be desirable for an online document service to perform text retrieval for users, while protecting the privacy of their activities. In this article, we introduce a privacy-preserving, similarity-based text retrieval scheme that (a) prevents the server from accurately reconstructing the term composition of queries and documents, and (b) anonymizes the search results from unauthorized observers. At the same time, our scheme preserves the relevance-ranking of the search server, and enables accounting of the number of documents that each …

Player Performance Prediction In Massively Multiplayer Online Role-Playing Games (Mmorpgs), Kyong Jin Shim, Richa Sharan, Jaideep Srivastava

Research Collection School Of Computing and Information Systems

Recent years have seen an ever increasing number of people interacting in the online space. Massively multiplayer online role-playing games (MMORPGs) are personal computer or console-based digital games where thousands of players can simultaneously sign on to the same online, persistent virtual world to interact and collaborate with each other through their in-game characters. In recent years, researchers have found virtual environments to be a sound venue for studying learning, collaboration, social participation, literacy in online space, and learning trajectory at the individual level as well as at the group level. While many games today provide web and GUI-based reports …

Further Exploration On Relationship Between Crisp Sets And Fuzzy Sets, Zhaoxia Wang, Quan Wang, Ming Bai, Chen Zeng-Qiang, Zhen Sun

Research Collection School Of Computing and Information Systems

This paper employs the concept of fuzzify upgrade operator to describe the relationship between crisp sets, fuzzy sets and higher order fuzzy sets, such as type-2 fuzzy sets. Theory analysis and case studies demonstrate that a crisp set can be represented by a type-1 fuzzy set, a type-1 fuzzy set can be represented by a type-2 fuzzy set, and a type-n (n>=2) fuzzy set can be represented by a type-(n+1) (n>=2) fuzzy set. The fuzzify upgrade operator makes crisp sets, type-1 fuzzy sets, type-2 fuzzy sets and any fuzzy sets much more accessible to all readers. The relationship …