OpenRaiser/Intern-Atlas huggingface dataset:
Distributed Dominating Sets on Grids
Venue: arXiv cs.DS 2013
Year: 2013

This paper presents a distributed algorithm for finding near optimal dominating sets on grids. The basis for this algorithm is an existing centralized algorithm that constructs dominating sets on grids. The size of the dominating set provided by this centralized algorithm is upper-bounded by $\lceil\frac{(m+2)(n+2)}{5}\rceil$ for $m\times n$ grids and its difference from the optimal domination number of the grid is upper-bounded by five. Both the centralized and distributed algorithms are generalized for the $k$-distance dominating set problem, where all grid vertices are within distance $k$ of the vertices in the dominating set.
A 3D Curve Offset Approach for Ruled Surface Generation in Engineering Design
Venue: arXiv cs.CG 2013
Year: 2013

Ruled surface is widely used in engineering design such as parting surface design of injection mold and checking surface design of checking fixture, which are usually generated by offsetting 3D curves. However, in 3D curve offset, there often exist break,interaction and overlapping problems which can't be solved by current CAD software automatically. This paper is targeted at developing a 3D curve offsetting algorithm for ruled surface generation, and three key technologies are introduced in details: An improved curve division method is proposed to reduce the offset accuracy error resulted from different offset distances and curvatures; An offsetting curve overlapping detection and elimination method is proposed; And then, a curve transition method is presented to improve curve offsetting quality for the break and intersection/overlapping regions, where a new algorithm for generating positive weights spherical rational quartic Bezier curve is proposed to bridge the breaks of offset curves to create a smooth ruled surface. Finally, two practical design cases, parting surface and checking surface generation, show that the proposed approach can enhance the efficiency and quality for ruled surface generation in engineering design.
Statistical Regression to Predict Total Cumulative CPU Usage of MapReduce Jobs
Venue: arXiv cs.DC 2013
Year: 2013

Recently, businesses have started using MapReduce as a popular computation framework for processing large amount of data, such as spam detection, and different data mining tasks, in both public and private clouds. Two of the challenging questions in such environments are (1) choosing suitable values for MapReduce configuration parameters e.g., number of mappers, number of reducers, and DFS block size, and (2) predicting the amount of resources that a user should lease from the service provider. Currently, the tasks of both choosing configuration parameters and estimating required resources are solely the users responsibilities. In this paper, we present an approach to provision the total CPU usage in clock cycles of jobs in MapReduce environment. For a MapReduce job, a profile of total CPU usage in clock cycles is built from the job past executions with different values of two configuration parameters e.g., number of mappers, and number of reducers. Then, a polynomial regression is used to model the relation between these configuration parameters and total CPU usage in clock cycles of the job. We also briefly study the influence of input data scaling on measured total CPU usage in clock cycles. This derived model along with the scaling result can then be used to provision the total CPU usage in clock cycles of the same jobs with different input data size. We validate the accuracy of our models using three realistic applications (WordCount, Exim MainLog parsing, and TeraSort). Results show that the predicted total CPU usage in clock cycles of generated resource provisioning options are less than 8% of the measured total CPU usage in clock cycles in our 20-node virtual Hadoop cluster.
From propositional to first-order monitoring
Venue: arXiv cs.LO 2013
Year: 2013

The main purpose of this paper is to introduce a first-order temporal logic, LTLFO, and a corresponding monitor construction based on a new type of automaton, called spawning automaton. Specifically, we show that monitoring a specification in LTLFO boils down to an undecidable decision problem. The proof of this result revolves around specific ideas on what we consider a "proper" monitor. As these ideas are general, we outline them first in the setting of standard LTL, before lifting them to the setting of first-order logic and LTLFO. Although due to the above result one cannot hope to obtain a complete monitor for LTLFO, we prove the soundness of our automata-based construction and give experimental results from an implementation. These seem to substantiate our hypothesis that the automata-based construction leads to efficient runtime monitors whose size does not grow with increasing trace lengths (as is often observed in similar approaches). However, we also discuss formulae for which growth is unavoidable, irrespective of the chosen monitoring approach.
Optimal Power Allocation for Energy Harvesting and Power Grid Coexisting Wireless Communication Systems
Venue: arXiv cs.IT 2013
Year: 2013

