OpenRaiser/Intern-Atlas huggingface dataset:
A Deadline and Budget Constrained Cost-Time Optimisation Algorithm for Scheduling Task Farming Applications on Global Grids
Venue: arXiv cs.DC 2002
Year: 2002

Computational Grids and peer-to-peer (P2P) networks enable the sharing, selection, and aggregation of geographically distributed resources for solving large-scale problems in science, engineering, and commerce. The management and composition of resources and services for scheduling applications, however, becomes a complex undertaking. We have proposed a computational economy framework for regulating the supply and demand for resources and allocating them for applications based on the users quality of services requirements. The framework requires economy driven deadline and budget constrained (DBC) scheduling algorithms for allocating resources to application jobs in such a way that the users requirements are met. In this paper, we propose a new scheduling algorithm, called DBC cost-time optimisation, which extends the DBC cost-optimisation algorithm to optimise for time, keeping the cost of computation at the minimum. The superiority of this new scheduling algorithm, in achieving lower job completion time, is demonstrated by simulating the World-Wide Grid and scheduling task-farming applications for different deadline and budget scenarios using both this new and the cost optimisation scheduling algorithms.
NetNeg: A Connectionist-Agent Integrated System for Representing Musical Knowledge
Venue: arXiv cs.AI 2002
Year: 2002

The system presented here shows the feasibility of modeling the knowledge involved in a complex musical activity by integrating sub-symbolic and symbolic processes. This research focuses on the question of whether there is any advantage in integrating a neural network together with a distributed artificial intelligence approach within the music domain. The primary purpose of our work is to design a model that describes the different aspects a user might be interested in considering when involved in a musical activity. The approach we suggest in this work enables the musician to encode his knowledge, intuitions, and aesthetic taste into different modules. The system captures these aspects by computing and applying three distinct functions: rules, fuzzy concepts, and learning. As a case study, we began experimenting with first species two-part counterpoint melodies. We have developed a hybrid system composed of a connectionist module and an agent-based module to combine the sub-symbolic and symbolic levels to achieve this task. The technique presented here to represent musical knowledge constitutes a new approach for composing polyphonic music.
Agent trade servers in financial exchange systems
Venue: arXiv cs.CE 2002
Year: 2002

New services based on the best-effort paradigm could complement the current deterministic services of an electronic financial exchange. Four crucial aspects of such systems would benefit from a hybrid stance: proper use of processing resources, bandwidth management, fault tolerance, and exception handling. We argue that a more refined view on Quality-of-Service control for exchange systems, in which the principal ambition of upholding a fair and orderly marketplace is left uncompromised, would benefit all interested parties.
An Integrated Framework for Treebanks and Multilayer Annotations
Venue: arXiv cs.CL 2002
Year: 2002

Treebank formats and associated software tools are proliferating rapidly, with little consideration for interoperability. We survey a wide variety of treebank structures and operations, and show how they can be mapped onto the annotation graph model, and leading to an integrated framework encompassing tree and non-tree annotations alike. This development opens up new possibilities for managing and exploiting multilayer annotations.
An Assessment of the Consistency for Software Measurement Methods
Venue: arXiv cs.SE 2002
Year: 2002

Consistency, defined as the requirement that a series of measurements of the same project carried out by different raters using the same method should produce similar results, is one of the most important aspects to be taken into account in the measurement methods of the software. In spite of this, there is a widespread view that many measurement methods introduce an undesirable amount of subjectivity in the measurement process. This perception has made several organizations develop revisions of the standard methods whose main aim is to improve their consistency by introducing some suitable modifications of those aspects which are believed to introduce a greater degree of subjectivity.Each revision of a method must be empirically evaluated to determine to what extent is the aim of improving its consistency achieved. In this article we will define an homogeneous statistic intended to describe the consistency level of a method, and we will develop the statistical analysis which should be carried out in order to conclude whether or not a measurement method is more consistent than other one.
Seven Dimensions of Portability for Language Documentation and Description
Venue: arXiv cs.CL 2002
Year: 2002

The process of documenting and describing the world's languages is undergoing radical transformation with the rapid uptake of new digital technologies for capture, storage, annotation and dissemination. However, uncritical adoption of new tools and technologies is leading to resources that are difficult to reuse and which are less portable than the conventional printed resources they replace. We begin by reviewing current uses of software tools and digital technologies for language documentation and description. This sheds light on how digital language documentation and description are created and managed, leading to an analysis of seven portability problems under the following headings: content, format, discovery, access, citation, preservation and rights. After characterizing each problem we provide a series of value statements, and this provides the framework for a broad range of best practice recommendations.
Randomized selection revisited
Venue: arXiv cs.DS 2002
Year: 2002

