OpenRaiser/Intern-Atlas huggingface dataset:
Indexing of Tables Referencing Complex Structures
Venue: arXiv cs.DB 2003
Year: 2003

We introduce indexing of tables referencing complex structures such as digraphs and spatial objects, appearing in genetics and other data intensive analysis. The indexing is achieved by extracting dimension schemas from the referenced structures. The schemas and their dimensionality are determined by proper coloring algorithms and the duality between all such schemas and all such possible proper colorings is established. This duality, in turn, provides us with an extensive library of solutions when addressing indexing questions. It is illustrated how to use the schemas, in connection with additional relational database technologies, to optimize queries conditioned on the structural information being referenced. Comparisons using bitmap indexing in the Oracle 9.2i database, on the one hand, and multidimensional clustering in DB2 8.1.2, on the other hand, are used to illustrate the applicability of the indexing to different technology settings. Finally, we illustrate how the indexing can be used to extract low dimensional schemas from a binary interval tree in order to resolve efficiently interval and stabbing queries.
Exploration of RNA Editing and Design of Robust Genetic Algorithms
Venue: arXiv cs.NE 2003
Year: 2003

This paper presents our computational methodology using Genetic Algorithms (GA) for exploring the nature of RNA editing. These models are constructed using several genetic editing characteristics that are gleaned from the RNA editing system as observed in several organisms. We have expanded the traditional Genetic Algorithm with artificial editing mechanisms as proposed by (Rocha, 1997). The incorporation of editing mechanisms provides a means for artificial agents with genetic descriptions to gain greater phenotypic plasticity, which may be environmentally regulated. Our first implementations of these ideas have shed some light into the evolutionary implications of RNA editing. Based on these understandings, we demonstrate how to select proper RNA editors for designing more robust GAs, and the results will show promising applications to real-world problems. We expect that the framework proposed will both facilitate determining the evolutionary role of RNA editing in biology, and advance the current state of research in Genetic Algorithms.
Proposed Specification of a Distributed XML-Query Network
Venue: arXiv cs.DC 2003
Year: 2003

W3C's XML-Query language offers a powerful instrument for information retrieval on XML repositories. This article describes an implementation of this retrieval in a real world's scenario. Distributed XML-Query processing reduces load on every single attending node to an acceptable level. The network allows every participant to control their computing load themselves. Furthermore XML-repositories may stay at the rights holder, so every Data-Provider can decide, whether to process critical queries or not. If Data-Providers keep redundant information, this distributed network improves reliability of information with duplicates removed.
A Neural Network Assembly Memory Model Based on an Optimal Binary Signal Detection Theory
Venue: arXiv cs.AI 2003
Year: 2003

A ternary/binary data coding algorithm and conditions under which Hopfield networks implement optimal convolutional or Hamming decoding algorithms has been described. Using the coding/decoding approach (an optimal Binary Signal Detection Theory, BSDT) introduced a Neural Network Assembly Memory Model (NNAMM) is built. The model provides optimal (the best) basic memory performance and demands the use of a new memory unit architecture with two-layer Hopfield network, N-channel time gate, auxiliary reference memory, and two nested feedback loops. NNAMM explicitly describes the dependence on time of a memory trace retrieval, gives a possibility of metamemory simulation, generalized knowledge representation, and distinct description of conscious and unconscious mental processes. A model of smallest inseparable part or an "atom" of consciousness is also defined. The NNAMM's neurobiological backgrounds and its applications to solving some interdisciplinary problems are shortly discussed. BSDT could implement the "best neural code" used in nervous tissues of animals and humans.
A distributed algorithm to find k-dominating sets
Venue: arXiv cs.DC 2003
Year: 2003

We consider a connected undirected graph $G(n,m)$ with $n$ nodes and $m$ edges. A $k$-dominating set $D$ in $G$ is a set of nodes having the property that every node in $G$ is at most $k$ edges away from at least one node in $D$. Finding a $k$-dominating set of minimum size is NP-hard. We give a new synchronous distributed algorithm to find a $k$-dominating set in $G$ of size no greater than $\lfloor n/(k+1)\rfloor$. Our algorithm requires $O(k\log^*n)$ time and $O(m\log k+n\log k\log^*n)$ messages to run. It has the same time complexity as the best currently known algorithm, but improves on that algorithm's message complexity and is, in addition, conceptually simpler.
On reducing the complexity of matrix clocks
Venue: arXiv cs.DC 2003
Year: 2003

