OpenRaiser/Intern-Atlas huggingface dataset:
An efficient approach of controlling traffic congestion in scale-free networks
Venue: arXiv cs.NI 2008
Year: 2008

We propose and study a model of traffic in communication networks. The underlying network has a structure that is tunable between a scale-free growing network with preferential attachments and a random growing network. To model realistic situations where different nodes in a network may have different capabilities, the message or packet creation and delivering rates at a node are assumed to depend on the degree of the node. Noting that congestions are more likely to take place at the nodes with high degrees in networks with scale-free character, an efficient approach of selectively enhancing the message-processing capability of a small fraction (e.g. 3%) of the nodes is shown to perform just as good as enhancing the capability of all nodes. The interplay between the creation rate and the delivering rate in determining non-congested or congested traffic in a network is studied more numerically and analytically.
Tight Bounds for Hashing Block Sources
Venue: arXiv cs.DS 2008
Year: 2008

It is known that if a 2-universal hash function $H$ is applied to elements of a {\em block source} $(X_1,...,X_T)$, where each item $X_i$ has enough min-entropy conditioned on the previous items, then the output distribution $(H,H(X_1),...,H(X_T))$ will be ``close'' to the uniform distribution. We provide improved bounds on how much min-entropy per item is required for this to hold, both when we ask that the output be close to uniform in statistical distance and when we only ask that it be statistically close to a distribution with small collision probability. In both cases, we reduce the dependence of the min-entropy on the number $T$ of items from $2\log T$ in previous work to $\log T$, which we show to be optimal. This leads to corresponding improvements to the recent results of Mitzenmacher and Vadhan (SODA `08) on the analysis of hashing-based algorithms and data structures when the data items come from a block source.
On the existence of compactly supported reconstruction functions in a sampling problem
Venue: arXiv cs.IT 2008
Year: 2008

Assume that samples of a filtered version of a function in a shift-invariant space are avalaible. This work deals with the existence of a sampling formula involving these samples and having reconstruction functions with compact support. Thus, low computational complexity is involved and truncation errors are avoided. This is done in the light of the generalized sampling theory by using the oversampling technique: more samples than strictly necessary are used. For a suitable choice of the sampling period, a necessary and sufficient condition is given in terms of the Kronecker canonical form of a matrix pencil. Comparing with other characterizations in the mathematical literature, the given here has an important advantage: it can be reliable computed by using the GUPTRI form of the matrix pencil. Finally, a practical method for computing the compactly supported reconstruction functions is given for the important case where the oversampling rate is minimum.
Triangulation of Simple 3D Shapes with Well-Centered Tetrahedra
Venue: arXiv cs.CG 2008
Year: 2008

A completely well-centered tetrahedral mesh is a triangulation of a three dimensional domain in which every tetrahedron and every triangle contains its circumcenter in its interior. Such meshes have applications in scientific computing and other fields. We show how to triangulate simple domains using completely well-centered tetrahedra. The domains we consider here are space, infinite slab, infinite rectangular prism, cube and regular tetrahedron. We also demonstrate single tetrahedra with various combinations of the properties of dihedral acuteness, 2-well-centeredness and 3-well-centeredness.
Scaling of critical connectivity of mobile ad hoc communication networks
Venue: arXiv cs.NI 2008
Year: 2008

In this paper, critical global connectivity of mobile ad hoc communication networks (MAHCN) is investigated. We model the two-dimensional plane on which nodes move randomly with a triangular lattice. Demanding the best communication of the network, we account the global connectivity $η$ as a function of occupancy $σ$ of sites in the lattice by mobile nodes. Critical phenomena of the connectivity for different transmission ranges $r$ are revealed by numerical simulations, and these results fit well to the analysis based on the assumption of homogeneous mixing . Scaling behavior of the connectivity is found as $η\sim f(R^βσ)$, where $R=(r-r_{0})/r_{0}$, $r_{0}$ is the length unit of the triangular lattice and $β$ is the scaling index in the universal function $f(x)$. The model serves as a sort of site percolation on dynamic complex networks relative to geometric distance. Moreover, near each critical $σ_c(r)$ corresponding to certain transmission range $r$, there exists a cut-off degree $k_c$ below which the clustering coefficient of such self-organized networks keeps a constant while the averaged nearest neighbor degree exhibits a unique linear variation with the degree k, which may be useful to the designation of real MAHCN.
Development of Hybrid Intelligent Systems and their Applications from Engineering Systems to Complex Systems
Venue: arXiv cs.AI 2008
Year: 2008

In this study, we introduce general frame of MAny Connected Intelligent Particles Systems (MACIPS). Connections and interconnections between particles get a complex behavior of such merely simple system (system in system).Contribution of natural computing, under information granulation theory, are the main topic of this spacious skeleton. Upon this clue, we organize different algorithms involved a few prominent intelligent computing and approximate reasoning methods such as self organizing feature map (SOM)[9], Neuro- Fuzzy Inference System[10], Rough Set Theory (RST)[11], collaborative clustering, Genetic Algorithm and Ant Colony System. Upon this, we have employed our algorithms on the several engineering systems, especially emerged systems in Civil and Mineral processing. In other process, we investigated how our algorithms can be taken as a linkage of government-society interaction, where government catches various fashions of behavior: solid (absolute) or flexible. So, transition of such society, by changing of connectivity parameters (noise) from order to disorder is inferred. Add to this, one may find an indirect mapping among finical systems and eventual market fluctuations with MACIPS. In the following sections, we will mention the main topics of the suggested proposal, briefly Details of the proposed algorithms can be found in the references.
Prototyping and Performance Analysis of a QoS MAC Layer for Industrial Wireless Network
Venue: arXiv cs.NI 2008
Year: 2008

Today's industrial sensor networks require strong reliability and guarantees on messages delivery. These needs are even more important in real time applications like control/command, such as robotic wireless communications where strong temporal constraints are critical. For these reasons, classical random-based Medium Access Control (MAC) protocols present a non-null frame collision probability. In this paper we present an original full deterministic MAC-layer for industrial wireless network and its performance evaluation thanks to the development of a material prototype.
Proposition and validation of an original MAC layer with simultaneous medium accesses for low latency wireless control/command applications
Venue: arXiv cs.NI 2008
Year: 2008

Control/command processes require a transmission system with some characteristics like high reliability, low latency and strong guarantees on messages delivery. Concerning wire networks, field buses technologies like FIP offer this kind of service (periodic tasks, real time constraints...). Unfortunately, few wireless technologies can propose a communication system which respects such constraints. Indeed, wireless transmissions must deal with medium characteristics which make impossible the direct translation of mechanisms used with wire networks. The purpose of this paper is to present an original Medium Access Control (MAC) layer for a real time Low Power-Wireless Personal Area Network (LP-WPAN). The proposed MAC-layer has been validated by several complementary methods; in this paper, we focus on the specific Simultaneous Guaranteed Time Slot (SGTS) part.
On Certain Large Random Hermitian Jacobi Matrices with Applications to Wireless Communications
Venue: arXiv cs.IT 2008
Year: 2008

In this paper we study the spectrum of certain large random Hermitian Jacobi matrices. These matrices are known to describe certain communication setups. In particular we are interested in an uplink cellular channel which models mobile users experiencing a soft-handoff situation under joint multicell decoding. Considering rather general fading statistics we provide a closed form expression for the per-cell sum-rate of this channel in high-SNR, when an intra-cell TDMA protocol is employed. Since the matrices of interest are tridiagonal, their eigenvectors can be considered as sequences with second order linear recurrence. Therefore, the problem is reduced to the study of the exponential growth of products of two by two matrices. For the case where $K$ users are simultaneously active in each cell, we obtain a series of lower and upper bound on the high-SNR power offset of the per-cell sum-rate, which are considerably tighter than previously known bounds.
Biased Range Trees
Venue: arXiv cs.CG 2008
Year: 2008

A data structure, called a biased range tree, is presented that preprocesses a set S of n points in R^2 and a query distribution D for 2-sided orthogonal range counting queries. The expected query time for this data structure, when queries are drawn according to D, matches, to within a constant factor, that of the optimal decision tree for S and D. The memory and preprocessing requirements of the data structure are O(n log n).
Multi-agents architecture for supply chain management
Venue: arXiv cs.MA 2008
Year: 2008

The purpose of this paper is to propose a new approach for the supply chain management. This approach is based on the virtual enterprise paradigm and the used of multi-agent concept. Each entity (like enterprise) is autonomous and must perform local and global goals in relation with its environment. The base component of our approach is a Virtual Enterprise Node (VEN). The supply chain is viewed as a set of tiers (corresponding to the levels of production), in which each partner of the supply chain (VEN) is in relation with several customers and suppliers. Each VEN belongs to one tier. The main customer gives global objectives (quantity, cost and delay) to the supply chain. The Mediator Agent (MA) is in charge to manage the supply chain in order to respect those objectives as global level. Those objectives are taking over to Negotiator Agent at the tier level (NAT). These two agents are only active if a perturbation occurs; otherwise information flows are only exchange between VENs. This architecture allows supply chains management which is completely transparent seen from simple enterprise of the supply chain. The used of Multi-Agent System (MAS) allows physical distribution of the decisional system. Moreover, the hierarchical organizational structure with a decentralized control guaranties, in the same time, the autonomy of each entity and the whole flexibility.
Algorithmic Based Fault Tolerance Applied to High Performance Computing
Venue: arXiv cs.DC 2008
Year: 2008

We present a new approach to fault tolerance for High Performance Computing system. Our approach is based on a careful adaptation of the Algorithmic Based Fault Tolerance technique (Huang and Abraham, 1984) to the need of parallel distributed computation. We obtain a strongly scalable mechanism for fault tolerance. We can also detect and correct errors (bit-flip) on the fly of a computation. To assess the viability of our approach, we have developed a fault tolerant matrix-matrix multiplication subroutine and we propose some models to predict its running time. Our parallel fault-tolerant matrix-matrix multiplication scores 1.4 TFLOPS on 484 processors (cluster jacquard.nersc.gov) and returns a correct result while one process failure has happened. This represents 65% of the machine peak efficiency and less than 12% overhead with respect to the fastest failure-free implementation. We predict (and have observed) that, as we increase the processor count, the overhead of the fault tolerance drops significantly.
MOHCS: Towards Mining Overlapping Highly Connected Subgraphs
Venue: arXiv cs.DC 2008
Year: 2008

Many networks in real-life typically contain parts in which some nodes are more highly connected to each other than the other nodes of the network. The collection of such nodes are usually called clusters, communities, cohesive groups or modules. In graph terminology, it is called highly connected graph. In this paper, we first prove some properties related to highly connected graph. Based on these properties, we then redefine the highly connected subgraph which results in an algorithm that determines whether a given graph is highly connected in linear time. Then we present a computationally efficient algorithm, called MOHCS, for mining overlapping highly connected subgraphs. We have evaluated experimentally the performance of MOHCS using real and synthetic data sets from computer-generated graph and yeast protein network. Our results show that MOHCS is effective and reliable in finding overlapping highly connected subgraphs. Keywords-component; Highly connected subgraph, clustering algorithms, minimum cut, minimum degree
On the Search for High-Rate Quasi-Orthogonal Space-Time Block Code
Venue: arXiv cs.IT 2008
Year: 2008

A Quasi-Orthogonal Space-Time Block Code (QO-STBC) is attractive because it achieves higher code rate than Orthogonal STBC and lower decoding complexity than nonorthogonal STBC. In this paper, we first derive the algebraic structure of QO-STBC, then we apply it in a novel graph-based search algorithm to find high-rate QO-STBCs with code rates greater than 1. From the four-antenna codes found using this approach, it is found that the maximum code rate is limited to 5/4 with symbolwise diversity level of four, and 4 with symbolwise diversity level of two. The maximum likelihood decoding of these high-rate QO-STBCs can be performed on two separate sub-groups of symbols. The rate-5/4 codes are the first known QO-STBCs with code rate greater 1 that has full symbolwise diversity level.
Four-node Relay Network with Bi-directional Traffic Employing Wireless Network Coding with Pre-cancellation
Venue: arXiv cs.IT 2008
Year: 2008

Network coding has the potential to improve the overall throughput of a network by combining different streams of data and forwarding them. In wireless networks, the wireless channel provide an excellent medium for physical layer network coding as signals from different transmitters are combined automatically by the wireless channel. In such scenarios, it would be interesting to investigate protocols and algorithms which can optimally relay information. In this paper, we look at a four-node two-way or bidirectional relay network, and propose a relay protocol which can relay information efficiently in this network.
Round Trip Time Prediction Using the Symbolic Function Network Approach
Venue: arXiv cs.NE 2008
Year: 2008

In this paper, we develop a novel approach to model the Internet round trip time using a recently proposed symbolic type neural network model called symbolic function network. The developed predictor is shown to have good generalization performance and simple representation compared to the multilayer perceptron based predictors.
Cross-concordances: terminology mapping and its effectiveness for information retrieval
Venue: arXiv cs.DL 2008
Year: 2008

The German Federal Ministry for Education and Research funded a major terminology mapping initiative, which found its conclusion in 2007. The task of this terminology mapping initiative was to organize, create and manage 'cross-concordances' between controlled vocabularies (thesauri, classification systems, subject heading lists) centred around the social sciences but quickly extending to other subject areas. 64 crosswalks with more than 500,000 relations were established. In the final phase of the project, a major evaluation effort to test and measure the effectiveness of the vocabulary mappings in an information system environment was conducted. The paper reports on the cross-concordance work and evaluation results.
The Secrecy Rate Region of the Broadcast Channel
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, we consider a scenario where a source node wishes to broadcast two confidential messages for two respective receivers, while a wire-tapper also receives the transmitted signal. This model is motivated by wireless communications, where individual secure messages are broadcast over open media and can be received by any illegitimate receiver. The secrecy level is measured by equivocation rate at the eavesdropper. We first study the general (non-degraded) broadcast channel with confidential messages. We present an inner bound on the secrecy capacity region for this model. The inner bound coding scheme is based on a combination of random binning and the Gelfand-Pinsker bining. This scheme matches the Marton's inner bound on the broadcast channel without confidentiality constraint. We further study the situation where the channels are degraded. For the degraded broadcast channel with confidential messages, we present the secrecy capacity region. Our achievable coding scheme is based on Cover's superposition scheme and random binning. We refer to this scheme as Secret Superposition Scheme. In this scheme, we show that randomization in the first layer increases the secrecy rate of the second layer. This capacity region matches the capacity region of the degraded broadcast channel without security constraint. It also matches the secrecy capacity for the conventional wire-tap channel. Our converse proof is based on a combination of the converse proof of the conventional degraded broadcast channel and Csiszar lemma. Finally, we assume that the channels are Additive White Gaussian Noise (AWGN) and show that secret superposition scheme with Gaussian codebook is optimal. The converse proof is based on the generalized entropy power inequality.
Online network coding for optimal throughput and delay -- the three-receiver case
Venue: arXiv cs.IT 2008
Year: 2008

For a packet erasure broadcast channel with three receivers, we propose a new coding algorithm that makes use of feedback to dynamically adapt the code. Our algorithm is throughput optimal, and we conjecture that it also achieves an asymptotically optimal average decoding delay at the receivers. We consider heavy traffic asymptotics, where the load factor ρapproaches 1 from below with either the arrival rate (λ) or the channel parameter (μ) being fixed at a number less than 1. We verify through simulations that our algorithm achieves an asymptotically optimal decoding delay of O(1/(1-ρ)).
Interpolation in local theory extensions
Venue: arXiv cs.LO 2008
Year: 2008

In this paper we study interpolation in local extensions of a base theory. We identify situations in which it is possible to obtain interpolants in a hierarchical manner, by using a prover and a procedure for generating interpolants in the base theory as black-boxes. We present several examples of theory extensions in which interpolants can be computed this way, and discuss applications in verification, knowledge representation, and modular reasoning in combinations of local theories.
An Algebraic Approach for the MIMO Control of Small Scale Helicopter
Venue: arXiv cs.RO 2008
Year: 2008

The control of small-scale helicopter is a MIMO problem. To use of classical control approach to formally solve a MIMO problem, one needs to come up with multidimensional Root Locus diagram to tune the control parameters. The problem with the required dimension of the RL diagram for MIMO design has forced the design procedure of classical approach to be conducted in cascaded multi-loop SISO system starting from the innermost loop outward. To implement this control approach for a helicopter, a pitch and roll attitude control system is often subordinated to a, respectively, longitudinal and lateral velocity control system in a nested architecture. The requirement for this technique to work is that the inner attitude control loop must have a higher bandwidth than the outer velocity control loop which is not the case for high performance mini helicopter. To address the above problems, an algebraic design approach is proposed in this work. The designed control using s-CDM approach is demonstrated for hovering control of small-scale helicopter simultaneously subjected to plant parameter uncertainties and wind disturbances.
Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs
Venue: arXiv cs.DS 2008
Year: 2008

There is substantial literature dealing with fixed parameter algorithms for the dominating set problem on various families of graphs. In this paper, we give a $k^{O(dk)} n$ time algorithm for finding a dominating set of size at most $k$ in a $d$-degenerated graph with $n$ vertices. This proves that the dominating set problem is fixed-parameter tractable for degenerated graphs. For graphs that do not contain $K_h$ as a topological minor, we give an improved algorithm for the problem with running time $(O(h))^{hk} n$. For graphs which are $K_h$-minor-free, the running time is further reduced to $(O(\log h))^{hk/2} n$. Fixed-parameter tractable algorithms that are linear in the number of vertices of the graph were previously known only for planar graphs. For the families of graphs discussed above, the problem of finding an induced cycle of a given length is also addressed. For every fixed $H$ and $k$, we show that if an $H$-minor-free graph $G$ with $n$ vertices contains an induced cycle of size $k$, then such a cycle can be found in O(n) expected time as well as in $O(n \log n)$ worst-case time. Some results are stated concerning the (im)possibility of establishing linear time algorithms for the more general family of degenerated graphs.
Interprétation vague des contraintes structurelles pour la RI dans des corpus de documents XML - Évaluation d'une méthode approchée de RI structurée
Venue: arXiv cs.IR 2008
Year: 2008

We propose specific data structures designed to the indexing and retrieval of information elements in heterogeneous XML data bases. The indexing scheme is well suited to the management of various contextual searches, expressed either at a structural level or at an information content level. The approximate search mechanisms are based on a modified Levenshtein editing distance and information fusion heuristics. The implementation described highlights the mixing of structured information presented as field/value instances and free text elements. The retrieval performances of the proposed approach are evaluated within the INEX 2005 evaluation campaign. The evaluation results rank the proposed approach among the best evaluated XML IR systems for the VVCAS task.