OpenRaiser/Intern-Atlas huggingface dataset:
Supervised Random Walks: Predicting and Recommending Links in Social Networks
Venue: arXiv cs.SI 2010
Year: 2010

Predicting the occurrence of links is a fundamental problem in networks. In the link prediction problem we are given a snapshot of a network and would like to infer which interactions among existing members are likely to occur in the near future or which existing interactions are we missing. Although this problem has been extensively studied, the challenge of how to effectively combine the information from the network structure with rich node and edge attribute data remains largely open. We develop an algorithm based on Supervised Random Walks that naturally combines the information from the network structure with node and edge level attributes. We achieve this by using these attributes to guide a random walk on the graph. We formulate a supervised learning task where the goal is to learn a function that assigns strengths to edges in the network such that a random walker is more likely to visit the nodes to which new links will be created in the future. We develop an efficient training algorithm to directly learn the edge strength estimation function. Our experiments on the Facebook social graph and large collaboration networks show that our approach outperforms state-of-the-art unsupervised approaches as well as approaches that are based on feature extraction.
Motifs de graphe pour le calcul de dépendances syntaxiques complètes
Venue: arXiv cs.CL 2010
Year: 2010

This article describes a method to build syntactical dependencies starting from the phrase structure parsing process. The goal is to obtain all the information needed for a detailled semantical analysis. Interaction Grammars are used for parsing; the saturation of polarities which is the core of this formalism can be mapped to dependency relation. Formally, graph patterns are used to express the set of constraints which control dependency creations.
A Fuzzy Clustering Model for Fuzzy Data with Outliers
Venue: arXiv cs.CV 2010
Year: 2010

In this paper a fuzzy clustering model for fuzzy data with outliers is proposed. The model is based on Wasserstein distance between interval valued data which is generalized to fuzzy data. In addition, Keller's approach is used to identify outliers and reduce their influences. We have also defined a transformation to change our distance to the Euclidean distance. With the help of this approach, the problem of fuzzy clustering of fuzzy data is reduced to fuzzy clustering of crisp data. In order to show the performance of the proposed clustering algorithm, two simulation experiments are discussed.
Coverage games in small cells networks
Venue: arXiv cs.GT 2010
Year: 2010

This paper considers the problem of cooperative power control in distributed small cell wireless networks. We introduce a novel framework, based on repeated games, which models the interactions of the different transmit base stations in the downlink. By exploiting the specific structure of the game, we show that we can improve the system performance by selecting the Pareto optimal solution as well as reduce the price of stability.
Characterization and definability in modal first-order fragments
Venue: arXiv cs.LO 2010
Year: 2010

Model theoretic results such as Characterization and Definability give important information about different logics. It is well known that the proofs of those results for several modal logics have, somehow, the same 'taste'. A general proof for most modal logics below first order is still too ambitious. In this thesis we plan to isolate sufficient conditions for the characterization and definability theorems to hold in a wide range of logics. Along with these conditions we will prove that, whichever logic that meets them, satisfies both theorems. Therefore, one could give an unifying proof for logics with already known results. Moreover, one will be able to prove characterization and definability results for logics that have not yet been investigated. In both cases, it is only needed to check that a logic meets the requirements to automatically derive the desired results.
A self-managing fault management mechanism for wireless sensor networks
Venue: arXiv cs.NI 2010
Year: 2010

A sensor network can be described as a collection of sensor nodes which co-ordinate with each other to perform some specific function. These sensor nodes are mainly in large numbers and are densely deployed either inside the phenomenon or very close to it. They can be used for various application areas (e.g. health, military, home). Failures are inevitable in wireless sensor networks due to inhospitable environment and unattended deployment. Therefore, it is necessary that network failures are detected in advance and appropriate measures are taken to sustain network operation. We previously proposed a cellular approach for fault detection and recovery. In this paper we extend the cellular approach and propose a new fault management mechanism to deal with fault detection and recovery. We propose a hierarchical structure to properly distribute fault management tasks among sensor nodes by introducing more 'self-managing' functions. The proposed failure detection and recovery algorithm has been compared with some existing related work and proven to be more energy efficient.
State-Based Random Access: A Cross-Layer Approach
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we propose novel state-based algorithms which dynamically control the random access network based on its current state such as channel states of wireless links and backlog states of the queues. After formulating the problem, corresponding algorithms with diverse control functions are proposed. Consequently, it will be shown that the proposed state-based schemes for control of the random access networks, results in significant performance gains in comparison with previously proposed control algorithms. In order to select an appropriate control function, performances of the state-based control algorithms are compared for a wide range of traffic scenarios. It is also shown that even an approximate knowledge of network statistics helps in selecting the proper state dependent control function.
Computation of the shortest path between two curves on a parametric surface by geodesic-like method
Venue: arXiv cs.CG 2010
Year: 2010

