OpenRaiser/Intern-Atlas huggingface dataset:
Curve Tracking Control for Legged Locomotion in Horizontal Plane
Venue: arXiv cs.RO 2007
Year: 2007

We derive a hybrid feedback control law for the lateral leg spring (LLS) model so that the center of mass of a legged runner follows a curved path in horizontal plane. The control law enables the runner to change the placement and the elasticity of its legs to move in a desired direction. Stable motion along a curved path is achieved using curvature, bearing and relative distance between the runner and the curve as feedback. Constraints on leg parameters determine the class of curves that can be followed. We also derive an optimal control law that stabilizes the orientation of the runner's body relative to the velocity of the runner's center of mass.
Energy Conscious Interactive Communication for Sensor Networks
Venue: arXiv cs.IT 2007
Year: 2007

In this work, we are concerned with maximizing the lifetime of a cluster of sensors engaged in single-hop communication with a base-station. In a data-gathering network, the spatio-temporal correlation in sensor data induces data-redundancy. Also, the interaction between two communicating parties is well-known to reduce the communication complexity. This paper proposes a formalism that exploits these two opportunities to reduce the number of bits transmitted by a sensor node in a cluster, hence enhancing its lifetime. We argue that our approach has several inherent advantages in scenarios where the sensor nodes are acutely energy and computing-power constrained, but the base-station is not so. This provides us an opportunity to develop communication protocols, where most of the computing and communication is done by the base-station. The proposed framework casts the sensor nodes and base-station communication problem as the problem of multiple informants with correlated information communicating with a recipient and attempts to extend extant work on interactive communication between an informant-recipient pair to such scenarios. Our work makes four major contributions. Firstly, we explicitly show that in such scenarios interaction can help in reducing the communication complexity. Secondly, we show that the order in which the informants communicate with the recipient may determine the communication complexity. Thirdly, we provide the framework to compute the $m$-message communication complexity in such scenarios. Lastly, we prove that in a typical sensor network scenario, the proposed formalism significantly reduces the communication and computational complexities.
Time Series Forecasting: Obtaining Long Term Trends with Self-Organizing Maps
Venue: arXiv cs.LG 2007
Year: 2007

Kohonen self-organisation maps are a well know classification tool, commonly used in a wide variety of problems, but with limited applications in time series forecasting context. In this paper, we propose a forecasting method specifically designed for multi-dimensional long-term trends prediction, with a double application of the Kohonen algorithm. Practical applications of the method are also presented.
Bounds on Space-Time-Frequency Dimensionality
Venue: arXiv cs.IT 2007
Year: 2007

We bound the number of electromagnetic signals which may be observed over a frequency range $2W$ for a time $T$ within a region of space enclosed by a radius $R$. Our result implies that broadband fields in space cannot be arbitrarily complex: there is a finite amount of information which may be extracted from a region of space via electromagnetic radiation. Three-dimensional space allows a trade-off between large carrier frequency and bandwidth. We demonstrate applications in super-resolution and broadband communication.
Network Coding over a Noisy Relay : a Belief Propagation Approach
Venue: arXiv cs.IT 2007
Year: 2007

In recent years, network coding has been investigated as a method to obtain improvements in wireless networks. A typical assumption of previous work is that relay nodes performing network coding can decode the messages from sources perfectly. On a simple relay network, we design a scheme to obtain network coding gain even when the relay node cannot perfectly decode its received messages. In our scheme, the operation at the relay node resembles message passing in belief propagation, sending the logarithm likelihood ratio (LLR) of the network coded message to the destination. Simulation results demonstrate the gain obtained over different channel conditions. The goal of this paper is not to give a theoretical result, but to point to possible interaction of network coding with user cooperation in noisy scenario. The extrinsic information transfer (EXIT) chart is shown to be a useful engineering tool to analyze the performance of joint channel coding and network coding in the network.
Causing Communication Closure: Safe Program Composition with Reliable Non-FIFO Channels
Venue: arXiv cs.DC 2007
Year: 2007

