OpenRaiser/Intern-Atlas huggingface dataset:
Joint interpretation of on-board vision and static GPS cartography for determination of correct speed limit
Venue: arXiv cs.CV 2010
Year: 2010

We present here a first prototype of a "Speed Limit Support" Advance Driving Assistance System (ADAS) producing permanent reliable information on the current speed limit applicable to the vehicle. Such a module can be used either for information of the driver, or could even serve for automatic setting of the maximum speed of a smart Adaptive Cruise Control (ACC). Our system is based on a joint interpretation of cartographic information (for static reference information) with on-board vision, used for traffic sign detection and recognition (including supplementary sub-signs) and visual road lines localization (for detection of lane changes). The visual traffic sign detection part is quite robust (90% global correct detection and recognition for main speed signs, and 80% for exit-lane sub-signs detection). Our approach for joint interpretation with cartography is original, and logic-based rather than probability-based, which allows correct behaviour even in cases, which do happen, when both vision and cartography may provide the same erroneous information.
Combating False Reports for Secure Networked Control in Smart Grid via Trustiness Evaluation
Venue: arXiv cs.CR 2010
Year: 2010

Smart grid, equipped with modern communication infrastructures, is subject to possible cyber attacks. Particularly, false report attacks which replace the sensor reports with fraud ones may cause the instability of the whole power grid or even result in a large area blackout. In this paper, a trustiness system is introduced to the controller, who computes the trustiness of different sensors by comparing its prediction, obtained from Kalman filtering, on the system state with the reports from sensor. The trustiness mechanism is discussed and analyzed for the Linear Quadratic Regulation (LQR) controller. Numerical simulations show that the trustiness system can effectively combat the cyber attacks to smart grid.
On Graph Crossing Number and Edge Planarization
Venue: arXiv cs.DS 2010
Year: 2010

Given an n-vertex graph G, a drawing of G in the plane is a mapping of its vertices into points of the plane, and its edges into continuous curves, connecting the images of their endpoints. A crossing in such a drawing is a point where two such curves intersect. In the Minimum Crossing Number problem, the goal is to find a drawing of G with minimum number of crossings. The value of the optimal solution, denoted by OPT, is called the graph's crossing number. This is a very basic problem in topological graph theory, that has received a significant amount of attention, but is still poorly understood algorithmically. The best currently known efficient algorithm produces drawings with $O(\log^2 n)(n + OPT)$ crossings on bounded-degree graphs, while only a constant factor hardness of approximation is known. A closely related problem is Minimum Edge Planarization, in which the goal is to remove a minimum-cardinality subset of edges from G, such that the remaining graph is planar. Our main technical result establishes the following connection between the two problems: if we are given a solution of cost k to the Minimum Edge Planarization problem on graph G, then we can efficiently find a drawing of G with at most $\poly(d)\cdot k\cdot (k+OPT)$ crossings, where $d$ is the maximum degree in G. This result implies an $O(n\cdot \poly(d)\cdot \log^{3/2}n)$-approximation for Minimum Crossing Number, as well as improved algorithms for special cases of the problem, such as, for example, k-apex and bounded-genus graphs.
Broadcasting over the Relay Channel with Oblivious Cooperative Strategy
Venue: arXiv cs.IT 2010
Year: 2010

This paper investigates the problem of information transmission over the simultaneous relay channel with two users (or two possible channel outcomes) where for one of them the more suitable strategy is Decode-and-Forward (DF) while for the other one is Compress-and-Forward (CF). In this setting, it is assumed that the source wishes to send common and private informations to each of the users (or channel outcomes). This problem is relevant to: (i) the transmission of information over the broadcast relay channel (BRC) with different relaying strategies and (ii) the transmission of information over the conventional relay channel where the source is oblivious to the coding strategy of relay. A novel coding that integrates simultaneously DF and CF schemes is proposed and an inner bound on the capacity region is derived for the case of general memoryless BRCs. As special case, the Gaussian BRC is studied where it is shown that by means of the suggested broadcast coding the common rate can be improved compared to existing strategies. Applications of these results arise in broadcast scenarios with relays or in wireless scenarios where the source does not know whether the relay is collocated with the source or with the destination.
Time-aware Collaborative Filtering with the Piecewise Decay Function
Venue: arXiv cs.IR 2010
Year: 2010

