OpenRaiser/Intern-Atlas huggingface dataset:
Ordering Finite-State Markov Channels by Mutual Information
Venue: arXiv cs.IT 2007
Year: 2007

In previous work, an ordering result was given for the symbolwise probability of error using general Markov channels, under iterative decoding of LDPC codes. In this paper, the ordering result is extended to mutual information, under the assumption of an iid input distribution. For certain channels, in which the capacity-achieving input distribution is iid, this allows ordering of the channels by capacity. The complexity of analyzing general Markov channels is mitigated by this ordering, since it is possible to immediately determine that a wide class of channels, with different numbers of states, has a smaller mutual information than a given channel.
Workspace Analysis of the Orthoglide using Interval Analysis
Venue: arXiv cs.RO 2007
Year: 2007

This paper addresses the workspace analysis of the orthoglide, a 3-DOF parallel mechanism designed for machining applications. This machine features three fixed parallel linear joints which are mounted orthogonally and a mobile platform which moves in the Cartesian x-y-z space with fixed orientation. The workspace analysis is conducted on the bases of prescribed kinetostatic performances. The interesting features of the orthoglide are a regular Cartesian workspace shape, uniform performances in all directions and good compactness. Interval analysis based methods for computing the dextrous workspace and the largest cube enclosed in this workspace are presented.
On Optimum Power Allocation for the V-BLAST
Venue: arXiv cs.IT 2007
Year: 2007

A unified analytical framework for optimum power allocation in the unordered V-BLAST algorithm and its comparative performance analysis are presented. Compact closed-form approximations for the optimum power allocation are derived, based on average total and block error rates. The choice of the criterion has little impact on the power allocation and, overall, the optimum strategy is to allocate more power to lower step transmitters and less to higher ones. High-SNR approximations for optimized average block and total error rates are given. The SNR gain of optimization is rigorously defined and studied using analytical tools, including lower and upper bounds, high and low SNR approximations. The gain is upper bounded by the number of transmitters, for any modulation format and type of fading channel. While the average optimization is less complex than the instantaneous one, its performance is almost as good at high SNR. A measure of robustness of the optimized algorithm is introduced and evaluated. The optimized algorithm is shown to be robust to perturbations in individual and total transmit powers. Based on the algorithm robustness, a pre-set power allocation is suggested as a low-complexity alternative to the other optimization strategies, which exhibits only a minor loss in performance over the practical SNR range.
A Workspace based Classification of 3R Orthogonal Manipulators
Venue: arXiv cs.RO 2007
Year: 2007

A classification of a family of 3-revolute (3R) positioning manipulators is established. This classification is based on the topology of their workspace. The workspace is characterized in a half-cross section by the singular curves of the manipulator. The workspace topology is defined by the number of cusps and nodes that appear on these singular curves. The design parameters space is shown to be partitioned into nine subspaces of distinct workspace topologies. Each separating surface is given as an explicit expression in the DH-parameters.
DWEB: A Data Warehouse Engineering Benchmark
Venue: arXiv cs.DB 2007
Year: 2007

Data warehouse architectural choices and optimization techniques are critical to decision support query performance. To facilitate these choices, the performance of the designed data warehouse must be assessed. This is usually done with the help of benchmarks, which can either help system users comparing the performances of different systems, or help system engineers testing the effect of various design choices. While the TPC standard decision support benchmarks address the first point, they are not tuneable enough to address the second one and fail to model different data warehouse schemas. By contrast, our Data Warehouse Engineering Benchmark (DWEB) allows to generate various ad-hoc synthetic data warehouses and workloads. DWEB is fully parameterized to fulfill data warehouse design needs. However, two levels of parameterization keep it relatively easy to tune. Finally, DWEB is implemented as a Java free software that can be interfaced with most existing relational database management systems. A sample usage of DWEB is also provided in this paper.
DOEF: A Dynamic Object Evaluation Framework
Venue: arXiv cs.DB 2007
Year: 2007

In object-oriented or object-relational databases such as multimedia databases or most XML databases, access patterns are not static, i.e., applications do not always access the same objects in the same order repeatedly. However, this has been the way these databases and associated optimisation techniques like clustering have been evaluated up to now. This paper opens up research regarding this issue by proposing a dynamic object evaluation framework (DOEF) that accomplishes access pattern change by defining configurable styles of change. This preliminary prototype has been designed to be open and fully extensible. To illustrate the capabilities of DOEF, we used it to compare the performances of four state of the art dynamic clustering algorithms. The results show that DOEF is indeed effective at determining the adaptability of each dynamic clustering algorithm to changes in access pattern.
Actin - Technical Report
Venue: arXiv cs.NE 2007
Year: 2007