A semantic framework for analyzing safe composition of distributed programs is presented. Its applicability is illustrated by a study of program composition when communication is reliable but not necessarily FIFO\@. In this model, special care must be taken to ensure that messages do not accidentally overtake one another in the composed program. We show that barriers do not exist in this model. Indeed, no program that sends or receives messages can automatically be composed with arbitrary programs without jeopardizing their intended behavior. Safety of composition becomes context-sensitive and new tools are needed for ensuring it. A notion of \emph{sealing} is defined, where if a program $P$ is immediately followed by a program $Q$ that seals $P$ then $P$ will be communication-closed--it will execute as if it runs in isolation. The investigation of sealing in this model reveals a novel connection between Lamport causality and safe composition. A characterization of sealable programs is given, as well as efficient algorithms for testing if $Q$ seals $P$ and for constructing a seal for a significant class of programs. It is shown that every sealable program that is open to interference on $O(n^2)$ channels can be sealed using O(n) messages.
On formulas for decoding binary cyclic codes
Venue: arXiv cs.IT 2007
Year: 2007

We adress the problem of the algebraic decoding of any cyclic code up to the true minimum distance. For this, we use the classical formulation of the problem, which is to find the error locator polynomial in terms of the syndroms of the received word. This is usually done with the Berlekamp-Massey algorithm in the case of BCH codes and related codes, but for the general case, there is no generic algorithm to decode cyclic codes. Even in the case of the quadratic residue codes, which are good codes with a very strong algebraic structure, there is no available general decoding algorithm. For this particular case of quadratic residue codes, several authors have worked out, by hand, formulas for the coefficients of the locator polynomial in terms of the syndroms, using the Newton identities. This work has to be done for each particular quadratic residue code, and is more and more difficult as the length is growing. Furthermore, it is error-prone. We propose to automate these computations, using elimination theory and Grbner bases. We prove that, by computing appropriate Grbner bases, one automatically recovers formulas for the coefficients of the locator polynomial, in terms of the syndroms.
A decision procedure for linear "big O" equations
Venue: arXiv cs.LO 2007
Year: 2007

Let $F$ be the set of functions from an infinite set, $S$, to an ordered ring, $R$. For $f$, $g$, and $h$ in $F$, the assertion $f = g + O(h)$ means that for some constant $C$, $|f(x) - g(x)| \leq C |h(x)|$ for every $x$ in $S$. Let $L$ be the first-order language with variables ranging over such functions, symbols for $0, +, -, \min, \max$, and absolute value, and a ternary relation $f = g + O(h)$. We show that the set of quantifier-free formulas in this language that are valid in the intended class of interpretations is decidable, and does not depend on the underlying set, $S$, or the ordered ring, $R$. If $R$ is a subfield of the real numbers, we can add a constant 1 function, as well as multiplication by constants from any computable subfield. We obtain further decidability results for certain situations in which one adds symbols denoting the elements of a fixed sequence of functions of strictly increasing rates of growth.
Time-complexity semantics for feasible affine recursions (extended abstract)
Venue: arXiv cs.LO 2007
Year: 2007

The authors' ATR programming formalism is a version of call-by-value PCF under a complexity-theoretically motivated type system. ATR programs run in type-2 polynomial-time and all standard type-2 basic feasible functionals are ATR-definable (ATR types are confined to levels 0, 1, and 2). A limitation of the original version of ATR is that the only directly expressible recursions are tail-recursions. Here we extend ATR so that a broad range of affine recursions are directly expressible. In particular, the revised ATR can fairly naturally express the classic insertion- and selection-sort algorithms, thus overcoming a sticking point of most prior implicit-complexity-based formalisms. The paper's main work is in extending and simplifying the original time-complexity semantics for ATR to develop a set of tools for extracting and solving the higher-type recurrences arising from feasible affine recursions.
Iterative LDPC decoding using neighborhood reliabilities
Venue: arXiv cs.IT 2007
Year: 2007

