OpenRaiser/Intern-Atlas huggingface dataset:
The TESLA Requirements Database
Venue: arXiv cs.DB 2003
Year: 2003

In preparation for the planned linear collider TESLA, DESY is designing the required buildings and facilities. The accelerator and infrastructure components have to be allocated to buildings, and their required areas for installation, operation and maintenance have to be determined. Interdisciplinary working groups specify the project from different viewpoints and need to develop a common vision as a precondition for an optimal solution. A commercial requirements database is used as a collaborative tool, enabling concurrent requirements specification by independent working groups. The requirements database ensures long term storage and availability of the emerging knowledge, and it offers a central platform for communication which is available for all project members. It is successfully operating since summer 2002 and has since then become an important tool for the design team.
Integrated Information Management for TESLA
Venue: arXiv cs.DB 2003
Year: 2003

Next-generation projects in High Energy Physics will reach again a new dimension of complexity. Information management has to ensure an efficient and economic information flow within the collaborations, offering world-wide up-to-date information access to the collaborators as one condition for successful projects. DESY introduces several information systems in preparation for the planned linear collider TESLA: a Requirements Management System (RMS) is in production for the TESLA planning group, a Product Data Management System (PDMS) is in production since the beginning of 2002 and is supporting the cavity preparation and the general engineering of accelerator components. A pilot Asset Management System (AMS) is in production for supporting the management and maintenance of the technical infrastructure, and a Facility Management System (FMS) with a Geographic Information System (GIS) is currently being introduced to support civil engineering. Efforts have been started to integrate the systems with the goal that users can retrieve information through a single point of access. The paper gives an introduction to information management and the activities at DESY.
BOA: Framework for Automated Builds
Venue: arXiv cs.SE 2003
Year: 2003

Managing large-scale software products is a complex software engineering task. The automation of the software development, release and distribution process is most beneficial in the large collaborations, where the big number of developers, multiple platforms and distributed environment are typical factors. This paper describes Build and Output Analyzer framework and its components that have been developed in CMS to facilitate software maintenance and improve software quality. The system allows to generate, control and analyze various types of automated software builds and tests, such as regular rebuilds of the development code, software integration for releases and installation of the existing versions.
GANGA: a user-Grid interface for Atlas and LHCb
Venue: arXiv cs.SE 2003
Year: 2003

The Gaudi/Athena and Grid Alliance (GANGA) is a front-end for the configuration, submission, monitoring, bookkeeping, output collection, and reporting of computing jobs run on a local batch system or on the grid. In particular, GANGA handles jobs that use applications written for the Gaudi software framework shared by the Atlas and LHCb experiments. GANGA exploits the commonality of Gaudi-based computing jobs, while insulating against grid-, batch- and framework-specific technicalities, to maximize end-user productivity in defining, configuring, and executing jobs. Designed for a python-based component architecture, GANGA has a modular underpinning and is therefore well placed for contributing to, and benefiting from, work in related projects. Its functionality is accessible both from a scriptable command-line interface, for expert users and automated tasks, and through a graphical interface, which simplifies the interaction with GANGA for beginning and c1asual users. This paper presents the GANGA design and implementation, the development of the underlying software bus architecture, and the functionality of the first public GANGA release.
Primary Numbers Database for ATLAS Detector Description Parameters
Venue: arXiv cs.DB 2003
Year: 2003

We present the design and the status of the database for detector description parameters in ATLAS experiment. The ATLAS Primary Numbers are the parameters defining the detector geometry and digitization in simulations, as well as certain reconstruction parameters. Since the detailed ATLAS detector description needs more than 10,000 such parameters, a preferred solution is to have a single verified source for all these data. The database stores the data dictionary for each parameter collection object, providing schema evolution support for object-based retrieval of parameters. The same Primary Numbers are served to many different clients accessing the database: the ATLAS software framework Athena, the Geant3 heritage framework Atlsim, the Geant4 developers framework FADS/Goofy, the generator of XML output for detector description, and several end-user clients for interactive data navigation, including web-based browsers and ROOT. The choice of the MySQL database product for the implementation provides additional benefits: the Primary Numbers database can be used on the developers laptop when disconnected (using the MySQL embedded server technology), with data being updated when the laptop is connected (using the MySQL database replication).
Sharing a conceptual model of grid resources and services
Venue: arXiv cs.DC 2003
Year: 2003

