OpenRaiser/Intern-Atlas huggingface dataset:
Multiple-precision zero-finding methods and the complexity of elementary function evaluation
Venue: arXiv cs.NA 2010
Year: 2010

We consider methods for finding high-precision approximations to simple zeros of smooth functions. As an application, we give fast methods for evaluating the elementary functions log(x), exp(x), sin(x) etc. to high precision. For example, if x is a positive floating-point number with an n-bit fraction, then (under rather weak assumptions) an n-bit approximation to log(x) or exp(x) may be computed in time asymptotically equal to 13M(n)lg(n), where M(n) is the time required to multiply floating-point numbers with n-bit fractions. Similar results are given for the other elementary functions. Some analogies with operations on formal power series (over a field of characteristic zero) are discussed. In particular, it is possible to compute the first n terms in log(1 + a_1.x + ...) or exp(a_1.x + ...) in time O(M(n)), where M(n) is the time required to multiply two polynomials of degree n - 1. It follows that the first n terms in a q-th power (1 + a_1.x + ...)^q can be computed in time O(M(n)), independent of q. One of the results of this paper is the "Gauss-Legendre" or "Brent-Salamin" algorithm for computing pi. This is the first quadratically convergent algorithm for pi. It was also published in Brent [J. ACM 23 (1976), 242-251], and independently by Salamin [Math. Comp. 30 (1976), 565-570].
Towards Providing Low-Risk and Economically Feasible Network Data Transfer Services
Venue: arXiv cs.NI 2010
Year: 2010

In the first part of this paper we present the first steps towards providing low-risk and economically feasible network data transfer services. We introduce three types of data transfer services and present general guidelines and algorithms for managing service prices, risks and schedules. In the second part of the paper we solve two packet scheduling cost optimization problems and present efficient algorithms for identifying maximum weight (k-level-) caterpillar subtrees in tree networks.
Comparison of the Performance of Two Service Disciplines for a Shared Bus Multiprocessor with Private Caches
Venue: arXiv cs.PF 2010
Year: 2010

In this paper, we compare two analytical models for evaluation of cache coherence overhead of a shared bus multiprocessor with private caches. The models are based on a closed queuing network with different service disciplines. We find that the priority discipline can be used as a lower-level bound. Some numerical results are shown graphically.
A QoS Provisioning Recurrent Neural Network based Call Admission Control for beyond 3G Networks
Venue: arXiv cs.NI 2010
Year: 2010

The Call admission control (CAC) is one of the Radio Resource Management (RRM) techniques that plays influential role in ensuring the desired Quality of Service (QoS) to the users and applications in next generation networks. This paper proposes a fuzzy neural approach for making the call admission control decision in multi class traffic based Next Generation Wireless Networks (NGWN). The proposed Fuzzy Neural call admission control (FNCAC) scheme is an integrated CAC module that combines the linguistic control capabilities of the fuzzy logic controller and the learning capabilities of the neural networks. The model is based on recurrent radial basis function networks which have better learning and adaptability that can be used to develop intelligent system to handle the incoming traffic in an heterogeneous network environment. The simulation results are optimistic and indicates that the proposed FNCAC algorithm performs better than the other two methods and the call blocking probability is minimal when compared to other two methods.
Integrating User's Domain Knowledge with Association Rule Mining
Venue: arXiv cs.DB 2010
Year: 2010

This paper presents a variation of Apriori algorithm that includes the role of domain expert to guide and speed up the overall knowledge discovery task. Usually, the user is interested in finding relationships between certain attributes instead of the whole dataset. Moreover, he can help the mining algorithm to select the target database which in turn takes less time to find the desired association rules. Variants of the standard Apriori and Interactive Apriori algorithms have been run on artificial datasets. The results show that incorporating user's preference in selection of target attribute helps to search the association rules efficiently both in terms of space and time.
Comparison of Two Context-Free Rewriting Systems with Simple Context-Checking Mechanisms
Venue: arXiv cs.FL 2010
Year: 2010