We show that several versions of Floyd and Rivest's algorithm Select for finding the $k$th smallest of $n$ elements require at most $n+\min\{k,n-k\}+o(n)$ comparisons on average and with high probability. This rectifies the analysis of Floyd and Rivest, and extends it to the case of nondistinct elements. Our computational results confirm that Select may be the best algorithm in practice.
Technology For Information Engineering (TIE): A New Way of Storing, Retrieving and Analyzing Information
Venue: arXiv cs.DB 2002
Year: 2002

The theoretical foundations of a new model and paradigm (called TIE) for data storage and access are introduced. Associations between data elements are stored in a single Matrix table, which is usually kept entirely in RAM for quick access. The model ties together a very intuitive "guided" GUI to the Matrix structure, allowing extremely easy complex searches through the data. Although it is an "Associative Model" in that it stores the data associations separately from the data itself, in contrast to other implementations of that model TIE guides the user to only the available information ensuring that every search is always fruitful. Very many diverse applications of the technology are reviewed.
Precongruence Formats for Decorated Trace Semantics
Venue: arXiv cs.LO 2002
Year: 2002

This paper explores the connection between semantic equivalences and preorders for concrete sequential processes, represented by means of labelled transition systems, and formats of transition system specifications using Plotkin's structural approach. For several preorders in the linear time - branching time spectrum a format is given, as general as possible, such that this preorder is a precongruence for all operators specifiable in that format. The formats are derived using the modal characterizations of the corresponding preorders.
Preprocessing Chains for Fast Dihedral Rotations Is Hard or Even Impossible
Venue: arXiv cs.CG 2002
Year: 2002

We examine a computational geometric problem concerning the structure of polymers. We model a polymer as a polygonal chain in three dimensions. Each edge splits the polymer into two subchains, and a dihedral rotation rotates one of these chains rigidly about this edge. The problem is to determine, given a chain, an edge, and an angle of rotation, if the motion can be performed without causing the chain to self-intersect. An Omega(n log n) lower bound on the time complexity of this problem is known. We prove that preprocessing a chain of n edges and answering n dihedral rotation queries is 3SUM-hard, giving strong evidence that solving n queries requires Omega(n^2) time in the worst case. For dynamic queries, which also modify the chain if the requested dihedral rotation is feasible, we show that answering n queries is by itself 3SUM-hard, suggesting that sublinear query time is impossible after any amount of preprocessing.
Optimal Aggregation Algorithms for Middleware
Venue: arXiv cs.DB 2002
Year: 2002

Let D be a database of N objects where each object has m fields. The objects are given in m sorted lists (where the ith list is sorted according to the ith field). Our goal is to find the top k objects according to a monotone aggregation function t, while minimizing access to the lists. The problem arises in several contexts. In particular Fagin (JCSS 1999) considered it for the purpose of aggregating information in a multimedia database system. We are interested in instance optimality, i.e. that our algorithm will be as good as any other (correct) algorithm on any instance. We provide and analyze several instance optimal algorithms for the task, with various access costs and models.
Weaves: A Novel Direct Code Execution Interface for Parallel High Performance Scientific Codes
Venue: arXiv cs.DC 2002
Year: 2002

Scientific codes are increasingly being used in compositional settings, especially problem solving environments (PSEs). Typical compositional modeling frameworks require significant buy-in, in the form of commitment to a particular style of programming (e.g., distributed object components). While this solution is feasible for newer generations of component-based scientific codes, large legacy code bases present a veritable software engineering nightmare. We introduce Weaves a novel framework that enables modeling, composition, direct code execution, performance characterization, adaptation, and control of unmodified high performance scientific codes. Weaves is an efficient generalized framework for parallel compositional modeling that is a proper superset of the threads and processes models of programming. In this paper, our focus is on the transparent code execution interface enabled by Weaves. We identify design constraints, their impact on implementation alternatives, configuration scenarios, and present results from a prototype implementation on Intel x86 architectures.
Improved Bicriteria Existence Theorems for Scheduling
Venue: arXiv cs.DS 2002
Year: 2002

Two common objectives for evaluating a schedule are the makespan, or schedule length, and the average completion time. This short note gives improved bounds on the existence of schedules that simultaneously optimize both criteria. In particular, for any rho> 0, there exists a schedule of makespan at most 1+rho times the minimum, with average completion time at most (1-e)^rho times the minimum. The proof uses an infininite-dimensional linear program to generalize and strengthen a previous analysis by Cliff Stein and Joel Wein (1997).
Approximate Data Structures with Applications
Venue: arXiv cs.DS 2002
Year: 2002