Grid technologies aim at enabling a coordinated resource-sharing and problem-solving capabilities over local and wide area networks and span locations, organizations, machine architectures and software boundaries. The heterogeneity of involved resources and the need for interoperability among different grid middlewares require the sharing of a common information model. Abstractions of different flavors of resources and services and conceptual schemas of domain specific entities require a collaboration effort in order to enable a coherent information services cooperation. With this paper, we present the result of our experience in grid resources and services modelling carried out within the Grid Laboratory Uniform Environment (GLUE) effort, a joint US and EU High Energy Physics projects collaboration towards grid interoperability. The first implementation-neutral agreement on services such as batch computing and storage manager, resources such as the hierarchy cluster, sub-cluster, host and the storage library are presented. Design guidelines and operational results are depicted together with open issues and future evolutions.
Bayesian Treatment of Incomplete Discrete Data applied to Mutual Information and Feature Selection
Venue: arXiv cs.LG 2003
Year: 2003

Given the joint chances of a pair of random variables one can compute quantities of interest, like the mutual information. The Bayesian treatment of unknown chances involves computing, from a second order prior distribution and the data likelihood, a posterior distribution of the chances. A common treatment of incomplete data is to assume ignorability and determine the chances by the expectation maximization (EM) algorithm. The two different methods above are well established but typically separated. This paper joins the two approaches in the case of Dirichlet priors, and derives efficient approximations for the mean, mode and the (co)variance of the chances and the mutual information. Furthermore, we prove the unimodality of the posterior distribution, whence the important property of convergence of EM to the global maximum in the chosen framework. These results are applied to the problem of selecting features for incremental learning and naive Bayes classification. A fast filter based on the distribution of mutual information is shown to outperform the traditional filter based on empirical mutual information on a number of incomplete real data sets.
Development of a Java Package for Matrix Programming
Venue: arXiv cs.MS 2003
Year: 2003

We had assembled a Java package, known as MatrixPak, of four classes for the purpose of numerical matrix computation. The classes are matrix, matrix_operations, StrToMatrix, and MatrixToStr; all of which are inherited from java.lang.Object class. Class matrix defines a matrix as a two-dimensional array of float types, and contains the following mathematical methods: transpose, adjoint, determinant, inverse, minor and cofactor. Class matrix_operations contains the following mathematical methods: matrix addition, matrix subtraction, matrix multiplication, and matrix exponential. Class StrToMatrix contains methods necessary to parse a string representation (for example, [[2 3 4]-[5 6 7]]) of a matrix into a matrix definition, whereas class MatrixToStr does the reverse.
Complexity of Cycle Length Modularity Problems in Graphs
Venue: arXiv cs.CC 2003
Year: 2003

