OpenRaiser/Intern-Atlas huggingface dataset:
Estimating the Benefits of Electric Vehicle Smart Charging at Non-Residential Locations: A Data-Driven Approach
Venue: arXiv cs.SY 2015
Year: 2015

In this paper, we use data collected from over 2000 non-residential electric vehicle supply equipments (EVSEs) located in Northern California for the year of 2013 to estimate the potential benefits of smart electric vehicle (EV) charging. We develop a smart charging framework to identify the benefits of non-residential EV charging to the load aggregators and the distribution grid. Using this extensive dataset, we aim to improve upon past studies focusing on the benefits of smart EV charging by relaxing the assumptions made in these studies regarding: (i) driving patterns, driver behavior and driver types; (ii) the scalability of a limited number of simulated vehicles to represent different load aggregation points in the power system with different customer characteristics; and (iii) the charging profile of EVs. First, we study the benefits of EV aggregations behind-the-meter, where a time-of-use pricing schema is used to understand the benefits to the owner when EV aggregations shift load from high cost periods to lower cost periods. For the year of 2013, we show a reduction of up to 24.8% in the monthly bill is possible. Then, following a similar aggregation strategy, we show that EV aggregations decrease their contribution to the system peak load by approximately 40% when charging is controlled within arrival and departure times. Our results also show that it could be expected to shift approximately 0.25kWh (~2.8%) of energy per non-residential EV charging session from peak periods (12PM-6PM) to off-peak periods (after 6PM) in Northern California for the year of 2013.
An approach to computing downward closures
Venue: arXiv cs.FL 2015
Year: 2015

The downward closure of a word language is the set of all (not necessarily contiguous) subwords of its members. It is well-known that the downward closure of any language is regular. While the downward closure appears to be a powerful abstraction, algorithms for computing a finite automaton for the downward closure of a given language have been established only for few language classes. This work presents a simple general method for computing downward closures. For language classes that are closed under rational transductions, it is shown that the computation of downward closures can be reduced to checking a certain unboundedness property. This result is used to prove that downward closures are computable for (i) every language class with effectively semilinear Parikh images that are closed under rational transductions, (ii) matrix languages, and (iii) indexed languages (equivalently, languages accepted by higher-order pushdown automata of order 2).
Recognizing k-equistable graphs in FPT time
Venue: arXiv cs.DS 2015
Year: 2015

A graph $G = (V,E)$ is called equistable if there exist a positive integer $t$ and a weight function $w : V \to \mathbb{N}$ such that $S \subseteq V$ is a maximal stable set of $G$ if and only if $w(S) = t$. Such a function $w$ is called an equistable function of $G$. For a positive integer $k$, a graph $G = (V,E)$ is said to be $k$-equistable if it admits an equistable function which is bounded by $k$. We prove that the problem of recognizing $k$-equistable graphs is fixed parameter tractable when parameterized by $k$, affirmatively answering a question of Levit et al. In fact, the problem admits an $O(k^5)$-vertex kernel that can be computed in linear time.
Autonomous surveillance for biosecurity
Venue: arXiv cs.RO 2015
Year: 2015

The global movement of people and goods has increased the risk of biosecurity threats and their potential to incur large economic, social, and environmental costs. Conventional manual biosecurity surveillance methods are limited by their scalability in space and time. This article focuses on autonomous surveillance systems, comprising sensor networks, robots, and intelligent algorithms, and their applicability to biosecurity threats. We discuss the spatial and temporal attributes of autonomous surveillance technologies and map them to three broad categories of biosecurity threat: (i) vector-borne diseases; (ii) plant pests; and (iii) aquatic pests. Our discussion reveals a broad range of opportunities to serve biosecurity needs through autonomous surveillance.
Contract-Based Interference Coordination in Heterogeneous Cloud Radio Access Networks
Venue: arXiv cs.IT 2015
Year: 2015

Heterogeneous cloud radio access networks (HCRANs) are potential solutions to improve both spectral and energy efficiencies by embedding cloud computing into heterogeneous networks (HetNets). The interference among remote radio heads (RRHs) can be suppressed with centralized cooperative processing in the base band unit (BBU) pool, while the intertier interference between RRHs and macro base stations (MBSs) is still challenging in H-CRANs. In this paper, to mitigate this inter-tier interference, a contract-based interference coordination framework is proposed, where three scheduling schemes are involved, and the downlink transmission interval is divided into three phases accordingly. The core idea of the proposed framework is that the BBU pool covering all RRHs is selected as the principal that would offer a contract to the MBS, and the MBS as the agent decides whether to accept the contract or not according to an individual rational constraint. An optimal contract design that maximizes the rate-based utility is derived when perfect channel state information (CSI) is acquired at both principal and agent. Furthermore, contract optimization under the situation where only the partial CSI can be obtained from practical channel estimation is addressed as well. Monte Carlo simulations are provided to confirm the analysis, and simulation results show that the proposed framework can significantly increase the transmission data rates over baselines, thus demonstrating the effectiveness of the proposed contract-based solution.
Competitive Diffusion in Social Networks: Quality or Seeding?
Venue: arXiv cs.GT 2015
Year: 2015

