OpenRaiser/Intern-Atlas huggingface dataset:
Online Bipartite Matching with Decomposable Weights
Venue: arXiv cs.DS 2014
Year: 2014

We study a weighted online bipartite matching problem: $G(V_1, V_2, E)$ is a weighted bipartite graph where $V_1$ is known beforehand and the vertices of $V_2$ arrive online. The goal is to match vertices of $V_2$ as they arrive to vertices in $V_1$, so as to maximize the sum of weights of edges in the matching. If assignments to $V_1$ cannot be changed, no bounded competitive ratio is achievable. We study the weighted online matching problem with {\em free disposal}, where vertices in $V_1$ can be assigned multiple times, but only get credit for the maximum weight edge assigned to them over the course of the algorithm. For this problem, the greedy algorithm is $0.5$-competitive and determining whether a better competitive ratio is achievable is a well known open problem. We identify an interesting special case where the edge weights are decomposable as the product of two factors, one corresponding to each end point of the edge. This is analogous to the well studied related machines model in the scheduling literature, although the objective functions are different. For this case of decomposable edge weights, we design a 0.5664 competitive randomized algorithm in complete bipartite graphs. We show that such instances with decomposable weights are non-trivial by establishing upper bounds of 0.618 for deterministic and $0.8$ for randomized algorithms. A tight competitive ratio of $1-1/e \approx 0.632$ was known previously for both the 0-1 case as well as the case where edge weights depend on the offline vertices only, but for these cases, reassignments cannot change the quality of the solution. Beating 0.5 for weighted matching where reassignments are necessary has been a significant challenge. We thus give the first online algorithm with competitive ratio strictly better than 0.5 for a non-trivial case of weighted matching with free disposal.
Analyzing the Language of Food on Social Media
Venue: arXiv cs.CL 2014
Year: 2014

We investigate the predictive power behind the language of food on social media. We collect a corpus of over three million food-related posts from Twitter and demonstrate that many latent population characteristics can be directly predicted from this data: overweight rate, diabetes rate, political leaning, and home geographical location of authors. For all tasks, our language-based models significantly outperform the majority-class baselines. Performance is further improved with more complex natural language processing, such as topic modeling. We analyze which textual features have most predictive power for these datasets, providing insight into the connections between the language of food, geographic locale, and community characteristics. Lastly, we design and implement an online system for real-time query and visualization of the dataset. Visualization tools, such as geo-referenced heatmaps, semantics-preserving wordclouds and temporal histograms, allow us to discover more complex, global patterns mirrored in the language of food.
A wireless hand-held platform for robotic behavior control
Venue: arXiv cs.HC 2014
Year: 2014

The need for customizable properties in autonomous robotic platforms, such as in-home nursing care for the elderly and parallel implementations of human-to-machine control interfaces creates an opportunity to introduce methods deploying commonly available mobile devices running robotic command applications in managed code. This paper will discuss a human-to-machine interface and demonstrate a prototype consisting of a mobile device running a configurable application communicating with a mobile robot using a managed, type-safe language, C#.NET, over Bluetooth.
Managing Flexibility in Multi-Area Power Systems
Venue: arXiv cs.SY 2014
Year: 2014

In this paper we present a framework to efficiently characterize the available operational flexibility in a multi-area power system. We focus on the available reserves and the tie-line flows. The proposed approach is an alternative to the current calculation of the Available Transfer Capacity (ATC), as it considers location and availability of reserves, transmission constraints, and interdependencies of tie-line flows between different areas, while it takes into account the N-1 security criterion. The method is based on computational geometry using polytopic projections. It requires only a limited amount of information exchange and does not need central coordination. The method has two versions: a passive and an active approach, where neighboring areas can share reserves. In that respect we also introduce the term "exported flexibility", which could form the basis for a new trading product in electricity markets. Case studies demonstrate the improved tie-line utilization, especially if reserves are shared, and the visualization benefits.
DCT${^2}$Gen: A Versatile TCP Traffic Generator for Data Centers
Venue: arXiv cs.NI 2014
Year: 2014

Only little is publicly known about traffic in non-educational data centers. Recent studies made some knowledge available, which gives us the opportunity to create more realistic traffic models for data center research. We used this knowledge to create the first publicly available traffic generator that produces realistic traffic between hosts in data centers of arbitrary size. We characterize traffic by using six probability distribution functions and concentrate on the generation of traffic on flow-level. The distribution functions are described as step functions, which makes our generator highly configurable to generate traffic for different kinds of data centers. Moreover, in data centers, traffic between hosts in the same rack and hosts in different racks have different properties. We model this phenomenon, making our generated traffic very realistic. We carefully evaluated our approach and conclude that it reproduces these characteristics with high accuracy.
Secure pseudo-random linear binary sequences generators based on arithmetic polynoms
Venue: arXiv cs.CR 2014
Year: 2014