In this paper, we present the geodesic-like algorithm for the computation of the shortest path between two objects on NURBS surfaces and periodic surfaces. This method can improve the distance problem not only on surfaces but in $\mathbb{R}^3$. Moreover, the geodesic-like algorithm also provides an efficient approach to simulate the minimal geodesic between two holes on a NURBS surfaces.
World of Movable Objects. Part 2
Venue: arXiv cs.HC 2010
Year: 2010

This book is about the transformation of screen objects into movable and resizable and about the design of applications entirely on the basis of such elements. The screen objects have a wide variety of shapes; they can be either graphical objects or controls; there are solitary objects and very complex objects parts of which are involved in individual, synchronous, and related movements. Objects can be involved in forward movements and rotation; they can be resized and reconfigured; all these movements and situations are considered. On the basis of total movability, the new type of programs -- user-driven applications -- are designed. These applications continue to work according to their main purposes, but the whole control of what, when, and how must appear on the screen is passed from designers to users. Due to the size restriction used on CoRR, the book is divided here into two parts and one appendix is deleted. At www.sourceforge.net in the project MoveableGraphics the whole book is available in a single file together with the accompanying application with all its source codes.
Energy Efficient Clustering and Routing in Mobile Wireless Sensor Network
Venue: arXiv cs.NI 2010
Year: 2010

A critical need in Mobile Wireless Sensor Network (MWSN) is to achieve energy efficiency during routing as the sensor nodes have scarce energy resource. The nodes' mobility in MWSN poses a challenge to design an energy efficient routing protocol. Clustering helps to achieve energy efficiency by reducing the organization complexity overhead of the network which is proportional to the number of nodes in the network. This paper proposes a novel hybrid multipath routing algorithm with an efficient clustering technique. A node is selected as cluster head if it has high surplus energy, better transmission range and least mobility. The Energy Aware (EA) selection mechanism and the Maximal Nodal Surplus Energy estimation technique incorporated in this algorithm improves the energy performance during routing. Simulation results can show that the proposed clustering and routing algorithm can scale well in dynamic and energy deficient mobile sensor network.
VHDL Implementation and Verification of ARINC-429 Core
Venue: arXiv cs.OH 2010
Year: 2010

Modern Avionics are controlled by sophisticated mission components in the Aircraft. The control function is implemented via a standard ARINC-429 bus interface. It is a two-wire point-topoint serial data bus for control communications in Avionics. The bus operates 12.5 or 100kb/sec, the implementation is envisaged for one transmits and receive channel respectively. Further the code can be modified for more no of independent Tx and Rx channels. An on chip memory allotment on the FPGA will provide a buffer bank for storing the incoming or outgoing data. For this purpose SRAM based FPGAs are utilized. This flexible ARINC429 solution gives exactly what is needed for real time applications. The IP can be programmed to send an interrupt to the host and also prepare it to process the data. Majority of the hardware function of digital natures are embedded into a single FPGA by saving in terms of PCB board space, power consumption and volume results. This paper deals with the development, implementation, simulation, and verification of ARINC_429 formats. The IP core development is described in VHDL.
An Adaptive Multi-channel P2P Video-on-Demand System using Plug-and-Play Helpers
Venue: arXiv cs.NI 2010
Year: 2010

We present a multi-channel P2P Video-on-Demand (VoD) system using "plug-and-play" helpers. Helpers are heterogenous "micro-servers" with limited storage, bandwidth and number of users they can serve simultaneously. Our proposed system has the following salient features: (1) it minimizes the server load; (2) it is distributed, and requires little or no maintenance overhead and which can easily adapt to system dynamics; and (3) it is adaptable to varying supply and demand patterns across multiple video channels irrespective of video popularity. Our proposed solution jointly optimizes over helper-user topology, video storage allocation and bandwidth allocation. The combinatorial nature of the problem and the system demand for distributed algorithms makes the problem uniquely challenging. By utilizing Lagrangian decomposition and Markov chain approximation based arguments, we address this challenge by designing two distributed algorithms running in tandem: a primal-dual storage and bandwidth allocation algorithm and a "soft-worst-neighbor-choking" topology-building algorithm. Our scheme provably converges to a near-optimal solution, and is easy to implement in practice. Simulation results validate that the proposed scheme achieves minimum sever load under highly heterogeneous combinations of supply and demand patterns, and is robust to system dynamics of user/helper churn, user/helper asynchrony, and random delays in the network.
SICStus Prolog -- the first 25 years
Venue: arXiv cs.PL 2010
Year: 2010

