OpenRaiser/Intern-Atlas huggingface dataset:
Voiced speech as secondary response of a self-consistent fundamental drive
Venue: arXiv cs.SD 2006
Year: 2006

Voiced segments of speech are assumed to be composed of non-stationary acoustic objects which can be described as stationary response of a non-stationary fundamental drive (FD) process and which are furthermore suited to reconstruct the hidden FD by using a voice adapted (self-consistent) part-tone decomposition of the speech signal. The universality and robustness of human pitch perception encourages the reconstruction of a band-limited FD in the frequency range of the pitch. The self-consistent decomposition of voiced continuants generates several part-tones which can be confirmed to be topologically equivalent to corresponding acoustic modes of the excitation on the transmitter side. As topologically equivalent image of a glottal master oscillator, the self-consistent FD is suited to serve as low frequency part of the basic time-scale separation of auditive perception and to describe the broadband voiced excitation as entrained (synchronized) and/or modulated primary response. Being guided by the acoustic correlates of pitch and loudness perception, the time-scale separation avoids the conventional assumption of stationary excitation and represents the basic decoding step of an advanced precision transmission protocol of self-consistent (voiced) acoustic objects. The present study is focussed on the adaptation of the trajectories (contours) of the centre filter frequency of the part-tones to the chirp of the glottal master oscillator.
Architecture for Modular Data Centers
Venue: arXiv cs.DB 2006
Year: 2006

Several factors are driving high-scale deployments of large data centers built upon commodity components. These commodity clusters are far cheaper than mainframe systems of the past but they bring serious heat and power density issues. Also the high failure rate of the individual components drives significant administrative costs. This proposal outlines an architecture for data center design based upon 20'x8'x8' modules that substantially changes how these systems are acquired, administered, and then later recycled.
SASE: Complex Event Processing over Streams
Venue: arXiv cs.DB 2006
Year: 2006

RFID technology is gaining adoption on an increasing scale for tracking and monitoring purposes. Wide deployments of RFID devices will soon generate an unprecedented volume of data. Emerging applications require the RFID data to be filtered and correlated for complex pattern detection and transformed to events that provide meaningful, actionable information to end applications. In this work, we design and develop SASE, a com-plex event processing system that performs such data-information transformation over real-time streams. We design a complex event language for specifying application logic for such transformation, devise new query processing techniques to effi-ciently implement the language, and develop a comprehensive system that collects, cleans, and processes RFID data for deliv-ery of relevant, timely information as well as storing necessary data for future querying. We demonstrate an initial prototype of SASE through a real-world retail management scenario.
Turning Cluster Management into Data Management: A System Overview
Venue: arXiv cs.DB 2006
Year: 2006

This paper introduces the CondorJ2 cluster management system. Traditionally, cluster management systems such as Condor employ a process-oriented approach with little or no use of modern database system technology. In contrast, CondorJ2 employs a data-centric, 3-tier web-application architecture for all system functions (e.g., job submission, monitoring and scheduling; node configuration, monitoring and management, etc.) except for job execution. Employing a data-oriented approach allows the core challenge (i.e., managing and coordinating a large set of distributed computing resources) to be transformed from a relatively low-level systems problem into a more abstract, higher-level data management problem. Preliminary results suggest that CondorJ2's use of standard 3-tier software represents a significant step forward to the design and implementation of large clusters (1,000 to 10,000 nodes).
On the Computational Complexity of Defining Sets
Venue: arXiv cs.CC 2006
Year: 2006

