OpenRaiser/Intern-Atlas huggingface dataset:
Orchestrating Metadata Enhancement Services: Introducing Lenny
Venue: arXiv cs.DL 2005
Year: 2005

Harvested metadata often suffers from uneven quality to the point that utility is compromised. Although some aggregators have developed methods for evaluating and repairing specific metadata problems, it has been unclear how these methods might be scaled into services that can be used within an automated production environment. The National Science Digital Library (NSDL), as part of its work with INFOMINE, has developed a model of ser-vice interaction that enables loosely-coupled third party services to provide metadata enhancements to a central repository, with interactions orchestrated by a centralized software application.
Towards Automated Integration of Guess and Check Programs in Answer Set Programming: A Meta-Interpreter and Applications
Venue: arXiv cs.AI 2005
Year: 2005

Answer set programming (ASP) with disjunction offers a powerful tool for declaratively representing and solving hard problems. Many NP-complete problems can be encoded in the answer set semantics of logic programs in a very concise and intuitive way, where the encoding reflects the typical "guess and check" nature of NP problems: The property is encoded in a way such that polynomial size certificates for it correspond to stable models of a program. However, the problem-solving capacity of full disjunctive logic programs (DLPs) is beyond NP, and captures a class of problems at the second level of the polynomial hierarchy. While these problems also have a clear "guess and check" structure, finding an encoding in a DLP reflecting this structure may sometimes be a non-obvious task, in particular if the "check" itself is a coNP-complete problem; usually, such problems are solved by interleaving separate guess and check programs, where the check is expressed by inconsistency of the check program. In this paper, we present general transformations of head-cycle free (extended) disjunctive logic programs into stratified and positive (extended) disjunctive logic programs based on meta-interpretation techniques. The answer sets of the original and the transformed program are in simple correspondence, and, moreover, inconsistency of the original program is indicated by a designated answer set of the transformed program. Our transformations facilitate the integration of separate "guess" and "check" programs, which are often easy to obtain, automatically into a single disjunctive logic program. Our results complement recent results on meta-interpretation in ASP, and extend methods and techniques for a declarative "guess and check" problem solving paradigm through ASP.
Information estimations and analysis of structures
Venue: arXiv cs.IT 2005
Year: 2005

In this paper have written the results of the information analysis of structures. The obtained information estimation (IE) are based on an entropy measure of C. Shannon. Obtained IE is univalent both for the non-isomorphic and for the isomorphic graphs, algorithmically, it is asymptotically steady and has vector character. IE can be used for the solution of the problems ranking of structures by the preference, the evaluation of the structurization of subject area, the solution of the problems of structural optimization. Information estimations and method of the information analysis of structures it can be used in many fields of knowledge (Electrical Systems and Circuit, Image recognition, Computer technology, Databases and Bases of knowledge, Organic chemistry, Biology and others) and it can be base for the structure calculus.
Issues in Exploiting GermaNet as a Resource in Real Applications
Venue: arXiv cs.AI 2005
Year: 2005

This paper reports about experiments with GermaNet as a resource within domain specific document analysis. The main question to be answered is: How is the coverage of GermaNet in a specific domain? We report about results of a field test of GermaNet for analyses of autopsy protocols and present a sketch about the integration of GermaNet inside XDOC. Our remarks will contribute to a GermaNet user's wish list.
Multi-Vehicle Cooperative Control Using Mixed Integer Linear Programming
Venue: arXiv cs.RO 2005
Year: 2005

We present methods to synthesize cooperative strategies for multi-vehicle control problems using mixed integer linear programming. Complex multi-vehicle control problems are expressed as mixed logical dynamical systems. Optimal strategies for these systems are then solved for using mixed integer linear programming. We motivate the methods on problems derived from an adversarial game between two teams of robots called RoboFlag. We assume the strategy for one team is fixed and governed by state machines. The strategy for the other team is generated using our methods. Finally, we perform an average case computational complexity study on our approach.
Shawn: A new approach to simulating wireless sensor networks
Venue: arXiv cs.DC 2005
Year: 2005

