OpenRaiser/Intern-Atlas huggingface dataset:
Multilevel expander codes
Venue: arXiv cs.IT 2005
Year: 2005

We define multilevel codes on bipartite graphs that have properties analogous to multilevel serial concatenations. A decoding algorithm is described that corrects a proportion of errors equal to half the Blokh-Zyablov bound on the minimum distance. The error probability of this algorithm has exponent similar to that of serially concatenated multilevel codes.
On the Typicality of the Linear Code Among the LDPC Coset Code Ensemble
Venue: arXiv cs.IT 2005
Year: 2005

Density evolution (DE) is one of the most powerful analytical tools for low-density parity-check (LDPC) codes on memoryless binary-input/symmetric-output channels. The case of non-symmetric channels is tackled either by the LDPC coset code ensemble (a channel symmetrizing argument) or by the generalized DE for linear codes on non-symmetric channels. Existing simulations show that the bit error rate performances of these two different approaches are nearly identical. This paper explains this phenomenon by proving that as the minimum check node degree $d_c$ becomes sufficiently large, the performance discrepancy of the linear and the coset LDPC codes is theoretically indistinguishable. This typicality of linear codes among the LDPC coset code ensemble provides insight into the concentration theorem of LDPC coset codes.
Self-Replicating Strands that Self-Assemble into User-Specified Meshes
Venue: arXiv cs.NE 2005
Year: 2005

It has been argued that a central objective of nanotechnology is to make products inexpensively, and that self-replication is an effective approach to very low-cost manufacturing. The research presented here is intended to be a step towards this vision. In previous work (JohnnyVon 1.0), we simulated machines that bonded together to form self-replicating strands. There were two types of machines (called types 0 and 1), which enabled strands to encode arbitrary bit strings. However, the information encoded in the strands had no functional role in the simulation. The information was replicated without being interpreted, which was a significant limitation for potential manufacturing applications. In the current work (JohnnyVon 2.0), the information in a strand is interpreted as instructions for assembling a polygonal mesh. There are now four types of machines and the information encoded in a strand determines how it folds. A strand may be in an unfolded state, in which the bonds are straight (although they flex slightly due to virtual forces acting on the machines), or in a folded state, in which the bond angles depend on the types of machines. By choosing the sequence of machine types in a strand, the user can specify a variety of polygonal shapes. A simulation typically begins with an initial unfolded seed strand in a soup of unbonded machines. The seed strand replicates by bonding with free machines in the soup. The child strands fold into the encoded polygonal shape, and then the polygons drift together and bond to form a mesh. We demonstrate that a variety of polygonal meshes can be manufactured in the simulation, by simply changing the sequence of machine types in the seed.
The QuarkNet/Grid Collaborative Learning e-Lab
Venue: arXiv cs.DC 2005
Year: 2005

We describe a case study that uses grid computing techniques to support the collaborative learning of high school students investigating cosmic rays. Students gather and upload science data to our e-Lab portal. They explore those data using techniques from the GriPhyN collaboration. These techniques include virtual data transformations, workflows, metadata cataloging and indexing, data product provenance and persistence, as well as job planners. Students use web browsers and a custom interface that extends the GriPhyN Chiron portal to perform all of these tasks. They share results in the form of online posters and ask each other questions in this asynchronous environment. Students can discover and extend the research of other students, modeling the processes of modern large-scale scientific collaborations. Also, the e-Lab portal provides tools for teachers to guide student work throughout an investigation. http://quarknet.uchicago.edu/elab/cosmic
UNICORE - From Project Results to Production Grids
Venue: arXiv cs.DC 2005
Year: 2005

The UNICORE Grid-technology provides a seamless, secure and intuitive access to distributed Grid resources. In this paper we present the recent evolution from project results to production Grids. At the beginning UNICORE was developed as a prototype software in two projects funded by the German research ministry (BMBF). Over the following years, in various European-funded projects, UNICORE evolved to a full-grown and well-tested Grid middleware system, which today is used in daily production at many supercomputing centers worldwide. Beyond this production usage, the UNICORE technology serves as a solid basis in many European and International research projects, which use existing UNICORE components to implement advanced features, high level services, and support for applications from a growing range of domains. In order to foster these ongoing developments, UNICORE is available as open source under BSD licence at SourceForge, where new releases are published on a regular basis. This paper is a review of the UNICORE achievements so far and gives a glimpse on the UNICORE roadmap.
Gradient Vector Flow Models for Boundary Extraction in 2D Images
Venue: arXiv cs.CV 2005
Year: 2005

