OpenRaiser/Intern-Atlas huggingface dataset:
Database Engines: Evolution of Greenness
Venue: arXiv cs.SE 2017
Year: 2017

Context: Information Technology consumes up to 10\% of the world's electricity generation, contributing to CO2 emissions and high energy costs. Data centers, particularly databases, use up to 23% of this energy. Therefore, building an energy-efficient (green) database engine could reduce energy consumption and CO2 emissions. Goal: To understand the factors driving databases' energy consumption and execution time throughout their evolution. Method: We conducted an empirical case study of energy consumption by two MySQL database engines, InnoDB and MyISAM, across 40 releases. We examined the relationships of four software metrics to energy consumption and execution time to determine which metrics reflect the greenness and performance of a database. Results: Our analysis shows that database engines' energy consumption and execution time increase as databases evolve. Moreover, the Lines of Code metric is correlated moderately to strongly with energy consumption and execution time in 88% of cases. Conclusions: Our findings provide insights to both practitioners and researchers. Database administrators may use them to select a fast, green release of the MySQL database engine. MySQL database-engine developers may use the software metric to assess products' greenness and performance. Researchers may use our findings to further develop new hypotheses or build models to predict greenness and performance of databases.
Sliding-Window Superposition Coding:Two-User Interference Channels
Venue: arXiv cs.IT 2017
Year: 2017

A low-complexity coding scheme is developed to achieve the rate region of maximum likelihood decoding for interference channels. As in the classical rate-splitting multiple access scheme by Grant, Rimoldi, Urbanke, and Whiting, the proposed coding scheme uses superposition of multiple codewords with successive cancellation decoding, which can be implemented using standard point-to-point encoders and decoders. Unlike rate-splitting multiple access, which is not rate-optimal for multiple receivers, the proposed coding scheme transmits codewords over multiple blocks in a staggered manner and recovers them successively over sliding decoding windows, achieving the single-stream optimal rate region as well as the more general Han--Kobayashi inner bound for the two-user interference channel. The feasibility of this scheme in practice is verified by implementing it using commercial channel codes over the two-user Gaussian interference channel.
The Impact of Small-Cell Bandwidth Requirements on Strategic Operators
Venue: arXiv cs.IT 2017
Year: 2017

Small-cell deployment in licensed and unlicensed spectrum is considered to be one of the key approaches to cope with the ongoing wireless data demand explosion. Compared to traditional cellular base stations with large transmission power, small-cells typically have relatively low transmission power, which makes them attractive for some spectrum bands that have strict power regulations, for example, the 3.5GHz band [1]. In this paper we consider a heterogeneous wireless network consisting of one or more service providers (SPs). Each SP operates in both macro-cells and small-cells, and provides service to two types of users: mobile and fixed. Mobile users can only associate with macro-cells whereas fixed users can connect to either macro- or small-cells. The SP charges a price per unit rate for each type of service. Each SP is given a fixed amount of bandwidth and splits it between macro- and small-cells. Motivated by bandwidth regulations, such as those for the 3.5Gz band, we assume a minimum amount of bandwidth has to be set aside for small-cells. We study the optimal pricing and bandwidth allocation strategies in both monopoly and competitive scenarios. In the monopoly scenario the strategy is unique. In the competitive scenario there exists a unique Nash equilibrium, which depends on the regulatory constraints. We also analyze the social welfare achieved, and compare it to that without the small-cell bandwidth constraints. Finally, we discuss implications of our results on the effectiveness of the minimum bandwidth constraint on influencing small-cell deployments.
Stoic Ethics for Artificial Agents
Venue: arXiv cs.AI 2017
Year: 2017

We present a position paper advocating the notion that Stoic philosophy and ethics can inform the development of ethical A.I. systems. This is in sharp contrast to most work on building ethical A.I., which has focused on Utilitarian or Deontological ethical theories. We relate ethical A.I. to several core Stoic notions, including the dichotomy of control, the four cardinal virtues, the ideal Sage, Stoic practices, and Stoic perspectives on emotion or affect. More generally, we put forward an ethical view of A.I. that focuses more on internal states of the artificial agent rather than on external actions of the agent. We provide examples relating to near-term A.I. systems as well as hypothetical superintelligent agents.
Coflow Scheduling in Input-Queued Switches: Optimal Delay Scaling and Algorithms
Venue: arXiv cs.NI 2017
Year: 2017