This paper solves an open problem concerning the generative power of nonerasing context-free rewriting systems using a simple mechanism for checking for context dependencies, in the literature known as semi-conditional grammars of degree (1,1). In these grammars, two nonterminal symbols are attached to each context-free production, and such a production is applicable if one of the two attached symbols occurs in the current sentential form, while the other does not. Specifically, this paper demonstrates that the family of languages generated by semi-conditional grammars of degree (1,1) coincides with the family of random context languages. In addition, it shows that the normal form proved by Mayer for random context grammars with erasing productions holds for random context grammars without erasing productions, too. It also discusses two possible definitions of the relation of the direct derivation step used in the literature.
Parameterized Control Complexity in Fallback Voting
Venue: arXiv cs.CC 2010
Year: 2010

We study the parameterized control complexity of fallback voting, a voting system that combines preference-based with approval voting. Electoral control is one of many different ways for an external agent to tamper with the outcome of an election. We show that adding and deleting candidates in fallback voting are W[2]-hard for both the constructive and destructive case, parameterized by the amount of action taken by the external agent. Furthermore, we show that adding and deleting voters in fallback voting are W[2]-hard for the constructive case, parameterized by the amount of action taken by the external agent, and are in FPT for the destructive case.
Exact Sparse Matrix-Vector Multiplication on GPU's and Multicore Architectures
Venue: arXiv cs.DC 2010
Year: 2010

We propose different implementations of the sparse matrix--dense vector multiplication (\spmv{}) for finite fields and rings $\Zb/m\Zb$. We take advantage of graphic card processors (GPU) and multi-core architectures. Our aim is to improve the speed of \spmv{} in the \linbox library, and henceforth the speed of its black box algorithms. Besides, we use this and a new parallelization of the sigma-basis algorithm in a parallel block Wiedemann rank implementation over finite fields.
Threshold Saturation on BMS Channels via Spatial Coupling
Venue: arXiv cs.IT 2010
Year: 2010

We consider spatially coupled code ensembles. A particular instance are convolutional LDPC ensembles. It was recently shown that, for transmission over the binary erasure channel, this coupling increases the belief propagation threshold of the ensemble to the maximum a-priori threshold of the underlying component ensemble. We report on empirical evidence which suggest that the same phenomenon also occurs when transmission takes place over a general binary memoryless symmetric channel. This is confirmed both by simulations as well as by computing EBP GEXIT curves and by comparing the empirical BP thresholds of coupled ensembles to the empirically determined MAP thresholds of the underlying regular ensembles. We further consider ways of reducing the rate-loss incurred by such constructions.
Oil Price Trackers Inspired by Immune Memory
Venue: arXiv cs.AI 2010
Year: 2010

We outline initial concepts for an immune inspired algorithm to evaluate and predict oil price time series data. The proposed solution evolves a short term pool of trackers dynamically, with each member attempting to map trends and anticipate future price movements. Successful trackers feed into a long term memory pool that can generalise across repeating trend patterns. The resulting sequence of trackers, ordered in time, can be used as a forecasting tool. Examination of the pool of evolving trackers also provides valuable insight into the properties of the crude oil market.
A Message-Passing Algorithm for Counting Short Cycles in a Graph
Venue: arXiv cs.IT 2010
Year: 2010

A message-passing algorithm for counting short cycles in a graph is presented. For bipartite graphs, which are of particular interest in coding, the algorithm is capable of counting cycles of length g, g +2,..., 2g - 2, where g is the girth of the graph. For a general (non-bipartite) graph, cycles of length g; g + 1, ..., 2g - 1 can be counted. The algorithm is based on performing integer additions and subtractions in the nodes of the graph and passing extrinsic messages to adjacent nodes. The complexity of the proposed algorithm grows as $O(g|E|^2)$, where $|E|$ is the number of edges in the graph. For sparse graphs, the proposed algorithm significantly outperforms the existing algorithms in terms of computational complexity and memory requirements.
Analysis and Design of Binary Message-Passing Decoders
Venue: arXiv cs.IT 2010
Year: 2010