SICStus Prolog has evolved for nearly 25 years. This is an appropriate point in time for revisiting the main language and design decisions, and try to distill some lessons. SICStus Prolog was conceived in a context of multiple, conflicting Prolog dialect camps and a fledgling standardization effort. We reflect on the impact of this effort and role model implementations on our development. After summarizing the development history, we give a guided tour of the system anatomy, exposing some designs that were not published before. We give an overview of our new interactive development environment, and describe a sample of key applications. Finally, we try to identify key good and not so good design decisions.
Formulation Of A N-Degree Polynomial For Depth Estimation using a Single Image
Venue: arXiv cs.CV 2010
Year: 2010

The depth of a visible surface of a scene is the distance between the surface and the sensor. Recovering depth information from two-dimensional images of a scene is an important task in computer vision that can assist numerous applications such as object recognition, scene interpretation, obstacle avoidance, inspection and assembly. Various passive depth computation techniques have been developed for computer vision applications. They can be classified into two groups. The first group operates using just one image. The second group requires more than one image which can be acquired using either multiple cameras or a camera whose parameters and positioning can be changed. This project is aimed to find the real depth of the object from the camera which had been used to click the photograph. An n-degree polynomial was formulated, which maps the pixel depth of an image to the real depth. In order to find the coefficients of the polynomial, an experiment was carried out for a particular lens and thus, these coefficients are a unique feature of a particular camera. The procedure explained in this report is a monocular approach for estimation of depth of a scene. The idea involves mapping the Pixel Depth of the object photographed in the image with the Real Depth of the object from the camera lens with an interpolation function. In order to find the parameters of the interpolation function, a set of lines with predefined distance from camera is used, and then the distance of each line from the bottom edge of the picture (as the origin line) is calculated.
Dotted Version Vectors: Logical Clocks for Optimistic Replication
Venue: arXiv cs.DC 2010
Year: 2010

In cloud computing environments, a large number of users access data stored in highly available storage systems. To provide good performance to geographically disperse users and allow operation even in the presence of failures or network partitions, these systems often rely on optimistic replication solutions that guarantee only eventual consistency. In this scenario, it is important to be able to accurately and efficiently identify updates executed concurrently. In this paper, first we review, and expose problems with current approaches to causality tracking in optimistic replication: these either lose information about causality or do not scale, as they require replicas to maintain information that grows linearly with the number of clients or updates. Then, we propose a novel solution that fully captures causality while being very concise in that it maintains information that grows linearly only with the number of servers that register updates for a given data element, bounded by the degree of replication.
Edge Preserving Image Denoising in Reproducing Kernel Hilbert Spaces
Venue: arXiv cs.CV 2010
Year: 2010

The goal of this paper is the development of a novel approach for the problem of Noise Removal, based on the theory of Reproducing Kernels Hilbert Spaces (RKHS). The problem is cast as an optimization task in a RKHS, by taking advantage of the celebrated semiparametric Representer Theorem. Examples verify that in the presence of gaussian noise the proposed method performs relatively well compared to wavelet based technics and outperforms them significantly in the presence of impulse or mixed noise. A more detailed version of this work has been published in the IEEE Trans. Im. Proc. : P. Bouboulis, K. Slavakis and S. Theodoridis, Adaptive Kernel-based Image Denoising employing Semi-Parametric Regularization, IEEE Transactions on Image Processing, vol 19(6), 2010, 1465 - 1479.
Border basis detection is NP-complete
Venue: arXiv cs.CC 2010
Year: 2010

Border basis detection (BBD) is described as follows: given a set of generators of an ideal, decide whether that set of generators is a border basis of the ideal with respect to some order ideal. The motivation for this problem comes from a similar problem related to Gröbner bases termed as Gröbner basis detection (GBD) which was proposed by Gritzmann and Sturmfels (1993). GBD was shown to be NP-hard by Sturmfels and Wiegelmann (1996). In this paper, we investigate the computational complexity of BBD and show that it is NP-complete.
Performance Analysis of a 60 GHz Near Gigabit System for WPAN Applications
Venue: arXiv cs.NI 2010
Year: 2010

A 60 GHz wireless Gigabit Ethernet (G.E.) communication system capable of near gigabit data rate has been developed at IETR. The realized system covers 2 GHz available bandwidth. This paper describes the design and realization of the overall system including the baseband (BB), intermediate frequency (IF) and radiofrequency (RF) blocks. A differential binary shift keying (DBPSK) modulation and a differential demodulation are adopted at IF. In the BB processing block, an original byte/frame synchronization technique is designed to provide a small value of the preamble false alarm and missing probabilities. For the system performances, two different real scenarios are investigated: measurements carried out in a large gym and in hallways. Bit error rate (BER) measurements have been performed in different configurations: with/without RS (255, 239) coding, with frame synchronization using 32/64 bits preambles. As shown by simulation, the 64 bits preamble provides sufficient robustness and improves the system performance in term of BER. At a data rate of 875 Mbps, a BER of 10-8 was measured at 30 m using high gain antennas for line of-sight (LOS) conditions.
Steiner Transitive-Closure Spanners of d-Dimensional Posets
Venue: arXiv cs.DS 2010
Year: 2010