Matrix clocks are a generalization of the notion of vector clocks that allows the local representation of causal precedence to reach into an asynchronous distributed computation's past with depth $x$, where $x\ge 1$ is an integer. Maintaining matrix clocks correctly in a system of $n$ nodes requires that everymessage be accompanied by $O(n^x)$ numbers, which reflects an exponential dependency of the complexity of matrix clocks upon the desired depth $x$. We introduce a novel type of matrix clock, one that requires only $nx$ numbers to be attached to each message while maintaining what for many applications may be the most significant portion of the information that the original matrix clock carries. In order to illustrate the new clock's applicability, we demonstrate its use in the monitoring of certain resource-sharing computations.
A uniform approach to constraint-solving for lists, multisets, compact lists, and sets
Venue: arXiv cs.PL 2003
Year: 2003

Lists, multisets, and sets are well-known data structures whose usefulness is widely recognized in various areas of Computer Science. These data structures have been analyzed from an axiomatic point of view with a parametric approach in (*) where the relevant unification algorithms have been developed. In this paper we extend these results considering more general constraints including not only equality but also membership constraints as well as their negative counterparts. (*) A. Dovier, A. Policriti, and G. Rossi. A uniform axiomatic view of lists, multisets, and sets, and the relevant unification algorithms. Fundamenta Informaticae, 36(2/3):201--234, 1998.
The Liar and Related Paradoxes: Fuzzy Truth Value Assignment for Collections of Self-Referential Sentences
Venue: arXiv cs.LO 2003
Year: 2003

We study self-referential sentences of the type related to the Liar paradox. In particular, we consider the problem of assigning consistent fuzzy truth values to collections of self-referential sentences. We show that the problem can be reduced to the solution of a system of nonlinear equations. Furthermore, we prove that, under mild conditions, such a system always has a solution (i.e. a consistent truth value assignment) and that, for a particular implementation of logical ``and'', ``or'' and ``negation'', the ``mid-point'' solution is always consistent. Next we turn to computational issues and present several truth-value assignment algorithms; we argue that these algorithms can be understood as generalized sequential reasoning. In an Appendix we present a large number of examples of self-referential collections (including the Liar and the Strengthened Liar), we formulate the corresponding truth value equations and solve them analytically and/ or numerically.
Effective XML Representation for Spoken Language in Organisations
Venue: arXiv cs.CL 2003
Year: 2003

Spoken Language can be used to provide insights into organisational processes, unfortunately transcription and coding stages are very time consuming and expensive. The concept of partial transcription and coding is proposed in which spoken language is indexed prior to any subsequent processing. The functional linguistic theory of texture is used to describe the effects of partial transcription on observational records. The standard used to encode transcript context and metadata is called CHAT, but a previous XML schema developed to implement it contains design assumptions that make it difficult to support partial transcription for example. This paper describes a more effective XML schema that overcomes many of these problems and is intended for use in applications that support the rapid development of spoken language deliverables.
Availability Guarantee for Deterministic Replay Starting Points in Real-Time Systems
Venue: arXiv cs.SE 2003
Year: 2003

Cyclic debugging requires repeatable executions. As non-deterministic or real-time systems typically do not have the potential to provide this, special methods are required. One such method is replay, a process that requires monitoring of a running system and logging of the data produced by that monitoring. We shall discuss the process of preparing the replay, a part of the process that has not been very well described before.
Generalized Systematic Debugging for Attribute Grammars
Venue: arXiv cs.SE 2003
Year: 2003

Attribute grammars (AGs) are known to be a useful formalism for semantic analysis and translation. However, debugging AGs is complex owing to inherent difficulties of AGs, such as recursive grammar structure and attribute dependency. In this paper, a new systematic method of debugging AGs is proposed. Our approach is, in principle, based on previously proposed algorithmic debugging of AGs, but is more general. This easily enables integration of various query-based systematic debugging methods, including the slice-based method. The proposed method has been implemented in Aki, a debugger for AG description. We evaluated our new approach experimentally using Aki, which demonstrates the usability of our debugging method.
A weak definition of Delaunay triangulation
Venue: arXiv cs.CG 2003
Year: 2003

We show that the traditional criterion for a simplex to belong to the Delaunay triangulation of a point set is equivalent to a criterion which is a priori weaker. The argument is quite general; as well as the classical Euclidean case, it applies to hyperbolic and hemispherical geometries and to Edelsbrunner's weighted Delaunay triangulation. In spherical geometry, we establish a similar theorem under a genericity condition. The weak definition finds natural application in the problem of approximating a point-cloud data set with a simplical complex.
On Addressing Efficiency Concerns in Privacy Preserving Data Mining
Venue: arXiv cs.DB 2003
Year: 2003

Data mining services require accurate input data for their results to be meaningful, but privacy concerns may influence users to provide spurious information. To encourage users to provide correct inputs, we recently proposed a data distortion scheme for association rule mining that simultaneously provides both privacy to the user and accuracy in the mining results. However, mining the distorted database can be orders of magnitude more time-consuming as compared to mining the original database. In this paper, we address this issue and demonstrate that by (a) generalizing the distortion process to perform symbol-specific distortion, (b) appropriately choosing the distortion parameters, and (c) applying a variety of optimizations in the reconstruction process, runtime efficiencies that are well within an order of magnitude of undistorted mining can be achieved.
A Dynamic Programming Algorithm for the Segmentation of Greek Texts
Venue: arXiv cs.CL 2003
Year: 2003