The Boolean satisfiability problem (SAT) can be solved efficiently with variants of the DPLL algorithm. For industrial SAT problems, DPLL with conflict analysis dependent dynamic decision heuristics has proved to be particularly efficient, e.g. in Chaff. In this work, algorithms that initialize the variable activity values in the solver MiniSAT v1.14 by analyzing the CNF are evolved using genetic programming (GP), with the goal to reduce the total number of conflicts of the search and the solving time. The effect of using initial activities other than zero is examined by initializing with random numbers. The possibility of countering the detrimental effects of reordering the CNF with improved initialization is investigated. The best result found (with validation testing on further problems) was used in the solver Actin, which was submitted to SAT-Race 2006.
Finite Element Model Updating Using Response Surface Method
Venue: arXiv cs.CE 2007
Year: 2007

This paper proposes the response surface method for finite element model updating. The response surface method is implemented by approximating the finite element model surface response equation by a multi-layer perceptron. The updated parameters of the finite element model were calculated using genetic algorithm by optimizing the surface response equation. The proposed method was compared to the existing methods that use simulated annealing or genetic algorithm together with a full finite element model for finite element model updating. The proposed method was tested on an unsymmetri-cal H-shaped structure. It was observed that the proposed method gave the updated natural frequen-cies and mode shapes that were of the same order of accuracy as those given by simulated annealing and genetic algorithm. Furthermore, it was observed that the response surface method achieved these results at a computational speed that was more than 2.5 times as fast as the genetic algorithm and a full finite element model and 24 times faster than the simulated annealing.
A Closed-Form Method for LRU Replacement under Generalized Power-Law Demand
Venue: arXiv cs.DS 2007
Year: 2007

We consider the well known \emph{Least Recently Used} (LRU) replacement algorithm and analyze it under the independent reference model and generalized power-law demand. For this extensive family of demand distributions we derive a closed-form expression for the per object steady-state hit ratio. To the best of our knowledge, this is the first analytic derivation of the per object hit ratio of LRU that can be obtained in constant time without requiring laborious numeric computations or simulation. Since most applications of replacement algorithms include (at least) some scenarios under i.i.d. requests, our method has substantial practical value, especially when having to analyze multiple caches, where existing numeric methods and simulation become too time consuming.
TrustMIX: Trustworthy MIX for Energy Saving in Sensor Networks
Venue: arXiv cs.DC 2007
Year: 2007

MIX has recently been proposed as a new sensor scheme with better energy management for data-gathering in Wireless Sensor Networks. However, it is not known how it performs when some of the sensors carry out sinkhole attacks. In this paper, we propose a variant of MIX with adjunct computational trust management to limit the impact of such sinkhole attacks. We evaluate how MIX resists sinkhole attacks with and without computational trust management. The main result of this paper is to find that MIX is very vulnerable to sinkhole attacks but that the adjunct trust management efficiently reduces the impact of such attacks while preserving the main feature of MIX: increased lifetime of the network.
On the monotonization of the training set
Venue: arXiv cs.LG 2007
Year: 2007

We consider the problem of minimal correction of the training set to make it consistent with monotonic constraints. This problem arises during analysis of data sets via techniques that require monotone data. We show that this problem is NP-hard in general and is equivalent to finding a maximal independent set in special orgraphs. Practically important cases of that problem considered in detail. These are the cases when a partial order given on the replies set is a total order or has a dimension 2. We show that the second case can be reduced to maximization of a quadratic convex function on a convex set. For this case we construct an approximate polynomial algorithm based on convex optimization.
Worst-Case Background Knowledge for Privacy-Preserving Data Publishing
Venue: arXiv cs.DB 2007
Year: 2007

Recent work has shown the necessity of considering an attacker's background knowledge when reasoning about privacy in data publishing. However, in practice, the data publisher does not know what background knowledge the attacker possesses. Thus, it is important to consider the worst-case. In this paper, we initiate a formal study of worst-case background knowledge. We propose a language that can express any background knowledge about the data. We provide a polynomial time algorithm to measure the amount of disclosure of sensitive information in the worst case, given that the attacker has at most a specified number of pieces of information in this language. We also provide a method to efficiently sanitize the data so that the amount of disclosure in the worst case is less than a specified threshold.
An online algorithm for generating fractal hash chains applied to digital chains of custody
Venue: arXiv cs.CR 2007
Year: 2007

