OpenRaiser/Intern-Atlas huggingface dataset:
Online Coordinated Charging Decision Algorithm for Electric Vehicles without Future Information
Venue: arXiv cs.DS 2013
Year: 2013

The large-scale integration of plug-in electric vehicles (PEVs) to the power grid spurs the need for efficient charging coordination mechanisms. It can be shown that the optimal charging schedule smooths out the energy consumption over time so as to minimize the total energy cost. In practice, however, it is hard to smooth out the energy consumption perfectly, because the future PEV charging demand is unknown at the moment when the charging rate of an existing PEV needs to be determined. In this paper, we propose an Online cooRdinated CHARging Decision (ORCHARD) algorithm, which minimizes the energy cost without knowing the future information. Through rigorous proof, we show that ORCHARD is strictly feasible in the sense that it guarantees to fulfill all charging demands before due time. Meanwhile, it achieves the best known competitive ratio of 2.39. To further reduce the computational complexity of the algorithm, we propose a novel reduced-complexity algorithm to replace the standard convex optimization techniques used in ORCHARD. Through extensive simulations, we show that the average performance gap between ORCHARD and the offline optimal solution, which utilizes the complete future information, is as small as 14%. By setting a proper speeding factor, the average performance gap can be further reduced to less than 6%.
Selection Policy: Fighting against Filter Effect in Network of Caches
Venue: arXiv cs.NI 2013
Year: 2013

Many Information Centric Networking (ICN) proposals use a network of caches to bring the contents closer to the consumers, reduce the load on producers and decrease the unnecessary retransmission for ISPs. Nevertheless, the existing cache management scheme for the network of caches obtain poor performance. The main reason for performance degradation in a network of caches is the filter effect of the replacement policy. A cache serves the requests that generate cache-hits and forwards the requests that generate cache-misses. This filtering changes the pattern of requests and leads to decreased hit ratios in the subsequent caches. In this paper, we propose a coordinated caching scheme to solve the filter effect problem by introducing the selection policy. This policy manages a cache such that: i) the cache obtains a high hit ratio ii) the missed requests from the cache can be used by subsequent caches to obtain a high hit ratio. Our coordinated selection scheme achieves an overall hit ratio of a network of caches equivalent to that of edge routers with big caches. Moreover, our scheme decreases the average number of evictions per cache slot by four order of magnitude compared to the LRU universal caching.
Misfire Detection in IC Engine using Kstar Algorithm
Venue: arXiv cs.CV 2013
Year: 2013

Misfire in an IC Engine continues to be a problem leading to reduced fuel efficiency, increased power loss and emissions containing heavy concentration of hydrocarbons. Misfiring creates a unique vibration pattern attributed to a particular cylinder. Useful features can be extracted from these patterns and can be analyzed to detect misfire. Statistical features from these vibration signals were extracted. Out of these, useful features were identified using the J48 decision tree algorithm and selected features were used for classification using the Kstar algorithm. In this paper performance analysis of Kstar algorithm is presented.
HARQ Feedback in Spectrum Sharing Networks
Venue: arXiv cs.IT 2013
Year: 2013

This letter studies the throughput and the outage probability of spectrum sharing networks utilizing hybrid automatic repeat request (HARQ) feedback. We focus on the repetition time diversity and the incremental redundancy HARQ protocols where the results are obtained for both continuous and bursting communication models. The channel data transmission efficiency is investigated in the presence of both secondary user peak transmission power and primary user received interference power constraints. Finally, we evaluate the effect of secondary-primary channel state information imperfection on the performance of the secondary channel. Simulation results show that, while the throughput is not necessarily increased by HARQ, substantial outage probability reduction is achieved in all conditions.
Validation Rules for Assessing and Improving SKOS Mapping Quality
Venue: arXiv cs.AI 2013
Year: 2013

The Simple Knowledge Organization System (SKOS) is popular for expressing controlled vocabularies, such as taxonomies, classifications, etc., for their use in Semantic Web applications. Using SKOS, concepts can be linked to other concepts and organized into hierarchies inside a single terminology system. Meanwhile, expressing mappings between concepts in different terminology systems is also possible. This paper discusses potential quality issues in using SKOS to express these terminology mappings. Problematic patterns are defined and corresponding rules are developed to automatically detect situations where the mappings either result in 'SKOS Vocabulary Hijacking' to the source vocabularies or cause conflicts. An example of using the rules to validate sample mappings between two clinical terminologies is given. The validation rules, expressed in N3 format, are available as open source.
On Measure Concentration of Random Maximum A-Posteriori Perturbations
Venue: arXiv cs.LG 2013
Year: 2013