Suppose we have a family ${\cal F}$ of sets. For every $S \in {\cal F}$, a set $D \subseteq S$ is a {\sf defining set} for $({\cal F},S)$ if $S$ is the only element of $\cal{F}$ that contains $D$ as a subset. This concept has been studied in numerous cases, such as vertex colorings, perfect matchings, dominating sets, block designs, geodetics, orientations, and Latin squares. In this paper, first, we propose the concept of a defining set of a logical formula, and we prove that the computational complexity of such a problem is $Σ_2$-complete. We also show that the computational complexity of the following problem about the defining set of vertex colorings of graphs is $Σ_2$-complete: {\sc Instance:} A graph $G$ with a vertex coloring $c$ and an integer $k$. {\sc Question:} If ${\cal C}(G)$ be the set of all $χ(G)$-colorings of $G$, then does $({\cal C}(G),c)$ have a defining set of size at most $k$? Moreover, we study the computational complexity of some other variants of this problem.
Intelligent location of simultaneously active acoustic emission sources: Part II
Venue: arXiv cs.NE 2007
Year: 2007

Part I describes an intelligent acoustic emission locator, while Part II discusses blind source separation, time delay estimation and location of two continuous acoustic emission sources. Acoustic emission (AE) analysis is used for characterization and location of developing defects in materials. AE sources often generate a mixture of various statistically independent signals. A difficult problem of AE analysis is separation and characterization of signal components when the signals from various sources and the mode of mixing are unknown. Recently, blind source separation (BSS) by independent component analysis (ICA) has been used to solve these problems. The purpose of this paper is to demonstrate the applicability of ICA to locate two independent simultaneously active acoustic emission sources on an aluminum band specimen. The method is promising for non-destructive testing of aircraft frame structures by acoustic emission analysis.
Differential Recursion and Differentially Algebraic Functions
Venue: arXiv cs.CC 2007
Year: 2007

Moore introduced a class of real-valued "recursive" functions by analogy with Kleene's formulation of the standard recursive functions. While his concise definition inspired a new line of research on analog computation, it contains some technical inaccuracies. Focusing on his "primitive recursive" functions, we pin down what is problematic and discuss possible attempts to remove the ambiguity regarding the behavior of the differential recursion operator on partial functions. It turns out that in any case the purported relation to differentially algebraic functions, and hence to Shannon's model of analog computation, fails.
Optimal Routing for Decode-and-Forward based Cooperation in Wireless Networks
Venue: arXiv cs.IT 2007
Year: 2007

We investigate cooperative wireless relay networks in which the nodes can help each other in data transmission. We study different coding strategies in the single-source single-destination network with many relay nodes. Given the myriad of ways in which nodes can cooperate, there is a natural routing problem, i.e., determining an ordered set of nodes to relay the data from the source to the destination. We find that for a given route, the decode-and-forward strategy, which is an information theoretic cooperative coding strategy, achieves rates significantly higher than that achievable by the usual multi-hop coding strategy, which is a point-to-point non-cooperative coding strategy. We construct an algorithm to find an optimal route (in terms of rate maximizing) for the decode-and-forward strategy. Since the algorithm runs in factorial time in the worst case, we propose a heuristic algorithm that runs in polynomial time. The heuristic algorithm outputs an optimal route when the nodes transmit independent codewords. We implement these coding strategies using practical low density parity check codes to compare the performance of the strategies on different routes.
Revisiting the Issues On Netflow Sample and Export Performance
Venue: arXiv cs.PF 2007
Year: 2007

The high volume of packets and packet rates of traffic on some router links makes it exceedingly difficult for routers to examine every packet in order to keep detailed statistics about the traffic which is traversing the router. Sampling is commonly applied on routers in order to limit the load incurred by the collection of information that the router has to undertake when evaluating flow information for monitoring purposes. The sampling process in nearly all cases is a deterministic process of choosing 1 in every N packets on a per-interface basis, and then forming the flow statistics based on the collected sampled statistics. Even though this sampling may not be significant for some statistics, such as packet rate, others can be severely distorted. However, it is important to consider the sampling techniques and their relative accuracy when applied to different traffic patterns. The main disadvantage of sampling is the loss of accuracy in the collected trace when compared to the original traffic stream. To date there has not been a detailed analysis of the impact of sampling at a router in various traffic profiles and flow criteria. In this paper, we assess the performance of the sampling process as used in NetFlow in detail, and we discuss some techniques for the compensation of loss of monitoring detail.
P-adic arithmetic coding
Venue: arXiv cs.DS 2007
Year: 2007

