OpenRaiser/Intern-Atlas huggingface dataset:
State of the Art, Evaluation and Recommendations regarding "Document Processing and Visualization Techniques"
Venue: arXiv cs.CL 2004
Year: 2004

Several Networks of Excellence have been set up in the framework of the European FP5 research program. Among these Networks of Excellence, the NEMIS project focuses on the field of Text Mining. Within this field, document processing and visualization was identified as one of the key topics and the WG1 working group was created in the NEMIS project, to carry out a detailed survey of techniques associated with the text mining process and to identify the relevant research topics in related research areas. In this document we present the results of this comprehensive survey. The report includes a description of the current state-of-the-art and practice, a roadmap for follow-up research in the identified areas, and recommendations for anticipated technological development in the domain of text mining.
Thematic Annotation: extracting concepts out of documents
Venue: arXiv cs.CL 2004
Year: 2004

Contrarily to standard approaches to topic annotation, the technique used in this work does not centrally rely on some sort of -- possibly statistical -- keyword extraction. In fact, the proposed annotation algorithm uses a large scale semantic database -- the EDR Electronic Dictionary -- that provides a concept hierarchy based on hyponym and hypernym relations. This concept hierarchy is used to generate a synthetic representation of the document by aggregating the words present in topically homogeneous document segments into a set of concepts best preserving the document's content. This new extraction technique uses an unexplored approach to topic selection. Instead of using semantic similarity measures based on a semantic resource, the later is processed to extract the part of the conceptual hierarchy relevant to the document content. Then this conceptual hierarchy is searched to extract the most relevant set of concepts to represent the topics discussed in the document. Notice that this algorithm is able to extract generic concepts that are not directly present in the document.
Approximation Algorithms for Covering/Packing Integer Programs
Venue: arXiv cs.DS 2005
Year: 2005

Given matrices A and B and vectors a, b, c and d, all with non-negative entries, we consider the problem of computing min {c.x: x in Z^n_+, Ax > a, Bx < b, x < d}. We give a bicriteria-approximation algorithm that, given epsilon in (0, 1], finds a solution of cost O(ln(m)/epsilon^2) times optimal, meeting the covering constraints (Ax > a) and multiplicity constraints (x < d), and satisfying Bx < (1 + epsilon)b + beta, where beta is the vector of row sums beta_i = sum_j B_ij. Here m denotes the number of rows of A. This gives an O(ln m)-approximation algorithm for CIP -- minimum-cost covering integer programs with multiplicity constraints, i.e., the special case when there are no packing constraints Bx < b. The previous best approximation ratio has been O(ln(max_j sum_i A_ij)) since 1982. CIP contains the set cover problem as a special case, so O(ln m)-approximation is the best possible unless P=NP.
Programming and Verifying Subgame Perfect Mechanisms
Venue: arXiv cs.LO 2005
Year: 2005

An extension of the WHILE-language is developed for programming game-theoretic mechanisms involving multiple agents. Examples of such mechanisms include auctions, voting procedures, and negotiation protocols. A structured operational semantics is provided in terms of extensive games of almost perfect information. Hoare-style partial correctness assertions are proposed to reason about the correctness of these mechanisms, where correctness is interpreted as the existence of a subgame perfect equilibrium. Using an extensional approach to pre- and postconditions, we show that an extension of Hoare's original calculus is sound and complete for reasoning about subgame perfect equilibria in game-theoretic mechanisms.
Risk-Management Methods for the Libor Market Model Using Semidefinite Programming
Venue: arXiv cs.CE 2005
Year: 2005

When interest rate dynamics are described by the Libor Market Model as in BGM97, we show how some essential risk-management results can be obtained from the dual of the calibration program. In particular, if the objetive is to maximize another swaption's price, we show that the optimal dual variables describe a hedging portfolio in the sense of \cite{Avel96}. In the general case, the local sensitivity of the covariance matrix to all market movement scenarios can be directly computed from the optimal dual solution. We also show how semidefinite programming can be used to manage the Gamma exposure of a portfolio.
Optimal Covering Tours with Turn Costs
Venue: arXiv cs.DS 2005
Year: 2005