The maximum a-posteriori (MAP) perturbation framework has emerged as a useful approach for inference and learning in high dimensional complex models. By maximizing a randomly perturbed potential function, MAP perturbations generate unbiased samples from the Gibbs distribution. Unfortunately, the computational cost of generating so many high-dimensional random variables can be prohibitive. More efficient algorithms use sequential sampling strategies based on the expected value of low dimensional MAP perturbations. This paper develops new measure concentration inequalities that bound the number of samples needed to estimate such expected values. Applying the general result to MAP perturbations can yield a more efficient algorithm to approximate sampling from the Gibbs distribution. The measure concentration result is of general interest and may be applicable to other areas involving expected estimations.
Dynamic cache reconfiguration based techniques for improving cache energy efficiency
Venue: arXiv cs.AR 2013
Year: 2013

Modern multicore processors are employing large last-level caches, for example Intel's E7-8800 processor uses 24MB L3 cache. Further, with each CMOS technology generation, leakage energy has been dramatically increasing and hence, leakage energy is expected to become a major source of energy dissipation, especially in last-level caches (LLCs). The conventional schemes of cache energy saving either aim at saving dynamic energy or are based on properties specific to first-level caches, and thus these schemes have limited utility for last-level caches. Further, several other techniques require offline profiling or per-application tuning and hence are not suitable for product systems. In this research, we propose novel cache leakage energy saving schemes for single-core and multicore systems; desktop, QoS, real-time and server systems. We propose software-controlled, hardware-assisted techniques which use dynamic cache reconfiguration to configure the cache to the most energy efficient configuration while keeping the performance loss bounded. To profile and test a large number of potential configurations, we utilize low-overhead, micro-architecture components, which can be easily integrated into modern processor chips. We adopt a system-wide approach to save energy to ensure that cache reconfiguration does not increase energy consumption of other components of the processor. We have compared our techniques with the state-of-art techniques and have found that our techniques outperform them in their energy efficiency. This research has important applications in improving energy-efficiency of higher-end embedded, desktop, server processors and multitasking systems. We have also proposed performance estimation approach for efficient design space exploration and have implemented time-sampling based simulation acceleration approach for full-system architectural simulators.
Ear-Phone: A Context-Aware Noise Mapping using Smart Phones
Venue: arXiv cs.OH 2013
Year: 2013

A noise map facilitates the monitoring of environmental noise pollution in urban areas. However, state-of-the-art techniques for rendering noise maps in urban areas are expensive and rarely updated, as they rely on population and traffic models rather than on real data. Smart phone based urban sensing can be leveraged to create an open and inexpensive platform for rendering up-to- date noise maps. In this paper, we present the design, implementation and performance evaluation of an end-to-end, context-aware, noise mapping system called Ear-Phone. Ear-Phone investigates the use of different interpolation and regularization methods to address the fundamental problem of recovering the noise map from incomplete and random samples obtained by crowdsourcing data collection. Ear-Phone, implemented on Nokia N95, N97 and HP iPAQ, HTC One mobile devices, also addresses the challenge of collecting accurate noise pollution readings at a mobile device. A major challenge of using smart phones as sensors is that even at the same location, the sensor reading may vary depending on the phone orientation and user context (for example, whether the user is carrying the phone in a bag or holding it in her palm). To address this problem, Ear-Phone leverages context-aware sensing. We develop classifiers to accurately determine the phone sensing context. Upon context discovery, Ear-Phone automatically decides whether to sense or not. Ear-phone also implements in-situ calibration which performs simple calibration that can be carried out without any technical skills whatsoever required on the user's part. Extensive simulations and outdoor experiments demonstrate that Ear-Phone is a feasible platform to assess noise pollution, incurring reasonable system resource consumption at mobile devices and providing high reconstruction accuracy of the noise map.
A novel weighting scheme for random $k$-SAT
Venue: arXiv cs.DM 2013
Year: 2013

Consider a random $k$-CNF formula $F_{k}(n, rn)$ with $n$ variables and $rn$ clauses. For every truth assignment $σ\in \{0, 1\}^{n}$ and every clause $c=\ell_{1}\vee\cdots\vee\ell_{k}$, let $d=d(σ, c)$ be the number of satisfied literal occurrences in $c$ under $σ$. For fixed $β>-1$ and $λ>0$, we take $ω(σ, c)=0$, if $d=0$; $ω(σ, c)=λ(1+β)$, if $d=1$ and $ω(σ, c)=λ^{d}$, if $d>1$. Applying the above weighting scheme, we get that if $F_{k}(n, rn)$ is unsatisfiable with probability tending to one as $n\rightarrow\infty$, then $r\geq2.83, 8.09, 18.91, 40.81, 84.87$ for $k=3, 4, 5, 6$ and $7,$ respectively.
Fully-abstract concurrent games for pi
Venue: arXiv cs.LO 2013
Year: 2013