A new incremental algorithm for data compression is presented. For a sequence of input symbols algorithm incrementally constructs a p-adic integer number as an output. Decoding process starts with less significant part of a p-adic integer and incrementally reconstructs a sequence of input symbols. Algorithm is based on certain features of p-adic numbers and p-adic norm. p-adic coding algorithm may be considered as of generalization a popular compression technique - arithmetic coding algorithms. It is shown that for p = 2 the algorithm works as integer variant of arithmetic coding; for a special class of models it gives exactly the same codes as Huffman's algorithm, for another special model and a specific alphabet it gives Golomb-Rice codes.
Fast paths in large-scale dynamic road networks
Venue: arXiv cs.NI 2007
Year: 2007

Efficiently computing fast paths in large scale dynamic road networks (where dynamic traffic information is known over a part of the network) is a practical problem faced by several traffic information service providers who wish to offer a realistic fast path computation to GPS terminal enabled vehicles. The heuristic solution method we propose is based on a highway hierarchy-based shortest path algorithm for static large-scale networks; we maintain a static highway hierarchy and perform each query on the dynamically evaluated network.
Text Line Segmentation of Historical Documents: a Survey
Venue: arXiv cs.CV 2007
Year: 2007

There is a huge amount of historical documents in libraries and in various National Archives that have not been exploited electronically. Although automatic reading of complete pages remains, in most cases, a long-term objective, tasks such as word spotting, text/image alignment, authentication and extraction of specific fields are in use today. For all these tasks, a major step is document segmentation into text lines. Because of the low quality and the complexity of these documents (background noise, artifacts due to aging, interfering lines),automatic text line segmentation remains an open research field. The objective of this paper is to present a survey of existing methods, developed during the last decade, and dedicated to documents of historical interest.
Supporting Knowledge and Expertise Finding within Australia's Defence Science and Technology Organisation
Venue: arXiv cs.OH 2007
Year: 2007

This paper reports on work aimed at supporting knowledge and expertise finding within a large Research and Development (R&D) organisation. The paper first discusses the nature of knowledge important to R&D organisations and presents a prototype information system developed to support knowledge and expertise finding. The paper then discusses a trial of the system within an R&D organisation, the implications and limitations of the trial, and discusses future research questions.
A Cut-free Sequent Calculus for Bi-Intuitionistic Logic: Extended Version
Venue: arXiv cs.LO 2007
Year: 2007

Bi-intuitionistic logic is the extension of intuitionistic logic with a connective dual to implication. Bi-intuitionistic logic was introduced by Rauszer as a Hilbert calculus with algebraic and Kripke semantics. But her subsequent ``cut-free'' sequent calculus for BiInt has recently been shown by Uustalu to fail cut-elimination. We present a new cut-free sequent calculus for BiInt, and prove it sound and complete with respect to its Kripke semantics. Ensuring completeness is complicated by the interaction between implication and its dual, similarly to future and past modalities in tense logic. Our calculus handles this interaction using extended sequents which pass information from premises to conclusions using variables instantiated at the leaves of failed derivation trees. Our simple termination argument allows our calculus to be used for automated deduction, although this is not its main purpose.
Low-density graph codes that are optimal for source/channel coding and binning
Venue: arXiv cs.IT 2007
Year: 2007

We describe and analyze the joint source/channel coding properties of a class of sparse graphical codes based on compounding a low-density generator matrix (LDGM) code with a low-density parity check (LDPC) code. Our first pair of theorems establish that there exist codes from this ensemble, with all degrees remaining bounded independently of block length, that are simultaneously optimal as both source and channel codes when encoding and decoding are performed optimally. More precisely, in the context of lossy compression, we prove that finite degree constructions can achieve any pair $(R, D)$ on the rate-distortion curve of the binary symmetric source. In the context of channel coding, we prove that finite degree codes can achieve any pair $(C, p)$ on the capacity-noise curve of the binary symmetric channel. Next, we show that our compound construction has a nested structure that can be exploited to achieve the Wyner-Ziv bound for source coding with side information (SCSI), as well as the Gelfand-Pinsker bound for channel coding with side information (CCSI). Although the current results are based on optimal encoding and decoding, the proposed graphical codes have sparse structure and high girth that renders them well-suited to message-passing and other efficient decoding procedures.
Transaction-Oriented Simulation In Ad Hoc Grids
Venue: arXiv cs.DC 2007
Year: 2007