This paper considers the power allocation of a single-link wireless communication with joint energy harvesting and grid power supply. We formulate the problem as minimizing the grid power consumption with random energy and data arrival, and analyze the structure of the optimal power allocation policy in some special cases. For the case that all the packets are arrived before transmission, it is a dual problem of throughput maximization, and the optimal solution is found by the two-stage water filling (WF) policy, which allocates the harvested energy in the first stage, and then allocates the power grid energy in the second stage. For the random data arrival case, we first assume grid energy or harvested energy supply only, and then combine the results to obtain the optimal structure of the coexisting system. Specifically, the reverse multi-stage WF policy is proposed to achieve the optimal power allocation when the battery capacity is infinite. Finally, some heuristic online schemes are proposed, of which the performance is evaluated by numerical simulations.
Minimum-violation LTL Planning with Conflicting Specifications
Venue: arXiv cs.RO 2013
Year: 2013

We consider the problem of automatic generation of control strategies for robotic vehicles given a set of high-level mission specifications, such as "Vehicle x must eventually visit a target region and then return to a base," "Regions A and B must be periodically surveyed," or "None of the vehicles can enter an unsafe region." We focus on instances when all of the given specifications cannot be reached simultaneously due to their incompatibility and/or environmental constraints. We aim to find the least-violating control strategy while considering different priorities of satisfying different parts of the mission. Formally, we consider the missions given in the form of linear temporal logic formulas, each of which is assigned a reward that is earned when the formula is satisfied. Leveraging ideas from the automata-based model checking, we propose an algorithm for finding an optimal control strategy that maximizes the sum of rewards earned if this control strategy is applied. We demonstrate the proposed algorithm on an illustrative case study.
Adaptive Mode Selection in Bidirectional Buffer-aided Relay Networks with Fixed Transmit Powers
Venue: arXiv cs.IT 2013
Year: 2013

We consider a bidirectional network in which two users exchange information with the help of a buffer-aided relay. In such a network without direct link between user 1 and user 2, there exist six possible transmission modes, i.e., four point-to-point modes (user 1-to-relay, user 2-to-relay, relay-to-user 1, relay-to-user 2), a multiple access mode (both users to the relay), and a broadcast mode (the relay to both users). Because of the buffering capability at the relay, the transmissions in the network are not restricted to adhere to a predefined schedule, and therefore, all the transmission modes in the bidirectional relay network can be used adaptively based on the instantaneous channel state information (CSI) of the involved links. For the considered network, assuming fixed transmit powers for both the users and the relay, we derive the optimal transmission mode selection policy which maximizes the sum rate. The proposed policy selects one out of the six possible transmission modes in each time slot based on the instantaneous CSI. Simulation results confirm the effectiveness of the proposed protocol compared to existing protocols.
The conservation of information, towards an axiomatized modular modeling approach to congestion control
Venue: arXiv cs.NI 2013
Year: 2013

We derive a modular fluid-flow network congestion control model based on a law of fundamental nature in networks: the conservation of information. Network elements such as queues, users, and transmission channels and network performance indicators like sending/acknowledgement rates and delays are mathematically modelled by applying this law locally. Our contributions are twofold. First, we introduce a modular metamodel that is sufficiently generic to represent any network topology. The proposed model is composed of building blocks that implement mechanisms ignored by the existing ones, which can be recovered from exact reduction or approximation of this new model. Second, we provide a novel classification of previously proposed models in the literature and show that they are often not capable of capturing the transient behavior of the network precisely. Numerical results obtained from packet-level simulations demonstrate the accuracy of the proposed model.
F1000 recommendations as a new data source for research evaluation: A comparison with citations
Venue: arXiv cs.DL 2013
Year: 2013

F1000 is a post-publication peer review service for biological and medical research. F1000 aims to recommend important publications in the biomedical literature, and from this perspective F1000 could be an interesting tool for research evaluation. By linking the complete database of F1000 recommendations to the Web of Science bibliographic database, we are able to make a comprehensive comparison between F1000 recommendations and citations. We find that about 2% of the publications in the biomedical literature receive at least one F1000 recommendation. Recommended publications on average receive 1.30 recommendations, and over 90% of the recommendations are given within half a year after a publication has appeared. There turns out to be a clear correlation between F1000 recommendations and citations. However, the correlation is relatively weak, at least weaker than the correlation between journal impact and citations. More research is needed to identify the main reasons for differences between recommendations and citations in assessing the impact of publications.
Overview of Optical Interconnect Technology
Venue: arXiv cs.ET 2013
Year: 2013

Optical interconnect is seen as a potential solution to meet the performance requirements of current and future generation of data processors. Optical interconnects have negligible frequency dependent loss, low cross talk and high band width. Optical interconnects are not much used commercially since optical interconnects technology is incompatible with manufacturing processes and assembly methods that are currently used in the semiconductor industry. There are many promising optical interconnect technologies and this paper presents a brief analysis of current state of optical interconnect technology.
Wireless Information and Power Transfer: Energy Efficiency Optimization in OFDMA Systems
Venue: arXiv cs.IT 2013
Year: 2013