The Gradient Vector Flow (GVF) is a vector diffusion approach based on Partial Differential Equations (PDEs). This method has been applied together with snake models for boundary extraction medical images segmentation. The key idea is to use a diffusion-reaction PDE to generate a new external force field that makes snake models less sensitivity to initialization as well as improves the snake's ability to move into boundary concavities. In this paper, we firstly review basic results about convergence and numerical analysis of usual GVF schemes. We point out that GVF presents numerical problems due to discontinuities image intensity. This point is considered from a practical viewpoint from which the GVF parameters must follow a relationship in order to improve numerical convergence. Besides, we present an analytical analysis of the GVF dependency from the parameters values. Also, we observe that the method can be used for multiply connected domains by just imposing the suitable boundary condition. In the experimental results we verify these theoretical points and demonstrate the utility of GVF on a segmentation approach that we have developed based on snakes.
Property analysis of symmetric travelling salesman problem instances acquired through evolution
Venue: arXiv cs.NE 2005
Year: 2005

We show how an evolutionary algorithm can successfully be used to evolve a set of difficult to solve symmetric travelling salesman problem instances for two variants of the Lin-Kernighan algorithm. Then we analyse the instances in those sets to guide us towards deferring general knowledge about the efficiency of the two variants in relation to structural properties of the symmetric travelling sale sman problem.
Effective Requirements Generation: Synchronizing Early Verification & Validation, Methods and Method Selection Criteria
Venue: arXiv cs.SE 2005
Year: 2005

This paper presents an approach for the implementation and execution of an effective requirements generation process. We achieve this goal by providing a well-defined requirements engineering model that includes verification and validation (V&V), and analysis. In addition, we identify focused activity objectives and map popular methods to lower-level activities, and define a criterion based process for optimizing method selection for attendant activities. Our model, unlike other models, addresses the complete requirements generation process and consists of activities defined at more adequate levels of abstraction. Furthermore, our model also incorporates a unique approach to V&V that enhances quality and reduces the cost of generating requirements. Additionally, activity objectives are identified and explicitly stated - not implied as in the current models. To assist in the selection of an appropriate set of methods, we have mapped commonly used methods to activities based on their objectives. Finally, we have identified method selection criteria and prescribed a reduced set of methods that optimize these criteria for each activity in our model. Thus, our approach assists in the task of selecting methods by using selection criteria to reduce a large collection of potential methods to a smaller, manageable set. The model, clear mapping of methods to activity objectives, and the criteria based process, taken together, provide the much needed guidance for the effective implementation and execution of the requirements generation process.
High efficiency and low absorption Fresnel compound zone plates for hard X-ray focusing
Venue: arXiv cs.OH 2005
Year: 2005

Circular and linear zone plates have been fabricated on the surface of silicon crystals for the energy of 8 keV by electron beam lithography and deep ion plasma etching methods. Various variants of compound zone plates with first, second, third diffraction orders have been made. The zone relief height is about 10 mkm, the outermost zone width of the zone plate is 0.4 mkm. The experimental testing of the zone plates has been conducted on SPring-8 and ESRF synchrotron radiation sources. A focused spot size and diffraction efficiency measured by knife-edge scanning are accordingly 0.5 mkm and 39% for the first order circular zone plate.
Shuffling a Stacked Deck: The Case for Partially Randomized Ranking of Search Engine Results
Venue: arXiv cs.IR 2005
Year: 2005

In-degree, PageRank, number of visits and other measures of Web page popularity significantly influence the ranking of search results by modern search engines. The assumption is that popularity is closely correlated with quality, a more elusive concept that is difficult to measure directly. Unfortunately, the correlation between popularity and quality is very weak for newly-created pages that have yet to receive many visits and/or in-links. Worse, since discovery of new content is largely done by querying search engines, and because users usually focus their attention on the top few results, newly-created but high-quality pages are effectively ``shut out,'' and it can take a very long time before they become popular. We propose a simple and elegant solution to this problem: the introduction of a controlled amount of randomness into search result ranking methods. Doing so offers new pages a chance to prove their worth, although clearly using too much randomness will degrade result quality and annul any benefits achieved. Hence there is a tradeoff between exploration to estimate the quality of new pages and exploitation of pages already known to be of high quality. We study this tradeoff both analytically and via simulation, in the context of an economic objective function based on aggregate result quality amortized over time. We show that a modest amount of randomness leads to improved search results.
A Systematic Aspect-Oriented Refactoring and Testing Strategy, and its Application to JHotDraw
Venue: arXiv cs.SE 2005
Year: 2005