In this paper, we study a strategic model of marketing and product consumption in social networks. We consider two firms in a market competing to maximize the consumption of their products. Firms have a limited budget which can be either invested on the quality of the product or spent on initial seeding in the network in order to better facilitate spread of the product. After the decision of firms, agents choose their consumptions following a myopic best response dynamics which results in a local, linear update for their consumption decision. We characterize the unique Nash equilibrium of the game between firms and study the effect of the budgets as well as the network structure on the optimal allocation. We show that at the equilibrium, firms invest more budget on quality when their budgets are close to each other. However, as the gap between budgets widens, competition in qualities becomes less effective and firms spend more of their budget on seeding. We also show that given equal budget of firms, if seeding budget is nonzero for a balanced graph, it will also be nonzero for any other graph, and if seeding budget is zero for a star graph it will be zero for any other graph as well. As a practical extension, we then consider a case where products have some preset qualities that can be only improved marginally. At some point in time, firms learn about the network structure and decide to utilize a limited budget to mount their market share by either improving the quality or new seeding some agents to incline consumers towards their products. We show that the optimal budget allocation in this case simplifies to a threshold strategy. Interestingly, we derive similar results to that of the original problem, in which preset qualities simulate the role that budgets had in the original setup.
Bethe Learning of Conditional Random Fields via MAP Decoding
Venue: arXiv cs.LG 2015
Year: 2015

Many machine learning tasks can be formulated in terms of predicting structured outputs. In frameworks such as the structured support vector machine (SVM-Struct) and the structured perceptron, discriminative functions are learned by iteratively applying efficient maximum a posteriori (MAP) decoding. However, maximum likelihood estimation (MLE) of probabilistic models over these same structured spaces requires computing partition functions, which is generally intractable. This paper presents a method for learning discrete exponential family models using the Bethe approximation to the MLE. Remarkably, this problem also reduces to iterative (MAP) decoding. This connection emerges by combining the Bethe approximation with a Frank-Wolfe (FW) algorithm on a convex dual objective which circumvents the intractable partition function. The result is a new single loop algorithm MLE-Struct, which is substantially more efficient than previous double-loop methods for approximate maximum likelihood estimation. Our algorithm outperforms existing methods in experiments involving image segmentation, matching problems from vision, and a new dataset of university roommate assignments.
Tensors, !-graphs, and non-commutative quantum structures (extended version)
Venue: arXiv cs.LO 2015
Year: 2015

!-graphs provide a means of reasoning about infinite families of string diagrams and have proven useful in manipulation of (co)algebraic structures like Hopf algebras, Frobenius algebras, and compositions thereof. However, they have previously been limited by an inability to express families of diagrams involving non-commutative structures which play a central role in algebraic quantum information and the theory of quantum groups. In this paper, we fix this shortcoming by offering a new semantics for non-commutative !-graphs using an enriched version of Penrose's abstract tensor notation.
Optimal Constructions for Chain-based Cryptographic Enforcement of Information Flow Policies
Venue: arXiv cs.CR 2015
Year: 2015

The simple security property in an information flow policy can be enforced by encrypting data objects and distributing an appropriate secret to each user. A user derives a suitable decryption key from the secret and publicly available information. A chain-based enforcement scheme provides an alternative method of cryptographic enforcement that does not require any public information, the trade-off being that a user may require more than one secret. For a given information flow policy, there will be many different possible chain-based enforcement schemes. In this paper, we provide a polynomial-time algorithm for selecting a chain-based scheme which uses the minimum possible number of keys. We also compute the number of secrets that will be required and establish an upper bound on the number of secrets required by any user.
A Hierarchical Approach for Joint Multi-view Object Pose Estimation and Categorization
Venue: arXiv cs.CV 2015
Year: 2015