We give the first algorithmic study of a class of ``covering tour'' problems related to the geometric Traveling Salesman Problem: Find a polygonal tour for a cutter so that it sweeps out a specified region (``pocket''), in order to minimize a cost that depends mainly on the number of em turns. These problems arise naturally in manufacturing applications of computational geometry to automatic tool path generation and automatic inspection systems, as well as arc routing (``postman'') problems with turn penalties. We prove the NP-completeness of minimum-turn milling and give efficient approximation algorithms for several natural versions of the problem, including a polynomial-time approximation scheme based on a novel adaptation of the m-guillotine method.
Threshold values of Random K-SAT from the cavity method
Venue: arXiv cs.CC 2005
Year: 2005

Using the cavity equations of \cite{mezard:parisi:zecchina:02,mezard:zecchina:02}, we derive the various threshold values for the number of clauses per variable of the random $K$-satisfiability problem, generalizing the previous results to $K \ge 4$. We also give an analytic solution of the equations, and some closed expressions for these thresholds, in an expansion around large $K$. The stability of the solution is also computed. For any $K$, the satisfiability threshold is found to be in the stable region of the solution, which adds further credit to the conjecture that this computation gives the exact satisfiability threshold.
Aperiodic Tilings: Breaking Translational Symmetry
Venue: arXiv cs.DM 2005
Year: 2005

Classical results on aperiodic tilings are rather complicated and not widely understood. Below, an alternative approach is discussed in hope to provide additional intuition not apparent in classical works.
Incentive Systems in Multi-Level Markets for Virtual Goods
Venue: arXiv cs.GT 2005
Year: 2005

As an alternative to rigid DRM measures, ways of marketing virtual goods through multi-level or networked marketing have raised some interest. This report is a first approach to multi-level markets for virtual goods from the viewpoint of theoretical economy. A generic, kinematic model for the monetary flow in multi-level markets, which quantitatively describes the incentives that buyers receive through resales revenues, is devised. Building on it, the competition of goods is examined in a dynamical, utility-theoretic model enabling, in particular, a treatment of the free-rider problem. The most important implications for the design of multi-level market mechanisms for virtual goods, or multi-level incentive management systems, are outlined.
Fast Query Processing by Distributing an Index over CPU Caches
Venue: arXiv cs.DC 2005
Year: 2005

Data intensive applications on clusters often require requests quickly be sent to the node managing the desired data. In many applications, one must look through a sorted tree structure to determine the responsible node for accessing or storing the data. Examples include object tracking in sensor networks, packet routing over the internet, request processing in publish-subscribe middleware, and query processing in database systems. When the tree structure is larger than the CPU cache, the standard implementation potentially incurs many cache misses for each lookup; one cache miss at each successive level of the tree. As the CPU-RAM gap grows, this performance degradation will only become worse in the future. We propose a solution that takes advantage of the growing speed of local area networks for clusters. We split the sorted tree structure among the nodes of the cluster. We assume that the structure will fit inside the aggregation of the CPU caches of the entire cluster. We then send a word over the network (as part of a larger packet containing other words) in order to examine the tree structure in another node's CPU cache. We show that this is often faster than the standard solution, which locally incurs multiple cache misses while accessing each successive level of the tree.
Lower-Stretch Spanning Trees
Venue: arXiv cs.DS 2005
Year: 2005

We prove that every weighted graph contains a spanning tree subgraph of average stretch O((log n log log n)^2). Moreover, we show how to construct such a tree in time O(m log^2 n).
On the existence of truly autonomic computing systems and the link with quantum computing
Venue: arXiv cs.LO 2005
Year: 2005

