OpenRaiser/Intern-Atlas huggingface dataset:
Performance Evaluation for Clustering Algorithms in Object-Oriented Database Systems
Venue: arXiv cs.DB 2007
Year: 2007

It is widely acknowledged that good object clustering is critical to the performance of object-oriented databases. However, object clustering always involves some kind of overhead for the system. The aim of this paper is to propose a modelling methodology in order to evaluate the performances of different clustering policies. This methodology has been used to compare the performances of three clustering algorithms found in the literature (Cactis, CK and ORION) that we considered representative of the current research in the field of object clustering. The actual performance evaluation was performed using simulation. Simulation experiments we performed showed that the Cactis algorithm is better than the ORION algorithm and that the CK algorithm totally outperforms both other algorithms in terms of response time and clustering overhead.
Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
Venue: arXiv cs.DS 2007
Year: 2007

We consider the {\it indexable dictionary} problem, which consists of storing a set $S \subseteq \{0,...,m-1\}$ for some integer $m$, while supporting the operations of $\Rank(x)$, which returns the number of elements in $S$ that are less than $x$ if $x \in S$, and -1 otherwise; and $\Select(i)$ which returns the $i$-th smallest element in $S$. We give a data structure that supports both operations in O(1) time on the RAM model and requires ${\cal B}(n,m) + o(n) + O(\lg \lg m)$ bits to store a set of size $n$, where ${\cal B}(n,m) = \ceil{\lg {m \choose n}}$ is the minimum number of bits required to store any $n$-element subset from a universe of size $m$. Previous dictionaries taking this space only supported (yes/no) membership queries in O(1) time. In the cell probe model we can remove the $O(\lg \lg m)$ additive term in the space bound, answering a question raised by Fich and Miltersen, and Pagh. We present extensions and applications of our indexable dictionary data structure, including: An information-theoretically optimal representation of a $k$-ary cardinal tree that supports standard operations in constant time, A representation of a multiset of size $n$ from $\{0,...,m-1\}$ in ${\cal B}(n,m+n) + o(n)$ bits that supports (appropriate generalizations of) $\Rank$ and $\Select$ operations in constant time, and A representation of a sequence of $n$ non-negative integers summing up to $m$ in ${\cal B}(n,m+n) + o(n)$ bits that supports prefix sum queries in constant time.
NodeTrix: Hybrid Representation for Analyzing Social Networks
Venue: arXiv cs.HC 2007
Year: 2007

The need to visualize large social networks is growing as hardware capabilities make analyzing large networks feasible and many new data sets become available. Unfortunately, the visualizations in existing systems do not satisfactorily answer the basic dilemma of being readable both for the global structure of the network and also for detailed analysis of local communities. To address this problem, we present NodeTrix, a hybrid representation for networks that combines the advantages of two traditional representations: node-link diagrams are used to show the global structure of a network, while arbitrary portions of the network can be shown as adjacency matrices to better support the analysis of communities. A key contribution is a set of interaction techniques. These allow analysts to create a NodeTrix visualization by dragging selections from either a node-link or a matrix, flexibly manipulate the NodeTrix representation to explore the dataset, and create meaningful summary visualizations of their findings. Finally, we present a case study applying NodeTrix to the analysis of the InfoVis 2004 coauthorship dataset to illustrate the capabilities of NodeTrix as both an exploration tool and an effective means of communicating results.
Approximate textual retrieval
Venue: arXiv cs.IR 2007
Year: 2007

An approximate textual retrieval algorithm for searching sources with high levels of defects is presented. It considers splitting the words in a query into two overlapping segments and subsequently building composite regular expressions from interlacing subsets of the segments. This procedure reduces the probability of missed occurrences due to source defects, yet diminishes the retrieval of irrelevant, non-contextual occurrences.
Non-cooperative games for spreading code optimization, power control and receiver design in wireless data networks
Venue: arXiv cs.IT 2007
Year: 2007

