OpenRaiser/Intern-Atlas huggingface dataset:
On sensing capacity of sensor networks for the class of linear observation, fixed SNR models
Venue: arXiv cs.IT 2007
Year: 2007

In this paper we address the problem of finding the sensing capacity of sensor networks for a class of linear observation models and a fixed SNR regime. Sensing capacity is defined as the maximum number of signal dimensions reliably identified per sensor observation. In this context sparsity of the phenomena is a key feature that determines sensing capacity. Precluding the SNR of the environment the effect of sparsity on the number of measurements required for accurate reconstruction of a sparse phenomena has been widely dealt with under compressed sensing. Nevertheless the development there was motivated from an algorithmic perspective. In this paper our aim is to derive these bounds in an information theoretic set-up and thus provide algorithm independent conditions for reliable reconstruction of sparse signals. In this direction we first generalize the Fano's inequality and provide lower bounds to the probability of error in reconstruction subject to an arbitrary distortion criteria. Using these lower bounds to the probability of error, we derive upper bounds to sensing capacity and show that for fixed SNR regime sensing capacity goes down to zero as sparsity goes down to zero. This means that disproportionately more sensors are required to monitor very sparse events. Our next main contribution is that we show the effect of sensing diversity on sensing capacity, an effect that has not been considered before. Sensing diversity is related to the effective \emph{coverage} of a sensor with respect to the field. In this direction we show the following results (a) Sensing capacity goes down as sensing diversity per sensor goes down; (b) Random sampling (coverage) of the field by sensors is better than contiguous location sampling (coverage).
An Automated Evaluation Metric for Chinese Text Entry
Venue: arXiv cs.HC 2007
Year: 2007

In this paper, we propose an automated evaluation metric for text entry. We also consider possible improvements to existing text entry evaluation metrics, such as the minimum string distance error rate, keystrokes per character, cost per correction, and a unified approach proposed by MacKenzie, so they can accommodate the special characteristics of Chinese text. Current methods lack an integrated concern about both typing speed and accuracy for Chinese text entry evaluation. Our goal is to remove the bias that arises due to human factors. First, we propose a new metric, called the correction penalty (P), based on Fitts' law and Hick's law. Next, we transform it into the approximate amortized cost (AAC) of information theory. An analysis of the AAC of Chinese text input methods with different context lengths is also presented.
A Unified Approach to Energy-Efficient Power Control in Large CDMA Systems
Venue: arXiv cs.IT 2007
Year: 2007

A unified approach to energy-efficient power control is proposed for code-division multiple access (CDMA) networks. The approach is applicable to a large family of multiuser receivers including the matched filter, the decorrelator, the linear minimum mean-square error (MMSE) receiver, and the (nonlinear) optimal detectors. It exploits the linear relationship that has been shown to exist between the transmit power and the output signal-to-interference-plus-noise ratio (SIR) in the large-system limit. It is shown that, for this family of receivers, when users seek to selfishly maximize their own energy efficiency, the Nash equilibrium is SIR-balanced. In addition, a unified power control (UPC) algorithm for reaching the Nash equilibrium is proposed. The algorithm adjusts the user's transmit powers by iteratively computing the large-system multiuser efficiency, which is independent of instantaneous spreading sequences. The convergence of the algorithm is proved for the matched filter, the decorrelator, and the MMSE receiver, and is demonstrated by means of simulation for an optimal detector. Moreover, the performance of the algorithm in finite-size systems is studied and compared with that of a conventional power control scheme, in which user powers depend on the instantaneous spreading sequences.
An algorithm for clock synchronization with the gradient property in sensor networks
Venue: arXiv cs.DC 2007
Year: 2007