Aspect oriented programming aims at achieving better modularization for a system's crosscutting concerns in order to improve its key quality attributes, such as evolvability and reusability. Consequently, the adoption of aspect-oriented techniques in existing (legacy) software systems is of interest to remediate software aging. The refactoring of existing systems to employ aspect-orientation will be considerably eased by a systematic approach that will ensure a safe and consistent migration. In this paper, we propose a refactoring and testing strategy that supports such an approach and consider issues of behavior conservation and (incremental) integration of the aspect-oriented solution with the original system. The strategy is applied to the JHotDraw open source project and illustrated on a group of selected concerns. Finally, we abstract from the case study and present a number of generic refactorings which contribute to an incremental aspect-oriented refactoring process and associate particular types of crosscutting concerns to the model and features of the employed aspect language. The contributions of this paper are both in the area of supporting migration towards aspect-oriented solutions and supporting the development of aspect languages that are better suited for such migrations.
Fast-Forward on the Green Road to Open Access: The Case Against Mixing Up Green and Gold
Venue: arXiv cs.IR 2005
Year: 2005

This article is a critique of: "The 'Green' and 'Gold' Roads to Open Access: The Case for Mixing and Matching" by Jean-Claude Guedon (in Serials Review 30(4) 2004). Open Access (OA) means: free online access to all peer-reviewed journal articles. Jean-Claude Guedon argues against the efficacy of author self-archiving of peer-reviewed journal articles (the "Green" road to OA). He suggests instead that we should convert to Open Access Publishing (the "Golden" road to OA) by "mixing and matching" Green and Gold as follows: o First, self-archive dissertations (not published, peer-reviewed journal articles). o Second, identify and tag how those dissertations have been evaluated and reviewed. o Third, self-archive unrefereed preprints (not published, peer-reviewed journal articles). o Fourth, develop new mechanisms for evaluating and reviewing those unrefereed preprints, at multiple levels. The result will be OA Publishing (Gold). I argue that rather than yet another 10 years of speculation like this, what is actually needed (and imminent) is for OA self-archiving to be mandated by research funders and institutions so that the self-archiving of published, peer-reviewed journal articles (Green) can be fast-forwarded to 100% OA.
Fine-Grained Word Sense Disambiguation Based on Parallel Corpora, Word Alignment, Word Clustering and Aligned Wordnets
Venue: arXiv cs.AI 2005
Year: 2005

The paper presents a method for word sense disambiguation based on parallel corpora. The method exploits recent advances in word alignment and word clustering based on automatic extraction of translation equivalents and being supported by available aligned wordnets for the languages in the corpus. The wordnets are aligned to the Princeton Wordnet, according to the principles established by EuroWordNet. The evaluation of the WSD system, implementing the method described herein showed very encouraging results. The same system used in a validation mode, can be used to check and spot alignment errors in multilingually aligned wordnets as BalkaNet and EuroWordNet.
On Generalized Computable Universal Priors and their Convergence
Venue: arXiv cs.LG 2005
Year: 2005

Solomonoff unified Occam's razor and Epicurus' principle of multiple explanations to one elegant, formal, universal theory of inductive inference, which initiated the field of algorithmic information theory. His central result is that the posterior of the universal semimeasure M converges rapidly to the true sequence generating posterior mu, if the latter is computable. Hence, M is eligible as a universal predictor in case of unknown mu. The first part of the paper investigates the existence and convergence of computable universal (semi)measures for a hierarchy of computability classes: recursive, estimable, enumerable, and approximable. For instance, M is known to be enumerable, but not estimable, and to dominate all enumerable semimeasures. We present proofs for discrete and continuous semimeasures. The second part investigates more closely the types of convergence, possibly implied by universality: in difference and in ratio, with probability 1, in mean sum, and for Martin-Loef random sequences. We introduce a generalized concept of randomness for individual sequences and use it to exhibit difficulties regarding these issues. In particular, we show that convergence fails (holds) on generalized-random sequences in gappy (dense) Bernoulli classes.
A Suffix Tree Approach to Email Filtering
Venue: arXiv cs.AI 2005
Year: 2005

We present an approach to email filtering based on the suffix tree data structure. A method for the scoring of emails using the suffix tree is developed and a number of scoring and score normalisation functions are tested. Our results show that the character level representation of emails and classes facilitated by the suffix tree can significantly improve classification accuracy when compared with the currently popular methods, such as naive Bayes. We believe the method can be extended to the classification of documents in other domains.
Complexity Issues in Finding Succinct Solutions of PSPACE-Complete Problems
Venue: arXiv cs.AI 2005
Year: 2005

We study the problem of deciding whether some PSPACE-complete problems have models of bounded size. Contrary to problems in NP, models of PSPACE-complete problems may be exponentially large. However, such models may take polynomial space in a succinct representation. For example, the models of a QBF are explicitely represented by and-or trees (which are always of exponential size) but can be succinctely represented by circuits (which can be polynomial or exponential). We investigate the complexity of deciding the existence of such succinct models when a bound on size is given.
On Multiflows in Random Unit-Disk Graphs, and the Capacity of Some Wireless Networks
Venue: arXiv cs.IT 2005
Year: 2005