This paper focuses on the issue of energy efficiency in wireless data networks through a game theoretic approach. The case considered is that in which each user is allowed to vary its transmit power, spreading code, and uplink receiver in order to maximize its own utility, which is here defined as the ratio of data throughput to transmit power. In particular, the case in which linear multiuser detectors are employed at the receiver is treated first, and, then, the more challenging case in which non-linear decision feedback multiuser receivers are adopted is addressed. It is shown that, for both receivers, the problem at hand of utility maximization can be regarded as a non-cooperative game, and it is proved that a unique Nash equilibrium point exists. Simulation results show that significant performance gains can be obtained through both non-linear processing and spreading code optimization; in particular, for systems with a number of users not larger than the processing gain, remarkable gains come from spreading code optimization, while, for overloaded systems, the largest gainscome from the use of non-linear processing. In every case, however, the non-cooperative games proposed here are shown to outperform competing alternatives.
Overview of the Netsukuku network
Venue: arXiv cs.NI 2007
Year: 2007

Netsukuku is a P2P network system designed to handle a large number of nodes with minimal CPU and memory resources. It can be easily used to build a worldwide distributed, anonymous and not controlled network, separated from the Internet, without the support of any servers, ISPs or authority controls. In this document, we give a generic and non technical description of the Netsukuku network, emphasizing its main ideas and features.
Achievable Rates and Optimal Resource Allocation for Imperfectly-Known Fading Relay Channels
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, achievable rates of imperfectly-known fading relay channels are studied. It is assumed that communication starts with the network training phase in which the receivers estimate the fading coefficients of their respective channels. In the data transmission phase, amplify-and-forward and decode-and-forward relaying schemes are considered, and the corresponding achievable rate expressions are obtained. The achievable rate expressions are then employed to identify the optimal resource allocation strategies.
Predicting the Presence of Internet Worms using Novelty Detection
Venue: arXiv cs.CR 2007
Year: 2007

Internet worms cause billions of dollars in damage yearly, affecting millions of users worldwide. For countermeasures to be deployed timeously, it is necessary to use an automated system to detect the spread of a worm. This paper discusses a method of determining the presence of a worm, based on routing information currently available from Internet routers. An autoencoder, which is a specialized type of neural network, was used to detect anomalies in normal routing behavior. The autoencoder was trained using information from a single router, and was able to detect both global instability caused by worms as well as localized routing instability.
Degree Optimization and Stability Condition for the Min-Sum Decoder
Venue: arXiv cs.IT 2007
Year: 2007

The min-sum (MS) algorithm is arguably the second most fundamental algorithm in the realm of message passing due to its optimality (for a tree code) with respect to the {\em block error} probability \cite{Wiberg}. There also seems to be a fundamental relationship of MS decoding with the linear programming decoder \cite{Koetter}. Despite its importance, its fundamental properties have not nearly been studied as well as those of the sum-product (also known as BP) algorithm. We address two questions related to the MS rule. First, we characterize the stability condition under MS decoding. It turns out to be essentially the same condition as under BP decoding. Second, we perform a degree distribution optimization. Contrary to the case of BP decoding, under MS decoding the thresholds of the best degree distributions for standard irregular LDPC ensembles are significantly bounded away from the Shannon threshold. More precisely, on the AWGN channel, for the best codes that we find, the gap to capacity is 1dB for a rate 0.3 code and it is 0.4dB when the rate is 0.9 (the gap decreases monotonically as we increase the rate). We also used the optimization procedure to design codes for modified MS algorithm where the output of the check node is scaled by a constant $1/α$. For $α= 1.25$, we observed that the gap to capacity was lesser for the modified MS algorithm when compared with the MS algorithm. However, it was still quite large, varying from 0.75 dB to 0.2 dB for rates between 0.3 and 0.9. We conclude by posing what we consider to be the most important open questions related to the MS algorithm.
Matroid Pathwidth and Code Trellis Complexity
Venue: arXiv cs.DM 2007
Year: 2007