Given a directed graph G and an integer k >= 1, a k-transitive-closure-spanner (k-TCspanner) of G is a directed graph H that has (1) the same transitive-closure as G and (2) diameter at most k. In some applications, the shortcut paths added to the graph in order to obtain small diameter can use Steiner vertices, that is, vertices not in the original graph G. The resulting spanner is called a Steiner transitive-closure spanner (Steiner TC-spanner). Motivated by applications to property reconstruction and access control hierarchies, we concentrate on Steiner TC-spanners of directed acyclic graphs or, equivalently, partially ordered sets. In these applications, the goal is to find a sparsest Steiner k-TC-spanner of a poset G for a given k and G. The focus of this paper is the relationship between the dimension of a poset and the size of its sparsest Steiner TCspanner. The dimension of a poset G is the smallest d such that G can be embedded into a d-dimensional directed hypergrid via an order-preserving embedding. We present a nearly tight lower bound on the size of Steiner 2-TC-spanners of d-dimensional directed hypergrids. It implies better lower bounds on the complexity of local reconstructors of monotone functions and functions with low Lipschitz constant. The proof of the lower bound constructs a dual solution to a linear programming relaxation of the Steiner 2-TC-spanner problem. We also show that one can efficiently construct a Steiner 2-TC-spanner, of size matching the lower bound, for any low-dimensional poset. Finally, we present a lower bound on the size of Steiner k-TC-spanners of d-dimensional posets that shows that the best-known construction, due to De Santis et al., cannot be improved significantly.
Toward a Push-Scalable Global Internet
Venue: arXiv cs.NI 2010
Year: 2010

Push message delivery, where a client maintains an ``always-on'' connection with a server in order to be notified of a (asynchronous) message arrival in real-time, is increasingly being used in Internet services. The key message in this paper is that push message delivery on the World Wide Web is not scalable for servers, intermediate network elements, and battery-operated mobile device clients. We present a measurement analysis of a commercially deployed WWW push email service to highlight some of these issues. Next, we suggest content-based optimization to reduce the always-on connection requirement of push messaging. Our idea is based on exploiting the periodic nature of human-to-human messaging. We show how machine learning can accurately model the times of a day or week when messages are least likely to arrive; and turn off always-on connections these times. We apply our approach to a real email data set and our experiments demonstrate that the number of hours of active always-on connections can be cut by half while still achieving real-time message delivery for up to 90% of all messages.
Almost Optimal Explicit Johnson-Lindenstrauss Transformations
Venue: arXiv cs.DS 2010
Year: 2010

The Johnson-Lindenstrauss lemma is a fundamental result in probability with several applications in the design and analysis of algorithms in high dimensional geometry. Most known constructions of linear embeddings that satisfy the Johnson-Lindenstrauss property involve randomness. We address the question of explicitly constructing such embedding families and provide a construction with an almost optimal use of randomness: we use O(log(n/delta)log(log(n/delta)/epsilon)) random bits for embedding n dimensions to O(log(1/delta)/epsilon^2) dimensions with error probability at most delta, and distortion at most epsilon. In particular, for delta = 1/poly(n) and fixed epsilon, we use O(log n loglog n) random bits. Previous constructions required at least O(log^2 n) random bits to get polynomially small error.
Avoiding another Green Elephant - A Proposal for the Next Generation HLA based on the Model Driven Architecture
Venue: arXiv cs.OH 2010
Year: 2010

When looking through the proceedings of the recent Simulation Interoperability Workshops, a lot of papers - some of them even awarded by the committee - are dealing with alternative concepts outside or beyond the High Level Architecture (HLA): Web Services, the extensible Markup Language (XML), Java Beans, Simple Object Access Protocol (SOAP), etc. Similarly, requirements driven by interoperability issues have resulted in the need to use meta modeling, adaptive models, and common repositories. The use of the Unified Modeling Language (UML) as a model description language is also rapidly becoming a standard. All these concepts have relations to the HLA, but they are not part of it. There seems to be the danger that HLA is overrun by respective developments of the free market and will become irrelevant finally. ... This paper introduces the MDA concept and shows, how the HLA can be integrated to become a standard stub for simulation applications of legacy systems, systems under development, and systems of the future.