We introduce a distributed algorithm for clock synchronization in sensor networks. Our algorithm assumes that nodes in the network only know their immediate neighborhoods and an upper bound on the network's diameter. Clock-synchronization messages are only sent as part of the communication, assumed reasonably frequent, that already takes place among nodes. The algorithm has the gradient property of [2], achieving an O(1) worst-case skew between the logical clocks of neighbors. As in the case of [3,8], the algorithm's actions are such that no constant lower bound exists on the rate at which logical clocks progress in time, and for this reason the lower bound of [2,5] that forbids constant skew between neighbors does not apply.
Acyclic Preference Systems in P2P Networks
Venue: arXiv cs.DS 2007
Year: 2007

In this work we study preference systems natural for the Peer-to-Peer paradigm. Most of them fall in three categories: global, symmetric and complementary. All these systems share an acyclicity property. As a consequence, they admit a stable (or Pareto efficient) configuration, where no participant can collaborate with better partners than their current ones. We analyze the representation of the such preference systems and show that any acyclic system can be represented with a symmetric mark matrix. This gives a method to merge acyclic preference systems and retain the acyclicity. We also consider such properties of the corresponding collaboration graph, as clustering coefficient and diameter. In particular, studying the example of preferences based on real latency measurements, we observe that its stable configuration is a small-world graph.
The Complexity of Model Checking Higher-Order Fixpoint Logic
Venue: arXiv cs.LO 2007
Year: 2007

Higher-Order Fixpoint Logic (HFL) is a hybrid of the simply typed λ-calculus and the modal λ-calculus. This makes it a highly expressive temporal logic that is capable of expressing various interesting correctness properties of programs that are not expressible in the modal λ-calculus. This paper provides complexity results for its model checking problem. In particular we consider those fragments of HFL built by using only types of bounded order k and arity m. We establish k-fold exponential time completeness for model checking each such fragment. For the upper bound we use fixpoint elimination to obtain reachability games that are singly-exponential in the size of the formula and k-fold exponential in the size of the underlying transition system. These games can be solved in deterministic linear time. As a simple consequence, we obtain an exponential time upper bound on the expression complexity of each such fragment. The lower bound is established by a reduction from the word problem for alternating (k-1)-fold exponential space bounded Turing Machines. Since there are fixed machines of that type whose word problems are already hard with respect to k-fold exponential time, we obtain, as a corollary, k-fold exponential time completeness for the data complexity of our fragments of HFL, provided m exceeds 3. This also yields a hierarchy result in expressive power.
Diversity of MIMO Multihop Relay Channels - Part I: Amplify-and-Forward
Venue: arXiv cs.IT 2007
Year: 2007

In this two-part paper, we consider the multiantenna multihop relay channels in which the source signal arrives at the destination through N independent relaying hops in series. The main concern of this work is to design relaying strategies that utilize efficiently the relays in such a way that the diversity is maximized. In part I, we focus on the amplify-and-forward (AF) strategy with which the relays simply scale the received signal and retransmit it. More specifically, we characterize the diversity-multiplexing tradeoff (DMT) of the AF scheme in a general multihop channel with arbitrary number of antennas and arbitrary number of hops. The DMT is in closed-form expression as a function of the number of antennas at each node. First, we provide some basic results on the DMT of the general Rayleigh product channels. It turns out that these results have very simple and intuitive interpretation. Then, the results are applied to the AF multihop channels which is shown to be equivalent to the Rayleigh product channel, in the DMT sense. Finally, the project-and-forward (PF) scheme, a variant of the AF scheme, is proposed. We show that the PF scheme has the same DMT as the AF scheme, while the PF can have significant power gain over the AF scheme in some cases. In part II, we will derive the upper bound on the diversity of the multihop channels and show that it can be achieved by partitioning the multihop channel into AF subchannels.
An Energy Efficiency Perspective on Training for Fading Channels
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, the bit energy requirements of training-based transmission over block Rayleigh fading channels are studied. Pilot signals are employed to obtain the minimum mean-square-error (MMSE) estimate of the channel fading coefficients. Energy efficiency is analyzed in the worst case scenario where the channel estimate is assumed to be perfect and the error in the estimate is considered as another source of additive Gaussian noise. It is shown that bit energy requirement grows without bound as the snr goes to zero, and the minimum bit energy is achieved at a nonzero snr value below which one should not operate. The effect of the block length on both the minimum bit energy and the snr value at which the minimum is achieved is investigated. Flash training schemes are analyzed and shown to improve the energy efficiency in the low-snr regime. Energy efficiency analysis is also carried out when peak power constraints are imposed on pilot signals.
Error Probability Analysis of Peaky Signaling over Fading Channels
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, the performance of signaling strategies with high peak-to-average power ratio is analyzed in both coherent and noncoherent fading channels. Two recently proposed modulation schemes, namely on-off binary phase-shift keying and on-off quaternary phase-shift keying, are considered. For these modulation formats, the optimal decision rules used at the detector are identified and analytical expressions for the error probabilities are obtained. Numerical techniques are employed to compute the error probabilities. It is concluded that increasing the peakedness of the signals results in reduced error rates for a given power level and hence improve the energy efficiency.
Oblivious Transfer based on Key Exchange
Venue: arXiv cs.CR 2007
Year: 2007