We propose a joint object pose estimation and categorization approach which extracts information about object poses and categories from the object parts and compositions constructed at different layers of a hierarchical object representation algorithm, namely Learned Hierarchy of Parts (LHOP). In the proposed approach, we first employ the LHOP to learn hierarchical part libraries which represent entity parts and compositions across different object categories and views. Then, we extract statistical and geometric features from the part realizations of the objects in the images in order to represent the information about object pose and category at each different layer of the hierarchy. Unlike the traditional approaches which consider specific layers of the hierarchies in order to extract information to perform specific tasks, we combine the information extracted at different layers to solve a joint object pose estimation and categorization problem using distributed optimization algorithms. We examine the proposed generative-discriminative learning approach and the algorithms on two benchmark 2-D multi-view image datasets. The proposed approach and the algorithms outperform state-of-the-art classification, regression and feature extraction algorithms. In addition, the experimental results shed light on the relationship between object categorization, pose estimation and the part realizations observed at different layers of the hierarchy.
Invariant EKF Design for Scan Matching-aided Localization
Venue: arXiv cs.SY 2015
Year: 2015

Localization in indoor environments is a technique which estimates the robot's pose by fusing data from onboard motion sensors with readings of the environment, in our case obtained by scan matching point clouds captured by a low-cost Kinect depth camera. We develop both an Invariant Extended Kalman Filter (IEKF)-based and a Multiplicative Extended Kalman Filter (MEKF)-based solution to this problem. The two designs are successfully validated in experiments and demonstrate the advantage of the IEKF design.
Combinatorial Auction-Based Pricing for Multi-tenant Autonomous Vehicle Public Transportation System
Venue: arXiv cs.GT 2015
Year: 2015

A smart city provides its people with high standard of living through advanced technologies and transport is one of the major foci. With the advent of autonomous vehicles (AVs), an AV-based public transportation system has been proposed recently, which is capable of providing new forms of transportation services with high efficiency, high flexibility, and low cost. For the benefit of passengers, multitenancy can increase market competition leading to lower service charge and higher quality of service. In this paper, we study the pricing issue of the multi-tenant AV public transportation system and three types of services are defined. The pricing process for each service type is modeled as a combinatorial auction, in which the service providers, as bidders, compete for offering transportation services. The winners of the auction are determined through an integer linear program. To prevent the bidders from raising their bids for higher returns, we propose a strategy-proof Vickrey-Clarke-Groves-based charging mechanism, which can maximize the social welfare, to settle the final charges for the customers. We perform extensive simulations to verify the analytical results and evaluate the performance of the charging mechanism.
Predicting opponent team activity in a RoboCup environment
Venue: arXiv cs.AI 2015
Year: 2015

The goal of this project is to predict the opponent's configuration in a RoboCup SSL environment. For simplicity, a Markov model assumption is made such that the predicted formation of the opponent team only depends on its current formation. The field is divided into a grid and a robot state per player is created with information about its position and its velocity. To gather a more general sense of what the opposing team is doing, the state also incorporates the team's average position (centroid). All possible state transitions are stored in a hash table that requires minimum storage space. The table is populated with transition probabilities that are learned by reading vision packages and counting the state transitions regardless of the specific robot player. Therefore, the computation during the game is reduced to interpreting a given vision package to assign each player to a state, and looking for the most likely state it will transition to. The confidence of the predicted team's formation is the product of each individual player's probability. The project is noteworthy in that it minimizes the time and space complexity requirements for opponent's moves prediction.
Genetic optimization of the Hyperloop route through the Grapevine
Venue: arXiv cs.NE 2015
Year: 2015

We demonstrate a genetic algorithm that employs a versatile fitness function to optimize route selection for the Hyperloop, a proposed high speed passenger transportation system.
Binary-Decision-Diagrams for Set Abstraction
Venue: arXiv cs.LO 2015
Year: 2015

Whether explicit or implicit, sets are a critical part of many pieces of software. As a result, it is necessary to develop abstractions of sets for the purposes of abstract interpretation, model checking, and deductive verification. However, the construction of effective abstractions for sets is challenging because they are a higher-order construct. It is necessary to reason about contents of sets as well as relationships between sets. This paper presents a new abstraction for sets that is based on binary decision diagrams. It is optimized for precisely and efficiently representing relations between sets while still providing limited support for content reasoning.
MSOL-Definability Equals Recognizability for Halin Graphs and Bounded Degree $k$-Outerplanar Graphs
Venue: arXiv cs.LO 2015
Year: 2015

One of the most famous algorithmic meta-theorems states that every graph property that can be defined by a sentence in counting monadic second order logic (CMSOL) can be checked in linear time for graphs of bounded treewidth, which is known as Courcelle's Theorem. These algorithms are constructed as finite state tree automata, and hence every CMSOL-definable graph property is recognizable. Courcelle also conjectured that the converse holds, i.e. every recognizable graph property is definable in CMSOL for graphs of bounded treewidth. We prove this conjecture for a number of special cases in a stronger form. That is, we show that each recognizable property is definable in MSOL, i.e. the counting operation is not needed in our expressions. We give proofs for Halin graphs, bounded degree $k$-outerplanar graphs and some related graph classes. We furthermore show that the conjecture holds for any graph class that admits tree decompositions that can be defined in MSOL, thus providing a useful tool for future proofs.
Video-Based Facial Expression Recognition Using Local Directional Binary Pattern
Venue: arXiv cs.CV 2015
Year: 2015