In this paper, we determine the appropriate decay function for item-based collaborative filtering (CF). Instead of intuitive deduction, we introduce the Similarity-Signal-to-Noise-Ratio (SSNR) to quantify the impacts of rated items on current recommendations. By measuring the variation of SSNR over time, drift in user interest is well visualized and quantified. Based on the trend changes of SSNR, the piecewise decay function is thus devised and incorporated to build our time-aware CF algorithm. Experiments show that the proposed algorithm strongly outperforms the conventional item-based CF algorithm and other time-aware algorithms with various decay functions.
Colour Guided Colour Image Steganography
Venue: arXiv cs.MM 2010
Year: 2010

Information security has become a cause of concern because of the electronic eavesdropping. Capacity, robustness and invisibility are important parameters in information hiding and are quite difficult to achieve in a single algorithm. This paper proposes a novel steganography technique for digital color image which achieves the purported targets. The professed methodology employs a complete random scheme for pixel selection and embedding of data. Of the three colour channels (Red, Green, Blue) in a given colour image, the least two significant bits of any one of the channels of the color image is used to channelize the embedding capacity of the remaining two channels. We have devised three approaches to achieve various levels of our desired targets. In the first approach, Red is the default guide but it results in localization of MSE in the remaining two channels, which makes it slightly vulnerable. In the second approach, user gets the liberty to select the guiding channel (Red, Green or Blue) to guide the remaining two channels. It will increase the robustness and imperceptibility of the embedded image however the MSE factor will still remain as a drawback. The third approach improves the performance factor as a cyclic methodology is employed and the guiding channel is selected in a cyclic fashion. This ensures the uniform distribution of MSE, which gives better robustness and imperceptibility along with enhanced embedding capacity. The imperceptibility has been enhanced by suitably adapting optimal pixel adjustment process (OPAP) on the stego covers.
Efficient Matrix Completion with Gaussian Models
Venue: arXiv cs.LG 2010
Year: 2010

A general framework based on Gaussian models and a MAP-EM algorithm is introduced in this paper for solving matrix/table completion problems. The numerical experiments with the standard and challenging movie ratings data show that the proposed approach, based on probably one of the simplest probabilistic models, leads to the results in the same ballpark as the state-of-the-art, at a lower computational cost.
Towards an SDP-based Approach to Spectral Methods: A Nearly-Linear-Time Algorithm for Graph Partitioning and Decomposition
Venue: arXiv cs.DS 2010
Year: 2010

In this paper, we consider the following graph partitioning problem: The input is an undirected graph $G=(V,E),$ a balance parameter $b \in (0,1/2]$ and a target conductance value $γ\in (0,1).$ The output is a cut which, if non-empty, is of conductance at most $O(f),$ for some function $f(G, γ),$ and which is either balanced or well correlated with all cuts of conductance at most $γ.$ Spielman and Teng gave an $\tilde{O}(|E|/γ^{2})$-time algorithm for $f= \sqrt{γ\log^{3}|V|}$ and used it to decompose graphs into a collection of near-expanders. We present a new spectral algorithm for this problem which runs in time $\tilde{O}(|E|/γ)$ for $f=\sqrtγ.$ Our result yields the first nearly-linear time algorithm for the classic Balanced Separator problem that achieves the asymptotically optimal approximation guarantee for spectral methods. Our method has the advantage of being conceptually simple and relies on a primal-dual semidefinite-programming SDP approach. We first consider a natural SDP relaxation for the Balanced Separator problem. While it is easy to obtain from this SDP a certificate of the fact that the graph has no balanced cut of conductance less than $γ,$ somewhat surprisingly, we can obtain a certificate for the stronger correlation condition. This is achieved via a novel separation oracle for our SDP and by appealing to Arora and Kale's framework to bound the running time. Our result contains technical ingredients that may be of independent interest.
A Protocol for Self-Synchronized Duty-Cycling in Sensor Networks: Generic Implementation in Wiselib
Venue: arXiv cs.AI 2010
Year: 2010