This paper considers orthogonal frequency division multiple access systems with simultaneous wireless information and power transfer. We study the resource allocation algorithm design for maximization of the energy efficiency of data transmission. In particular, we focus on power splitting hybrid receivers which are able to split the received signals into two power streams for concurrent information decoding and energy harvesting. Two scenarios are investigated considering different power splitting abilities of the receivers. In the first scenario, we assume receivers which can split the received power into a continuous set of power streams with arbitrary power splitting ratios. In the second scenario, we examine receivers which can split the received power only into a discrete set of power streams with fixed power splitting ratios. In both scenarios, we formulate the corresponding algorithm design as a non-convex optimization problem which takes into account the circuit power consumption, the minimum data rate requirements of delay constrained services, the minimum required system data rate, and the minimum amount of power that has to be delivered to the receivers. Subsequently, by exploiting fractional programming and dual decomposition, suboptimal iterative resource allocation algorithms are proposed to solve the non-convex problems. Simulation results illustrate that the proposed iterative resource allocation algorithms approach the optimal solution within a small number of iterations and unveil the trade-off between energy efficiency, system capacity, and wireless power transfer.
On multi-class learning through the minimization of the confusion matrix norm
Venue: arXiv cs.LG 2013
Year: 2013

In imbalanced multi-class classification problems, the misclassification rate as an error measure may not be a relevant choice. Several methods have been developed where the performance measure retained richer information than the mere misclassification rate: misclassification costs, ROC-based information, etc. Following this idea of dealing with alternate measures of performance, we propose to address imbalanced classification problems by using a new measure to be optimized: the norm of the confusion matrix. Indeed, recent results show that using the norm of the confusion matrix as an error measure can be quite interesting due to the fine-grain informations contained in the matrix, especially in the case of imbalanced classes. Our first contribution then consists in showing that optimizing criterion based on the confusion matrix gives rise to a common background for cost-sensitive methods aimed at dealing with imbalanced classes learning problems. As our second contribution, we propose an extension of a recent multi-class boosting method --- namely AdaBoost.MM --- to the imbalanced class problem, by greedily minimizing the empirical norm of the confusion matrix. A theoretical analysis of the properties of the proposed method is presented, while experimental results illustrate the behavior of the algorithm and show the relevancy of the approach compared to other methods.
A comment on the generalization of the Marinatto-Weber quantum game scheme
Venue: arXiv cs.GT 2013
Year: 2013

Iqbal and Toor [Phys. Rev. A {\bf 65}, 022306 (2002)] and [Commun. Theor. Phys. {\bf 42}, 335 (2004)] generalized the Marinatto-Weber quantum scheme for $2 \times 2$ games in order to study bimatrix games of $3 \times 3$ dimension, in particular the Rock-Paper-Scissors game. In our paper we show that Iqbal and Toor's generalization exhibits certain undesirable property that can considerably influence the game result. To support our argumentation, in the further part of the paper we construct the protocol corresponding to the MW concept for any finite bimatrix game that is free from the fault.
Bootstrapping Trust in Online Dating: Social Verification of Online Dating Profiles
Venue: arXiv cs.CR 2013
Year: 2013

Online dating is an increasingly thriving business which boasts billion-dollar revenues and attracts users in the tens of millions. Notwithstanding its popularity, online dating is not impervious to worrisome trust and privacy concerns raised by the disclosure of potentially sensitive data as well as the exposure to self-reported (and thus potentially misrepresented) information. Nonetheless, little research has, thus far, focused on how to enhance privacy and trustworthiness. In this paper, we report on a series of semi-structured interviews involving 20 participants, and show that users are significantly concerned with the veracity of online dating profiles. To address some of these concerns, we present the user-centered design of an interface, called Certifeye, which aims to bootstrap trust in online dating profiles using existing social network data. Certifeye verifies that the information users report on their online dating profile (e.g., age, relationship status, and/or photos) matches that displayed on their own Facebook profile. Finally, we present the results of a 161-user Mechanical Turk study assessing whether our veracity-enhancing interface successfully reduced concerns in online dating users and find a statistically significant trust increase.
A relation between additive and multiplicative complexity of Boolean functions
Venue: arXiv cs.DS 2013
Year: 2013

In the present note we prove an asymptotically tight relation between additive and multiplicative complexity of Boolean functions with respect to implementation by circuits over the basis {+,*,1}.
On the Computing of the Minimum Distance of Linear Block Codes by Heuristic Methods
Venue: arXiv cs.IT 2013
Year: 2013