In this paper we introduce a dynamic programming algorithm to perform linear text segmentation by global minimization of a segmentation cost function which consists of: (a) within-segment word similarity and (b) prior information about segment length. The evaluation of the segmentation accuracy of the algorithm on a text collection consisting of Greek texts showed that the algorithm achieves high segmentation accuracy and appears to be very innovating and promissing.
An O(m) Algorithm for Cores Decomposition of Networks
Venue: arXiv cs.DS 2003
Year: 2003

The structure of large networks can be revealed by partitioning them to smaller parts, which are easier to handle. One of such decompositions is based on $k$--cores, proposed in 1983 by Seidman. In the paper an efficient, $O(m)$, $m$ is the number of lines, algorithm for determining the cores decomposition of a given network is presented.
Local-search techniques for propositional logic extended with cardinality constraints
Venue: arXiv cs.AI 2003
Year: 2003

We study local-search satisfiability solvers for propositional logic extended with cardinality atoms, that is, expressions that provide explicit ways to model constraints on cardinalities of sets. Adding cardinality atoms to the language of propositional logic facilitates modeling search problems and often results in concise encodings. We propose two ``native'' local-search solvers for theories in the extended language. We also describe techniques to reduce the problem to standard propositional satisfiability and allow us to use off-the-shelf SAT solvers. We study these methods experimentally. Our general finding is that native solvers designed specifically for the extended language perform better than indirect methods relying on SAT solvers.
Utility-Probability Duality
Venue: arXiv cs.AI 2003
Year: 2003

This paper presents duality between probability distributions and utility functions.
On The Cost Distribution of a Memory Bound Function
Venue: arXiv cs.CR 2003
Year: 2003

Memory Bound Functions have been proposed for fighting spam, resisting Sybil attacks and other purposes. A particular implementation of such functions has been proposed in which the average effort required to generate a proof of effort is set by parameters E and l to E * l. The distribution of effort required to generate an individual proof about this average is fairly broad. When particular uses of these functions are envisaged, the choice of E and l, and the system design surrounding the generation and verification of proofs of effort, need to take the breadth of the distribution into account. We show the distribution for this implementation, discuss the system design issues in the context of two proposed applications, and suggest an improved implementation.
Replay Debugging of Complex Real-Time Systems: Experiences from Two Industrial Case Studies
Venue: arXiv cs.RO 2003
Year: 2003

Deterministic replay is a method for allowing complex multitasking real-time systems to be debugged using standard interactive debuggers. Even though several replay techniques have been proposed for parallel, multi-tasking and real-time systems, the solutions have so far lingered on a prototype academic level, with very little results to show from actual state-of-the-practice commercial applications. This paper describes a major deterministic replay debugging case study performed on a full-scale industrial robot control system, as well as a minor replay instrumentation case study performed on a military aircraft radar system. In this article, we will show that replay debugging is feasible in complex multi-million lines of code software projects running on top of off-the-shelf real-time operating systems. Furthermore, we will discuss how replay debugging can be introduced in existing systems without impracticable analysis efforts. In addition, we will present benchmarking results from both studies, indicating that the instrumentation overhead is acceptable and affordable.
Visualization of variations in human brain morphology using differentiating reflection functions
Venue: arXiv cs.GR 2003
Year: 2003

Conventional visualization media such as MRI prints and computer screens are inherently two dimensional, making them incapable of displaying true 3D volume data sets. By applying only transparency or intensity projection, and ignoring light-matter interaction, results will likely fail to give optimal results. Little research has been done on using reflectance functions to visually separate the various segments of a MRI volume. We will explore if applying specific reflectance functions to individual anatomical structures can help in building an intuitive 2D image from a 3D dataset. We will test our hypothesis by visualizing a statistical analysis of the genetic influences on variations in human brain morphology because it inherently contains complex and many different types of data making it a good candidate for our approach
Measuring the Functional Load of Phonological Contrasts
Venue: arXiv cs.CL 2003
Year: 2003

Frequency counts are a measure of how much use a language makes of a linguistic unit, such as a phoneme or word. However, what is often important is not the units themselves, but the contrasts between them. A measure is therefore needed for how much use a language makes of a contrast, i.e. the functional load (FL) of the contrast. We generalize previous work in linguistics and speech recognition and propose a family of measures for the FL of several phonological contrasts, including phonemic oppositions, distinctive features, suprasegmentals, and phonological rules. We then test it for robustness to changes of corpora. Finally, we provide examples in Cantonese, Dutch, English, German and Mandarin, in the context of historical linguistics, language acquisition and speech recognition. More information can be found at http://dinoj.info/research/fload
Copyright and Creativity: Authors and Photographers
Venue: arXiv cs.CY 2003
Year: 2003