This paper analyses the possibilities of performing parallel transaction-oriented simulations with a special focus on the space-parallel approach and discrete event simulation synchronisation algorithms that are suitable for transaction-oriented simulation and the target environment of Ad Hoc Grids. To demonstrate the findings a Java-based parallel transaction-oriented simulator for the simulation language GPSS/H is implemented on the basis of the promising Shock Resistant Time Warp synchronisation algorithm and using the Grid framework ProActive. The validation of this parallel simulator shows that the Shock Resistant Time Warp algorithm can successfully reduce the number of rolled back Transaction moves but it also reveals circumstances in which the Shock Resistant Time Warp algorithm can be outperformed by the normal Time Warp algorithm. The conclusion of this paper suggests possible improvements to the Shock Resistant Time Warp algorithm to avoid such problems.
Large System Analysis of Game-Theoretic Power Control in UWB Wireless Networks with Rake Receivers
Venue: arXiv cs.IT 2007
Year: 2007

This paper studies the performance of partial-Rake (PRake) receivers in impulse-radio ultrawideband wireless networks when an energy-efficient power control scheme is adopted. Due to the large bandwidth of the system, the multipath channel is assumed to be frequency-selective. By using noncooperative game-theoretic models and large system analysis, explicit expressions are derived in terms of network parameters to measure the effects of self- and multiple-access interference at a receiving access point. Performance of the PRake is compared in terms of achieved utilities and loss to that of the all-Rake receiver.
Light Logics and Optimal Reduction: Completeness and Complexity
Venue: arXiv cs.LO 2007
Year: 2007

Typing of lambda-terms in Elementary and Light Affine Logic (EAL, LAL, resp.) has been studied for two different reasons: on the one hand the evaluation of typed terms using LAL (EAL, resp.) proof-nets admits a guaranteed polynomial (elementary, resp.) bound; on the other hand these terms can also be evaluated by optimal reduction using the abstract version of Lamping's algorithm. The first reduction is global while the second one is local and asynchronous. We prove that for LAL (EAL, resp.) typed terms, Lamping's abstract algorithm also admits a polynomial (elementary, resp.) bound. We also show its soundness and completeness (for EAL and LAL with type fixpoints), by using a simple geometry of interaction model (context semantics).
STBCs from Representation of Extended Clifford Algebras
Venue: arXiv cs.IT 2007
Year: 2007

A set of sufficient conditions to construct $λ$-real symbol Maximum Likelihood (ML) decodable STBCs have recently been provided by Karmakar et al. STBCs satisfying these sufficient conditions were named as Clifford Unitary Weight (CUW) codes. In this paper, the maximal rate (as measured in complex symbols per channel use) of CUW codes for $λ=2^a,a\in\mathbb{N}$ is obtained using tools from representation theory. Two algebraic constructions of codes achieving this maximal rate are also provided. One of the constructions is obtained using linear representation of finite groups whereas the other construction is based on the concept of right module algebra over non-commutative rings. To the knowledge of the authors, this is the first paper in which matrices over non-commutative rings is used to construct STBCs. An algebraic explanation is provided for the 'ABBA' construction first proposed by Tirkkonen et al and the tensor product construction proposed by Karmakar et al. Furthermore, it is established that the 4 transmit antenna STBC originally proposed by Tirkkonen et al based on the ABBA construction is actually a single complex symbol ML decodable code if the design variables are permuted and signal sets of appropriate dimensions are chosen.
On Algebraic Decoding of $q$-ary Reed-Muller and Product-Reed-Solomon Codes
Venue: arXiv cs.IT 2007
Year: 2007