We consider the simulation of wireless sensor networks (WSN) using a new approach. We present Shawn, an open-source discrete-event simulator that has considerable differences to all other existing simulators. Shawn is very powerful in simulating large scale networks with an abstract point of view. It is, to the best of our knowledge, the first simulator to support generic high-level algorithms as well as distributed protocols on exactly the same underlying networks.
Asymptotic Log-loss of Prequential Maximum Likelihood Codes
Venue: arXiv cs.LG 2005
Year: 2005

We analyze the Dawid-Rissanen prequential maximum likelihood codes relative to one-parameter exponential family models M. If data are i.i.d. according to an (essentially) arbitrary P, then the redundancy grows at rate c/2 ln n. We show that c=v1/v2, where v1 is the variance of P, and v2 is the variance of the distribution m* in M that is closest to P in KL divergence. This shows that prequential codes behave quite differently from other important universal codes such as the 2-part MDL, Shtarkov and Bayes codes, for which c=1. This behavior is undesirable in an MDL model selection setting.
Amazons is PSPACE-complete
Venue: arXiv cs.CC 2005
Year: 2005

Amazons is a board game which combines elements of Chess and Go. It has become popular in recent years, and has served as a useful platform for both game-theoretic study and AI games research. Buro showed that simple Amazons endgames are NP-equivalent, leaving the complexity of the general case as an open problem. We settle this problem, by showing that deciding the outcome of an n x n Amazons position is PSPACE-hard. We give a reduction from one of the PSPACE-complete two-player formula games described by Schaefer. Since the number of moves in an Amazons game is polynomially bounded (unlike Chess and Go), Amazons is in PSPACE. It is thus on a par with other two-player, bounded-move, perfect-information games such as Hex, Othello, and Kayles. Our construction also provides an alternate proof that simple Amazons endgames are NP-equivalent. Our reduction uses a number of amazons polynomial in the input formula length; a remaining open problem is the complexity of Amazons when only a constant number of amazons is used.
When Database Systems Meet the Grid
Venue: arXiv cs.DC 2005
Year: 2005

We illustrate the benefits of combining database systems and Grid technologies for data-intensive applications. Using a cluster of SQL servers, we reimplemented an existing Grid application that finds galaxy clusters in a large astronomical database. The SQL implementation runs an order of magnitude faster than the earlier Tcl-C-file-based implementation. We discuss why and how Grid applications can take advantage of database systems.
Logic Column 11: The Finite and the Infinite in Temporal Logic
Venue: arXiv cs.LO 2005
Year: 2005

This article examines the interpretation of the LTL temporal operators over finite and infinite sequences. This is used as the basis for deriving a sound and complete axiomatization for Caret, a recent temporal logic for reasoning about programs with nested procedure calls and returns.
Pseudo-Codewords of Cycle Codes via Zeta Functions
Venue: arXiv cs.IT 2005
Year: 2005

Cycle codes are a special case of low-density parity-check (LDPC) codes and as such can be decoded using an iterative message-passing decoding algorithm on the associated Tanner graph. The existence of pseudo-codewords is known to cause the decoding algorithm to fail in certain instances. In this paper, we draw a connection between pseudo-codewords of cycle codes and the so-called edge zeta function of the associated normal graph and show how the Newton polyhedron of the zeta function equals the fundamental cone of the code, which plays a crucial role in characterizing the performance of iterative decoding algorithms.
Improved Iterative Decoding for Perpendicular Magnetic Recording
Venue: arXiv cs.IT 2005
Year: 2005

An algorithm of improving the performance of iterative decoding on perpendicular magnetic recording is presented. This algorithm follows on the authors' previous works on the parallel and serial concatenated turbo codes and low-density parity-check codes. The application of this algorithm with signal-to-noise ratio mismatch technique shows promising results in the presence of media noise. We also show that, compare to the standard iterative decoding algorithm, an improvement of within one order of magnitude can be achieved.
Unified Large System Analysis of MMSE and Adaptive Least Squares Receivers for a class of Random Matrix Channels
Venue: arXiv cs.IT 2005
Year: 2005