In this paper we study the impact of the processing order of nodes of a bipartite graph, on the performance of an iterative message-passing decoding. To this end, we introduce the concept of neighborhood reliabilities of graph's nodes. Nodes reliabilities are calculated at each iteration and then are used to obtain a processing order within a serial or serial/parallel scheduling. The basic idea is that by processing first the most reliable data, the decoder is reinforced before processing the less reliable one. Using neighborhood reliabilities, the Min-Sum decoder of LDPC codes approaches the performance of the Sum-Product decoder.
Throughput Scaling Laws for Wireless Networks with Fading Channels
Venue: arXiv cs.IT 2007
Year: 2007

A network of $n$ wireless communication links is considered. Fading is assumed to be the dominant factor affecting the strength of the channels between nodes. The objective is to analyze the achievable throughput of the network when power allocation is allowed. By proposing a decentralized on-off power allocation strategy, a lower bound on the achievable throughput is obtained for a general fading model. In particular, under Rayleigh fading conditions the achieved sum-rate is of order $\log n$, which is, by a constant factor, larger than what is obtained with a centralized scheme in the work of Gowaikar et al. Similar to most of previous works on large networks, the proposed scheme assigns a vanishingly small rate for each link. However, it is shown that by allowing the sum-rate to decrease by a factor $α<1$, this scheme is capable of providing non-zero rate-per-links of order $Θ(1)$. To obtain larger non-zero rate-per-links, the proposed scheme is modified to a centralized version. It turns out that for the same number of active links the centralized scheme achieves a much larger rate-per-link. Moreover, at large values of rate-per-link, it achieves a sum-rate close to $\log n$, i.e., the maximum achieved by the decentralized scheme.
Maximizing the Probability of Delivery of Multipoint Relay Broadcast Protocol in Wireless Ad Hoc Networks with a Realistic Physical Layer
Venue: arXiv cs.NI 2007
Year: 2007

It is now commonly accepted that the unit disk graph used to model the physical layer in wireless networks does not reflect real radio transmissions, and that the lognormal shadowing model better suits to experimental simulations. Previous work on realistic scenarios focused on unicast, while broadcast requirements are fundamentally different and cannot be derived from unicast case. Therefore, broadcast protocols must be adapted in order to still be efficient under realistic assumptions. In this paper, we study the well-known multipoint relay protocol (MPR). In the latter, each node has to choose a set of neighbors to act as relays in order to cover the whole 2-hop neighborhood. We give experimental results showing that the original method provided to select the set of relays does not give good results with the realistic model. We also provide three new heuristics in replacement and their performances which demonstrate that they better suit to the considered model. The first one maximizes the probability of correct reception between the node and the considered relays multiplied by their coverage in the 2-hop neighborhood. The second one replaces the coverage by the average of the probabilities of correct reception between the considered neighbor and the 2-hop neighbors it covers. Finally, the third heuristic keeps the same concept as the second one, but tries to maximize the coverage level of the 2-hop neighborhood: 2-hop neighbors are still being considered as uncovered while their coverage level is not higher than a given coverage threshold, many neighbors may thus be selected to cover the same 2-hop neighbors.
Citation advantage of Open Access articles likely explained by quality differential and media effects
Venue: arXiv cs.DL 2007
Year: 2007

In a study of articles published in the Proceedings of the National Academy of Sciences, Gunther Eysenbach discovered a significant citation advantage for those articles made freely-available upon publication (Eysenbach 2006). While the author attempted to control for confounding factors that may have explained the citation differential, the study was unable to control for characteristics of the article that may have led some authors to pay the additional page charges ($1,000) for immediate OA status. OA articles published in PNAS were more than twice as likely to be featured on the front cover of the journal (3.3% vs. 1.4%), nearly twice as likely to be picked up by the media (15% vs. 8%) and when cited reached, on average, nearly twice as many news outlets as subscription-based articles (4.2 vs. 2.6). The citation advantage of Open Access articles in PNAS may likely be explained by a quality differential and the amplification of media effects.
Algorithmic Complexity Bounds on Future Prediction Errors
Venue: arXiv cs.LG 2007
Year: 2007