Binary message-passing decoders for low-density parity-check (LDPC) codes are studied by using extrinsic information transfer (EXIT) charts. The channel delivers hard or soft decisions and the variable node decoder performs all computations in the L-value domain. A hard decision channel results in the well-know Gallager B algorithm, and increasing the output alphabet from hard decisions to two bits yields a gain of more than 1.0 dB in the required signal to noise ratio when using optimized codes. The code optimization requires adapting the mixing property of EXIT functions to the case of binary message-passing decoders. Finally, it is shown that errors on cycles consisting only of degree two and three variable nodes cannot be corrected and a necessary and sufficient condition for the existence of a cycle-free subgraph is derived.
Computers and the Conservation of Energy
Venue: arXiv cs.CY 2010
Year: 2010

The purpose of this report is to show that computer and allied technologies can be used to increase energy efficiency. The report is divided into transport, industrial, commercial and domestic sections, which correspond to the major energy consuming sectors of the economy. Each section considers the various ways in which energy can be saved by the use of the computer. The report concludes that it is economic to incorporate computer based energy management systems in a wide variety of applications and that it is important that this capability is realised on a large scale. A comprehensive reference list and a bibliography are included.
Efficient volume sampling for row/column subset selection
Venue: arXiv cs.DS 2010
Year: 2010

We give efficient algorithms for volume sampling, i.e., for picking $k$-subsets of the rows of any given matrix with probabilities proportional to the squared volumes of the simplices defined by them and the origin (or the squared volumes of the parallelepipeds defined by these subsets of rows). This solves an open problem from the monograph on spectral algorithms by Kannan and Vempala. Our first algorithm for volume sampling $k$-subsets of rows from an $m$-by-$n$ matrix runs in $O(kmn^ω \log n)$ arithmetic operations and a second variant of it for $(1+ε)$-approximate volume sampling runs in $O(mn \log m \cdot k^{2}/ε^{2} + m \log^ω m \cdot k^{2ω+1}/ε^{2ω} \cdot \log(k ε^{-1} \log m))$ arithmetic operations, which is almost linear in the size of the input (i.e., the number of entries) for small $k$. Our efficient volume sampling algorithms imply several interesting results for low-rank matrix approximation.
Symmetric M-tree
Venue: arXiv cs.DB 2010
Year: 2010

The M-tree is a paged, dynamically balanced metric access method that responds gracefully to the insertion of new objects. To date, no algorithm has been published for the corresponding Delete operation. We believe this to be non-trivial because of the design of the M-tree's Insert algorithm. We propose a modification to Insert that overcomes this problem and give the corresponding Delete algorithm. The performance of the tree is comparable to the M-tree and offers additional benefits in terms of supported operations, which we briefly discuss.
Analysis of Basis Pursuit Via Capacity Sets
Venue: arXiv cs.NA 2010
Year: 2010

Finding the sparsest solution $α$ for an under-determined linear system of equations $Dα=s$ is of interest in many applications. This problem is known to be NP-hard. Recent work studied conditions on the support size of $α$ that allow its recovery using L1-minimization, via the Basis Pursuit algorithm. These conditions are often relying on a scalar property of $D$ called the mutual-coherence. In this work we introduce an alternative set of features of an arbitrarily given $D$, called the "capacity sets". We show how those could be used to analyze the performance of the basis pursuit, leading to improved bounds and predictions of performance. Both theoretical and numerical methods are presented, all using the capacity values, and shown to lead to improved assessments of the basis pursuit success in finding the sparest solution of $Dα=s$.
Towards Closed World Reasoning in Dynamic Open Worlds (Extended Version)
Venue: arXiv cs.AI 2010
Year: 2010