This paper explores the notion of approximate data structures, which return approximately correct answers to queries, but run faster than their exact counterparts. The paper describes approximate variants of the van Emde Boas data structure, which support the same dynamic operations as the standard van Emde Boas data structure (min, max, successor, predecessor, and existence queries, as well as insertion and deletion), except that answers to queries are approximate. The variants support all operations in constant time provided the performance guarantee is 1+1/polylog(n), and in O(loglogn) time provided the performance guarantee is 1+1/polynomial(n), for n elements in the data structure. Applications described include Prim's minimum-spanning-tree algorithm, Dijkstra's single-source shortest paths algorithm, and an on-line variant of Graham's convex hull algorithm. To obtain output which approximates the desired output with the performance guarantee tending to 1, Prim's algorithm requires only linear time, Dijkstra's algorithm requires O(mloglogn) time, and the on-line variant of Graham's algorithm requires constant amortized time per operation.
Typed Generic Traversal With Term Rewriting Strategies
Venue: arXiv cs.PL 2002
Year: 2002

A typed model of strategic term rewriting is developed. The key innovation is that generic traversal is covered. To this end, we define a typed rewriting calculus S'_{gamma}. The calculus employs a many-sorted type system extended by designated generic strategy types gamma. We consider two generic strategy types, namely the types of type-preserving and type-unifying strategies. S'_{gamma} offers traversal combinators to construct traversals or schemes thereof from many-sorted and generic strategies. The traversal combinators model different forms of one-step traversal, that is, they process the immediate subterms of a given term without anticipating any scheme of recursion into terms. To inhabit generic types, we need to add a fundamental combinator to lift a many-sorted strategy $s$ to a generic type gamma. This step is called strategy extension. The semantics of the corresponding combinator states that s is only applied if the type of the term at hand fits, otherwise the extended strategy fails. This approach dictates that the semantics of strategy application must be type-dependent to a certain extent. Typed strategic term rewriting with coverage of generic term traversal is a simple but expressive model of generic programming. It has applications in program transformation and program analysis.
A (non)static 0-order statistical model and its implementation for compressing virtually uncompressible data
Venue: arXiv cs.DS 2002
Year: 2002

We give an implementation of a statistical model, which can be successfully applied for compressing of a sequence of binary digits with behavior close to random.
Sequential and Parallel Algorithms for Mixed Packing and Covering
Venue: arXiv cs.DS 2002
Year: 2002

Mixed packing and covering problems are problems that can be formulated as linear programs using only non-negative coefficients. Examples include multicommodity network flow, the Held-Karp lower bound on TSP, fractional relaxations of set cover, bin-packing, knapsack, scheduling problems, minimum-weight triangulation, etc. This paper gives approximation algorithms for the general class of problems. The sequential algorithm is a simple greedy algorithm that can be implemented to find an epsilon-approximate solution in O(epsilon^-2 log m) linear-time iterations. The parallel algorithm does comparable work but finishes in polylogarithmic time. The results generalize previous work on pure packing and covering (the special case when the constraints are all "less-than" or all "greater-than") by Michael Luby and Noam Nisan (1993) and Naveen Garg and Jochen Konemann (1998).
Approximating the Minimum Equivalent Digraph
Venue: arXiv cs.DS 2002
Year: 2002

The MEG (minimum equivalent graph) problem is, given a directed graph, to find a small subset of the edges that maintains all reachability relations between nodes. The problem is NP-hard. This paper gives an approximation algorithm with performance guarantee of pi^2/6 ~ 1.64. The algorithm and its analysis are based on the simple idea of contracting long cycles. (This result is strengthened slightly in ``On strongly connected digraphs with bounded cycle length'' (1996).) The analysis applies directly to 2-Exchange, a simple ``local improvement'' algorithm, showing that its performance guarantee is 1.75.
Parameterized Intractability of Motif Search Problems
Venue: arXiv cs.CC 2002
Year: 2002

We show that Closest Substring, one of the most important problems in the field of biological sequence analysis, is W[1]-hard when parameterized by the number k of input strings (and remains so, even over a binary alphabet). This problem is therefore unlikely to be solvable in time O(f(k)\cdot n^{c}) for any function f of k and constant c independent of k. The problem can therefore be expected to be intractable, in any practical sense, for k>=3. Our result supports the intuition that Closest Substring is computationally much harder than the special case of Closest String, although both problems are NP-complete. We also prove W[1]-hardness for other parameterizations in the case of unbounded alphabet size. Our W[1]-hardness result for Closest Substring generalizes to Consensus Patterns, a problem of similar significance in computational biology.
Minimizing Cache Misses in Scientific Computing Using Isoperimetric Bodies
Venue: arXiv cs.PF 2002
Year: 2002