We relate the notion of matroid pathwidth to the minimum trellis state-complexity (which we term trellis-width) of a linear code, and to the pathwidth of a graph. By reducing from the problem of computing the pathwidth of a graph, we show that the problem of determining the pathwidth of a representable matroid is NP-hard. Consequently, the problem of computing the trellis-width of a linear code is also NP-hard. For a finite field $\F$, we also consider the class of $\F$-representable matroids of pathwidth at most $w$, and correspondingly, the family of linear codes over $\F$ with trellis-width at most $w$. These are easily seen to be minor-closed. Since these matroids (and codes) have branchwidth at most $w$, a result of Geelen and Whittle shows that such matroids (and the corresponding codes) are characterized by finitely many excluded minors. We provide the complete list of excluded minors for $w=1$, and give a partial list for $w=2$.
A New Concept of Modular Parallel Mechanism for Machining Applications
Venue: arXiv cs.RO 2007
Year: 2007

The subject of this paper is the design of a new concept of modular parallel mechanisms for three, four or five-axis machining applications. Most parallel mechanisms are designed for three- or six-axis machining applications. In the last case, the position and the orientation of the tool are coupled and the shape of the workspace is complex. The aim of this paper is to use a simple parallel mechanism with two-degree-of-freedom (dof) for translation motions and to add one or two legs to add one or two-dofs for rotation motions. The kinematics and singular configurations are studied for each mechanism.
Typer la dé-sérialisation sans sérialiser les types
Venue: arXiv cs.PL 2007
Year: 2007

In this paper, we propose a way of assigning static type information to unmarshalling functions and we describe a verification technique for unmarshalled data that preserves the execution safety provided by static type checking. This technique, whose correctness is proven, relies on singleton types whose values are transmitted to unmarshalling routines at runtime, and on an efficient checking algorithm able to deal with sharing and cycles.
Mixing the Objective Caml and C# Programming Models in the .Net Framework
Venue: arXiv cs.PL 2007
Year: 2007

We present a new code generator, called O'Jacare.net, to inter-operate between C# and Objective Caml through their object models. O'Jacare.net defines a basic IDL (Interface Definition Language) that describes classes and interfaces in order to communicate between Objective Caml and C#. O'Jacare.net generates all needed wrapper classes and takes advantage of static type checking in both worlds. Although the IDL intersects these two object models, O'Jacare.net allows to combine features from both.
Wireless Networking to Support Data and Voice Communication Using Spread Spectrum Technology in The Physical Layer
Venue: arXiv cs.NI 2007
Year: 2007

Wireless networking is rapidly growing and becomes an inexpensive technology which allows multiple users to simultaneously access the network and the internet while roaming about the campus. In the present work, the software development of a wireless LAN(WLAN) is highlighted. This WLAN utilizes direct sequence spread spectrum (DSSS) technology at 902MHz RF carrier frequency in its physical layer. Cost effective installation and antijaming property of spread spectrum technology are the major advantages of this work.
Using artificial intelligence for data reduction in mechanical engineering
Venue: arXiv cs.CE 2007
Year: 2007

In this paper artificial neural networks and support vector machines are used to reduce the amount of vibration data that is required to estimate the Time Domain Average of a gear vibration signal. Two models for estimating the time domain average of a gear vibration signal are proposed. The models are tested on data from an accelerated gear life test rig. Experimental results indicate that the required data for calculating the Time Domain Average of a gear vibration signal can be reduced by up to 75% when the proposed models are implemented.
Towards Informative Statistical Flow Inversion
Venue: arXiv cs.NI 2007
Year: 2007

A problem which has recently attracted research attention is that of estimating the distribution of flow sizes in internet traffic. On high traffic links it is sometimes impossible to record every packet. Researchers have approached the problem of estimating flow lengths from sampled packet data in two separate ways. Firstly, different sampling methodologies can be tried to more accurately measure the desired system parameters. One such method is the sample-and-hold method where, if a packet is sampled, all subsequent packets in that flow are sampled. Secondly, statistical methods can be used to ``invert'' the sampled data and produce an estimate of flow lengths from a sample. In this paper we propose, implement and test two variants on the sample-and-hold method. In addition we show how the sample-and-hold method can be inverted to get an estimation of the genuine distribution of flow sizes. Experiments are carried out on real network traces to compare standard packet sampling with three variants of sample-and-hold. The methods are compared for their ability to reconstruct the genuine distribution of flow sizes in the traffic.
Multi-Dimensional Recurrent Neural Networks
Venue: arXiv cs.AI 2007
Year: 2007