The even cycle problem for both undirected and directed graphs has been the topic of intense research in the last decade. In this paper, we study the computational complexity of \emph{cycle length modularity problems}. Roughly speaking, in a cycle length modularity problem, given an input (undirected or directed) graph, one has to determine whether the graph has a cycle $C$ of a specific length (or one of several different lengths), modulo a fixed integer. We denote the two families (one for undirected graphs and one for directed graphs) of problems by $(S,m)\hbox{-}{\rm UC}$ and $(S,m)\hbox{-}{\rm DC}$, where $m \in \mathcal{N}$ and $S \subseteq \{0,1, ..., m-1\}$. $(S,m)\hbox{-}{\rm UC}$ (respectively, $(S,m)\hbox{-}{\rm DC}$) is defined as follows: Given an undirected (respectively, directed) graph $G$, is there a cycle in $G$ whose length, modulo $m$, is a member of $S$? In this paper, we fully classify (i.e., as either polynomial-time solvable or as ${\rm NP}$-complete) each problem $(S,m)\hbox{-}{\rm UC}$ such that $0 \in S$ and each problem $(S,m)\hbox{-}{\rm DC}$ such that $0 \notin S$. We also give a sufficient condition on $S$ and $m$ for the following problem to be polynomial-time computable: $(S,m)\hbox{-}{\rm UC}$ such that $0 \notin S$.
Serving Database Information Using a Flexible Server in a Three Tier Architecture
Venue: arXiv cs.DC 2003
Year: 2003

The D0 experiment at Fermilab relies on a central Oracle database for storing all detector calibration information. Access to this data is needed by hundreds of physics applications distributed worldwide. In order to meet the demands of these applications from scarce resources, we have created a distributed system that isolates the user applications from the database facilities. This system, known as the Database Application Network (DAN) operates as the middle tier in a three tier architecture. A DAN server employs a hierarchical caching scheme and database connection management facility that limits access to the database resource. The modular design allows for caching strategies and database access components to be determined by runtime configuration. To solve scalability problems, a proxy database component allows for DAN servers to be arranged in a hierarchy. Also included is an event based monitoring system that is currently being used to collect statistics for performance analysis and problem diagnosis. DAN servers are currently implemented as a Python multithreaded program using CORBA for network communications and interface specification. The requirement details, design, and implementation of DAN are discussed along with operational experience and future plans.
Management of Grid Jobs and Information within SAMGrid
Venue: arXiv cs.DC 2003
Year: 2003

We describe some of the key aspects of the SAMGrid system, used by the D0 and CDF experiments at Fermilab. Having sustained success of the data handling part of SAMGrid, we have developed new services for job and information services. Our job management is rooted in \CondorG and uses enhancements that are general applicability for HEP grids. Our information system is based on a uniform framework for configuration management based on XML data representation and processing.
Improving the Security and Performance of the BaBar Detector Controls System
Venue: arXiv cs.NI 2003
Year: 2003

It starts out innocently enough - users want to monitor Online data and so run their own copies of the detector control GUIs in their offices and at home. But over time, the number of processes making requests for values to display on GUIs, webpages and stripcharts can grow, and affect the performance of an Input/Output Controller (IOC) such that it is unable to respond to requests from requests critical to data-taking. At worst, an IOC can hang, its CPU having been allocated 100% to responding to network requests. For the BaBar Online Detector Control System, we were able to eliminate this problem and make great gains in security by moving all of the IOCs to a non-routed, virtual LAN and by enlisting a workstation with two network interface cards to act as the interface between the virtual LAN and the public BaBar network. On the interface machine, we run the Experimental Physics Industrial Control System (EPICS) Channel Access (CA) gateway software (originating from Advanced Photon Source). This software accepts as inputs, all the channels which are loaded into the EPICS databases on all the IOCs. It polls them to update its copy of the values. It answers requests from applications by sending them the currently cached value. We adopted the requirement that data-taking would be independent of the gateway, so that, in the event of a gateway failure, data-taking would be uninterrupted. In this way, we avoided introducing any new risk elements to data-taking. Security rules already in use by the IOC were propagated to the gateway's own security rules and the security of the IOCs themselves was improved by removing them from the public BaBar network.
Range Mode and Range Median Queries on Lists and Trees
Venue: arXiv cs.DS 2003
Year: 2003

We consider algorithms for preprocessing labelled lists and trees so that, for any two nodes u and v we can answer queries of the form: What is the mode or median label in the sequence of labels on the path from u to v.
An Extension of the Lovasz Local Lemma, and its Applications to Integer Programming
Venue: arXiv cs.DS 2003
Year: 2003