A number of known techniques for improving cache performance in scientific computations involve the reordering of the iteration space. Some of these reorderings can be considered coverings of the iteration space with sets having small surface-to-volume ratios. Use of such sets may reduce the number of cache misses in computations of local operators having the iteration space as their domain. First, we derive lower bounds on cache misses that any algorithm must suffer while computing a local operator on a grid. Then, we explore coverings of iteration spaces of structured and unstructured discretization grid operators which allow us to approach these lower bounds. For structured grids we introduce a covering by successive minima tiles based on the interference lattice of the grid. We show that the covering has a small surface-to-volume ratio and present a computer experiment showing actual reduction of the cache misses achieved by using these tiles. For planar unstructured grids we show existence of a covering which reduces the number of cache misses to the level of that of structured grids. Next, we introduce a class of multidimensional grids, called starry grids in this paper. These grids represent an abstraction of unstructured grids used in, for example, molecular simulations and the solution of partial differential equations. We show that starry grids can be covered by sets having a low surface-to-volume ratio and, hence have the same cache efficiency as structured grids. Finally, we present a triangulation of a three-dimensional cube that has the property that any local operator on the corresponding grid must incur a significantly larger number of cache misses than a similar operator on a structured grid of the same size.
Computer modeling of feelings and emotions: a quantitative neural network model of the feeling-of-knowing
Venue: arXiv cs.AI 2002
Year: 2002

The first quantitative neural network model of feelings and emotions is proposed on the base of available data on their neuroscience and evolutionary biology nature, and on a neural network human memory model which admits distinct description of conscious and unconscious mental processes in a time dependent manner. As an example, proposed model is applied to quantitative description of the feeling of knowing.
The Fastest and Shortest Algorithm for All Well-Defined Problems
Venue: arXiv cs.CC 2002
Year: 2002

An algorithm $M$ is described that solves any well-defined problem $p$ as quickly as the fastest algorithm computing a solution to $p$, save for a factor of 5 and low-order additive terms. $M$ optimally distributes resources between the execution of provably correct $p$-solving programs and an enumeration of all proofs, including relevant proofs of program correctness and of time bounds on program runtimes. $M$ avoids Blum's speed-up theorem by ignoring programs without correctness proof. $M$ has broader applicability and can be faster than Levin's universal search, the fastest method for inverting functions save for a large multiplicative constant. An extension of Kolmogorov complexity and two novel natural measures of function complexity are used to show that the most efficient program computing some function $f$ is also among the shortest programs provably computing $f$.
Computer-Generated Photorealistic Hair
Venue: arXiv cs.GR 2002
Year: 2002

This paper presents an efficient method for generating and rendering photorealistic hair in two dimensional pictures. The method consists of three major steps. Simulating an artist drawing is used to design the rough hair shape. A convolution based filter is then used to generate photorealistic hair patches. A refine procedure is finally used to blend the boundaries of the patches with surrounding areas. This method can be used to create all types of photorealistic human hair (head hair, facial hair and body hair). It is also suitable for fur and grass generation. Applications of this method include: hairstyle designing/editing, damaged hair image restoration, human hair animation, virtual makeover of a human, and landscape creation.
Symmetric boundary knot method
Venue: arXiv cs.CE 2002
Year: 2002

The boundary knot method (BKM) is a recent boundary-type radial basis function (RBF) collocation scheme for general PDEs. Like the method of fundamental solution (MFS), the RBF is employed to approximate the inhomogeneous terms via the dual reciprocity principle. Unlike the MFS, the method uses a nonsingular general solution instead of a singular fundamental solution to evaluate the homogeneous solution so as to circumvent the controversial artificial boundary outside the physical domain. The BKM is meshfree, superconvergent, integration free, very easy to learn and program. The original BKM, however, loses symmetricity in the presense of mixed boundary. In this study, by analogy with Hermite RBF interpolation, we developed a symmetric BKM scheme. The accuracy and efficiency of the symmetric BKM are also numerically validated in some 2D and 3D Helmholtz and diffusion reaction problems under complicated geometries.
A Compact Graph Model of Handwritten Images: Integration into Authentification and Recognition
Venue: arXiv cs.HC 2002
Year: 2002

A novel algorithm for creating a mathematical model of curved shapes is introduced. The core of the algorithm is based on building a graph representation of the contoured image, which occupies less storage space than produced by raster compression techniques. Different advanced applications of the mathematical model are discussed: recognition of handwritten characters and verification of handwritten text and signatures for authentification purposes. Reducing the storage requirements due to the efficient mathematical model results in faster retrieval and processing times. The experimental outcomes in compression of contoured images and recognition of handwritten numerals are given.