We present a new approach to constructing of pseudo-random binary sequences (PRS) generators for the purpose of cryptographic data protection, secured from the perpetrator's attacks, caused by generation of masses of hardware errors and faults. The new method is based on use of linear polynomial arithmetic for the realization of systems of boolean characteristic functions of PRS' generators. "Arithmetizatio" of systems of logic formulas has allowed to apply mathematical apparatus of residue systems for multisequencing of the process of PRS generation and organizing control of computing errors, caused by hardware faults. This has guaranteed high security of PRS generator's functioning and, consequently, security of tools for cryptographic data protection based on those PRSs.
Evaluation of Enhanced Security Solutions in 802.11-Based Networks
Venue: arXiv cs.CR 2014
Year: 2014

Traditionally, 802.11-based networks that relied on wired equivalent protocol (WEP) were especially vulnerable to packet sniffing. Today, wireless networks are more prolific, and the monitoring devices used to find them are mobile and easy to access. Securing wireless networks can be difficult because these networks consist of radio transmitters and receivers, and anybody can listen, capture data and attempt to compromise it. In recent years, a range of technologies and mechanisms have helped make networking more secure. This paper holistically evaluated various enhanced protocols proposed to solve WEP related authentication, confidentiality and integrity problems. It discovered that strength of each solution depends on how well the encryption, authentication and integrity techniques work. The work suggested using a Defence-in-Depth Strategy and integration of biometric solution in 802.11i. Comprehensive in-depth comparative analysis of each of the security mechanisms is driven by review of related work in WLAN security solutions.
Towards a Family-based Analysis of Applicability Conditions in Architectural Delta Models
Venue: arXiv cs.SE 2014
Year: 2014

Modeling variability in software architectures is a fundamental part of software product line development. ?-MontiArc allows describing architectural variability in a modular way by a designated core architecture and a set of architectural delta models modifying the core architecture to realize other architecture variants. Delta models have to satisfy a set of applicability conditions for the definedness of the architectural variants. The applicability conditions can in principle be checked by generating all possible architecture variants, which requires considering the same intermediate architectures repeatedly. In order to reuse previously computed architecture variants, we propose a family-based analysis of the applicability conditions using the concept of inverse deltas.
Hierarchical Variability Modeling for Software Architectures
Venue: arXiv cs.SE 2014
Year: 2014

Hierarchically decomposed component-based system development reduces design complexity by supporting distribution of work and component reuse. For product line development, the variability of the components to be deployed in different products has to be represented by appropriate means. In this paper, we propose hierarchical variability modeling which allows specifying component variability integrated with the component hierarchy and locally to the components. Components can contain variation points determining where components may vary. Associated variants define how this variability can be realized in different component configurations. We present a meta model for hierarchical variability modeling to formalize the conceptual ideas. In order to obtain an implementation of the proposed approach together with tool support, we extend the existing architectural description language MontiArc with hierarchical variability modeling. We illustrate the presented approach using an example from the automotive systems domain.
Towards a Semantics of Activity Diagrams with Semantic Variation Points
Venue: arXiv cs.SE 2014
Year: 2014

UML activity diagrams have become an established notation to model control and data ow on various levels of abstraction, ranging from fine-grained descriptions of algorithms to high-level workflow models in business applications. A formal semantics has to capture the flexibility of the interpretation of activity diagrams in real systems, which makes it inappropriate to define a fixed formal semantics. In this paper, we define a semantics with semantic variation points that allow for a customizable, application-specific interpretation of activity diagrams. We examine concrete variants of the activity diagram semantics which may also entail variants of the syntax re ecting the intended use at hand.
Rapid Integration and Calibration of New Sensors Using the Berkeley Aachen Robotics Toolkit (BART)
Venue: arXiv cs.SE 2014
Year: 2014

After the three DARPA Grand Challenge contests many groups around the world have continued to actively research and work toward an autonomous vehicle capable of accomplishing a mission in a given context (e.g. desert, city) while following a set of prescribed rules, but none has been completely successful in uncontrolled environments, a task that many people trivially fulfill every day. We believe that, together with improving the sensors used in cars and the artificial intelligence algorithms used to process the information, the community should focus on the systems engineering aspects of the problem, i.e. the limitations of the car (in terms of space, power, or heat dissipation) and the limitations of the software development cycle. This paper explores these issues and our experiences overcoming them.
Interrupt Timed Automata with Auxiliary Clocks and Parameters
Venue: arXiv cs.LO 2014
Year: 2014