We consider the capacity problem for wireless networks. Networks are modeled as random unit-disk graphs, and the capacity problem is formulated as one of finding the maximum value of a multicommodity flow. In this paper, we develop a proof technique based on which we are able to obtain a tight characterization of the solution to the linear program associated with the multiflow problem, to within constants independent of network size. We also use this proof method to analyze network capacity for a variety of transmitter/receiver architectures, for which we obtain some conclusive results. These results contain as a special case (and strengthen) those of Gupta and Kumar for random networks, for which a new derivation is provided using only elementary counting and discrete probability tools.
A hybrid MLP-PNN architecture for fast image superresolution
Venue: arXiv cs.CV 2005
Year: 2005

Image superresolution methods process an input image sequence of a scene to obtain a still image with increased resolution. Classical approaches to this problem involve complex iterative minimization procedures, typically with high computational costs. In this paper is proposed a novel algorithm for super-resolution that enables a substantial decrease in computer load. First, a probabilistic neural network architecture is used to perform a scattered-point interpolation of the image sequence data. The network kernel function is optimally determined for this problem by a multi-layer perceptron trained on synthetic data. Network parameters dependence on sequence noise level is quantitatively analyzed. This super-sampled image is spatially filtered to correct finite pixel size effects, to yield the final high-resolution estimate. Results on a real outdoor sequence are presented, showing the quality of the proposed method.
Semi-automatic vectorization of linear networks on rasterized cartographic maps
Venue: arXiv cs.CV 2005
Year: 2005

A system for semi-automatic vectorization of linear networks (roads, rivers, etc.) on rasterized cartographic maps is presented. In this system, human intervention is limited to a graphic, interactive selection of the color attributes of the information to be obtained. Using this data, the system performs a preliminary extraction of the linear network, which is subsequently completed, refined and vectorized by means of an automatic procedure. Results on maps of different sources and scales are included. ----- Se presenta un sistema semi-automatico de vectorizacion de redes de objetos lineales (carreteras, rios, etc.) en mapas cartograficos digitalizados. En este sistema, la intervencion humana queda reducida a la seleccion grafica interactiva de los atributos de color de la informacion a obtener. Con estos datos, el sistema realiza una extraccion preliminar de la red lineal, que se completa, refina y vectoriza mediante un procedimiento automatico. Se presentan resultados de la aplicacion del sistema sobre imagenes digitalizadas de mapas de distinta procedencia y escala.
Integrity Constraints in Trust Management
Venue: arXiv cs.CR 2005
Year: 2005

We introduce the use, monitoring, and enforcement of integrity constraints in trust management-style authorization systems. We consider what portions of the policy state must be monitored to detect violations of integrity constraints. Then we address the fact that not all participants in a trust management system can be trusted to assist in such monitoring, and show how many integrity constraints can be monitored in a conservative manner so that trusted participants detect and report if the system enters a policy state from which evolution in unmonitored portions of the policy could lead to a constraint violation.
Data-Structure Rewriting
Venue: arXiv cs.PL 2005
Year: 2005

We tackle the problem of data-structure rewriting including pointer redirections. We propose two basic rewrite steps: (i) Local Redirection and Replacement steps the aim of which is redirecting specific pointers determined by means of a pattern, as well as adding new information to an existing data ; and (ii) Global Redirection steps which are aimed to redirect all pointers targeting a node towards another one. We define these two rewriting steps following the double pushout approach. We define first the category of graphs we consider and then define rewrite rules as pairs of graph homomorphisms of the form "L <- K ->R". Unfortunately, inverse pushouts (complement pushouts) are not unique in our setting and pushouts do not always exist. Therefore, we define rewriting steps so that a rewrite rule can always be performed once a matching is found.
Consistency in Models for Distributed Learning under Communication Constraints
Venue: arXiv cs.IT 2005
Year: 2005

Motivated by sensor networks and other distributed settings, several models for distributed learning are presented. The models differ from classical works in statistical pattern recognition by allocating observations of an independent and identically distributed (i.i.d.) sampling process amongst members of a network of simple learning agents. The agents are limited in their ability to communicate to a central fusion center and thus, the amount of information available for use in classification or regression is constrained. For several basic communication models in both the binary classification and regression frameworks, we question the existence of agent decision rules and fusion rules that result in a universally consistent ensemble. The answers to this question present new issues to consider with regard to universal consistency. Insofar as these models present a useful picture of distributed scenarios, this paper addresses the issue of whether or not the guarantees provided by Stone's Theorem in centralized environments hold in distributed settings.