OpenRaiser/Intern-Atlas huggingface dataset:
Optimized network structure and routing metric in wireless multihop ad hoc communication
Venue: arXiv cs.NI 2005
Year: 2005

Inspired by the Statistical Physics of complex networks, wireless multihop ad hoc communication networks are considered in abstracted form. Since such engineered networks are able to modify their structure via topology control, we search for optimized network structures, which maximize the end-to-end throughput performance. A modified version of betweenness centrality is introduced and shown to be very relevant for the respective modeling. The calculated optimized network structures lead to a significant increase of the end-to-end throughput. The discussion of the resulting structural properties reveals that it will be almost impossible to construct these optimized topologies in a technologically efficient distributive manner. However, the modified betweenness centrality also allows to propose a new routing metric for the end-to-end communication traffic. This approach leads to an even larger increase of throughput capacity and is easily implementable in a technologically relevant manner.
ADF95: Tool for automatic differentiation of a FORTRAN code designed for large numbers of independent variables
Venue: arXiv cs.MS 2005
Year: 2005

ADF95 is a tool to automatically calculate numerical first derivatives for any mathematical expression as a function of user defined independent variables. Accuracy of derivatives is achieved within machine precision. ADF95 may be applied to any FORTRAN 77/90/95 conforming code and requires minimal changes by the user. It provides a new derived data type that holds the value and derivatives and applies forward differencing by overloading all FORTRAN operators and intrinsic functions. An efficient indexing technique leads to a reduced memory usage and a substantially increased performance gain over other available tools with operator overloading. This gain is especially pronounced for sparse systems with large number of independent variables. A wide class of numerical simulations, e.g., those employing implicit solvers, can profit from ADF95.
Theory and Practice of Transactional Method Caching
Venue: arXiv cs.DB 2005
Year: 2005

Nowadays, tiered architectures are widely accepted for constructing large scale information systems. In this context application servers often form the bottleneck for a system's efficiency. An application server exposes an object oriented interface consisting of set of methods which are accessed by potentially remote clients. The idea of method caching is to store results of read-only method invocations with respect to the application server's interface on the client side. If the client invokes the same method with the same arguments again, the corresponding result can be taken from the cache without contacting the server. It has been shown that this approach can considerably improve a real world system's efficiency. This paper extends the concept of method caching by addressing the case where clients wrap related method invocations in ACID transactions. Demarcating sequences of method calls in this way is supported by many important application server standards. In this context the paper presents an architecture, a theory and an efficient protocol for maintaining full transactional consistency and in particular serializability when using a method cache on the client side. In order to create a protocol for scheduling cached method results, the paper extends a classical transaction formalism. Based on this extension, a recovery protocol and an optimistic serializability protocol are derived. The latter one differs from traditional transactional cache protocols in many essential ways. An efficiency experiment validates the approach: Using the cache a system's performance and scalability are considerably improved.
Stabilization of Cooperative Information Agents in Unpredictable Environment: A Logic Programming Approach
Venue: arXiv cs.LO 2005
Year: 2005

An information agent is viewed as a deductive database consisting of 3 parts: an observation database containing the facts the agent has observed or sensed from its surrounding environment, an input database containing the information the agent has obtained from other agents, and an intensional database which is a set of rules for computing derived information from the information stored in the observation and input databases. Stabilization of a system of information agents represents a capability of the agents to eventually get correct information about their surrounding despite unpredictable environment changes and the incapability of many agents to sense such changes causing them to have temporary incorrect information. We argue that the stabilization of a system of cooperative information agents could be understood as the convergence of the behavior of the whole system toward the behavior of a "superagent", who has the sensing and computing capabilities of all agents combined. We show that unfortunately, stabilization is not guaranteed in general, even if the agents are fully cooperative and do not hide any information from each other. We give sufficient conditions for stabilization and discuss the consequences of our results.
Mining Top-k Approximate Frequent Patterns
Venue: arXiv cs.DB 2005
Year: 2005