The need for integration of ontologies with nonmonotonic rules has been gaining importance in a number of areas, such as the Semantic Web. A number of researchers addressed this problem by proposing a unified semantics for hybrid knowledge bases composed of both an ontology (expressed in a fragment of first-order logic) and nonmonotonic rules. These semantics have matured over the years, but only provide solutions for the static case when knowledge does not need to evolve. In this paper we take a first step towards addressing the dynamics of hybrid knowledge bases. We focus on knowledge updates and, considering the state of the art of belief update, ontology update and rule update, we show that current solutions are only partial and difficult to combine. Then we extend the existing work on ABox updates with rules, provide a semantics for such evolving hybrid knowledge bases and study its basic properties. To the best of our knowledge, this is the first time that an update operator is proposed for hybrid knowledge bases.
SHIELD: Social sensing and Help In Emergency using mobiLe Devices
Venue: arXiv cs.NI 2010
Year: 2010

School and College campuses face a perceived threat of violent crimes and require a realistic plan against unpredictable emergencies and disasters. Existing emergency systems (e.g., 911, campus-wide alerts) are quite useful, but provide delayed response (often tens of minutes) and do not utilize proximity or locality. There is a need to augment such systems with proximity-based systems for more immediate response to attempt to prevent and deter crime. In this paper we propose SHIELD, an on-campus emergency rescue and alert management service. It is a fully distributed infrastructure-less platform based on proximity-enabled trust and cooperation. It relies on localized responses, sent using Bluetooth and/or WiFi on the fly to achieve minimal response time and maximal availability thereby augmenting the traditional notion of emergency services. Analysis of campus crime statistics and WLAN traces surprisingly show a strong positive correlation (over 55%) between on-campus crime statistics and spatio-temporal density distribution of on-campus mobile users. This result provides a motivation to develop such platform and points to the promise in reducing crime incidences. We also show an implementation of a prototype application to be used in such scenarios.
Spatially-Adaptive Reconstruction in Computed Tomography Based on Statistical Learning
Venue: arXiv cs.CV 2010
Year: 2010

We propose a direct reconstruction algorithm for Computed Tomography, based on a local fusion of a few preliminary image estimates by means of a non-linear fusion rule. One such rule is based on a signal denoising technique which is spatially adaptive to the unknown local smoothness. Another, more powerful fusion rule, is based on a neural network trained off-line with a high-quality training set of images. Two types of linear reconstruction algorithms for the preliminary images are employed for two different reconstruction tasks. For an entire image reconstruction from full projection data, the proposed scheme uses a sequence of Filtered Back-Projection algorithms with a gradually growing cut-off frequency. To recover a Region Of Interest only from local projections, statistically-trained linear reconstruction algorithms are employed. Numerical experiments display the improvement in reconstruction quality when compared to linear reconstruction algorithms.
An Intelligent Call Admission Control Decision Mechanism for Wireless Networks
Venue: arXiv cs.NI 2010
Year: 2010

The Call admission control (CAC) is one of the Radio Resource Management (RRM) techniques plays instrumental role in ensuring the desired Quality of Service (QoS) to the users working on different applications which have diversified nature of QoS requirements. This paper proposes a fuzzy neural approach for call admission control in a multi class traffic based Next Generation Wireless Networks (NGWN). The proposed Fuzzy Neural Call Admission Control (FNCAC) scheme is an integrated CAC module that combines the linguistic control capabilities of the fuzzy logic controller and the learning capabilities of the neural networks .The model is based on Recurrent Radial Basis Function Networks (RRBFN) which have better learning and adaptability that can be used to develop the intelligent system to handle the incoming traffic in the heterogeneous network environment. The proposed FNCAC can achieve reduced call blocking probability keeping the resource utilisation at an optimal level. In the proposed algorithm we have considered three classes of traffic having different QoS requirements. We have considered the heterogeneous network environment which can effectively handle this traffic. The traffic classes taken for the study are Conversational traffic, Interactive traffic and back ground traffic which are with varied QoS parameters. The paper also presents the analytical model for the CAC .The paper compares the call blocking probabilities for all the three types of traffic in both the models. The simulation results indicate that compared to Fuzzy logic based CAC, Conventional CAC, The simulation results are optimistic and indicates that the proposed FNCAC algorithm performs better where the call blocking probability is minimal when compared to other two methods.
Crowd simulation influenced by agent's socio-psychological state
Venue: arXiv cs.MA 2010
Year: 2010