The evaluation of the minimum distance of linear block codes remains an open problem in coding theory, and it is not easy to determine its true value by classical methods, for this reason the problem has been solved in the literature with heuristic techniques such as genetic algorithms and local search algorithms. In this paper we propose two approaches to attack the hardness of this problem. The first approach is based on genetic algorithms and it yield to good results comparing to another work based also on genetic algorithms. The second approach is based on a new randomized algorithm which we call Multiple Impulse Method MIM, where the principle is to search codewords locally around the all-zero codeword perturbed by a minimum level of noise, anticipating that the resultant nearest nonzero codewords will most likely contain the minimum Hamming-weight codeword whose Hamming weight is equal to the minimum distance of the linear code.
BarQL: Collaborating Through Change
Venue: arXiv cs.DB 2013
Year: 2013

Applications such as Google Docs, Office 365, and Dropbox show a growing trend towards incorporating multi-user live collaboration functionality into web applications. These collaborative applications share a need to efficiently express shared state, and a common strategy for doing so is a shared log abstraction. Extensive research efforts on log abstractions by the database, programming languages, and distributed systems communities have identified a variety of optimization techniques based on the algebraic properties of updates (i.e., pairwise commutativity, subsumption, and idempotence). Although these techniques have been applied to specific applications and use-cases, to the best of our knowledge, no attempt has been made to create a general framework for such optimizations in the context of a non-trivial update language. In this paper, we introduce mutation languages, a low-level framework for reasoning about the algebraic properties of state updates, or mutations. We define BarQL, a general purpose state-update language, and show how mutation languages allow us to reason about the algebraic properties of updates expressed in BarQ L .
Challenges with Automation in Digital Forensic Investigations
Venue: arXiv cs.CY 2013
Year: 2013

The use of automation in digital forensic investigations is not only a technological issue, but also has political and social implications. This work discusses some challenges with the implementation and acceptance of automation in digital forensic investigation, and possible implications for current digital forensic investigators. Current attitudes towards the use of automation in digital forensic investigations are examined, as well as the issue of digital investigators knowledge acquisition and retention. The argument is made for a well planned, careful use of automation going forward that allows for a more efficient and effective use of automation in digital forensic investigations while at the same time attempting to improve the overall quality of expert investigators. Targeting and carefully controlling automated solutions for beginning investigators may improve the speed and quality of investigations while at the same time letting expert digital investigators spend more time utilizing expert level knowledge required in manual phases of investigations. By considering how automated solutions are being implemented into digital investigations, investigation unit managers can increase the efficiency of their unit while at the same time maximizing their return on investment for expert level digital investigator training.
Markov chain aggregation and its applications to combinatorial reaction networks
Venue: arXiv cs.DM 2013
Year: 2013

We consider a continuous-time Markov chain (CTMC) whose state space is partitioned into aggregates, and each aggregate is assigned a probability measure. A sufficient condition for defining a CTMC over the aggregates is presented as a variant of weak lumpability, which also characterizes that the measure over the original process can be recovered from that of the aggregated one. We show how the applicability of de-aggregation depends on the initial distribution. The application section is a major aspect of the article, where we illustrate that the stochastic rule-based models for biochemical reaction networks form an important area for usage of the tools developed in the paper. For the rule-based models, the construction of the aggregates and computation of the distribution over the aggregates are algorithmic. The techniques are exemplified in three case studies.
Optimization of FASTEST-3D for Modern Multicore Systems
Venue: arXiv cs.PF 2013
Year: 2013

FASTEST-3D is an MPI-parallel finite-volume flow solver based on block-structured meshes that has been developed at the University of Erlangen-Nuremberg since the early 1990s. It can be used to solve the laminar or turbulent incompressible Navier-Stokes equations. Up to now its scalability was strongly limited by a rather rigid communication infrastructure, which led to a dominance of MPI time already at small process counts. This paper describes several optimizations to increase the performance, scalability, and flexibility of FASTEST-3D. First, a node-level performance analysis is carried out in order to pinpoint the main bottlenecks and identify sweet spots for energy-efficient execution. In addition, a single-precision version of the solver for the linear equation system arising from the discretization of the governing equations is devised, which significantly increases the single-core performance. Then the communication mechanisms in FASTEST-3D are analyzed and a new communication strategy based on non-blocking calls is implemented. Performance results with the revised version show significantly increased single-node performance and considerably improved communication patterns along with much better parallel scalability. In this context we discuss the concept of "acceptable parallel efficiency" and how it influences the real gain of the optimizations. Scaling measurements are carried out on a modern petascale system. The obtained improvements are of major importance for the use of FASTEST-3D on current high-performance computer clusters and will help to perform simulations with much higher spatial and temporal resolution to tackle turbulent flow in technical applications.