Frequent pattern (itemset) mining in transactional databases is one of the most well-studied problems in data mining. One obstacle that limits the practical usage of frequent pattern mining is the extremely large number of patterns generated. Such a large size of the output collection makes it difficult for users to understand and use in practice. Even restricting the output to the border of the frequent itemset collection does not help much in alleviating the problem. In this paper we address the issue of overwhelmingly large output size by introducing and studying the following problem: mining top-k approximate frequent patterns. The union of the power sets of these k sets should satisfy the following conditions: (1) including itemsets with larger support as many as possible and (2) including itemsets with smaller support as less as possible. An integrated objective function is designed to combine these two objectives. Consequently, we derive the upper bounds on objective function and present an approximate branch-and-bound method for finding the feasible solution. We give empirical evidence showing that our formulation and approximation methods work well in practice.
Uplink User Capacity in a CDMA System with Hotspot Microcells: Effects of Finite Transmit Power and Dispersion
Venue: arXiv cs.IT 2005
Year: 2005

This paper examines the uplink user capacity in a two-tier code division multiple access (CDMA) system with hotspot microcells when user terminal power is limited and the wireless channel is finitely-dispersive. A finitely-dispersive channel causes variable fading of the signal power at the output of the RAKE receiver. First, a two-cell system composed of one macrocell and one embedded microcell is studied and analytical methods are developed to estimate the user capacity as a function of a dimensionless parameter that depends on the transmit power constraint and cell radius. Next, novel analytical methods are developed to study the effect of variable fading, both with and without transmit power constraints. Finally, the analytical methods are extended to estimate uplink user capacity for multicell CDMA systems, composed of multiple macrocells and multiple embedded microcells. In all cases, the analysis-based estimates are compared with and confirmed by simulation results.
Contextual Constraint Modeling in Grid Application Workflows
Venue: arXiv cs.DC 2005
Year: 2005

This paper introduces a new mechanism for specifying constraints in distributed workflows. By introducing constraints in a contextual form, it is shown how different people and groups within collaborative communities can cooperatively constrain workflows. A comparison with existing state-of-the-art workflow systems is made. These ideas are explored in practice with an illustrative example from High Energy Physics.
Construction of Small Worlds in the Physical Topology of Wireless Networks
Venue: arXiv cs.NI 2005
Year: 2005

The concept of small worlds is introduced into the physical topology of wireless networks in this work. A. Helmy provided two con- struction schemes of small worlds for the wireless networks, link rewiring and link addition, but he mainly focused on the virtual topology. Based on the broadcasting nature of the radio transmission, we propose a con- struction scheme of small worlds for the physical topology of Multiple- Input Multiple-Output (MIMO) wireless networks. Besides the topology- related topics, we also evaluate the reduction of the power required by a request.
Zeta-Dimension
Venue: arXiv cs.CC 2005
Year: 2005

The zeta-dimension of a set A of positive integers is the infimum s such that the sum of the reciprocals of the s-th powers of the elements of A is finite. Zeta-dimension serves as a fractal dimension on the positive integers that extends naturally usefully to discrete lattices such as the set of all integer lattice points in d-dimensional space. This paper reviews the origins of zeta-dimension (which date to the eighteenth and nineteenth centuries) and develops its basic theory, with particular attention to its relationship with algorithmic information theory. New results presented include extended connections between zeta-dimension and classical fractal dimensions, a gale characterization of zeta-dimension, and a theorem on the zeta-dimensions of pointwise sums and products of sets of positive integers.
Analytic Definition of Curves and Surfaces by Parabolic Blending
Venue: arXiv cs.GR 2005
Year: 2005

A procedure for interpolating between specified points of a curve or surface is described. The method guarantees slope continuity at all junctions. A surface panel divided into p x q contiguous patches is completely specified by the coordinates of (p+1) x (q+1) points. Each individual patch, however, depends parametrically on the coordinates of 16 points, allowing shape flexibility and global conformity.
A Practical Approach for Circuit Routing on Dynamic Reconfigurable Devices
Venue: arXiv cs.AR 2005
Year: 2005