Recurrent neural networks (RNNs) have proved effective at one dimensional sequence learning tasks, such as speech and online handwriting recognition. Some of the properties that make RNNs suitable for such tasks, for example robustness to input warping, and the ability to access contextual information, are also desirable in multidimensional domains. However, there has so far been no direct way of applying RNNs to data with more than one spatio-temporal dimension. This paper introduces multi-dimensional recurrent neural networks (MDRNNs), thereby extending the potential applicability of RNNs to vision, video processing, medical imaging and many other areas, while avoiding the scaling problems that have plagued other multi-dimensional models. Experimental results are provided for two image segmentation tasks.
Reduced Complexity Sphere Decoding for Square QAM via a New Lattice Representation
Venue: arXiv cs.IT 2007
Year: 2007

Sphere decoding (SD) is a low complexity maximum likelihood (ML) detection algorithm, which has been adapted for different linear channels in digital communications. The complexity of the SD has been shown to be exponential in some cases, and polynomial in others and under certain assumptions. The sphere radius and the number of nodes visited throughout the tree traversal search are the decisive factors for the complexity of the algorithm. The radius problem has been addressed and treated widely in the literature. In this paper, we propose a new structure for SD, which drastically reduces the overall complexity. The complexity is measured in terms of the floating point operations per second (FLOPS) and the number of nodes visited throughout the algorithm tree search. This reduction in the complexity is due to the ability of decoding the real and imaginary parts of each jointly detected symbol independently of each other, making use of the new lattice representation. We further show by simulations that the new approach achieves 80% reduction in the overall complexity compared to the conventional SD for a 2x2 system, and almost 50% reduction for the 4x4 and 6x6 cases, thus relaxing the requirements for hardware implementation.
Non-Coherent Capacity and Reliability of Sparse Multipath Channels in the Wideband Regime
Venue: arXiv cs.IT 2007
Year: 2007

In contrast to the prevalent assumption of rich multipath in information theoretic analysis of wireless channels, physical channels exhibit sparse multipath, especially at large bandwidths. We propose a model for sparse multipath fading channels and present results on the impact of sparsity on non-coherent capacity and reliability in the wideband regime. A key implication of sparsity is that the statistically independent degrees of freedom in the channel, that represent the delay-Doppler diversity afforded by multipath, scale at a sub-linear rate with the signal space dimension (time-bandwidth product). Our analysis is based on a training-based communication scheme that uses short-time Fourier (STF) signaling waveforms. Sparsity in delay-Doppler manifests itself as time-frequency coherence in the STF domain. From a capacity perspective, sparse channels are asymptotically coherent: the gap between coherent and non-coherent extremes vanishes in the limit of large signal space dimension without the need for peaky signaling. From a reliability viewpoint, there is a fundamental tradeoff between channel diversity and learnability that can be optimized to maximize the error exponent at any rate by appropriately choosing the signaling duration as a function of bandwidth.
Multiuser detection in a dynamic environment Part I: User identification and data detection
Venue: arXiv cs.IT 2007
Year: 2007