Key-exchange protocols have been overlooked as a possible means for implementing oblivious transfer (OT). In this paper we present a protocol for mutual exchange of secrets, 1-out-of-2 OT and coin flipping similar to Diffie-Hellman protocol using the idea of obliviously exchanging encryption keys. Since, Diffie-Hellman scheme is widely used, our protocol may provide a useful alternative to the conventional methods for implementation of oblivious transfer and a useful primitive in building larger cryptographic schemes.
Undirected Graphs of Entanglement Two
Venue: arXiv cs.LO 2007
Year: 2007

Entanglement is a complexity measure of directed graphs that origins in fixed point theory. This measure has shown its use in designing efficient algorithms to verify logical properties of transition systems. We are interested in the problem of deciding whether a graph has entanglement at most k. As this measure is defined by means of games, game theoretic ideas naturally lead to design polynomial algorithms that, for fixed k, decide the problem. Known characterizations of directed graphs of entanglement at most 1 lead, for k = 1, to design even faster algorithms. In this paper we present an explicit characterization of undirected graphs of entanglement at most 2. With such a characterization at hand, we devise a linear time algorithm to decide whether an undirected graph has this property.
Frugal Colouring of Graphs
Venue: arXiv cs.DM 2007
Year: 2007

A $k$-frugal colouring of a graph $G$ is a proper colouring of the vertices of $G$ such that no colour appears more than $k$ times in the neighbourhood of a vertex. This type of colouring was introduced by Hind, Molloy and Reed in 1997. In this paper, we study the frugal chromatic number of planar graphs, planar graphs with large girth, and outerplanar graphs, and relate this parameter with several well-studied colourings, such as colouring of the square, cyclic colouring, and $L(p,q)$-labelling. We also study frugal edge-colourings of multigraphs.
The Design of Efficiently-Encodable Rate-Compatible LDPC Codes
Venue: arXiv cs.IT 2007
Year: 2007

We present a new class of irregular low-density parity-check (LDPC) codes for moderate block lengths (up to a few thousand bits) that are well-suited for rate-compatible puncturing. The proposed codes show good performance under puncturing over a wide range of rates and are suitable for usage in incremental redundancy hybrid-automatic repeat request (ARQ) systems. In addition, these codes are linear-time encodable with simple shift-register circuits. For a block length of 1200 bits the codes outperform optimized irregular LDPC codes and extended irregular repeat-accumulate (eIRA) codes for all puncturing rates 0.6~0.9 (base code performance is almost the same) and are particularly good at high puncturing rates where good puncturing performance has been previously difficult to achieve.
Clustering with Lattices in the Analysis of Graph Patterns
Venue: arXiv cs.AI 2007
Year: 2007