A theoretical model of truly autonomic computing systems (ACS), with infinitely many constraints, is proposed. An argument similar to Turing's for the unsolvability of the halting problem, which is permitted in classical logic, shows that such systems cannot exist. Turing's argument fails in the recently proposed non-Aristotelian finitary logic (NAFL), which permits the existence of ACS. NAFL also justifies quantum superposition and entanglement, which are essential ingredients of quantum algorithms, and resolves the Einstein-Podolsky-Rosen (EPR) paradox in favour of quantum mechanics and non-locality. NAFL requires that the autonomic manager (AM) must be conceptually and architecturally distinct from the managed element, in order for the ACS to exist as a non-self-referential entity. Such a scenario is possible if the AM uses quantum algorithms and is protected from all problems by (unbreakable) quantum encryption, while the managed element remains classical. NAFL supports such a link between autonomic and quantum computing, with the AM existing as a metamathematical entity. NAFL also allows quantum algorithms to access truly random elements and thereby supports non-standard models of quantum (hyper-) computation that permit infinite parallelism.
A Monte Carlo algorithm for efficient large matrix inversion
Venue: arXiv cs.DS 2005
Year: 2005

This paper introduces a new Monte Carlo algorithm to invert large matrices. It is based on simultaneous coupled draws from two random vectors whose covariance is the required inverse. It can be considered a generalization of a previously reported algorithm for hermitian matrices inversion based in only one draw. The use of two draws allows the inversion on non-hermitian matrices. Both the conditions for convergence and the rate of convergence are similar to the Gauss-Seidel algorithm. Results on two examples are presented, a real non-symmetric matrix related to quantitative genetics and a complex non-hermitian matrix relevant for physicists. Compared with other Monte Carlo algorithms it reveals a large reduction of the processing time showing eight times faster processing in the examples studied.
Formal Languages and Algorithms for Similarity based Retrieval from Sequence Databases
Venue: arXiv cs.LO 2005
Year: 2005

The paper considers various formalisms based on Automata, Temporal Logic and Regular Expressions for specifying queries over sequences. Unlike traditional binary semantics, the paper presents a similarity based semantics for thse formalisms. More specifically, a distance measure in the range [0,1] is associated with a sequence, query pair denoting how closely the sequence satisfies the query. These measures are defined using a spectrum of normed vector distance measures. Various distance measures based on the syntax and the traditional semantics of the query are presented. Efficient algorithms for computing these distance measure are presented. These algorithms can be employed for retrieval of sequence from a database that closely satisfy a given.
Application of Generating Functions and Partial Differential Equations in Coding Theory
Venue: arXiv cs.IT 2005
Year: 2005

In this work we have considered formal power series and partial differential equations, and their relationship with Coding Theory. We have obtained the nature of solutions for the partial differential equations for Cycle Poisson Case. The coefficients for this case have been simulated, and the high tendency of growth is shown. In the light of Complex Analysis, the Hadamard Multiplication's Theorem is presented as a new approach to divide the power sums relating to the error probability, each part of which can be analyzed later.
Large-scale lattice Boltzmann simulations of complex fluids: advances through the advent of computational grids
Venue: arXiv cs.DC 2005
Year: 2005

During the last two years the RealityGrid project has allowed us to be one of the few scientific groups involved in the development of computational grids. Since smoothly working production grids are not yet available, we have been able to substantially influence the direction of software development and grid deployment within the project. In this paper we review our results from large scale three-dimensional lattice Boltzmann simulations performed over the last two years. We describe how the proactive use of computational steering and advanced job migration and visualization techniques enabled us to do our scientific work more efficiently. The projects reported on in this paper are studies of complex fluid flows under shear or in porous media, as well as large-scale parameter searches, and studies of the self-organisation of liquid cubic mesophases. Movies are available at http://www.ica1.uni-stuttgart.de/~jens/pub/05/05-PhilTransReview.html
Symmetry and interactivity in Programming
Venue: arXiv cs.LO 2005
Year: 2005