This paper gives an online algorithm for generating Jakobsson's fractal hash chains. Our new algorithm compliments Jakobsson's fractal hash chain algorithm for preimage traversal since his algorithm assumes the entire hash chain is precomputed and a particular list of Ceiling(log n) hash elements or pebbles are saved. Our online algorithm for hash chain traversal incrementally generates a hash chain of n hash elements without knowledge of n before it starts. For any n, our algorithm stores only the Ceiling(log n) pebbles which are precisely the inputs for Jakobsson's amortized hash chain preimage traversal algorithm. This compact representation is useful to generate, traverse, and store a number of large digital hash chains on a small and constrained device. We also give an application using both Jakobsson's and our new algorithm applied to digital chains of custody for validating dynamically changing forensics data.
The Road to Quantum Artificial Intelligence
Venue: arXiv cs.AI 2007
Year: 2007

This paper overviews the basic principles and recent advances in the emerging field of Quantum Computation (QC), highlighting its potential application to Artificial Intelligence (AI). The paper provides a very brief introduction to basic QC issues like quantum registers, quantum gates and quantum algorithms and then it presents references, ideas and research guidelines on how QC can be used to deal with some basic AI problems, such as search and pattern matching, as soon as quantum computers become widely available.
Linearly bounded infinite graphs
Venue: arXiv cs.LO 2007
Year: 2007

Linearly bounded Turing machines have been mainly studied as acceptors for context-sensitive languages. We define a natural class of infinite automata representing their observable computational behavior, called linearly bounded graphs. These automata naturally accept the same languages as the linearly bounded machines defining them. We present some of their structural properties as well as alternative characterizations in terms of rewriting systems and context-sensitive transductions. Finally, we compare these graphs to rational graphs, which are another class of automata accepting the context-sensitive languages, and prove that in the bounded-degree case, rational graphs are a strict sub-class of linearly bounded graphs.
Making Random Choices Invisible to the Scheduler
Venue: arXiv cs.CR 2007
Year: 2007

When dealing with process calculi and automata which express both nondeterministic and probabilistic behavior, it is customary to introduce the notion of scheduler to solve the nondeterminism. It has been observed that for certain applications, notably those in security, the scheduler needs to be restricted so not to reveal the outcome of the protocol's random choices, or otherwise the model of adversary would be too strong even for ``obviously correct'' protocols. We propose a process-algebraic framework in which the control on the scheduler can be specified in syntactic terms, and we show how to apply it to solve the problem mentioned above. We also consider the definition of (probabilistic) may and must preorders, and we show that they are precongruences with respect to the restricted schedulers. Furthermore, we show that all the operators of the language, except replication, distribute over probabilistic summation, which is a useful property for verification.
On complexity of optimized crossover for binary representations
Venue: arXiv cs.NE 2007
Year: 2007

We consider the computational complexity of producing the best possible offspring in a crossover, given two solutions of the parents. The crossover operators are studied on the class of Boolean linear programming problems, where the Boolean vector of variables is used as the solution representation. By means of efficient reductions of the optimized gene transmitting crossover problems (OGTC) we show the polynomial solvability of the OGTC for the maximum weight set packing problem, the minimum weight set partition problem and for one of the versions of the simple plant location problem. We study a connection between the OGTC for linear Boolean programming problem and the maximum weight independent set problem on 2-colorable hypergraph and prove the NP-hardness of several special cases of the OGTC problem in Boolean linear programming.
Average Stopping Set Weight Distribution of Redundant Random Matrix Ensembles
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, redundant random matrix ensembles (abbreviated as redundant random ensembles) are defined and their stopping set (SS) weight distributions are analyzed. A redundant random ensemble consists of a set of binary matrices with linearly dependent rows. These linearly dependent rows (redundant rows) significantly reduce the number of stopping sets of small size. An upper and lower bound on the average SS weight distribution of the redundant random ensembles are shown. From these bounds, the trade-off between the number of redundant rows (corresponding to decoding complexity of BP on BEC) and the critical exponent of the asymptotic growth rate of SS weight distribution (corresponding to decoding performance) can be derived. It is shown that, in some cases, a dense matrix with linearly dependent rows yields asymptotically (i.e., in the regime of small erasure probability) better performance than regular LDPC matrices with comparable parameters.
The Distance Geometry of Music
Venue: arXiv cs.CG 2007
Year: 2007

We demonstrate relationships between the classic Euclidean algorithm and many other fields of study, particularly in the context of music and distance geometry. Specifically, we show how the structure of the Euclidean algorithm defines a family of rhythms which encompass over forty timelines (\emph{ostinatos}) from traditional world music. We prove that these \emph{Euclidean rhythms} have the mathematical property that their onset patterns are distributed as evenly as possible: they maximize the sum of the Euclidean distances between all pairs of onsets, viewing onsets as points on a circle. Indeed, Euclidean rhythms are the unique rhythms that maximize this notion of \emph{evenness}. We also show that essentially all Euclidean rhythms are \emph{deep}: each distinct distance between onsets occurs with a unique multiplicity, and these multiplicies form an interval $1,2,...,k-1$. Finally, we characterize all deep rhythms, showing that they form a subclass of generated rhythms, which in turn proves a useful property called shelling. All of our results for musical rhythms apply equally well to musical scales. In addition, many of the problems we explore are interesting in their own right as distance geometry problems on the circle; some of the same problems were explored by Erdős in the plane.
Grover search algorithm
Venue: arXiv cs.DS 2007
Year: 2007