In this work we present a protocol for self-synchronized duty-cycling in wireless sensor networks with energy harvesting capabilities. The protocol is implemented in Wiselib, a library of generic algorithms for sensor networks. Simulations are conducted with the sensor network simulator Shawn. They are based on the specifications of real hardware known as iSense sensor nodes. The experimental results show that the proposed mechanism is able to adapt to changing energy availabilities. Moreover, it is shown that the system is very robust against packet loss.
Parallel Sparse Matrix Solver on the GPU Applied to Simulation of Electrical Machines
Venue: arXiv cs.DC 2010
Year: 2010

Nowadays, several industrial applications are being ported to parallel architectures. In fact, these platforms allow acquire more performance for system modelling and simulation. In the electric machines area, there are many problems which need speed-up on their solution. This paper examines the parallelism of sparse matrix solver on the graphics processors. More specifically, we implement the conjugate gradient technique with input matrix stored in CSR, and Symmetric CSR and CSC formats. This method is one of the most efficient iterative methods available for solving the finite-element basis functions of Maxwell's equations. The GPU (Graphics Processing Unit), which is used for its implementation, provides mechanisms to parallel the algorithm. Thus, it increases significantly the computation speed in relation to serial code on CPU based systems.
Cluster based Key Management in Wireless Sensor Networks
Venue: arXiv cs.CR 2010
Year: 2010

Wireless sensor networks consist of sensor nodes with limited computational and communication capabilities. In this paper, the whole network of sensor nodes is divided into clusters based on their physical locations. In addition, efficient ways of key distribution among the nodes within the cluster and among controllers of each cluster are discussed. Also, inter and intra cluster communications are presented in detail. The security of the entire network through efficient key management by taking into consideration the network's power capabilities is discussed. A graphical representation of the simulation on the scheme is also presented.
Design-on-demand or how to create a target-oriented social web-site
Venue: arXiv cs.CY 2010
Year: 2010

We describe an informal methodology for developing on-line applications, which is, to some extent, complementary to the Web 2.0 aspects of web development. The presented methodology is suitable for developing low-cost and non-cost web sites targeted at medium-sized communities. We present basic building blocks used in the described strategy. To achieve a better understanding of the discussed concepts we comment on their application during the realization of two web projects. We focus on the role of community-driven development, which is crucial for projects of the discussed type.
On Design of Collaborative Beamforming for Two-Way Relay Networks
Venue: arXiv cs.IT 2010
Year: 2010

We consider a two-way relay network, where two source nodes, S1 and S2, exchange information through a cluster of relay nodes. The relay nodes receive the sum signal from S1 and S2 in the first time slot. In the second time slot, each relay node multiplies its received signal by a complex coefficient and retransmits the signal to the two source nodes, which leads to a collaborative two-way beamforming system. By applying the principle of analog network coding, each receiver at S1 and S2 cancels the "self-interference" in the received signal from the relay cluster and decodes the message. This paper studies the 2-dimensional achievable rate region for such a two-way relay network with collaborative beamforming. With different assumptions of channel reciprocity between the source-relay and relay-source channels, the achievable rate region is characterized under two setups. First, with reciprocal channels, we investigate the achievable rate regions when the relay cluster is subject to a sum-power constraint or individual-power constraints. We show that the optimal beamforming vectors obtained from solving the weighted sum inverse-SNR minimization (WSISMin) problems are sufficient to characterize the corresponding achievable rate region. Furthermore, we derive the closed form solutions for those optimal beamforming vectors and consequently propose the partially distributed algorithms to implement the optimal beamforming, where each relay node only needs the local channel information and one global parameter. Second, with the non-reciprocal channels, the achievable rate regions are also characterized for both the sum-power constraint case and the individual-power constraint case. Although no closed-form solutions are available under this setup, we present efficient numerical algorithms.
On optimizing over lift-and-project closures
Venue: arXiv cs.RO 2010
Year: 2010