Management of communication by on-line routing in new FPGAs with a large amount of logic resources and partial reconfigurability is a new challenging problem. A Network-on-Chip (NoC) typically uses packet routing mechanism, which has often unsafe data transfers, and network interface overhead. In this paper, circuit routing for such dynamic NoCs is investigated, and a practical 1-dimensional network with an efficient routing algorithm is proposed and implemented. Also, this concept has been extended to the 2-dimensional case. The implementation results show the low area overhead and high performance of this network.
Improved message passing for inference in densely connected systems
Venue: arXiv cs.IT 2005
Year: 2005

An improved inference method for densely connected systems is presented. The approach is based on passing condensed messages between variables, representing macroscopic averages of microscopic messages. We extend previous work that showed promising results in cases where the solution space is contiguous to cases where fragmentation occurs. We apply the method to the signal detection problem of Code Division Multiple Access (CDMA) for demonstrating its potential. A highly efficient practical algorithm is also derived on the basis of insight gained from the analysis.
Tensor manipulation in GPL Maxima
Venue: arXiv cs.SC 2005
Year: 2005

GPL Maxima is an open-source computer algebra system based on DOE-MACSYMA. GPL Maxima included two tensor manipulation packages from DOE-MACSYMA, but these were in various states of disrepair. One of the two packages, CTENSOR, implemented component-based tensor manipulation; the other, ITENSOR, treated tensor symbols as opaque, manipulating them based on their index properties. The present paper describes the state in which these packages were found, the steps that were needed to make the packages fully functional again, and the new functionality that was implemented to make them more versatile. A third package, ATENSOR, was also implemented; fully compatible with the identically named package in the commercial version of MACSYMA, ATENSOR implements abstract tensor algebras.
Obtaining Membership Functions from a Neuron Fuzzy System extended by Kohonen Network
Venue: arXiv cs.NE 2005
Year: 2005

This article presents the Neo-Fuzzy-Neuron Modified by Kohonen Network (NFN-MK), an hybrid computational model that combines fuzzy system technique and artificial neural networks. Its main task consists in the automatic generation of membership functions, in particular, triangle forms, aiming a dynamic modeling of a system. The model is tested by simulating real systems, here represented by a nonlinear mathematical function. Comparison with the results obtained by traditional neural networks, and correlated studies of neurofuzzy systems applied in system identification area, shows that the NFN-MK model has a similar performance, despite its greater simplicity.
Enforcing Semantic Integrity on Untrusted Clients in Networked Virtual Environments
Venue: arXiv cs.CR 2005
Year: 2005

During the last years, large-scale simulations of realistic physical environments which support the interaction of multiple participants over the Internet have become increasingly available and economically significant, most notably in the computer gaming industry. Such systems, commonly called networked virtual environments (NVEs), are usually based on a client-server architecture where for performance reasons and bandwidth restrictions, the simulation is partially deferred to the clients. This inevitable architectural choice renders the simulation vulnerable to attacks against the semantic integrity of the simulation: malicious clients may attempt to compromise the physical and logical laws governing the simulation, or to alter the causality of events a posteriori. In this paper, we initiate the systematic study of semantic integrity in NVEs from a security point of view. We argue that naive policies to enforce semantic integrity involve intolerable network load, and are therefore not practically feasible. We present a new semantic integrity protocol based on cryptographic primitives which enables the server system to audit the local computations of the clients on demand. Our approach facilitates low network and CPU load, incurs reasonable engineering overhead, and maximally decouples the auditing process from the soft real time constraints of the simulation.
The Peculiarities of Nonstationary Formation of Inhomogeneous Structures of Charged Particles in the Electrodiffusion Processes
Venue: arXiv cs.CE 2005
Year: 2005