The Lovasz Local Lemma due to Erdos and Lovasz is a powerful tool in proving the existence of rare events. We present an extension of this lemma, which works well when the event to be shown to exist is a conjunction of individual events, each of which asserts that a random variable does not deviate much from its mean. As applications, we consider two classes of NP-hard integer programs: minimax and covering integer programs. A key technique, randomized rounding of linear relaxations, was developed by Raghavan and Thompson to derive good approximation algorithms for such problems. We use our extension of the Local Lemma to prove that randomized rounding produces, with non-zero probability, much better feasible solutions than known before, if the constraint matrices of these integer programs are column-sparse (e.g., routing using short paths, problems on hypergraphs with small dimension/degree). This complements certain well-known results from discrepancy theory. We also generalize the method of pessimistic estimators due to Raghavan, to obtain constructive (algorithmic) versions of our results for covering integer programs.
Rational Radial Distortion Models with Analytical Undistortion Formulae
Venue: arXiv cs.CV 2003
Year: 2003

The common approach to radial distortion is by the means of polynomial approximation, which introduces distortion-specific parameters into the camera model and requires estimation of these distortion parameters. The task of estimating radial distortion is to find a radial distortion model that allows easy undistortion as well as satisfactory accuracy. This paper presents a new class of rational radial distortion models with easy analytical undistortion formulae. Experimental results are presented to show that with this class of rational radial distortion models, satisfactory and comparable accuracy is achieved.
Limit groups and groups acting freely on $\bbR^n$-trees
Venue: arXiv cs.DL 2003
Year: 2003

We give a simple proof of the finite presentation of Sela's limit groups by using free actions on $\bbR^n$-trees. We first prove that Sela's limit groups do have a free action on an $\bbR^n$-tree. We then prove that a finitely generated group having a free action on an $\bbR^n$-tree can be obtained from free abelian groups and surface groups by a finite sequence of free products and amalgamations over cyclic groups. As a corollary, such a group is finitely presented, has a finite classifying space, its abelian subgroups are finitely generated and contains only finitely many conjugacy classes of non-cyclic maximal abelian subgroups.
Gridscape: A Tool for the Creation of Interactive and Dynamic Grid Testbed Web Portals
Venue: arXiv cs.DC 2003
Year: 2003

The notion of grid computing has gained an increasing popularity recently as a realistic solution to many of our large-scale data storage and processing needs. It enables the sharing, selection and aggregation of resources geographically distributed across collaborative organisations. Now more and more people are beginning to embrace grid computing and thus are seeing the need to set up their own grids and grid testbeds. With this comes the need to have some means to enable them to view and monitor the status of the resources in these testbeds (eg. Web based Grid portal). Generally developers invest a substantial amount of time and effort developing custom monitoring software. To overcome this limitation, this paper proposes Gridscape ? a tool that enables the rapid creation of interactive and dynamic testbed portals (without any programming effort). Gridscape primarily aims to provide a solution for those users who need to be able to create a grid testbed portal but don?t necessarily have the time or resources to build a system of their own from scratch.
From Statistical Knowledge Bases to Degrees of Belief
Venue: arXiv cs.AI 2003
Year: 2003

An intelligent agent will often be uncertain about various properties of its environment, and when acting in that environment it will frequently need to quantify its uncertainty. For example, if the agent wishes to employ the expected-utility paradigm of decision theory to guide its actions, it will need to assign degrees of belief (subjective probabilities) to various assertions. Of course, these degrees of belief should not be arbitrary, but rather should be based on the information available to the agent. This paper describes one approach for inducing degrees of belief from very rich knowledge bases, that can include information about particular individuals, statistical correlations, physical laws, and default rules. We call our approach the random-worlds method. The method is based on the principle of indifference: it treats all of the worlds the agent considers possible as being equally likely. It is able to integrate qualitative default reasoning with quantitative probabilistic reasoning by providing a language in which both types of information can be easily expressed. Our results show that a number of desiderata that arise in direct inference (reasoning from statistical information to conclusions about individuals) and default reasoning follow directly {from} the semantics of random worlds. For example, random worlds captures important patterns of reasoning such as specificity, inheritance, indifference to irrelevant information, and default assumptions of independence. Furthermore, the expressive power of the language used and the intuitive semantics of random worlds allow the method to deal with problems that are beyond the scope of many other non-deductive reasoning systems.
A logic for reasoning about upper probabilities
Venue: arXiv cs.AI 2003
Year: 2003