A quantum algorithm is a set of instructions for a quantum computer, however, unlike algorithms in classical computer science their results cannot be guaranteed. A quantum system can undergo two types of operation, measurement and quantum state transformation, operations themselves must be unitary (reversible). Most quantum algorithms involve a series of quantum state transformations followed by a measurement. Currently very few quantum algorithms are known and no general design methodology exists for their construction.
PERCEVAL: a Computer-Driven System for Experimentation on Auditory and Visual Perception
Venue: arXiv cs.SE 2007
Year: 2007

Since perception tests are highly time-consuming, there is a need to automate as many operations as possible, such as stimulus generation, procedure control, perception testing, and data analysis. The computer-driven system we are presenting here meets these objectives. To achieve large flexibility, the tests are controlled by scripts. The system's core software resembles that of a lexical-syntactic analyzer, which reads and interprets script files sent to it. The execution sequence (trial) is modified in accordance with the commands and data received. This type of operation provides a great deal of flexibility and supports a wide variety of tests such as auditory-lexical decision making, phoneme monitoring, gating, phonetic categorization, word identification, voice quality, etc. To achieve good performance, we were careful about timing accuracy, which is the greatest problem in computerized perception tests.
Modeling Computations in a Semantic Network
Venue: arXiv cs.AI 2007
Year: 2007

Semantic network research has seen a resurgence from its early history in the cognitive sciences with the inception of the Semantic Web initiative. The Semantic Web effort has brought forth an array of technologies that support the encoding, storage, and querying of the semantic network data structure at the world stage. Currently, the popular conception of the Semantic Web is that of a data modeling medium where real and conceptual entities are related in semantically meaningful ways. However, new models have emerged that explicitly encode procedural information within the semantic network substrate. With these new technologies, the Semantic Web has evolved from a data modeling medium to a computational medium. This article provides a classification of existing computational modeling efforts and the requirements of supporting technologies that will aid in the further growth of this burgeoning domain.
On the End-to-End Distortion for a Buffered Transmission over Fading Channel
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, we study the end-to-end distortion/delay tradeoff for a analogue source transmitted over a fading channel. The analogue source is quantized and stored in a buffer until it is transmitted. There are two extreme cases as far as buffer delay is concerned: no delay and infinite delay. We observe that there is a significant power gain by introducing a buffer delay. Our goal is to investigate the situation between these two extremes. Using recently proposed \emph{effective capacity} concept, we derive a closed-form formula for this tradeoff. For SISO case, an asymptotically tight upper bound for our distortion-delay curve is derived, which approaches to the infinite delay lower bound as $\mathcal{D}_\infty \exp(\frac{C}{τ_n})$, with $τ_n$ is the normalized delay, $C$ is a constant. For more general MIMO channel, we computed the distortion SNR exponent -- the exponential decay rate of the expected distortion in the high SNR regime. Numerical results demonstrate that introduction of a small amount delay can save significant transmission power.
Watermark Embedding and Detection
Venue: arXiv cs.MM 2007
Year: 2007

The embedder and the detector (or decoder) are the two most important components of the digital watermarking systems. Thus in this work, we discuss how to design a better embedder and detector (or decoder). I first give a summary of the prospective applications of watermarking technology and major watermarking schemes in the literature. My review on the literature closely centers upon how the side information is exploited at both embedders and detectors. In Chapter 3, I explore the optimum detector or decoder according to a particular probability distribution of the host signals. We found that the performance of both multiplicative and additive spread spectrum schemes depends on the shape parameter of the host signals. For spread spectrum schemes, the performance of the detector or the decoder is reduced by the host interference. Thus I present a new host-interference rejection technique for the multiplicative spread spectrum schemes. Its embedding rule is tailored to the optimum detection or decoding rule. Though the host interference rejection schemes enjoy a big performance gain over the traditional spread spectrum schemes, their drawbacks that it is difficult for them to be implemented with the perceptual analysis to achieve the maximum allowable embedding level discourage their use in real scenarios. Thus, in the last chapters of this work, I introduce a double-sided technique to tackle this drawback. It differs from the host interference rejection schemes in that it utilizes but does not reject the host interference at its embedder. The perceptual analysis can be easily implemented in our scheme to achieve the maximum allowable level of embedding strength.