In this paper the distribution of charged particles is constructed under the approximation of ambipolar diffusion. The results of mathematical modelling in two-dimensional case taking into account the velocities of the system are presented.
Dynamic Shannon Coding
Venue: arXiv cs.IT 2005
Year: 2005

We present a new algorithm for dynamic prefix-free coding, based on Shannon coding. We give a simple analysis and prove a better upper bound on the length of the encoding produced than the corresponding bound for dynamic Huffman coding. We show how our algorithm can be modified for efficient length-restricted coding, alphabetic coding and coding with unequal letter costs.
A Rule-Based Logic for Quantum Information
Venue: arXiv cs.LO 2005
Year: 2005

In the present article, we explore a new approach for the study of orthomodular lattices, where we replace the problematic conjunction by a binary operator, called the Sasaki projection. We present a characterization of orthomodular lattices based on the use of an algebraic version of the Sasaki projection operator (together with orthocomplementation) rather than on the conjunction. We then define of a new logic, which we call Sasaki Orthologic, which is closely related to quantum logic, and provide a rule-based definition of this logic.
Near Perfect Decoding of LDPC Codes
Venue: arXiv cs.IT 2005
Year: 2005

Cooperative optimization is a new way for finding global optima of complicated functions of many variables. It has some important properties not possessed by any conventional optimization methods. It has been successfully applied in solving many large scale optimization problems in image processing, computer vision, and computational chemistry. This paper shows the application of this optimization principle in decoding LDPC codes, which is another hard combinatorial optimization problem. In our experiments, it significantly out-performed the sum-product algorithm, the best known method for decoding LDPC codes. Compared to the sum-product algorithm, our algorithm reduced the error rate further by three fold, improved the speed by six times, and lowered error floors dramatically in the decoding.
Fitness Uniform Deletion: A Simple Way to Preserve Diversity
Venue: arXiv cs.NE 2005
Year: 2005

A commonly experienced problem with population based optimisation methods is the gradual decline in population diversity that tends to occur over time. This can slow a system's progress or even halt it completely if the population converges on a local optimum from which it cannot escape. In this paper we present the Fitness Uniform Deletion Scheme (FUDS), a simple but somewhat unconventional approach to this problem. Under FUDS the deletion operation is modified to only delete those individuals which are "common" in the sense that there exist many other individuals of similar fitness in the population. This makes it impossible for the population to collapse to a collection of highly related individuals with similar fitness. Our experimental results on a range of optimisation problems confirm this, in particular for deceptive optimisation problems the performance is significantly more robust to variation in the selection intensity.
Oracles Are Subtle But Not Malicious
Venue: arXiv cs.CC 2005
Year: 2005

Theoretical computer scientists have been debating the role of oracles since the 1970's. This paper illustrates both that oracles can give us nontrivial insights about the barrier problems in circuit complexity, and that they need not prevent us from trying to solve those problems. First, we give an oracle relative to which PP has linear-sized circuits, by proving a new lower bound for perceptrons and low- degree threshold polynomials. This oracle settles a longstanding open question, and generalizes earlier results due to Beigel and to Buhrman, Fortnow, and Thierauf. More importantly, it implies the first nonrelativizing separation of "traditional" complexity classes, as opposed to interactive proof classes such as MIP and MA-EXP. For Vinodchandran showed, by a nonrelativizing argument, that PP does not have circuits of size n^k for any fixed k. We present an alternative proof of this fact, which shows that PP does not even have quantum circuits of size n^k with quantum advice. To our knowledge, this is the first nontrivial lower bound on quantum circuit size. Second, we study a beautiful algorithm of Bshouty et al. for learning Boolean circuits in ZPP^NP. We show that the NP queries in this algorithm cannot be parallelized by any relativizing technique, by giving an oracle relative to which ZPP^||NP and even BPP^||NP have linear-size circuits. On the other hand, we also show that the NP queries could be parallelized if P=NP. Thus, classes such as ZPP^||NP inhabit a "twilight zone," where we need to distinguish between relativizing and black-box techniques. Our results on this subject have implications for computational learning theory as well as for the circuit minimization problem.
Learning from Web: Review of Approaches
Venue: arXiv cs.NE 2005
Year: 2005