We present a unified large system analysis of linear receivers for a class of random matrix channels. The technique unifies the analysis of both the minimum-mean-squared-error (MMSE) receiver and the adaptive least-squares (ALS) receiver, and also uses a common approach for both random i.i.d. and random orthogonal precoding. We derive expressions for the asymptotic signal-to-interference-plus-noise (SINR) of the MMSE receiver, and both the transient and steady-state SINR of the ALS receiver, trained using either i.i.d. data sequences or orthogonal training sequences. The results are in terms of key system parameters, and allow for arbitrary distributions of the power of each of the data streams and the eigenvalues of the channel correlation matrix. In the case of the ALS receiver, we allow a diagonal loading constant and an arbitrary data windowing function. For i.i.d. training sequences and no diagonal loading, we give a fundamental relationship between the transient/steady-state SINR of the ALS and the MMSE receivers. We demonstrate that for a particular ratio of receive to transmit dimensions and window shape, all channels which have the same MMSE SINR have an identical transient ALS SINR response. We demonstrate several applications of the results, including an optimization of information throughput with respect to training sequence length in coded block transmission.
On quasi-cyclic interleavers for parallel turbo codes
Venue: arXiv cs.IT 2005
Year: 2005

We present an interleaving scheme that yields quasi-cyclic turbo codes. We prove that randomly chosen members of this family yield with probability almost 1 turbo codes with asymptotically optimum minimum distance, i.e. growing as a logarithm of the interleaver size. These interleavers are also very practical in terms of memory requirements and their decoding error probabilities for small block lengths compare favorably with previous interleaving schemes.
Co-Authorship Networks in the Digital Library Research Community
Venue: arXiv cs.DL 2005
Year: 2005

The field of digital libraries (DLs) coalesced in 1994: the first digital library conferences were held that year, awareness of the World Wide Web was accelerating, and the National Science Foundation awarded $24 Million (U.S.) for the Digital Library Initiative (DLI). In this paper we examine the state of the DL domain after a decade of activity by applying social network analysis to the co-authorship network of the past ACM, IEEE, and joint ACM/IEEE digital library conferences. We base our analysis on a common binary undirectional network model to represent the co-authorship network, and from it we extract several established network measures. We also introduce a weighted directional network model to represent the co-authorship network, for which we define $AuthorRank$ as an indicator of the impact of an individual author in the network. The results are validated against conference program committee members in the same period. The results show clear advantages of PageRank and AuthorRank over degree, closeness and betweenness centrality metrics. We also investigate the amount and nature of international participation in Joint Conference on Digital Libraries (JCDL).
Tree Parity Machine Rekeying Architectures
Venue: arXiv cs.CR 2005
Year: 2005

The necessity to secure the communication between hardware components in embedded systems becomes increasingly important with regard to the secrecy of data and particularly its commercial use. We suggest a low-cost (i.e. small logic-area) solution for flexible security levels and short key lifetimes. The basis is an approach for symmetric key exchange using the synchronisation of Tree Parity Machines. Fast successive key generation enables a key exchange within a few milliseconds, given realistic communication channels with a limited bandwidth. For demonstration we evaluate characteristics of a standard-cell ASIC design realisation as IP-core in 0.18-micrometer CMOS-technology.
Bidimensionality, Map Graphs, and Grid Minors
Venue: arXiv cs.DM 2005
Year: 2005

In this paper we extend the theory of bidimensionality to two families of graphs that do not exclude fixed minors: map graphs and power graphs. In both cases we prove a polynomial relation between the treewidth of a graph in the family and the size of the largest grid minor. These bounds improve the running times of a broad class of fixed-parameter algorithms. Our novel technique of using approximate max-min relations between treewidth and size of grid minors is powerful, and we show how it can also be used, e.g., to prove a linear relation between the treewidth of a bounded-genus graph and the treewidth of its dual.
A note on the Burrows-Wheeler transformation
Venue: arXiv cs.DS 2005
Year: 2005