We recall some of the early occurrences of the notions of interactivity and symmetry in the operational and denotational semantics of programming languages. We suggest some connections with ludics.
Oligopolistic Competition in an Evolutionary Environment: a Computer Simulation
Venue: arXiv cs.CY 2005
Year: 2005

The following notes contain a computer simulation concerning effective competition in an evolutionary environment. The scope is to underline the existence of a side effect pertaining to the competitive processes: the tendency toward an excess of supply by producers which operate in a strongly competitive situation. A set of four oligopolistic firms will be employed in the formal reconstruction. The simulation will operate following the Edmond Malinvaud "short side" approach, as far as the price adjustment is concerned, and the sequential Hicksian "weeks" structure with regard of the temporal characterization. The content of the present paper ought to be considered as a development of the writing: Michele Tucci, Evolution and Gravitation: a Computer Simulation of a Non-Walrasian Equilibrium Model, published with the E-print Archives at arXiv.com (section: Computer Science, registration number: cs.CY/0209017). In such a paper there can be found some preliminary considerations regarding the comparison between the evolutionary and the gravitational paradigms and the evaluation of approaches belonging to rival schools of economic thought.
Data Tastes Better Seasoned: Introducing the ASH Family of Hashing Algorithms
Venue: arXiv cs.CR 2005
Year: 2005

Over the recent months it has become clear that the current generation of cryptographic hashing algorithms are insufficient to meet future needs. The ASH family of algorithms provides modifications to the existing SHA-2 family. These modifications are designed with two main goals: 1) Providing increased collision resistance. 2) Increasing mitigation of security risks post-collision. The unique public/private sections and salt/pepper design elements provide increased flexibility for a broad range of applications. The ASH family is a new generation of cryptographic hashing algorithms.
Low Complexity Joint Iterative Equalization and Multiuser Detection in Dispersive DS-CDMA Channels
Venue: arXiv cs.IT 2005
Year: 2005

Communications in dispersive direct-sequence code-division multiple-access (DS-CDMA) channels suffer from intersymbol and multiple-access interference, which can significantly impair performance. Joint maximum \textit{a posteriori} probability (MAP) equalization and multiuser detection with error control decoding can be used to mitigate this interference and to achieve the optimal bit error rate. Unfortunately, such optimal detection typically requires prohibitive computational complexity. This problem is addressed in this paper through the development of a reduced state trellis search detection algorithm, based on decision feedback from channel decoders. The performance of this algorithm is analyzed in the large-system limit. This analysis and simulations show that this low-complexity algorithm can obtain near-optimal performance under moderate signal-to-noise ratio and attains larger system load capacity than parallel interference cancellation.
Performance Evaluation of Impulse Radio UWB Systems with Pulse-Based Polarity Randomization
Venue: arXiv cs.IT 2005
Year: 2005

In this paper, the performance of a binary phase shift keyed random time-hopping impulse radio system with pulse-based polarity randomization is analyzed. Transmission over frequency-selective channels is considered and the effects of inter-frame interference and multiple access interference on the performance of a generic Rake receiver are investigated for both synchronous and asynchronous systems. Closed form (approximate) expressions for the probability of error that are valid for various Rake combining schemes are derived. The asynchronous system is modelled as a chip-synchronous system with uniformly distributed timing jitter for the transmitted pulses of interfering users. This model allows the analytical technique developed for the synchronous case to be extended to the asynchronous case. An approximate closed-form expression for the probability of bit error, expressed in terms of the autocorrelation function of the transmitted pulse, is derived for the asynchronous case. Then, transmission over an additive white Gaussian noise channel is studied as a special case, and the effects of multiple-access interference is investigated for both synchronous and asynchronous systems. The analysis shows that the chip-synchronous assumption can result in over-estimating the error probability, and the degree of over-estimation mainly depends on the autocorrelation function of the ultra-wideband pulse and the signal-to-interference-plus-noise-ratio of the system. Simulations studies support the approximate analysis.
On the Capacity of Multiple Antenna Systems in Rician Fading
Venue: arXiv cs.IT 2005
Year: 2005