We bound the future loss when predicting any (computably) stochastic sequence online. Solomonoff finitely bounded the total deviation of his universal predictor $M$ from the true distribution $mu$ by the algorithmic complexity of $mu$. Here we assume we are at a time $t>1$ and already observed $x=x_1...x_t$. We bound the future prediction performance on $x_{t+1}x_{t+2}...$ by a new variant of algorithmic complexity of $mu$ given $x$, plus the complexity of the randomness deficiency of $x$. The new complexity is monotone in its condition in the sense that this complexity can only decrease if the condition is prolonged. We also briefly discuss potential generalizations to Bayesian model classes and to classification problems.
Effective Beam Width of Directional Antennas in Wireless Ad Hoc Networks
Venue: arXiv cs.IT 2007
Year: 2007

It is known at a qualitative level that directional antennas can be used to boost the capacity of wireless ad hoc networks. Lacking is a measure to quantify this advantage and to compare directional antennas of different footprint patterns. This paper introduces the concept of the effective beam width (and the effective null width as its dual counterpart) as a measure which quantitatively captures the capacity-boosting capability of directional antennas. Beam width is commonly defined to be the directional angle spread within which the main-lobe beam power is above a certain threshold. In contrast, our effective beam width definition lumps the effects of the (i) antenna pattern, (ii) active-node distribution, and (iii) channel characteristics, on network capacity into a single quantitative measure. We investigate the mathematical properties of the effective beam width and show how the convenience afforded by these properties can be used to analyze the effectiveness of complex directional antenna patterns in boosting network capacity, with fading and multi-user interference taken into account. In particular, we derive the extent to which network capacity can be scaled with the use of phased array antennas. We show that a phased array antenna with N elements can boost transport capacity of an Aloha-like network by a factor of order N^1.620.
The Case for Redundant Arrays of Internet Links (RAIL)
Venue: arXiv cs.NI 2007
Year: 2007

It is well-known that wide-area networks face today several performance and reliability problems. In this work, we propose to solve these problems by connecting two or more local-area networks together via a Redundant Array of Internet Links (or RAIL) and by proactively replicating each packet over these links. In that sense, RAIL is for networks what RAID (Redundant Array of Inexpensive Disks) was for disks. In this paper, we describe the RAIL approach, present our prototype (called the RAILedge), and evaluate its performance. First, we demonstrate that using multiple Internet links significantly improves the end-to-end performance in terms of network-level as well as application-level metrics for Voice-over-IP and TCP. Second, we show that a delay padding mechanism is needed to complement RAIL when there is significant delay disparity between the paths. Third, we show that two paths provide most of the benefit, if carefully managed. Finally, we discuss a RAIL-network architecture, where RAILedges make use of path redundancy, route control and application-specific mechanisms, to improve WAN performance.
Byzantine Fault Tolerance for Nondeterministic Applications
Venue: arXiv cs.DC 2007
Year: 2007

All practical applications contain some degree of nondeterminism. When such applications are replicated to achieve Byzantine fault tolerance (BFT), their nondeterministic operations must be controlled to ensure replica consistency. To the best of our knowledge, only the most simplistic types of replica nondeterminism have been dealt with. Furthermore, there lacks a systematic approach to handling common types of nondeterminism. In this paper, we propose a classification of common types of replica nondeterminism with respect to the requirement of achieving Byzantine fault tolerance, and describe the design and implementation of the core mechanisms necessary to handle such nondeterminism within a Byzantine fault tolerance framework.
Power-Bandwidth Tradeoff in Dense Multi-Antenna Relay Networks
Venue: arXiv cs.IT 2007
Year: 2007