We relate the Burrows-Wheeler transformation with a result in combinatorics on words known as the Gessel-Reutenauer transformation.
On sample complexity for computational pattern recognition
Venue: arXiv cs.LG 2005
Year: 2005

In statistical setting of the pattern recognition problem the number of examples required to approximate an unknown labelling function is linear in the VC dimension of the target learning class. In this work we consider the question whether such bounds exist if we restrict our attention to computable pattern recognition methods, assuming that the unknown labelling function is also computable. We find that in this case the number of examples required for a computable method to approximate the labelling function not only is not linear, but grows faster (in the VC dimension of the class) than any computable function. No time or space constraints are put on the predictors or target functions; the only resource we consider is the training examples. The task of pattern recognition is considered in conjunction with another learning problem -- data compression. An impossibility result for the task of data compression allows us to estimate the sample complexity for pattern recognition.
How far will you walk to find your shortcut: Space Efficient Synopsis Construction Algorithms
Venue: arXiv cs.DS 2005
Year: 2005

In this paper we consider the wavelet synopsis construction problem without the restriction that we only choose a subset of coefficients of the original data. We provide the first near optimal algorithm. We arrive at the above algorithm by considering space efficient algorithms for the restricted version of the problem. In this context we improve previous algorithms by almost a linear factor and reduce the required space to almost linear. Our techniques also extend to histogram construction, and improve the space-running time tradeoffs for V-Opt and range query histograms. We believe the idea applies to a broad range of dynamic programs and demonstrate it by showing improvements in a knapsack-like setting seen in construction of Extended Wavelets.
A New Non-Iterative Decoding Algorithm for the Erasure Channel : Comparisons with Enhanced Iterative Methods
Venue: arXiv cs.IT 2005
Year: 2005

This paper investigates decoding of binary linear block codes over the binary erasure channel (BEC). Of the current iterative decoding algorithms on this channel, we review the Recovery Algorithm and the Guess Algorithm. We then present a Multi-Guess Algorithm extended from the Guess Algorithm and a new algorithm -- the In-place Algorithm. The Multi-Guess Algorithm can push the limit to break the stopping sets. However, the performance of the Guess and the Multi-Guess Algorithm depend on the parity-check matrix of the code. Simulations show that we can decrease the frame error rate by several orders of magnitude using the Guess and the Multi-Guess Algorithms when the parity-check matrix of the code is sparse. The In-place Algorithm can obtain better performance even if the parity check matrix is dense. We consider the application of these algorithms in the implementation of multicast and broadcast techniques on the Internet. Using these algorithms, a user does not have to wait until the entire transmission has been received.
First-order Complete and Computationally Complete Query Languages for Spatio-Temporal Databases
Venue: arXiv cs.DB 2005
Year: 2005

We address a fundamental question concerning spatio-temporal database systems: ``What are exactly spatio-temporal queries?'' We define spatio-temporal queries to be computable mappings that are also generic, meaning that the result of a query may only depend to a limited extent on the actual internal representation of the spatio-temporal data. Genericity is defined as invariance under groups of geometric transformations that preserve certain characteristics of spatio-temporal data (e.g., collinearity, distance, velocity, acceleration, ...). These groups depend on the notions that are relevant in particular spatio-temporal database applications. These transformations also have the distinctive property that they respect the monotone and unidirectional nature of time. We investigate different genericity classes with respect to the constraint database model for spatio-temporal databases and we identify sound and complete languages for the first-order and the computable queries in these genericity classes. We distinguish between genericity determined by time-invariant transformations, genericity notions concerning physical quantities and genericity determined by time-dependent transformations.
File-based storage of Digital Objects and constituent datastreams: XMLtapes and Internet Archive ARC files
Venue: arXiv cs.DL 2005
Year: 2005