A coflow is a collection of parallel flows belonging to the same job. It has the all-or-nothing property: a coflow is not complete until the completion of all its constituent flows. In this paper, we focus on optimizing \emph{coflow-level delay}, i.e., the time to complete all the flows in a coflow, in the context of an $N\times N$ input-queued switch. In particular, we develop a throughput-optimal scheduling policy that achieves the best scaling of coflow-level delay as $N\rightarrow\infty$. We first derive lower bounds on the coflow-level delay that can be achieved by any scheduling policy. It is observed that these lower bounds critically depend on the variability of flow sizes. Then we analyze the coflow-level performance of some existing coflow-agnostic scheduling policies and show that none of them achieves provably optimal performance with respect to coflow-level delay. Finally, we propose the Coflow-Aware Batching (CAB) policy which achieves the optimal scaling of coflow-level delay under some mild assumptions.
Real-Time Bidding by Reinforcement Learning in Display Advertising
Venue: arXiv cs.LG 2017
Year: 2017

The majority of online display ads are served through real-time bidding (RTB) --- each ad display impression is auctioned off in real-time when it is just being generated from a user visit. To place an ad automatically and optimally, it is critical for advertisers to devise a learning algorithm to cleverly bid an ad impression in real-time. Most previous works consider the bid decision as a static optimization problem of either treating the value of each impression independently or setting a bid price to each segment of ad volume. However, the bidding for a given ad campaign would repeatedly happen during its life span before the budget runs out. As such, each bid is strategically correlated by the constrained budget and the overall effectiveness of the campaign (e.g., the rewards from generated clicks), which is only observed after the campaign has completed. Thus, it is of great interest to devise an optimal bidding strategy sequentially so that the campaign budget can be dynamically allocated across all the available impressions on the basis of both the immediate and future rewards. In this paper, we formulate the bid decision process as a reinforcement learning problem, where the state space is represented by the auction information and the campaign's real-time parameters, while an action is the bid price to set. By modeling the state transition via auction competition, we build a Markov Decision Process framework for learning the optimal bidding policy to optimize the advertising performance in the dynamic real-time bidding environment. Furthermore, the scalability problem from the large real-world auction volume and campaign budget is well handled by state value approximation using neural networks.
Untwisting two-way transducers in elementary time
Venue: arXiv cs.FL 2017
Year: 2017