We define a semantics for Milner's pi-calculus, with three main novelties. First, it provides a fully-abstract model for fair testing equivalence, whereas previous semantics covered variants of bisimilarity and the may and must testing equivalences. Second, it is based on reduction semantics, whereas previous semantics were based on labelled transition systems. Finally, it has a strong game semantical flavor in the sense of Hyland-Ong and Nickau. Indeed, our model may both be viewed as an innocent presheaf semantics and as a concurrent game semantics.
An FCA-based Boolean Matrix Factorisation for Collaborative Filtering
Venue: arXiv cs.IR 2013
Year: 2013

We propose a new approach for Collaborative Filtering which is based on Boolean Matrix Factorisation (BMF) and Formal Concept Analysis. In a series of experiments on real data (Movielens dataset) we compare the approach with the SVD- and NMF-based algorithms in terms of Mean Average Error (MAE). One of the experimental consequences is that it is enough to have a binary-scaled rating data to obtain almost the same quality in terms of MAE by BMF than for the SVD-based algorithm in case of non-scaled data.
Unfolding Orthogrids with Constant Refinement
Venue: arXiv cs.CG 2013
Year: 2013

We define a new class of orthogonal polyhedra, called orthogrids, that can be unfolded without overlap with constant refinement of the gridded surface.
A highly optimized flow-correlation attack
Venue: arXiv cs.CR 2013
Year: 2013

Deciding that two network flows are essentially the same is an important problem in intrusion detection and in tracing anonymous connections. A stepping stone or an anonymity network may try to prevent flow correlation by adding chaff traffic, splitting the flow in several subflows or adding random delays. A well-known attack for these types of systems is active watermarking. However, active watermarking systems can be detected and an attacker can modify the flow in such a way that the watermark is removed and can no longer be decoded. This leads to the two basic features of our scheme: a highlyoptimized algorithm that achieves very good performance and a passive analysis that is undetectable. We propose a new passive analysis technique where detection is based on Neyman-Pearson lemma. We correlate the inter-packet delays (IPDs) from both flows. Then, we derive a modification to deal with stronger adversary models that add chaff traffic, split the flows or add random delays. We empirically validate the detectors with a simulator. Afterwards, we create a watermarkbased version of our scheme to study the trade-off between performance and detectability. Then, we compare the results with other state-of-the-art traffic watermarking schemes in several scenarios concluding that our scheme outperforms the rest. Finally, we present results using an implementation of our method on live networks, showing that the conclusions can be extended to real-world scenarios. Our scheme needs only tens of packets under normal network interference and a few hundreds of packets when a number of countermeasures are taken.
Low complexity resource allocation for load minimization in OFDMA wireless networks
Venue: arXiv cs.IT 2013
Year: 2013

To cope with the ever increasing demand for bandwidth, future wireless networks will be designed with reuse distance equal to one. This scenario requires the implementation of techniques able to manage the strong multiple access interference each cell generates towards its neighbor cells. In particular, low complexity and reduced feedback are important requirements for practical algorithms. In this paper we study an allocation problem for OFDMA networks formulated with the objective of minimizing the load of each cell in the system subject to the constraint that each user meets its target rate. We decompose resource allocation into two sub-problems: channel allocation under deterministic power assignment and continuous power assignment optimization. Channel allocation is formulated as the problem of finding the maximum weighted independent set (MWIS) in graph theory. In addition, we propose a minimal weighted-degree greedy (MWDG) algorithm of which the approximation factor is analyzed. For power allocation, an iterative power reassignment algorithm (DPRA) is proposed. The control information requested to perform the allocation is limited and the computational burden is shared between the base station and the user equipments. Simulations have been carried out under constant bit rate traffic model and the results have been compared with other allocation schemes of similar complexity. MWDG has excellent performance and outperforms all other techniques.
Maximizing Barber's bipartite modularity is also hard
Venue: arXiv cs.SI 2013
Year: 2013

Modularity introduced by Newman and Girvan [Phys. Rev. E 69, 026113 (2004)] is a quality function for community detection. Numerous methods for modularity maximization have been developed so far. In 2007, Barber [Phys. Rev. E 76, 066102 (2007)] introduced a variant of modularity called bipartite modularity which is appropriate for bipartite networks. Although maximizing the standard modularity is known to be NP-hard, the computational complexity of maximizing bipartite modularity has yet to be revealed. In this study, we prove that maximizing bipartite modularity is also NP-hard. More specifically, we show the NP-completeness of its decision version by constructing a reduction from a classical partitioning problem.
Reliability Models for Highly Fault-tolerant Storage Systems
Venue: arXiv cs.DC 2013
Year: 2013

We found that a reliability model commonly used to estimate Mean-Time-To-Data-Loss (MTTDL), while suitable for modeling RAID 0 and RAID 5, fails to accurately model systems having a fault-tolerance greater than 1. Therefore, to model the reliability of RAID 6, Triple-Replication, or k-of-n systems requires an alternate technique. In this paper, we explore some alternatives, and evaluate their efficacy by comparing their predictions to simulations. Our main result is a new formula which more accurately models storage system reliability.
On Demand Memory Specialization for Distributed Graph Databases
Venue: arXiv cs.DB 2013
Year: 2013