Mining frequent subgraphs is an area of research where we have a given set of graphs (each graph can be seen as a transaction), and we search for (connected) subgraphs contained in many of these graphs. In this work we will discuss techniques used in our framework Lattice2SAR for mining and analysing frequent subgraph data and their corresponding lattice information. Lattice information is provided by the graph mining algorithm gSpan; it contains all supergraph-subgraph relations of the frequent subgraph patterns -- and their supports. Lattice2SAR is in particular used in the analysis of frequent graph patterns where the graphs are molecules and the frequent subgraphs are fragments. In the analysis of fragments one is interested in the molecules where patterns occur. This data can be very extensive and in this paper we focus on a technique of making it better available by using the lattice information in our clustering. Now we can reduce the number of times the highly compressed occurrence data needs to be accessed by the user. The user does not have to browse all the occurrence data in search of patterns occurring in the same molecules. Instead one can directly see which frequent subgraphs are of interest.
Risk Assessment Algorithms Based On Recursive Neural Networks
Venue: arXiv cs.NE 2007
Year: 2007

The assessment of highly-risky situations at road intersections have been recently revealed as an important research topic within the context of the automotive industry. In this paper we shall introduce a novel approach to compute risk functions by using a combination of a highly non-linear processing model in conjunction with a powerful information encoding procedure. Specifically, the elements of information either static or dynamic that appear in a road intersection scene are encoded by using directed positional acyclic labeled graphs. The risk assessment problem is then reformulated in terms of an inductive learning task carried out by a recursive neural network. Recursive neural networks are connectionist models capable of solving supervised and non-supervised learning problems represented by directed ordered acyclic graphs. The potential of this novel approach is demonstrated through well predefined scenarios. The major difference of our approach compared to others is expressed by the fact of learning the structure of the risk. Furthermore, the combination of a rich information encoding procedure with a generalized model of dynamical recurrent networks permit us, as we shall demonstrate, a sophisticated processing of information that we believe as being a first step for building future advanced intersection safety systems
Medical Image Segmentation and Localization using Deformable Templates
Venue: arXiv cs.CV 2007
Year: 2007

This paper presents deformable templates as a tool for segmentation and localization of biological structures in medical images. Structures are represented by a prototype template, combined with a parametric warp mapping used to deform the original shape. The localization procedure is achieved using a multi-stage, multi-resolution algorithm de-signed to reduce computational complexity and time. The algorithm initially identifies regions in the image most likely to contain the desired objects and then examines these regions at progressively increasing resolutions. The final stage of the algorithm involves warping the prototype template to match the localized objects. The algorithm is presented along with the results of four example applications using MRI, x-ray and ultrasound images.
Quantum Shortest Path Netsukuku
Venue: arXiv cs.NI 2007
Year: 2007

This document describes the QSPN, the routing discovery algorithm used by Netsukuku. Through a deductive analysis the main proprieties of the QSPN are shown. Moreover, a second version of the algorithm, is presented.
Enhancement of Noisy Planar Nuclear Medicine Images using Mean Field Annealing
Venue: arXiv cs.CV 2007
Year: 2007

Nuclear medicine (NM) images inherently suffer from large amounts of noise and blur. The purpose of this research is to reduce the noise and blur while maintaining image integrity for improved diagnosis. The proposed solution is to increase image quality after the standard pre- and post-processing undertaken by a gamma camera system. Mean Field Annealing (MFA) is the image processing technique used in this research. It is a computational iterative technique that makes use of the Point Spread Function (PSF) and the noise associated with the NM image. MFA is applied to NM images with the objective of reducing noise while not compromising edge integrity. Using a sharpening filter as a post-processing technique (after MFA) yields image enhancement of planar NM images.
A New Three-DOF Parallel Mechanism: Milling Machine Applications
Venue: arXiv cs.RO 2007
Year: 2007