Automatic facial expression analysis is a challenging issue and influenced so many areas such as human computer interaction. Due to the uncertainties of the light intensity and light direction, the face gray shades are uneven and the expression recognition rate under simple Local Binary Pattern is not ideal and promising. In this paper we propose two state-of-the-art descriptors for person-independent facial expression recognition. First the face regions of the whole images in a video sequence are modeled with Volume Local Directional Binary pattern (VLDBP), which is an extended version of the LDBP operator, incorporating movement and appearance together. To make the survey computationally simple and easy to expand, only the co-occurrences of the Local Directional Binary Pattern on three orthogonal planes (LDBP-TOP) are debated. After extracting the feature vectors the K-Nearest Neighbor classifier was used to recognize the expressions. The proposed methods are applied to the videos of the Extended Cohn-Kanade database (CK+) and the experimental outcomes demonstrate that the offered techniques achieve more accuracy in comparison with the classic and traditional algorithms.
Efficient Farthest-Point Queries in Two-Terminal Series-Parallel Networks
Venue: arXiv cs.DS 2015
Year: 2015

Consider the continuum of points along the edges of a network, i.e., a connected, undirected graph with positive edge weights. We measure the distance between these points in terms of the weighted shortest path distance, called the network distance. Within this metric space, we study farthest points and farthest distances. We introduce a data structure supporting queries for the farthest distance and the farthest points on two-terminal series-parallel networks. This data structure supports farthest-point queries in $O(k + \log n)$ time after $O(n \log p)$ construction time, where $k$ is the number of farthest points, $n$ is the size of the network, and $p$ parallel operations are required to generate the network.
Frequency Domain TOF: Encoding Object Depth in Modulation Frequency
Venue: arXiv cs.CV 2015
Year: 2015

Time of flight cameras may emerge as the 3-D sensor of choice. Today, time of flight sensors use phase-based sampling, where the phase delay between emitted and received, high-frequency signals encodes distance. In this paper, we present a new time of flight architecture that relies only on frequency---we refer to this technique as frequency-domain time of flight (FD-TOF). Inspired by optical coherence tomography (OCT), FD-TOF excels when frequency bandwidth is high. With the increasing frequency of TOF sensors, new challenges to time of flight sensing continue to emerge. At high frequencies, FD-TOF offers several potential benefits over phase-based time of flight methods.
Convex Color Image Segmentation with Optimal Transport Distances
Venue: arXiv cs.CV 2015
Year: 2015

This work is about the use of regularized optimal-transport distances for convex, histogram-based image segmentation. In the considered framework, fixed exemplar histograms define a prior on the statistical features of the two regions in competition. In this paper, we investigate the use of various transport-based cost functions as discrepancy measures and rely on a primal-dual algorithm to solve the obtained convex optimization problem.
Tomographic Image Reconstruction using Training images
Venue: arXiv cs.CV 2015
Year: 2015

We describe and examine an algorithm for tomographic image reconstruction where prior knowledge about the solution is available in the form of training images. We first construct a nonnegative dictionary based on prototype elements from the training images; this problem is formulated as a regularized non-negative matrix factorization. Incorporating the dictionary as a prior in a convex reconstruction problem, we then find an approximate solution with a sparse representation in the dictionary. The dictionary is applied to non-overlapping patches of the image, which reduces the computational complexity compared to other algorithms. Computational experiments clarify the choice and interplay of the model parameters and the regularization parameters, and we show that in few-projection low-dose settings our algorithm is competitive with total variation regularization and tends to include more texture and more correct edges.
Gender-Based Violence in 140 Characters or Fewer: A #BigData Case Study of Twitter
Venue: arXiv cs.SI 2015
Year: 2015

Public institutions are increasingly reliant on data from social media sites to measure public attitude and provide timely public engagement. Such reliance includes the exploration of public views on important social issues such as gender-based violence (GBV). In this study, we examine big (social) data consisting of nearly fourteen million tweets collected from Twitter over a period of ten months to analyze public opinion regarding GBV, highlighting the nature of tweeting practices by geographical location and gender. We demonstrate the utility of Computational Social Science to mine insight from the corpus while accounting for the influence of both transient events and sociocultural factors. We reveal public awareness regarding GBV tolerance and suggest opportunities for intervention and the measurement of intervention effectiveness assisting both governmental and non-governmental organizations in policy development.