In this paper, we propose the DN-tree that is a data structure to build lossy summaries of the frequent data access patterns of the queries in a distributed graph data management system. These compact representations allow us an efficient communication of the data structure in distributed systems. We exploit this data structure with a new \textit{Dynamic Data Partitioning} strategy (DYDAP) that assigns the portions of the graph according to historical data access patterns, and guarantees a small network communication and a computational load balance in distributed graph queries. This method is able to adapt dynamically to new workloads and evolve when the query distribution changes. Our experiments show that DYDAP yields a throughput up to an order of magnitude higher than previous methods based on cache specialization, in a variety of scenarios, and the average response time of the system is divided by two.
Practical Provably Secure Multi-node Communication
Venue: arXiv cs.CR 2013
Year: 2013

We present a practical and provably-secure multimode communication scheme in the presence of a passive eavesdropper. The scheme is based on a random scheduling approach that hides the identity of the transmitter from the eavesdropper. This random scheduling leads to ambiguity at the eavesdropper with regard to the origin of the transmitted frame. We present the details of the technique and analyze it to quantify the secrecy-fairness-overhead trade-off. Implementation of the scheme over Crossbow Telosb motes, equipped with CC2420 radio chips, shows that the scheme can achieve significant secrecy gain with vanishing outage probability. In addition, it has significant overhead advantage over direct extensions to two-nodes schemes. The technique also has the advantage of allowing inactive nodes to leverage sleep mode to further save energy.
A Logic-based Approach for Recognizing Textual Entailment Supported by Ontological Background Knowledge
Venue: arXiv cs.CL 2013
Year: 2013

We present the architecture and the evaluation of a new system for recognizing textual entailment (RTE). In RTE we want to identify automatically the type of a logical relation between two input texts. In particular, we are interested in proving the existence of an entailment between them. We conceive our system as a modular environment allowing for a high-coverage syntactic and semantic text analysis combined with logical inference. For the syntactic and semantic analysis we combine a deep semantic analysis with a shallow one supported by statistical models in order to increase the quality and the accuracy of results. For RTE we use logical inference of first-order employing model-theoretic techniques and automated reasoning tools. The inference is supported with problem-relevant background knowledge extracted automatically and on demand from external sources like, e.g., WordNet, YAGO, and OpenCyc, or other, more experimental sources with, e.g., manually defined presupposition resolutions, or with axiomatized general and common sense knowledge. The results show that fine-grained and consistent knowledge coming from diverse sources is a necessary condition determining the correctness and traceability of results.
Computing Preferred Extensions in Abstract Argumentation: a SAT-based Approach
Venue: arXiv cs.AI 2013
Year: 2013

This paper presents a novel SAT-based approach for the computation of extensions in abstract argumentation, with focus on preferred semantics, and an empirical evaluation of its performances. The approach is based on the idea of reducing the problem of computing complete extensions to a SAT problem and then using a depth-first search method to derive preferred extensions. The proposed approach has been tested using two distinct SAT solvers and compared with three state-of-the-art systems for preferred extension computation. It turns out that the proposed approach delivers significantly better performances in the large majority of the considered cases.
Online Classification Using a Voted RDA Method
Venue: arXiv cs.LG 2013
Year: 2013

We propose a voted dual averaging method for online classification problems with explicit regularization. This method employs the update rule of the regularized dual averaging (RDA) method, but only on the subsequence of training examples where a classification error is made. We derive a bound on the number of mistakes made by this method on the training set, as well as its generalization error rate. We also introduce the concept of relative strength of regularization, and show how it affects the mistake bound and generalization performance. We experimented with the method using $\ell_1$ regularization on a large-scale natural language processing task, and obtained state-of-the-art classification performance with fairly sparse models.
Distributional semantics beyond words: Supervised learning of analogy and paraphrase
Venue: arXiv cs.LG 2013
Year: 2013

There have been several efforts to extend distributional semantics beyond individual words, to measure the similarity of word pairs, phrases, and sentences (briefly, tuples; ordered sets of words, contiguous or noncontiguous). One way to extend beyond words is to compare two tuples using a function that combines pairwise similarities between the component words in the tuples. A strength of this approach is that it works with both relational similarity (analogy) and compositional similarity (paraphrase). However, past work required hand-coding the combination function for different tasks. The main contribution of this paper is that combination functions are generated by supervised learning. We achieve state-of-the-art results in measuring relational similarity between word pairs (SAT analogies and SemEval~2012 Task 2) and measuring compositional similarity between noun-modifier phrases and unigrams (multiple-choice paraphrase questions).