Functional transductions realized by two-way transducers (equivalently, by streaming transducers and by MSO transductions) are the natural and standard notion of "regular" mappings from words to words. It was shown recently (LICS'13) that it is decidable if such a transduction can be implemented by some one-way transducer, but the given algorithm has non-elementary complexity. We provide an algorithm of different flavor solving the above question, that has double exponential space complexity. We further apply our technique to decide whether the transduction realized by a two-way transducer can be implemented by a sweeping transducer, with either known or unknown number of passes.
Why It Takes So Long to Connect to a WiFi Access Point
Venue: arXiv cs.NI 2017
Year: 2017

Today's WiFi networks deliver a large fraction of traffic. However, the performance and quality of WiFi networks are still far from satisfactory. Among many popular quality metrics (throughput, latency), the probability of successfully connecting to WiFi APs and the time cost of the WiFi connection set-up process are the two of the most critical metrics that affect WiFi users' experience. To understand the WiFi connection set-up process in real-world settings, we carry out measurement studies on $5$ million mobile users from $4$ representative cities associating with $7$ million APs in $0.4$ billion WiFi sessions, collected from a mobile "WiFi Manager" App that tops the Android/iOS App market. To the best of our knowledge, we are the first to do such large scale study on: how large the WiFi connection set-up time cost is, what factors affect the WiFi connection set-up process, and what can be done to reduce the WiFi connection set-up time cost. Based on the measurement analysis, we develop a machine learning based AP selection strategy that can significantly improve WiFi connection set-up performance, against the conventional strategy purely based on signal strength, by reducing the connection set-up failures from $33\%$ to $3.6\%$ and reducing $80\%$ time costs of the connection set-up processes by more than $10$ times.
IoFClime: The fuzzy logic and the Internet of Things to control indoor temperature regarding the outdoor ambient conditions
Venue: arXiv cs.AI 2017
Year: 2017

The Internet of Things is arriving to our homes or cities through fields already known like Smart Homes, Smart Cities, or Smart Towns. The monitoring of environmental conditions of cities can help to adapt the indoor locations of the cities in order to be more comfortable for people who stay there. A way to improve the indoor conditions is an efficient temperature control, however, it depends on many factors like the different combinations of outdoor temperature and humidity. Therefore, adjusting the indoor temperature is not setting a value according to other value. There are many more factors to take into consideration, hence the traditional logic based in binary states cannot be used. Many problems cannot be solved with a set of binary solutions and we need a new way of development. Fuzzy logic is able to interpret many states, more than two states, giving to computers the capacity to react in a similar way to people. In this paper we will propose a new approach to control the temperature using the Internet of Things together its platforms and fuzzy logic regarding not only the indoor temperature but also the outdoor temperature and humidity in order to save energy and to set a more comfortable environment for their users. Finally, we will conclude that the fuzzy approach allows us to achieve an energy saving around 40% and thus, save money.
The ANTS problem
Venue: arXiv cs.DC 2017
Year: 2017

We introduce the Ants Nearby Treasure Search (ANTS) problem, which models natural cooperative foraging behavior such as that performed by ants around their nest. In this problem, k probabilistic agents, initially placed at a central location, collectively search for a treasure on the two-dimensional grid. The treasure is placed at a target location by an adversary and the agents' goal is to find it as fast as possible as a function of both k and D, where D is the (unknown) distance between the central location and the target. We concentrate on the case in which agents cannot communicate while searching. It is straightforward to see that the time until at least one agent finds the target is at least $Ω$(D + D 2 /k), even for very sophisticated agents, with unrestricted memory. Our algorithmic analysis aims at establishing connections between the time complexity and the initial knowledge held by agents (e.g., regarding their total number k), as they commence the search. We provide a range of both upper and lower bounds for the initial knowledge required for obtaining fast running time. For example, we prove that log log k + $Θ$(1) bits of initial information are both necessary and sufficient to obtain asymptotically optimal running time, i.e., O(D +D 2 /k). We also we prove that for every 0 \textless{} \textless{} 1, running in time O(log 1-- k $\times$(D +D 2 /k)) requires that agents have the capacity for storing $Ω$(log k) different states as they leave the nest to start the search. To the best of our knowledge, the lower bounds presented in this paper provide the first non-trivial lower bounds on the memory complexity of probabilistic agents in the context of search problems. We view this paper as a "proof of concept" for a new type of interdisciplinary methodology. To fully demonstrate this methodology, the theoretical tradeoff presented here (or a similar one) should be combined with measurements of the time performance of searching ants.
ChaLearn Looking at People: A Review of Events and Resources
Venue: arXiv cs.CV 2017
Year: 2017

This paper reviews the historic of ChaLearn Looking at People (LAP) events. We started in 2011 (with the release of the first Kinect device) to run challenges related to human action/activity and gesture recognition. Since then we have regularly organized events in a series of competitions covering all aspects of visual analysis of humans. So far we have organized more than 10 international challenges and events in this field. This paper reviews associated events, and introduces the ChaLearn LAP platform where public resources (including code, data and preprints of papers) related to the organized events are available. We also provide a discussion on perspectives of ChaLearn LAP activities.
Constraint Handling Rules - What Else?
Venue: arXiv cs.PL 2017
Year: 2017

Constraint Handling Rules (CHR) is both an effective concurrent declarative constraint-based programming language and a versatile computational formalism. While conceptually simple, CHR is distinguished by a remarkable combination of desirable features: - semantic foundation in classical and linear logic, - effective and efficient sequential and parallel execution model - guaranteed properties like the anytime online algorithm properties - powerful analysis methods for deciding essential program properties. This overview of CHR research and applications is by no complete. It concentrates on the years since 2000. Up-to-date information on CHR can be found at the CHR web-site www.constraint-handling-rules.org, including the slides of the keynote talk associated with this article, an extensive bibliography, online demo versions and free downloads of the language.
Digital Advertising Traffic Operation: Flow Management Analysis
Venue: arXiv cs.SI 2017
Year: 2017

In a Web Advertising Traffic Operation the Trafficking Routing Problem (TRP) consists in scheduling the management of Web Advertising (Adv) campaign between Trafficking campaigns in the most efficient way to oversee and manage relationship with partners and internal teams, managing expectations through integration and post-launch in order to ensure success for every stakeholders involved. For our own interest we did that independent research projects also through specific innovative tasks validate towards average working time declared on "specification required" by the main worldwide industry leading Advertising Agency. We present a Mixed Integer Linear Programming (MILP) formulation for end-to-end management of campaign workflow along a predetermined path and generalize it to include alternative path to oversee and manage detail-oriented relationship with partners and internal teams to achieve the goals above mentioned. To meet clients' KPIs, we consider an objective function that includes the punctuality indicators (the average waiting time and completion times) but also the main punctuality indicators (the average delay and the on time performance). Then we investigate their analytical relationships in the advertising domain through experiments based on real data from a Traffic Office. We show that the classic punctuality indicators are in contradiction with the task of reducing waiting times. We propose new indicators used for a synthesize analysis on projects or process changes for the wider team that are more sustainable, but also more relevant for stakeholders. We also show that the flow of a campaign (adv-ways) is the main bottleneck of a Traffic Office and that alternate paths cannot improve the performance indicators.
A Unified RGB-T Saliency Detection Benchmark: Dataset, Baselines, Analysis and A Novel Approach
Venue: arXiv cs.CV 2017
Year: 2017

Despite significant progress, image saliency detection still remains a challenging task in complex scenes and environments. Integrating multiple different but complementary cues, like RGB and Thermal (RGB-T), may be an effective way for boosting saliency detection performance. The current research in this direction, however, is limited by the lack of a comprehensive benchmark. This work contributes such a RGB-T image dataset, which includes 821 spatially aligned RGB-T image pairs and their ground truth annotations for saliency detection purpose. The image pairs are with high diversity recorded under different scenes and environmental conditions, and we annotate 11 challenges on these image pairs for performing the challenge-sensitive analysis for different saliency detection algorithms. We also implement 3 kinds of baseline methods with different modality inputs to provide a comprehensive comparison platform. With this benchmark, we propose a novel approach, multi-task manifold ranking with cross-modality consistency, for RGB-T saliency detection. In particular, we introduce a weight for each modality to describe the reliability, and integrate them into the graph-based manifold ranking algorithm to achieve adaptive fusion of different source data. Moreover, we incorporate the cross-modality consistent constraints to integrate different modalities collaboratively. For the optimization, we design an efficient algorithm to iteratively solve several subproblems with closed-form solutions. Extensive experiments against other baseline methods on the newly created benchmark demonstrate the effectiveness of the proposed approach, and we also provide basic insights and potential future research directions for RGB-T saliency detection.
Graph Equivalence Classes for Spectral Projector-Based Graph Fourier Transforms
Venue: arXiv cs.SI 2017
Year: 2017

We define and discuss the utility of two equivalence graph classes over which a spectral projector-based graph Fourier transform is equivalent: isomorphic equivalence classes and Jordan equivalence classes. Isomorphic equivalence classes show that the transform is equivalent up to a permutation on the node labels. Jordan equivalence classes permit identical transforms over graphs of nonidentical topologies and allow a basis-invariant characterization of total variation orderings of the spectral components. Methods to exploit these classes to reduce computation time of the transform as well as limitations are discussed.
Colored Image Encryption and Decryption Using Chaotic Lorenz System and DCT2
Venue: arXiv cs.CR 2017
Year: 2017

In this paper, a scheme for the encryption and decryption of colored images by using the Lorenz system and the discrete cosine transform in two dimensions (DCT2) is proposed. Although chaos is random, it has deterministic features that can be used for encryption; further, the same sequences can be produced at the transmitter and receiver under the same initial conditions. Another property of DCT2 is that the energy is concentrated in some elements of the coefficients. These two properties are used to efficiently encrypt and recover the image at the receiver by using three different keys with three different predefined number of shifts for each instance of key usage. Simulation results and statistical analysis show that the scheme high performance in weakening the correlation between the pixels of the image that resulted from the inverse of highest energy values of DCT2 that form 99.9 % of the energy as well as those of the difference image.
Optimal Compression for Two-Field Entries in Fixed-Width Memories
Venue: arXiv cs.IT 2017
Year: 2017

Data compression is a well-studied (and well-solved) problem in the setup of long coding blocks. But important emerging applications need to compress data to memory words of small fixed widths. This new setup is the subject of this paper. In the problem we consider we have two sources with known discrete distributions, and we wish to find codes that maximize the success probability that the two source outputs are represented in $L$ bits or less. A good practical use for this problem is a table with two-field entries that is stored in a memory of a fixed width $L$. Such tables of very large sizes drive the core functionalities of network switches and routers. After defining the problem formally, we solve it optimally with an efficient code-design algorithm. We also solve the problem in the more constrained case where a single code is used in both fields (to save space for storing code dictionaries). For both code-design problems we find decompositions that yield efficient dynamic-programming algorithms. With an empirical study we show the success probabilities of the optimal codes for different distributions and memory widths. In particular, the study demonstrates the superiority of the new codes over existing compression algorithms.
On Delay and Regret Determinization of Max-Plus Automata
Venue: arXiv cs.FL 2017
Year: 2017

Decidability of the determinization problem for weighted automata over the semiring $(\mathbb{Z} \cup {-\infty}, \max, +)$, WA for short, is a long-standing open question. We propose two ways of approaching it by constraining the search space of deterministic WA: k-delay and r-regret. A WA N is k-delay determinizable if there exists a deterministic automaton D that defines the same function as N and for all words α in the language of N, the accepting run of D on α is always at most k-away from a maximal accepting run of N on α. That is, along all prefixes of the same length, the absolute difference between the running sums of weights of the two runs is at most k. A WA N is r-regret determinizable if for all words α in its language, its non-determinism can be resolved on the fly to construct a run of N such that the absolute difference between its value and the value assigned to α by N is at most r. We show that a WA is determinizable if and only if it is k-delay determinizable for some k. Hence deciding the existence of some k is as difficult as the general determinization problem. When k and r are given as input, the k-delay and r-regret determinization problems are shown to be EXPtime-complete. We also show that determining whether a WA is r-regret determinizable for some r is in EXPtime.