In random-access communication systems, the number of active users varies with time, and has considerable bearing on receiver's performance. Thus, techniques aimed at identifying not only the information transmitted, but also that number, play a central role in those systems. An example of application of these techniques can be found in multiuser detection (MUD). In typical MUD analyses, receivers are based on the assumption that the number of active users is constant and known at the receiver, and coincides with the maximum number of users entitled to access the system. This assumption is often overly pessimistic, since many users might be inactive at any given time, and detection under the assumption of a number of users larger than the real one may impair performance. The main goal of this paper is to introduce a general approach to the problem of identifying active users and estimating their parameters and data in a random-access system where users are continuously entering and leaving the system. The tool whose use we advocate is Random-Set Theory: applying this, we derive optimum receivers in an environment where the set of transmitters comprises an unknown number of elements. In addition, we can derive Bayesian-filter equations which describe the evolution with time of the a posteriori probability density of the unknown user parameters, and use this density to derive optimum detectors. In this paper we restrict ourselves to interferer identification and data detection, while in a companion paper we shall examine the more complex problem of estimating users' parameters.
Distributed Transmit Diversity in Relay Networks
Venue: arXiv cs.IT 2007
Year: 2007

We analyze fading relay networks, where a single-antenna source-destination terminal pair communicates through a set of half-duplex single-antenna relays using a two-hop protocol with linear processing at the relay level. A family of relaying schemes is presented which achieves the entire optimal diversity-multiplexing (DM) tradeoff curve. As a byproduct of our analysis, it follows that delay diversity and phase-rolling at the relay level are optimal with respect to the entire DM-tradeoff curve, provided the delays and the modulation frequencies, respectively, are chosen appropriately.
On the Obfuscation Complexity of Planar Graphs
Venue: arXiv cs.DM 2007
Year: 2007

Being motivated by John Tantalo's Planarity Game, we consider straight line plane drawings of a planar graph $G$ with edge crossings and wonder how obfuscated such drawings can be. We define $obf(G)$, the obfuscation complexity of $G$, to be the maximum number of edge crossings in a drawing of $G$. Relating $obf(G)$ to the distribution of vertex degrees in $G$, we show an efficient way of constructing a drawing of $G$ with at least $obf(G)/3$ edge crossings. We prove bounds $(δ(G)^2/24-o(1))n^2 < \obf G <3 n^2$ for an $n$-vertex planar graph $G$ with minimum vertex degree $δ(G)\ge 2$. The shift complexity of $G$, denoted by $shift(G)$, is the minimum number of vertex shifts sufficient to eliminate all edge crossings in an arbitrarily obfuscated drawing of $G$ (after shifting a vertex, all incident edges are supposed to be redrawn correspondingly). If $δ(G)\ge 3$, then $shift(G)$ is linear in the number of vertices due to the known fact that the matching number of $G$ is linear. However, in the case $δ(G)\ge2$ we notice that $shift(G)$ can be linear even if the matching number is bounded. As for computational complexity, we show that, given a drawing $D$ of a planar graph, it is NP-hard to find an optimum sequence of shifts making $D$ crossing-free.
On the expressive power of planar perfect matching and permanents of bounded treewidth matrices
Venue: arXiv cs.DM 2007
Year: 2007

Valiant introduced some 25 years ago an algebraic model of computation along with the complexity classes VP and VNP, which can be viewed as analogues of the classical classes P and NP. They are defined using non-uniform sequences of arithmetic circuits and provides a framework to study the complexity for sequences of polynomials. Prominent examples of difficult (that is, VNP-complete) problems in this model includes the permanent and hamiltonian polynomials. While the permanent and hamiltonian polynomials in general are difficult to evaluate, there have been research on which special cases of these polynomials admits efficient evaluation. For instance, Barvinok has shown that if the underlying matrix has bounded rank, both the permanent and the hamiltonian polynomials can be evaluated in polynomial time, and thus are in VP. Courcelle, Makowsky and Rotics have shown that for matrices of bounded treewidth several difficult problems (including evaluating the permanent and hamiltonian polynomials) can be solved efficiently. An earlier result of this flavour is Kasteleyn's theorem which states that the sum of weights of perfect matchings of a planar graph can be computed in polynomial time, and thus is in VP also. For general graphs this problem is VNP-complete. In this paper we investigate the expressive power of the above results. We show that the permanent and hamiltonian polynomials for matrices of bounded treewidth both are equivalent to arithmetic formulas. Also, arithmetic weakly skew circuits are shown to be equivalent to the sum of weights of perfect matchings of planar graphs.