The lift-and-project closure is the relaxation obtained by computing all lift-and-project cuts from the initial formulation of a mixed integer linear program or equivalently by computing all mixed integer Gomory cuts read from all tableau's corresponding to feasible and infeasible bases. In this paper, we present an algorithm for approximating the value of the lift-and-project closure. The originality of our method is that it is based on a very simple cut generation linear programming problem which is obtained from the original linear relaxation by simply modifying the bounds on the variables and constraints. This separation LP can also be seen as the dual of the cut generation LP used in disjunctive programming procedures with a particular normalization. We study some properties of this separation LP in particular relating it to the equivalence between lift-and-project cuts and Gomory cuts shown by Balas and Perregaard. Finally, we present some computational experiments and comparisons with recent related works.
Translation-Invariant Representation for Cumulative Foot Pressure Images
Venue: arXiv cs.AI 2010
Year: 2010

Human can be distinguished by different limb movements and unique ground reaction force. Cumulative foot pressure image is a 2-D cumulative ground reaction force during one gait cycle. Although it contains pressure spatial distribution information and pressure temporal distribution information, it suffers from several problems including different shoes and noise, when putting it into practice as a new biometric for pedestrian identification. In this paper, we propose a hierarchical translation-invariant representation for cumulative foot pressure images, inspired by the success of Convolutional deep belief network for digital classification. Key contribution in our approach is discriminative hierarchical sparse coding scheme which helps to learn useful discriminative high-level visual features. Based on the feature representation of cumulative foot pressure images, we develop a pedestrian recognition system which is invariant to three different shoes and slight local shape change. Experiments are conducted on a proposed open dataset that contains more than 2800 cumulative foot pressure images from 118 subjects. Evaluations suggest the effectiveness of the proposed method and the potential of cumulative foot pressure images as a biometric.
Static vs Dynamic SAGAs
Venue: arXiv cs.PL 2010
Year: 2010

SAGAs calculi (or simply SAGAs) have been proposed by Bruni et al. as a model for long-running transactions. The approach therein can be considered static, while a dynamic approach has been proposed by Lanese and Zavattaro. In this paper we first extend both static SAGAs (in the centralized interruption policy) and dynamic SAGAs to deal with nesting, then we compare the two approaches.
Safety-Guarantee Controller Synthesis for Cyber-Physical Systems
Venue: arXiv cs.LO 2010
Year: 2010

The verification and validation of cyber-physical systems is known to be a difficult problem due to the different modeling abstractions used for control components and for software components. A recent trend to address this difficulty is to reduce the need for verification by adopting correct-by-design methodologies. According to the correct-by-design paradigm, one seeks to automatically synthesize a controller that can be refined into code and that enforces temporal specifications on the cyber-physical system. In this paper we consider an instance of this problem where the specifications are given by a fragment of Linear Temporal Logic (LTL) and the physical environment is described by a smooth differential equation. The contribution of this paper is to show that synthesis for cyber-physical systems is viable by considering a fragment of LTL that is expressive enough to describe interesting properties but simple enough to avoid Safra's construction. We report on two examples illustrating a preliminary implementation of these techniques on the tool PESSOALTL.
Analysis of temporal characteristics of the editorial processing in scientific periodicals
Venue: arXiv cs.DL 2010
Year: 2010