The effect of Rician-ness on the capacity of multiple antenna systems is investigated under the assumption that channel state information (CSI) is available only at the receiver. The average-power-constrained capacity of such systems is considered under two different assumptions on the knowledge about the fading available at the transmitter: the case in which the transmitter has no knowledge of fading at all, and the case in which the transmitter has knowledge of the distribution of the fading process but not the instantaneous CSI. The exact capacity is given for the former case while capacity bounds are derived for the latter case. A new signalling scheme is also proposed for the latter case and it is shown that by exploiting the knowledge of Rician-ness at the transmitter via this signalling scheme, significant capacity gain can be achieved. The derived capacity bounds are evaluated explicitly to provide numerical results in some representative situations.
Arbitrage in Fractal Modulated Markets When the Volatility is Stochastic
Venue: arXiv cs.IT 2005
Year: 2005

In this paper an arbitrage strategy is constructed for the modified Black-Scholes model driven by fractional Brownian motion or by a time changed fractional Brownian motion, when the volatility is stochastic. This latter property allows the heavy tailedness of the log returns of the stock prices to be also accounted for in addition to the long range dependence introduced by the fractional Brownian motion. Work has been done previously on this problem for the case with constant `volatility' and without a time change; here these results are extended to the case of stochastic volatility models when the modulator is fractional Brownian motion or a time change of it. (Volatility in fractional Black-Scholes models does not carry the same meaning as in the classic Black-Scholes framework, which is made clear in the text.) Since fractional Brownian motion is not a semi-martingale, the Black-Scholes differential equation is not well-defined sense for arbitrary predictable volatility processes. However, it is shown here that any almost surely continuous and adapted process having zero quadratic variation can act as an integrator over functions of the integrator and over the family of continuous adapted semi-martingales. Moreover it is shown that the integral also has zero quadratic variation, and therefore that the integral itself can be an integrator. This property of the integral is crucial in developing the arbitrage strategy. Since fractional Brownian motion and a time change of fractional Brownian motion have zero quadratic variation, these results are applicable to these cases in particular. The appropriateness of fractional Brownian motion as a means of modeling stock price returns is discussed as well.
Consistency Problems for Jump-Diffusion Models
Venue: arXiv cs.IT 2005
Year: 2005

In this paper consistency problems for multi-factor jump-diffusion models, where the jump parts follow multivariate point processes are examined. First the gap between jump-diffusion models and generalized Heath-Jarrow-Morton (HJM) models is bridged. By applying the drift condition for a generalized arbitrage-free HJM model, the consistency condition for jump-diffusion models is derived. Then we consider a case in which the forward rate curve has a separable structure, and obtain a specific version of the general consistency condition. In particular, a necessary and sufficient condition for a jump-diffusion model to be affine is provided. Finally the Nelson-Siegel type of forward curve structures is discussed. It is demonstrated that under regularity condition, there exists no jump-diffusion model consistent with the Nelson-Siegel curves.
Data Mining for Actionable Knowledge: A Survey
Venue: arXiv cs.DB 2005
Year: 2005

The data mining process consists of a series of steps ranging from data cleaning, data selection and transformation, to pattern evaluation and visualization. One of the central problems in data mining is to make the mined patterns or knowledge actionable. Here, the term actionable refers to the mined patterns suggest concrete and profitable actions to the decision-maker. That is, the user can do something to bring direct benefits (increase in profits, reduction in cost, improvement in efficiency, etc.) to the organization's advantage. However, there has been written no comprehensive survey available on this topic. The goal of this paper is to fill the void. In this paper, we first present two frameworks for mining actionable knowledge that are inexplicitly adopted by existing research methods. Then we try to situate some of the research on this topic from two different viewpoints: 1) data mining tasks and 2) adopted framework. Finally, we specify issues that are either not addressed or insufficiently studied yet and conclude the paper.