The aim our work is to create virtual humans as intelligent entities, which includes approximate the maximum as possible the virtual agent animation to the natural human behavior. In order to accomplish this task, our agent must be capable to interact with the environment, interacting with objects and other agents. The virtual agent needs to act as real person, so he should be capable to extract semantic information from the geometric model of the world where he is inserted, based on his own perception, and he realizes his own decision. The movement of the individuals is representing by the combination of two approaches of movement which are, the social force model and the based-rule model. These movements are influenced by a set of socio-psychological rules to give a more realistic result.
Visual Infrared Video Fusion for Night Vision using Background Estimation
Venue: arXiv cs.MM 2010
Year: 2010

Video fusion is a process that combines visual data from different sensors to obtain a single composite video preserving the information of the sources. The availability of a system, enhancing human ability to perceive the observed scenario, is crucial to improve the performance of a surveillance system. The infrared (IR) camera captures thermal image of object in night-time environment, when only limited visual information can be captured by RGB camera. The fusion of data recorded by an IR sensor and a visible RGB camera can produce information otherwise not obtainable by viewing the sensor outputs separately. In this paper we consider the problem of fusing two video streams acquired by an RGB camera and an IR sensor. The pedestrians, distinctly captured by IR video, are separated and fused with the RGB video. The algorithms implemented involve estimation of the background, followed by detection of object from the IR Video, after necessary denoising. Finally a suitable fusion algorithm is employed to combine the extracted pedestrians with the visual output. The obtained results clearly demonstrate the effectiveness of the proposed video fusion scheme, for night vision.
Effect of Crosstalk on Permutation in Optical Multistage Interconnection Networks
Venue: arXiv cs.NI 2010
Year: 2010

Optical MINs hold great promise and have advantages over their electronic networks.they also hold their own challenges. More research has been done on Electronic Multistage Interconnection Networks, (EMINs) but these days optical communication is a good networking choice to meet the increasing demands of high-performance computing communication applications for high bandwidth applications. The electronic Multistage Interconnection Networks (EMINs) and the Optical Multistage Interconnection Networks (OMINs) have many similarities, but there are some fundamental differences between them such as the optical-loss during switching and the crosstalk problem in the optical switches. To reduce the negative effect of crosstalk, various approaches which apply the concept of dilation in either the space or time domain have been proposed. With the space domain approach, extra SEs are used to ensure that at most one input and one output of every SE will be used at any given time. For an Optical network without crosstalk, it is needed to divide the messages into several groups, and then deliver the messages using one time slot (pass) for each group, which is called the time division multiplexing. This Paper discusses the permutation passability behavior of optical MINs. The bandwidth of optical MINs with or without crosstalk has also been explained. The results thus obtained shows that the performance of the networks improves by allowing crosstalk to some extent.
Survey and Comparison of Optical Switch Fabrication Techniques and Architectures
Venue: arXiv cs.NI 2010
Year: 2010

The main issue in the optical transmission is switching speed. The optical packet switching faces many significant challenges in processing and buffering. The generalized multilevel protocol switching seeks to eliminate the asynchronous transfer mode and synchronous optical network layer, hence the implementation of IP over WDM (wave length division multiplexing). Optical burst switching attempts to minimize the need for processing and buffering by aggregating flow of data packets in to burst. In this paper there is an extensive overview on current technologies and techniques concerning optical switching.