Knowledge discovery is defined as non-trivial extraction of implicit, previously unknown and potentially useful information from given data. Knowledge extraction from web documents deals with unstructured, free-format documents whose number is enormous and rapidly growing. The artificial neural networks are well suitable to solve a problem of knowledge discovery from web documents because trained networks are able more accurately and easily to classify the learning and testing examples those represent the text mining domain. However, the neural networks that consist of large number of weighted connections and activation units often generate the incomprehensible and hard-to-understand models of text classification. This problem may be also addressed to most powerful recurrent neural networks that employ the feedback links from hidden or output units to their input units. Due to feedback links, recurrent neural networks are able take into account of a context in document. To be useful for data mining, self-organizing neural network techniques of knowledge extraction have been explored and developed. Self-organization principles were used to create an adequate neural-network structure and reduce a dimensionality of features used to describe text documents. The use of these principles seems interesting because ones are able to reduce a neural-network redundancy and considerably facilitate the knowledge representation.
The Combined Technique for Detection of Artifacts in Clinical Electroencephalograms of Sleeping Newborns
Venue: arXiv cs.NE 2005
Year: 2005

In this paper we describe a new method combining the polynomial neural network and decision tree techniques in order to derive comprehensible classification rules from clinical electroencephalograms (EEGs) recorded from sleeping newborns. These EEGs are heavily corrupted by cardiac, eye movement, muscle and noise artifacts and as a consequence some EEG features are irrelevant to classification problems. Combining the polynomial network and decision tree techniques, we discover comprehensible classification rules whilst also attempting to keep their classification error down. This technique is shown to outperform a number of commonly used machine learning technique applied to automatically recognize artifacts in the sleep EEGs.
Dichotomy for Voting Systems
Venue: arXiv cs.GT 2005
Year: 2005

Scoring protocols are a broad class of voting systems. Each is defined by a vector $(α_1,α_2,...,α_m)$, $α_1 \geq α_2 \geq >... \geq α_m$, of integers such that each voter contributes $α_1$ points to his/her first choice, $α_2$ points to his/her second choice, and so on, and any candidate receiving the most points is a winner. What is it about scoring-protocol election systems that makes some have the desirable property of being NP-complete to manipulate, while others can be manipulated in polynomial time? We find the complete, dichotomizing answer: Diversity of dislike. Every scoring-protocol election system having two or more point values assigned to candidates other than the favorite--i.e., having $||\{α_i \condition 2 \leq i \leq m\}||\geq 2$--is NP-complete to manipulate. Every other scoring-protocol election system can be manipulated in polynomial time. In effect, we show that--other than trivial systems (where all candidates alway tie), plurality voting, and plurality voting's transparently disguised translations--\emph{every} scoring-protocol election system is NP-complete to manipulate.
Time, Space, and Energy in Reversible Computing
Venue: arXiv cs.CC 2005
Year: 2005

We survey results of a quarter century of work on computation by reversible general-purpose computers (in this setting Turing machines), and general reversible simulation of irreversible computations, with respect to energy-, time- and space requirements.
Discrete Morse Theory for free chain complexes
Venue: arXiv cs.DM 2005
Year: 2005

We extend the combinatorial Morse complex construction to the arbitrary free chain complexes, and give a short, self-contained, and elementary proof of the quasi-isomorphism between the original chain complex and its Morse complex. Even stronger, the main result states that, if $C_*$ is a free chain complex, and $\cm$ an acyclic matching, then $C_*=C_*^\cm\oplus T_*$, where $C_*^\cm$ is the Morse complex generated by the critical elements, and $T_*$ is an acyclic complex.