We present a propositional logic %which can be used to reason about the uncertainty of events, where the uncertainty is modeled by a set of probability measures assigning an interval of probability to each event. We give a sound and complete axiomatization for the logic, and show that the satisfiability problem is NP-complete, no harder than satisfiability for propositional logic.
Search and Navigation in Relational Databases
Venue: arXiv cs.DB 2003
Year: 2003

We present a new application for keyword search within relational databases, which uses a novel algorithm to solve the join discovery problem by finding Memex-like trails through the graph of foreign key dependencies. It differs from previous efforts in the algorithms used, in the presentation mechanism and in the use of primary-key only database queries at query-time to maintain a fast response for users. We present examples using the DBLP data set.
DPG: A Cache-Efficient Accelerator for Sorting and for Join Operators
Venue: arXiv cs.DB 2003
Year: 2003

We present a new algorithm for fast record retrieval, distribute-probe-gather, or DPG. DPG has important applications both in sorting and in joins. Current main memory sorting algorithms split their work into three phases: extraction of key-pointer pairs; sorting of the key-pointer pairs; and copying of the original records into the destination array according the sorted key-pointer pairs. The copying in the last phase dominates today's sorting time. Hence, the use of DPG in the third phase provides an accelerator for existing sorting algorithms. DPG also provides two new join methods for foreign key joins: DPG-move join and DPG-sort join. The resulting join methods with DPG are faster because DPG join is cache-efficient and at the same time DPG join avoids the need for sorting or for hashing. The ideas presented for foreign key join can also be extended to faster record pair retrieval for spatial and temporal databases.
On Applying Or-Parallelism and Tabling to Logic Programs
Venue: arXiv cs.PL 2003
Year: 2003

The past years have seen widening efforts at increasing Prolog's declarativeness and expressiveness. Tabling has proved to be a viable technique to efficiently overcome SLD's susceptibility to infinite loops and redundant subcomputations. Our research demonstrates that implicit or-parallelism is a natural fit for logic programs with tabling. To substantiate this belief, we have designed and implemented an or-parallel tabling engine -- OPTYap -- and we used a shared-memory parallel machine to evaluate its performance. To the best of our knowledge, OPTYap is the first implementation of a parallel tabling engine for logic programming systems. OPTYap builds on Yap's efficient sequential Prolog engine. Its execution model is based on the SLG-WAM for tabling, and on the environment copying for or-parallelism. Preliminary results indicate that the mechanisms proposed to parallelize search in the context of SLD resolution can indeed be effectively and naturally generalized to parallelize tabled computations, and that the resulting systems can achieve good performance on shared-memory parallel machines. More importantly, it emphasizes our belief that through applying or-parallelism and tabling to logic programs the range of applications for Logic Programming can be increased.
Constant-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations
Venue: arXiv cs.CC 2003
Year: 2003

We show that constant-depth Frege systems with counting axioms modulo $m$ polynomially simulate Nullstellensatz refutations modulo $m$. Central to this is a new definition of reducibility from formulas to systems of polynomials with the property that, for most previously studied translations of formulas to systems of polynomials, a formula reduces to its translation. When combined with a previous result of the authors, this establishes the first size separation between Nullstellensatz and polynomial calculus refutations. We also obtain new, small refutations for certain CNFs by constant-depth Frege systems with counting axioms.