The first part of our work is connected with the analysis of typical random variables for the specific human-initiated process. We study the data characterizing editorial work with received manuscripts in several scientific journals. In such a way we found the waiting time distributions that could be called the typical for an ordinary peer-review scientific journal. In the second part of this study a model of editorial processing of received manuscripts is developed. Within the model, different scenarios of the manuscript editorial processing are examined. Combining the results of the quantitative experiment and model simulations we arrive to the set of conclusions about time characteristics of editorial process in scientific journals and a peer-review contribution.
Random Graph Generator for Bipartite Networks Modeling
Venue: arXiv cs.AI 2010
Year: 2010

The purpose of this article is to introduce a new iterative algorithm with properties resembling real life bipartite graphs. The algorithm enables us to generate wide range of random bigraphs, which features are determined by a set of parameters.We adapt the advances of last decade in unipartite complex networks modeling to the bigraph setting. This data structure can be observed in several situations. However, only a few datasets are freely available to test the algorithms (e.g. community detection, influential nodes identification, information retrieval) which operate on such data. Therefore, artificial datasets are needed to enhance development and testing of the algorithms. We are particularly interested in applying the generator to the analysis of recommender systems. Therefore, we focus on two characteristics that, besides simple statistics, are in our opinion responsible for the performance of neighborhood based collaborative filtering algorithms. The features are node degree distribution and local clustering coeficient.
Random Graphs for Performance Evaluation of Recommender Systems
Venue: arXiv cs.AI 2010
Year: 2010

The purpose of this article is to introduce a new analytical framework dedicated to measuring performance of recommender systems. The standard approach is to assess the quality of a system by means of accuracy related statistics. However, the specificity of the environments in which recommender systems are deployed requires to pay much attention to speed and memory requirements of the algorithms. Unfortunately, it is implausible to assess accurately the complexity of various algorithms with formal tools. This can be attributed to the fact that such analyses are usually based on an assumption of dense representation of underlying data structures. Whereas, in real life the algorithms operate on sparse data and are implemented with collections dedicated for them. Therefore, we propose to measure the complexity of recommender systems with artificial datasets that posses real-life properties. We utilize recently developed bipartite graph generator to evaluate how state-of-the-art recommender systems' behavior is determined and diversified by topological properties of the generated datasets.
Feedback Vertex Set in Mixed Graphs
Venue: arXiv cs.DS 2010
Year: 2010

A mixed graph is a graph with both directed and undirected edges. We present an algorithm for deciding whether a given mixed graph on $n$ vertices contains a feedback vertex set (FVS) of size at most $k$, in time $2^{O(k)}k! O(n^4)$. This is the first fixed parameter tractable algorithm for FVS that applies to both directed and undirected graphs.
Well-formedness and typing rules for UML Composite Structures
Venue: arXiv cs.SE 2010
Year: 2010

Starting from version 2.0, UML introduced hierarchical composite structures, which are an expressive way of defining complex software architectures, but which have a very loosely defined semantics in the standard. In this paper we propose a set of consistency rules that disambiguate the meaning of UML composite structures. Our primary goal was to have an operational model of composite structures for the OMEGA UML profile, an executable profile dedicated to the formal specification and validation of real-time systems, developed in a past project to which we contributed. However, the rules and principles stated here are applicable to other hierarchical component models based on the same concepts, such as SysML. The presented ruleset is supported by an OCL formalization which is described in this report. This formalization was applied on different complex models for the evaluation and validation of the proposed principles.
On the Capacity of the 2-user Gaussian MAC Interfering with a P2P Link
Venue: arXiv cs.IT 2010
Year: 2010

A multiple access channel and a point-to-point channel sharing the same medium for communications are considered. We obtain an outer bound for the capacity region of this setup, and we show that this outer bound is achievable in some cases. These cases are mainly when interference is strong or very strong. A sum capacity upper bound is also obtained, which is nearly tight if the interference power at the receivers is low. In this case, using Gaussian codes and treating interference as noise achieves a sum rate close to the upper bound.