Interrupt Timed Automata (ITA) is an expressive timed model, introduced to take into account interruptions, according to levels. Due to this feature, this formalism is incomparable with Timed Automata. However several decidability results related to reachability and model checking have been obtained. We add auxiliary clocks to ITA, thereby extending its expressive power while preserving decidability of reachability. Moreover, we define a parametrized version of ITA, with polynomials of parameters appearing in guards and updates. While parametric reasoning is particularly relevant for timed models, it very often leads to undecidability results. We prove that various reachability problems, including "robust" reachability, are decidable for this model, and we give complexity upper bounds for a fixed or variable number of clocks, levels and parameters.
The Crypto-democracy and the Trustworthy
Venue: arXiv cs.CR 2014
Year: 2014

In the current architecture of the Internet, there is a strong asymmetry in terms of power between the entities that gather and process personal data (e.g., major Internet companies, telecom operators, cloud providers, ...) and the individuals from which this personal data is issued. In particular, individuals have no choice but to blindly trust that these entities will respect their privacy and protect their personal data. In this position paper, we address this issue by proposing an utopian crypto-democracy model based on existing scientific achievements from the field of cryptography. More precisely, our main objective is to show that cryptographic primitives, including in particular secure multiparty computation, offer a practical solution to protect privacy while minimizing the trust assumptions. In the crypto-democracy envisioned, individuals do not have to trust a single physical entity with their personal data but rather their data is distributed among several institutions. Together these institutions form a virtual entity called the Trustworthy that is responsible for the storage of this data but which can also compute on it (provided first that all the institutions agree on this). Finally, we also propose a realistic proof-of-concept of the Trustworthy, in which the roles of institutions are played by universities. This proof-of-concept would have an important impact in demonstrating the possibilities offered by the crypto-democracy paradigm.
Approximating solution structure of the Weighted Sentence Alignment problem
Venue: arXiv cs.CL 2014
Year: 2014

We study the complexity of approximating solution structure of the bijective weighted sentence alignment problem of DeNero and Klein (2008). In particular, we consider the complexity of finding an alignment that has a significant overlap with an optimal alignment. We discuss ways of representing the solution for the general weighted sentence alignment as well as phrases-to-words alignment problem, and show that computing a string which agrees with the optimal sentence partition on more than half (plus an arbitrarily small polynomial fraction) positions for the phrases-to-words alignment is NP-hard. For the general weighted sentence alignment we obtain such bound from the agreement on a little over 2/3 of the bits. Additionally, we generalize the Hamming distance approximation of a solution structure to approximating it with respect to the edit distance metric, obtaining similar lower bounds.
On the Chain Pair Simplification Problem
Venue: arXiv cs.CG 2014
Year: 2014

The problem of efficiently computing and visualizing the structural resemblance between a pair of protein backbones in 3D has led Bereg et al. to pose the Chain Pair Simplification problem (CPS). In this problem, given two polygonal chains $A$ and $B$ of lengths $m$ and $n$, respectively, one needs to simplify them simultaneously, such that each of the resulting simplified chains, $A'$ and $B'$, is of length at most $k$ and the discrete \frechet\ distance between $A'$ and $B'$ is at most $δ$, where $k$ and $δ$ are given parameters. In this paper we study the complexity of CPS under the discrete \frechet\ distance (CPS-3F), i.e., where the quality of the simplifications is also measured by the discrete \frechet\ distance. Since CPS-3F was posed in 2008, its complexity has remained open. However, it was believed to be \npc, since CPS under the Hausdorff distance (CPS-2H) was shown to be \npc. We first prove that the weighted version of CPS-3F is indeed weakly \npc\, even on the line, based on a reduction from the set partition problem. Then, we prove that CPS-3F is actually polynomially solvable, by presenting an $O(m^2n^2\min\{m,n\})$ time algorithm for the corresponding minimization problem. In fact, we prove a stronger statement, implying, for example, that if weights are assigned to the vertices of only one of the chains, then the problem remains polynomially solvable. We also study a few less rigid variants of CPS and present efficient solutions for them. Finally, we present some experimental results that suggest that (the minimization version of) CPS-3F is significantly better than previous algorithms for the motivating biological application.
Comparing Feature Detectors: A bias in the repeatability criteria, and how to correct it
Venue: arXiv cs.CV 2014
Year: 2014