We consider a dense fading multi-user network with multiple active multi-antenna source-destination pair terminals communicating simultaneously through a large common set of $K$ multi-antenna relay terminals in the full spatial multiplexing mode. We use Shannon-theoretic tools to analyze the tradeoff between energy efficiency and spectral efficiency (known as the power- bandwidth tradeoff) in meaningful asymptotic regimes of signal-to-noise ratio (SNR) and network size. We design linear distributed multi-antenna relay beamforming (LDMRB) schemes that exploit the spatial signature of multi-user interference and characterize their power-bandwidth tradeoff under a system wide power constraint on source and relay transmissions. The impact of multiple users, multiple relays and multiple antennas on the key performance measures of the high and low SNR regimes is investigated in order to shed new light on the possible reduction in power and bandwidth requirements through the usage of such practical relay cooperation techniques. Our results indicate that point-to-point coded multi-user networks supported by distributed relay beamforming techniques yield enhanced energy efficiency and spectral efficiency, and with appropriate signaling and sufficient antenna degrees of freedom, can achieve asymptotically optimal power-bandwidth tradeoff with the best possible (i.e., as in the cutset bound) energy scaling of $K^{-1}$ and the best possible spectral efficiency slope at any SNR for large number of relay terminals.
Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals
Venue: arXiv cs.DB 2007
Year: 2007

Data analysis applications typically aggregate data across many dimensions looking for anomalies or unusual patterns. The SQL aggregate functions and the GROUP BY operator produce zero-dimensional or one-dimensional aggregates. Applications need the N-dimensional generalization of these operators. This paper defines that operator, called the data cube or simply cube. The cube operator generalizes the histogram, cross-tabulation, roll-up, drill-down, and sub-total constructs found in most report writers. The novelty is that cubes are relations. Consequently, the cube operator can be imbedded in more complex non-procedural data analysis programs. The cube operator treats each of the N aggregation attributes as a dimension of N-space. The aggregate of a particular set of attribute values is a point in this space. The set of points forms an N-dimensional cube. Super-aggregates are computed by aggregating the N-cube to lower dimensional spaces. This paper (1) explains the cube and roll-up operators, (2) shows how they fit in SQL, (3) explains how users can define new aggregate functions for cubes, and (4) discusses efficient techniques to compute the cube. Many of these features are being added to the SQL Standard.
Supporting Finite Element Analysis with a Relational Database Backend, Part I: There is Life beyond Files
Venue: arXiv cs.DB 2007
Year: 2007

In this paper, we show how to use a Relational Database Management System in support of Finite Element Analysis. We believe it is a new way of thinking about data management in well-understood applications to prepare them for two major challenges, - size and integration (globalization). Neither extreme size nor integration (with other applications over the Web) was a design concern 30 years ago when the paradigm for FEA implementation first was formed. On the other hand, database technology has come a long way since its inception and it is past time to highlight its usefulness to the field of scientific computing and computer based engineering. This series aims to widen the list of applications for database designers and for FEA users and application developers to reap some of the benefits of database development.
Using Table Valued Functions in SQL Server 2005 To Implement a Spatial Data Library
Venue: arXiv cs.DB 2007
Year: 2007

This article explains how to add spatial search functions (point-near-point and point in polygon) to Microsoft SQL Server 2005 using C# and table-valued functions. It is possible to use this library to add spatial search to your application without writing any special code. The library implements the public-domain C# Hierarchical Triangular Mesh (HTM) algorithms from Johns Hopkins University. That C# library is connected to SQL Server 2005 via a set of scalar-valued and table-valued functions. These functions act as a spatial index.
Indexing the Sphere with the Hierarchical Triangular Mesh
Venue: arXiv cs.DB 2007
Year: 2007

We describe a method to subdivide the surface of a sphere into spherical triangles of similar, but not identical, shapes and sizes. The Hierarchical Triangular Mesh (HTM) is a quad-tree that is particularly good at supporting searches at different resolutions, from arc seconds to hemispheres. The subdivision scheme is universal, providing the basis for addressing and for fast lookups. The HTM provides the basis for an efficient geospatial indexing scheme in relational databases where the data have an inherent location on either the celestial sphere or the Earth. The HTM index is superior to cartographical methods using coordinates with singularities at the poles. We also describe a way to specify surface regions that efficiently represent spherical query areas. This article presents the algorithms used to identify the HTM triangles covering such regions.