This paper describes a new parallel kinematic architecture for machining applications, namely, the orthoglide. This machine features three fixed parallel linear joints which are mounted orthogonally and a mobile platform which moves in the Cartesian x-y-z space with fixed orientation. The main interest of the orthoglide is that it takes benefit from the advantages of the popular PPP serial machines (regular Cartesian workspace shape and uniform performances) as well as from the parallel kinematic arrangement of the links (less inertia and better dynamic performances), which makes the orthoglide well suited to high-speed machining applications. Possible extension of the orthoglide to 5-axis machining is also investigated.
Tracking User Attention in Collaborative Tagging Communities
Venue: arXiv cs.DL 2007
Year: 2007

Collaborative tagging has recently attracted the attention of both industry and academia due to the popularity of content-sharing systems such as CiteULike, del.icio.us, and Flickr. These systems give users the opportunity to add data items and to attach their own metadata (or tags) to stored data. The result is an effective content management tool for individual users. Recent studies, however, suggest that, as tagging communities grow, the added content and the metadata become harder to manage due to an ease in content diversity. Thus, mechanisms that cope with increase of diversity are fundamental to improve the scalability and usability of collaborative tagging systems. This paper analyzes whether usage patterns can be harnessed to improve navigability in a growing knowledge space. To this end, it presents a characterization of two collaborative tagging communities that target scientific literature: CiteULike and Bibsonomy. We explore three main directions: First, we analyze the tagging activity distribution across the user population. Second, we define new metrics for similarity in user interest and use these metrics to uncover the structure of the tagging communities we study. The structure we uncover suggests a clear segmentation of interests into a large number of individuals with unique preferences and a core set of users with interspersed interests. Finally, we offer preliminary results that demonstrate that the interest-based structure of the tagging community can be used to facilitate content usage as communities scale.
The Design of Parallel Kinematic Machine Tools Using Kinetostatic Performance Criteria
Venue: arXiv cs.RO 2007
Year: 2007

Most industrial machine tools have a serial kinematic architecture, which means that each axis has to carry the following one, including its actuators and joints. High Speed Machining highlights some drawbacks of such architectures: heavy moving parts require from the machine structure high stiffness to limit bending problems that lower the machine accuracy, and limit the dynamic performances of the feed axes. That is why PKMs attract more and more researchers and companies, because they are claimed to offer several advantages over their serial counterparts, like high structural rigidity and high dynamic capacities. Indeed, the parallel kinematic arrangement of the links provides higher stiffness and lower moving masses that reduce inertia effects. Thus, PKMs have better dynamic performances. However, the design of a parallel kinematic machine tool (PKMT) is a hard task that requires further research studies before wide industrial use can be expected. Many criteria need to be taken into account in the design of a PKMT. We pay special attention to the description of kinetostatic criteria that rely on the conditioning of the Jacobian matrix of the mechanism. The organisation of this paper is as follows: next section introduces general remarks about PKMs, then is explained why PKMs can be interesting alternative machine tool designs. Then are presented existing PKMTs. An application to the design of a small-scale machine tool prototype developed at IRCCyN is presented at the end of this paper.
Mining Patterns with a Balanced Interval
Venue: arXiv cs.AI 2007
Year: 2007

In many applications it will be useful to know those patterns that occur with a balanced interval, e.g., a certain combination of phone numbers are called almost every Friday or a group of products are sold a lot on Tuesday and Thursday. In previous work we proposed a new measure of support (the number of occurrences of a pattern in a dataset), where we count the number of times a pattern occurs (nearly) in the middle between two other occurrences. If the number of non-occurrences between two occurrences of a pattern stays almost the same then we call the pattern balanced. It was noticed that some very frequent patterns obviously also occur with a balanced interval, meaning in every transaction. However more interesting patterns might occur, e.g., every three transactions. Here we discuss a solution using standard deviation and average. Furthermore we propose a simpler approach for pruning patterns with a balanced interval, making estimating the pruning threshold more intuitive.