The history of the occupations "author" and "photographer" provides an insightful perspective on copyright and creativity. The concept of the romantic author, associated with personal creative genius, gained prominence in the eighteenth century. However, in the U.S. in 1900 only about three thousand persons professed their occupation to be "author." Self-professed "photographers" were then about ten times as numerous as authors. Being a photographer was associated with manufacturing and depended only on mastering technical skills and making a living. Being an author, in contrast, was an elite status associated with science and literature. Across the twentieth century, the number of writers and authors grew much more rapidly than the number of photographers. The relative success of writers and authors in creating jobs seems to have depended not on differences in copyright or possibilities for self-production, but on greater occupational innovation. Creativity in organizing daily work is an important form of creativity.
On Structuring Proof Search for First Order Linear Logic
Venue: arXiv cs.LO 2003
Year: 2003

Full first order linear logic can be presented as an abstract logic programming language in Miller's system Forum, which yields a sensible operational interpretation in the 'proof search as computation' paradigm. However, Forum still has to deal with syntactic details that would normally be ignored by a reasonable operational semantics. In this respect, Forum improves on Gentzen systems for linear logic by restricting the language and the form of inference rules. We further improve on Forum by restricting the class of formulae allowed, in a system we call G-Forum, which is still equivalent to full first order linear logic. The only formulae allowed in G-Forum have the same shape as Forum sequents: the restriction does not diminish expressiveness and makes G-Forum amenable to proof theoretic analysis. G-Forum consists of two (big) inference rules, for which we show a cut elimination procedure. This does not need to appeal to finer detail in formulae and sequents than is provided by G-Forum, thus successfully testing the internal symmetries of our system.
Taking the Initiative with Extempore: Exploring Out-of-Turn Interactions with Websites
Venue: arXiv cs.HC 2003
Year: 2003

We present the first study to explore the use of out-of-turn interaction in websites. Out-of-turn interaction is a technique which empowers the user to supply unsolicited information while browsing. This approach helps flexibly bridge any mental mismatch between the user and the website, in a manner fundamentally different from faceted browsing and site-specific search tools. We built a user interface (Extempore) which accepts out-of-turn input via voice or text; and employed it in a US congressional website, to determine if users utilize out-of-turn interaction for information-finding tasks, and their rationale for doing so. The results indicate that users are adept at discerning when out-of-turn interaction is necessary in a particular task, and actively interleaved it with browsing. However, users found cascading information across information-finding subtasks challenging. Therefore, this work not only improves our understanding of out-of-turn interaction, but also suggests further opportunities to enrich browsing experiences for users.
GridEmail: A Case for Economically Regulated Internet-based Interpersonal Communications
Venue: arXiv cs.DC 2003
Year: 2003

Email has emerged as a dominant form of electronic communication between people. Spam is a major problem for email users, with estimates of up to 56% of email falling into that category. Control of Spam is being attempted with technical and legislative methods. In this paper we look at email and spam from a supply-demand perspective. We propose Gridemail, an email system based on an economy of communicating parties, where participants? motivations are represented as pricing policies and profiles. This system is expected to help people regulate their personal communications to suit their conditions, and help in removing unwanted messages.
Distributed WWW Programming using (Ciao-)Prolog and the PiLLoW library
Venue: arXiv cs.DC 2003
Year: 2003

We discuss from a practical point of view a number of issues involved in writing distributed Internet and WWW applications using LP/CLP systems. We describe PiLLoW, a public-domain Internet and WWW programming library for LP/CLP systems that we have designed in order to simplify the process of writing such applications. PiLLoW provides facilities for accessing documents and code on the WWW; parsing, manipulating and generating HTML and XML structured documents and data; producing HTML forms; writing form handlers and CGI-scripts; and processing HTML/XML templates. An important contribution of PiLLoW is to model HTML/XML code (and, thus, the content of WWW pages) as terms. The PiLLoW library has been developed in the context of the Ciao Prolog system, but it has been adapted to a number of popular LP/CLP systems, supporting most of its functionality. We also describe the use of concurrency and a high-level model of client-server interaction, Ciao Prolog's active modules, in the context of WWW programming. We propose a solution for client-side downloading and execution of Prolog code, using generic browsers. Finally, we also provide an overview of related work on the topic.
Using sensors in the web crawling process
Venue: arXiv cs.IR 2003
Year: 2003

This paper offers a short description of an Internet information field monitoring system, which places a special module-sensor on the side of the Web-server to detect changes in information resources and subsequently reindexes only the resources signalized by the corresponding sensor. Concise results of simulation research and an implementation attempt of the given "sensors" concept are provided.