We consider a list decoding algorithm recently proposed by Pellikaan-Wu \cite{PW2005} for $q$-ary Reed-Muller codes $\mathcal{RM}_q(\ell, m, n)$ of length $n \leq q^m$ when $\ell \leq q$. A simple and easily accessible correctness proof is given which shows that this algorithm achieves a relative error-correction radius of $τ\leq (1 - \sqrt{\ell q^{m-1}/{n}})$. This is an improvement over the proof using one-point Algebraic-Geometric codes given in \cite{PW2005}. The described algorithm can be adapted to decode Product-Reed-Solomon codes. We then propose a new low complexity recursive algebraic decoding algorithm for Reed-Muller and Product-Reed-Solomon codes. Our algorithm achieves a relative error correction radius of $τ\leq \prod_{i=1}^m (1 - \sqrt{k_i/q})$. This technique is then proved to outperform the Pellikaan-Wu method in both complexity and error correction radius over a wide range of code rates.
Achievable Rates for Two-Way Wire-Tap Channels
Venue: arXiv cs.IT 2007
Year: 2007

We consider two-way wire-tap channels, where two users are communicating with each other in the presence of an eavesdropper, who has access to the communications through a multiple-access channel. We find achievable rates for two different scenarios, the Gaussian two-way wire-tap channel, (GTW-WT), and the binary additive two-way wire-tap channel, (BATW-WT). It is shown that the two-way channels inherently provide a unique advantage for wire-tapped scenarios, as the users know their own transmitted signals and in effect help encrypt the other user's messages, similar to a one-time pad. We compare the achievable rates to that of the Gaussian multiple-access wire-tap channel (GMAC-WT) to illustrate this advantage.
Space Time Codes from Permutation Codes
Venue: arXiv cs.IT 2007
Year: 2007

A new class of space time codes with high performance is presented. The code design utilizes tailor-made permutation codes, which are known to have large minimal distances as spherical codes. A geometric connection between spherical and space time codes has been used to translate them into the final space time codes. Simulations demonstrate that the performance increases with the block lengths, a result that has been conjectured already in previous work. Further, the connection to permutation codes allows for moderate complex en-/decoding algorithms.
Euclidean Shortest Paths in Simple Cube Curves at a Glance
Venue: arXiv cs.CG 2007
Year: 2007

This paper reports about the development of two provably correct approximate algorithms which calculate the Euclidean shortest path (ESP) within a given cube-curve with arbitrary accuracy, defined by $ε>0$, and in time complexity $κ(ε) \cdot {\cal O}(n)$, where $κ(ε)$ is the length difference between the path used for initialization and the minimum-length path, divided by $ε$. A run-time diagram also illustrates this linear-time behavior of the implemented ESP algorithm.
Lifetime Improvement in Wireless Sensor Networks via Collaborative Beamforming and Cooperative Transmission
Venue: arXiv cs.IT 2007
Year: 2007

Collaborative beamforming (CB) and cooperative transmission (CT) have recently emerged as communication techniques that can make effective use of collaborative/cooperative nodes to create a virtual multiple-input/multiple-output (MIMO) system. Extending the lifetime of networks composed of battery-operated nodes is a key issue in the design and operation of wireless sensor networks. This paper considers the effects on network lifetime of allowing closely located nodes to use CB/CT to reduce the load or even to avoid packet-forwarding requests to nodes that have critical battery life. First, the effectiveness of CB/CT in improving the signal strength at a faraway destination using energy in nearby nodes is studied. Then, the performance improvement obtained by this technique is analyzed for a special 2D disk case. Further, for general networks in which information-generation rates are fixed, a new routing problem is formulated as a linear programming problem, while for other general networks, the cost for routing is dynamically adjusted according to the amount of energy remaining and the effectiveness of CB/CT. From the analysis and the simulation results, it is seen that the proposed method can reduce the payloads of energy-depleting nodes by about 90% in the special case network considered and improve the lifetimes of general networks by about 10%, compared with existing techniques.