Most computer vision application rely on algorithms finding local correspondences between different images. These algorithms detect and compare stable local invariant descriptors centered at scale-invariant keypoints. Because of the importance of the problem, new keypoint detectors and descriptors are constantly being proposed, each one claiming to perform better (or to be complementary) to the preceding ones. This raises the question of a fair comparison between very diverse methods. This evaluation has been mainly based on a repeatability criterion of the keypoints under a series of image perturbations (blur, illumination, noise, rotations, homotheties, homographies, etc). In this paper, we argue that the classic repeatability criterion is biased towards algorithms producing redundant overlapped detections. To compensate this bias, we propose a variant of the repeatability rate taking into account the descriptors overlap. We apply this variant to revisit the popular benchmark by Mikolajczyk et al., on classic and new feature detectors. Experimental evidence shows that the hierarchy of these feature detectors is severely disrupted by the amended comparator.
A Manifesto for Semantic Model Differencing
Venue: arXiv cs.SE 2014
Year: 2014

Models are heavily used in software engineering and together with their systems they evolve over time. Thus, managing their changes is an important challenge for system maintainability. Existing approaches to model differencing concentrate on heuristics matching between model elements and on finding and presenting differences at a concrete or abstract syntactic level. While showing some success, these approaches are inherently limited to comparing syntactic structures. This paper is a manifesto for research on semantic model differencing. We present our vision to develop semantic diff operators for model comparisons: operators whose input consists of two models and whose output is a set of diff witnesses, instances of one model that are not instances of the other. In particular, if the models are syntactically different but there are no diff witnesses, the models are semantically equivalent. We demonstrate our vision using two concrete diff operators, for class diagrams and for activity diagrams. We motivate the use of semantic diff operators, brie y discuss the algorithms to compute them, list related challenges, and show their application and potential use as new fundamental building blocks for change management in model-driven engineering.
Performance Evaluation of HEVC over Broadband Networks
Venue: arXiv cs.NI 2014
Year: 2014

High efficiency video coding is the current trend setting standard for coding and transmission of video content. This standard has brought in many improvements over its predecessor H264 standard. In this paper, performance evaluation of transmitting HEVC content over the simulated network environment for disaster and calamity stricken area has been under taken. In the simulation the transmitted video sequences are subjected to various error models in NS3 simulator. The effects of speed and number of hosts on the jitter and delay characteristics of the underlying network while transmitting flows of HEVC based content has been evaluated. The extent and effect of network errors on the quality of HEVC bit stream in terms PSNR has also been tested. The results show that HEVC performs better for up to 0.001 percent network error, for up to 30 simultaneously transmitting nodes and for nodes travelling at speeds up to 100m/s.
Automatic Detection of Webpages that Share the Same Web Template
Venue: arXiv cs.IR 2014
Year: 2014

Template extraction is the process of isolating the template of a given webpage. It is widely used in several disciplines, including webpages development, content extraction, block detection, and webpages indexing. One of the main goals of template extraction is identifying a set of webpages with the same template without having to load and analyze too many webpages prior to identifying the template. This work introduces a new technique to automatically discover a reduced set of webpages in a website that implement the template. This set is computed with an hyperlink analysis that computes a very small set with a high level of confidence.
Social determinants of content selection in the age of (mis)information
Venue: arXiv cs.SI 2014
Year: 2014

Despite the enthusiastic rhetoric about the so called \emph{collective intelligence}, conspiracy theories -- e.g. global warming induced by chemtrails or the link between vaccines and autism -- find on the Web a natural medium for their dissemination. Users preferentially consume information according to their system of beliefs and the strife within users of opposite narratives may result in heated debates. In this work we provide a genuine example of information consumption from a sample of 1.2 million of Facebook Italian users. We show by means of a thorough quantitative analysis that information supporting different worldviews -- i.e. scientific and conspiracist news -- are consumed in a comparable way by their respective users. Moreover, we measure the effect of the exposure to 4709 evidently false information (satirical version of conspiracy theses) and to 4502 debunking memes (information aiming at contrasting unsubstantiated rumors) of the most polarized users of conspiracy claims. We find that either contrasting or teasing consumers of conspiracy narratives increases their probability to interact again with unsubstantiated rumors.
Innocent Strategies are Sheaves over Plays---Deterministic, Non-deterministic and Probabilistic Innocence
Venue: arXiv cs.PL 2014
Year: 2014

Although the HO/N games are fully abstract for PCF, the traditional notion of innocence (which underpins these games) is not satisfactory for such language features as non-determinism and probabilistic branching, in that there are stateless terms that are not innocent. Based on a category of P-visible plays with a notion of embedding as morphisms, we propose a natural generalisation by viewing innocent strategies as sheaves over (a site of) plays, echoing a slogan of Hirschowitz and Pous. Our approach gives rise to fully complete game models in each of the three cases of deterministic, nondeterministic and probabilistic branching. To our knowledge, in the second and third cases, ours are the first such factorisation-free constructions.