This paper introduces the write-once/read-many XMLtape/ARC storage approach for Digital Objects and their constituent datastreams. The approach combines two interconnected file-based storage mechanisms that are made accessible in a protocol-based manner. First, XML-based representations of multiple Digital Objects are concatenated into a single file named an XMLtape. An XMLtape is a valid XML file; its format definition is independent of the choice of the XML-based complex object format by which Digital Objects are represented. The creation of indexes for both the identifier and the creation datetime of the XML-based representation of the Digital Objects facilitates OAI-PMH-based access to Digital Objects stored in an XMLtape. Second, ARC files, as introduced by the Internet Archive, are used to contain the constituent datastreams of the Digital Objects in a concatenated manner. An index for the identifier of the datastream facilitates OpenURL-based access to an ARC file. The interconnection between XMLtapes and ARC files is provided by conveying the identifiers of ARC files associated with an XMLtape as administrative information in the XMLtape, and by including OpenURL references to constituent datastreams of a Digital Object in the XML-based representation of that Digital Object.
Earlier Web Usage Statistics as Predictors of Later Citation Impact
Venue: arXiv cs.IR 2005
Year: 2005

The use of citation counts to assess the impact of research articles is well established. However, the citation impact of an article can only be measured several years after it has been published. As research articles are increasingly accessed through the Web, the number of times an article is downloaded can be instantly recorded and counted. One would expect the number of times an article is read to be related both to the number of times it is cited and to how old the article is. This paper analyses how short-term Web usage impact predicts medium-term citation impact. The physics e-print archive (arXiv.org) is used to test this.
The Weighted Maximum-Mean Subtree and Other Bicriterion Subtree Problems
Venue: arXiv cs.CG 2005
Year: 2005

We consider problems in which we are given a rooted tree as input, and must find a subtree with the same root, optimizing some objective function of the nodes in the subtree. When this function is the sum of constant node weights, the problem is trivially solved in linear time. When the objective is the sum of weights that are linear functions of a parameter, we show how to list all optima for all possible parameter values in O(n log n) time; this parametric optimization problem can be used to solve many bicriterion optimizations problems, in which each node has two values xi and yi associated with it, and the objective function is a bivariate function f(SUM(xi),SUM(yi)) of the sums of these two values. A special case, when f is the ratio of the two sums, is the Weighted Maximum-Mean Subtree Problem, or equivalently the Fractional Prize-Collecting Steiner Tree Problem on Trees; for this special case, we provide a linear time algorithm for this problem when all weights are positive, improving a previous O(n log n) solution, and prove that the problem is NP-complete when negative weights are allowed.
A Taxonomy of Workflow Management Systems for Grid Computing
Venue: arXiv cs.DC 2005
Year: 2005

With the advent of Grid and application technologies, scientists and engineers are building more and more complex applications to manage and process large data sets, and execute scientific experiments on distributed resources. Such application scenarios require means for composing and executing complex workflows. Therefore, many efforts have been made towards the development of workflow management systems for Grid computing. In this paper, we propose a taxonomy that characterizes and classifies various approaches for building and executing workflows on Grids. We also survey several representative Grid workflow systems developed by various projects world-wide to demonstrate the comprehensiveness of the taxonomy. The taxonomy not only highlights the design and engineering similarities and differences of state-of-the-art in Grid workflow systems, but also identifies the areas that need further research.
An Introduction to the Summarization of Evolving Events: Linear and Non-linear Evolution
Venue: arXiv cs.CL 2005
Year: 2005

This paper examines the summarization of events that evolve through time. It discusses different types of evolution taking into account the time in which the incidents of an event are happening and the different sources reporting on the specific event. It proposes an approach for multi-document summarization which employs ``messages'' for representing the incidents of an event and cross-document relations that hold between messages according to certain conditions. The paper also outlines the current version of the summarization system we are implementing to realize this approach.