title: Efficient Hashing with Lookups in two Memory Accesses

abstract: The study of hashing is closely related to the analysis of balls and bins. It is well-known that instead of using a single hash function if we randomly hash a ball into two bins and place it in the smaller of the two, then this dramatically lowers the maximum load on bins. This leads to the concept of two-way hashing where the largest bucket contains $O(\log\log n)$ balls with high probability. The hash look up will now search in both the buckets an item hashes to. Since an item may be placed in one of two buckets, we could potentially move an item after it has been initially placed to reduce maximum load. with a maximum load of We show that by performing moves during inserts, a maximum load of 2 can be maintained on-line, with high probability, while supporting hash update operations. In fact, with $n$ buckets, even if the space for two items are pre-allocated per bucket, as may be desirable in hardware implementations, more than $n$ items can be stored giving a high memory utilization. We also analyze the trade-off between the number of moves performed during inserts and the maximum load on a bucket. By performing at most $h$ moves, we can maintain a maximum load of $O(\frac{\log \log n}{h \log(\log\log n/h)})$. So, even by performing one move, we achieve a better bound than by performing no moves at all.


title: An agent-based intelligent environmental monitoring system

abstract: Fairly rapid environmental changes call for continuous surveillance and on-line decision making. There are two main areas where IT technologies can be valuable. In this paper we present a multi-agent system for monitoring and assessing air-quality attributes, which uses data coming from a meteorological station. A community of software agents is assigned to monitor and validate measurements coming from several sensors, to assess air-quality, and, finally, to fire alarms to appropriate recipients, when needed. Data mining techniques have been used for adding data-driven, customized intelligence into agents. The architecture of the developed system, its domain ontology, and typical agent interactions are presented. Finally, the deployment of a real-world test case is demonstrated.


title: An agent framework for dynamic agent retraining: Agent academy

abstract: Agent Academy (AA) aims to develop a multi-agent society that can train new agents for specific or general tasks, while constantly retraining existing agents in a recursive mode. The system is based on collecting information both from the environment and the behaviors of the acting agents and their related successes/failures to generate a body of data, stored in the Agent Use Repository, which is mined by the Data Miner module, in order to generate useful knowledge about the application domain. Knowledge extracted by the Data Miner is used by the Agent Training Module as to train new agents or to enhance the behavior of agents already running. In this paper the Agent Academy framework is introduced, and its overall architecture and functionality are presented. Training issues as well as agent ontologies are discussed. Finally, a scenario, which aims to provide environmental alerts to both individuals and public authorities, is described an AA-based use case.


title: Summarizing Encyclopedic Term Descriptions on the Web

abstract: We are developing an automatic method to compile an encyclopedic corpus from the Web. In our previous work, paragraph-style descriptions for a term are extracted from Web pages and organized based on domains. However, these descriptions are independent and do not comprise a condensed text as in hand-crafted encyclopedias. To resolve this problem, we propose a summarization method, which produces a single text from multiple descriptions. The resultant summary concisely describes a term from different viewpoints. We also show the effectiveness of our method by means of experiments.


title: Unsupervised Topic Adaptation for Lecture Speech Retrieval

abstract: We are developing a cross-media information retrieval system, in which users can view specific segments of lecture videos by submitting text queries. To produce a text index, the audio track is extracted from a lecture video and a transcription is generated by automatic speech recognition. In this paper, to improve the quality of our retrieval system, we extensively investigate the effects of adapting acoustic and language models on speech recognition. We perform an MLLR-based method to adapt an acoustic model. To obtain a corpus for language model adaptation, we use the textbook for a target lecture to search a Web collection for the pages associated with the lecture topic. We show the effectiveness of our method by means of experiments.


title: Effects of Language Modeling on Speech-driven Question Answering

abstract: We integrate automatic speech recognition (ASR) and question answering (QA) to realize a speech-driven QA system, and evaluate its performance. We adapt an N-gram language model to natural language questions, so that the input of our system can be recognized with a high accuracy. We target WH-questions which consist of the topic part and fixed phrase used to ask about something. We first produce a general N-gram model intended to recognize the topic and emphasize the counts of the N-grams that correspond to the fixed phrases. Given a transcription by the ASR engine, the QA engine extracts the answer candidates from target documents. We propose a passage retrieval method robust against recognition errors in the transcription. We use the QA test collection produced in NTCIR, which is a TREC-style evaluation workshop, and show the effectiveness of our method by means of experiments.


title: Static versus Dynamic Arbitrage Bounds on Multivariate Option Prices

abstract: We compare static arbitrage price bounds on basket calls, i.e. bounds that only involve buy-and-hold trading strategies, with the price range obtained within a multi-variate generalization of the Black-Scholes model. While there is no gap between these two sets of prices in the univariate case, we observe here that contrary to our intuition about model risk for at-the-money calls, there is a somewhat large gap between model prices and static arbitrage prices, hence a similarly large set of prices on which a multivariate Black-Scholes model cannot be calibrated but where no conclusion can be drawn on the presence or not of a static arbitrage opportunity.


title: Scheduling with Fuzzy Methods

abstract: Nowadays, manufacturing industries -- driven by fierce competition and rising customer requirements -- are forced to produce a broader range of individual products of rising quality at the same (or preferably lower) cost. Meeting these demands implies an even more complex production process and thus also an appropriately increasing request to its scheduling. Aggravatingly, vagueness of scheduling parameters -- such as times and conditions -- are often inherent in the production process. In addition, the search for an optimal schedule normally leads to very difficult problems (NP-hard problems in the complexity theoretical sense), which cannot be solved effciently. With the intent to minimize these problems, the introduced heuristic method combines standard scheduling methods with fuzzy methods to get a nearly optimal schedule within an appropriate time considering vagueness adequately.


title: On Modal Logics of Partial Recursive Functions

abstract: The classical propositional logic is known to be sound and complete with respect to the set semantics that interprets connectives as set operations. The paper extends propositional language by a new binary modality that corresponds to partial recursive function type constructor under the above interpretation. The cases of deterministic and non-deterministic functions are considered and for both of them semantically complete modal logics are described and decidability of these logics is established.


title: Exposing Software Defined Radio Functionality To Native Operating System Applications via Virtual Devices

abstract: Many reconfigurable platforms require that applications be written specifically to take advantage of the reconfigurable hardware. In a PC-based environment, this presents an undesirable constraint in that the many already available applications cannot leverage on such hardware. Greatest benefit can only be derived from reconfigurable devices if even native OS applications can transparently utilize reconfigurable devices as they would normal full-fledged hardware devices. This paper presents how Proteus Virtual Devices are used to expose reconfigurable hardware in a transparent manner for use by typical native OS applications.


title: Track Layouts of Graphs

abstract: A \emph{$(k,t)$-track layout} of a graph $G$ consists of a (proper) vertex $t$-colouring of $G$, a total order of each vertex colour class, and a (non-proper) edge $k$-colouring such that between each pair of colour classes no two monochromatic edges cross. This structure has recently arisen in the study of three-dimensional graph drawings. This paper presents the beginnings of a theory of track layouts. First we determine the maximum number of edges in a $(k,t)$-track layout, and show how to colour the edges given fixed linear orderings of the vertex colour classes. We then describe methods for the manipulation of track layouts. For example, we show how to decrease the number of edge colours in a track layout at the expense of increasing the number of tracks, and vice versa. We then study the relationship between track layouts and other models of graph layout, namely stack and queue layouts, and geometric thickness. One of our principle results is that the queue-number and track-number of a graph are tied, in the sense that one is bounded by a function of the other. As corollaries we prove that acyclic chromatic number is bounded by both queue-number and stack-number. Finally we consider track layouts of planar graphs. While it is an open problem whether planar graphs have bounded track-number, we prove bounds on the track-number of outerplanar graphs, and give the best known lower bound on the track-number of planar graphs.


title: On the Complexity of Case-Based Planning

abstract: We analyze the computational complexity of problems related to case-based planning: planning when a plan for a similar instance is known, and planning from a library of plans. We prove that planning from a single case has the same complexity than generative planning (i.e., planning "from scratch"); using an extended definition of cases, complexity is reduced if the domain stored in the case is similar to the one to search plans for. Planning from a library of cases is shown to have the same complexity. In both cases, the complexity of planning remains, in the worst case, PSPACE-complete.


title: A Framework for High-Accuracy Privacy-Preserving Mining

abstract: To preserve client privacy in the data mining process, a variety of techniques based on random perturbation of data records have been proposed recently. In this paper, we present a generalized matrix-theoretic model of random perturbation, which facilitates a systematic approach to the design of perturbation mechanisms for privacy-preserving mining. Specifically, we demonstrate that (a) the prior techniques differ only in their settings for the model parameters, and (b) through appropriate choice of parameter settings, we can derive new perturbation techniques that provide highly accurate mining results even under strict privacy guarantees. We also propose a novel perturbation mechanism wherein the model parameters are themselves characterized as random variables, and demonstrate that this feature provides significant improvements in privacy at a very marginal cost in accuracy. While our model is valid for random-perturbation-based privacy-preserving mining in general, we specifically evaluate its utility here with regard to frequent-itemset mining on a variety of real datasets. The experimental results indicate that our mechanisms incur substantially lower identity and support errors as compared to the prior techniques.


title: All Maximal Independent Sets and Dynamic Dominance for Sparse Graphs

abstract: We describe algorithms, based on Avis and Fukuda's reverse search paradigm, for listing all maximal independent sets in a sparse graph in polynomial time and delay per output. For bounded degree graphs, our algorithms take constant time per set generated; for minor-closed graph families, the time is O(n) per set, and for more general sparse graph families we achieve subquadratic time per set. We also describe new data structures for maintaining a dynamic vertex set S in a sparse or minor-closed graph family, and querying the number of vertices not dominated by S; for minor-closed graph families the time per update is constant, while it is sublinear for any sparse graph family. We can also maintain a dynamic vertex set in an arbitrary m-edge graph and test the independence of the maintained set in time O(sqrt m) per update. We use the domination data structures as part of our enumeration algorithms.


title: Generalized Evolutionary Algorithm based on Tsallis Statistics

abstract: Generalized evolutionary algorithm based on Tsallis canonical distribution is proposed. The algorithm uses Tsallis generalized canonical distribution to weigh the configurations for `selection' instead of Gibbs-Boltzmann distribution. Our simulation results show that for an appropriate choice of non-extensive index that is offered by Tsallis statistics, evolutionary algorithms based on this generalization outperform algorithms based on Gibbs-Boltzmann distribution.


title: Model Checking of Statechart Models: Survey and Research Directions

abstract: We survey existing approaches to the formal verification of statecharts using model checking. Although the semantics and subset of statecharts used in each approach varies considerably, along with the model checkers and their specification languages, most approaches rely on translating the hierarchical structure into the flat representation of the input language of the model checker. This makes model checking difficult to scale to industrial models, as the state space grows exponentially with flattening. We look at current approaches to model checking hierarchical structures and find that their semantics is significantly different from statecharts. We propose to address the problem of state space explosion using a combination of techniques, which are proposed as directions for further research.


title: On the Convergence Speed of MDL Predictions for Bernoulli Sequences

abstract: We consider the Minimum Description Length principle for online sequence prediction. If the underlying model class is discrete, then the total expected square loss is a particularly interesting performance measure: (a) this quantity is bounded, implying convergence with probability one, and (b) it additionally specifies a `rate of convergence'. Generally, for MDL only exponential loss bounds hold, as opposed to the linear bounds for a Bayes mixture. We show that this is even the case if the model class contains only Bernoulli distributions. We derive a new upper bound on the prediction error for countable Bernoulli classes. This implies a small bound (comparable to the one for Bayes mixtures) for certain important model classes. The results apply to many Machine Learning tasks including classification and hypothesis testing. We provide arguments that our theorems generalize to countable classes of i.i.d. models.


title: Decomposition Based Search - A theoretical and experimental evaluation

abstract: In this paper we present and evaluate a search strategy called Decomposition Based Search (DBS) which is based on two steps: subproblem generation and subproblem solution. The generation of subproblems is done through value ranking and domain splitting. Subdomains are explored so as to generate, according to the heuristic chosen, promising subproblems first. We show that two well known search strategies, Limited Discrepancy Search (LDS) and Iterative Broadening (IB), can be seen as special cases of DBS. First we present a tuning of DBS that visits the same search nodes as IB, but avoids restarts. Then we compare both theoretically and computationally DBS and LDS using the same heuristic. We prove that DBS has a higher probability of being successful than LDS on a comparable number of nodes, under realistic assumptions. Experiments on a constraint satisfaction problem and an optimization problem show that DBS is indeed very effective if compared to LDS.


title: Exploiting Semidefinite Relaxations in Constraint Programming

abstract: Constraint programming uses enumeration and search tree pruning to solve combinatorial optimization problems. In order to speed up this solution process, we investigate the use of semidefinite relaxations within constraint programming. In principle, we use the solution of a semidefinite relaxation to guide the traversal of the search tree, using a limited discrepancy search strategy. Furthermore, a semidefinite relaxation produces a bound for the solution value, which is used to prune parts of the search tree. Experimental results on stable set and maximum clique problem instances show that constraint programming can indeed greatly benefit from semidefinite relaxations.


title: Postponing Branching Decisions

abstract: Solution techniques for Constraint Satisfaction and Optimisation Problems often make use of backtrack search methods, exploiting variable and value ordering heuristics. In this paper, we propose and analyse a very simple method to apply in case the value ordering heuristic produces ties: postponing the branching decision. To this end, we group together values in a tie, branch on this sub-domain, and defer the decision among them to lower levels of the search tree. We show theoretically and experimentally that this simple modification can dramatically improve the efficiency of the search strategy. Although in practise similar methods may have been applied already, to our knowledge, no empirical or theoretical study has been proposed in the literature to identify when and to what extent this strategy should be used.


title: A Hyper-Arc Consistency Algorithm for the Soft Alldifferent Constraint

abstract: This paper presents an algorithm that achieves hyper-arc consistency for the soft alldifferent constraint. To this end, we prove and exploit the equivalence with a minimum-cost flow problem. Consistency of the constraint can be checked in O(nm) time, and hyper-arc consistency is achieved in O(m) time, where n is the number of variables involved and m is the sum of the cardinalities of the domains. It improves a previous method that did not ensure hyper-arc consistency.


title: Reduced cost-based ranking for generating promising subproblems

abstract: In this paper, we propose an effective search procedure that interleaves two steps: subproblem generation and subproblem solution. We mainly focus on the first part. It consists of a variable domain value ranking based on reduced costs. Exploiting the ranking, we generate, in a Limited Discrepancy Search tree, the most promising subproblems first. An interesting result is that reduced costs provide a very precise ranking that allows to almost always find the optimal solution in the first generated subproblem, even if its dimension is significantly smaller than that of the original problem. Concerning the proof of optimality, we exploit a way to increase the lower bound for subproblems at higher discrepancies. We show experimental results on the TSP and its time constrained variant to show the effectiveness of the proposed approach, but the technique could be generalized for other problems.


title: The First-Order Theory of Sets with Cardinality Constraints is Decidable

abstract: We show that the decidability of the first-order theory of the language that combines Boolean algebras of sets of uninterpreted elements with Presburger arithmetic operations. We thereby disprove a recent conjecture that this theory is undecidable. Our language allows relating the cardinalities of sets to the values of integer variables, and can distinguish finite and infinite sets. We use quantifier elimination to show the decidability and obtain an elementary upper bound on the complexity. Precise program analyses can use our decidability result to verify representation invariants of data structures that use an integer field to represent the number of stored elements.


title: A Bimachine Compiler for Ranked Tagging Rules

abstract: This paper describes a novel method of compiling ranked tagging rules into a deterministic finite-state device called a bimachine. The rules are formulated in the framework of regular rewrite operations and allow unrestricted regular expressions in both left and right rule contexts. The compiler is illustrated by an application within a speech synthesis system.


title: Channel-Independent and Sensor-Independent Stimulus Representations

abstract: This paper shows how a machine, which observes stimuli through an uncharacterized, uncalibrated channel and sensor, can glean machine-independent information (i.e., channel- and sensor-independent information) about the stimuli. First, we demonstrate that a machine defines a specific coordinate system on the stimulus state space, with the nature of that coordinate system depending on the device's channel and sensor. Thus, machines with different channels and sensors "see" the same stimulus trajectory through state space, but in different machine-specific coordinate systems. For a large variety of physical stimuli, statistical properties of that trajectory endow the stimulus configuration space with differential geometric structure (a metric and parallel transfer procedure), which can then be used to represent relative stimulus configurations in a coordinate-system-independent manner (and, therefore, in a channel- and sensor-independent manner). The resulting description is an "inner" property of the stimulus time series in the sense that it does not depend on extrinsic factors like the observer's choice of a coordinate system in which the stimulus is viewed (i.e., the observer's choice of channel and sensor). This methodology is illustrated with analytic examples and with a numerically simulated experiment. In an intelligent sensory device, this kind of representation "engine" could function as a "front-end" that passes channel/sensor-independent stimulus representations to a pattern recognition module. After a pattern recognizer has been trained in one of these devices, it could be used without change in other devices having different channels and sensors.


title: Technological networks and the spread of computer viruses

abstract: Computer infections such as viruses and worms spread over networks of contacts between computers, with different types of networks being exploited by different types of infections. Here we analyze the structures of several of these networks, exploring their implications for modes of spread and the control of infection. We argue that vaccination strategies that focus on a limited number of network nodes, whether targeted or randomly chosen, are in many cases unlikely to be effective. An alternative dynamic mechanism for the control of contagion, called throttling, is introduced and argued to be effective under a range of conditions.


title: Preferred Answer Sets for Ordered Logic Programs

abstract: We extend answer set semantics to deal with inconsistent programs (containing classical negation), by finding a ``best'' answer set. Within the context of inconsistent programs, it is natural to have a partial order on rules, representing a preference for satisfying certain rules, possibly at the cost of violating less important ones. We show that such a rule order induces a natural order on extended answer sets, the minimal elements of which we call preferred answer sets. We characterize the expressiveness of the resulting semantics and show that it can simulate negation as failure, disjunction and some other formalisms such as logic programs with ordered disjunction. The approach is shown to be useful in several application areas, e.g. repairing database, where minimal repairs correspond to preferred answer sets. To appear in Theory and Practice of Logic Programming (TPLP).


title: Modeling and Validating Hybrid Systems Using VDM and Mathematica

abstract: Hybrid systems are characterized by the hybrid evolution of their state: A part of the state changes discretely, the other part changes continuously over time. Typically, modern control applications belong to this class of systems, where a digital controller interacts with a physical environment. In this article we illustrate how a combination of the formal method VDM and the computer algebra system Mathematica can be used to model and simulate both aspects: the control logic and the physics involved. A new Mathematica package emulating VDM-SL has been developed that allows the integration of differential equation systems into formal specifications. The SAFER example from Kelly (1997) serves to demonstrate the new simulation capabilities Mathematica adds: After the thruster selection process, the astronaut's actual position and velocity is calculated by numerically solving Euler's and Newton's equations for rotation and translation. Furthermore, interactive validation is supported by a graphical user interface and data animation.


title: Bug shallowness in open-source, Macintosh software

abstract: Central to the power of open-source software is bug shallowness, the relative ease of finding and fixing bugs. The open-source movement began with Unix software, so many users were also programmers capable of finding and fixing bugs given the source code. But as the open-source movement reaches the Macintosh platform, bugs may not be shallow because few Macintosh users are programmers. Based on reports from open-source developers, I, however, conclude that that bugs are as shallow in open-source, Macintosh software as in any other open-source software.


title: M@th Desktop and MD Tools - Mathematics and Mathematica Made Easy for Students

abstract: We present two add-ons for Mathematica for teaching mathematics to undergraduate and high school students. These two applications, M@th Desktop (MD) and M@th Desktop Tools (MDTools), include several palettes and notebooks covering almost every field. The underlying didactic concept is so-called "blended learning", in which these tools are meant to be used as a complement to the professor or teacher rather than as a replacement, which other e-learning applications do. They enable students to avoid the usual problem of computer-based learning, namely that too large an amount of time is wasted struggling with computer and program errors instead of actually learning the mathematical concepts. M@th Desktop Tools is palette-based and provides easily accessible and user-friendly templates for the most important functions in the fields of Analysis, Algebra, Linear Algebra and Statistics. M@th Desktop, in contrast, is a modern, interactive teaching and learning software package for mathematics classes. It is comprised of modules for Differentiation, Integration, and Statistics, and each module presents its topic with a combination of interactive notebooks and palettes. Both packages can be obtained from Deltasoft's homepage at http://www.deltasoft.at/ .


title: Design of a Parallel and Distributed Web Search Engine

abstract: This paper describes the architecture of MOSE (My Own Search Engine), a scalable parallel and distributed engine for searching the web. MOSE was specifically designed to efficiently exploit affordable parallel architectures, such as clusters of workstations. Its modular and scalable architecture can easily be tuned to fulfill the bandwidth requirements of the application at hand. Both task-parallel and data-parallel approaches are exploited within MOSE in order to increase the throughput and efficiently use communication, storing and computational resources. We used a collection of html documents as a benchmark, and conducted preliminary experiments on a cluster of three SMP Linux PCs.


title: From truth to computability I

abstract: The recently initiated approach called computability logic is a formal theory of interactive computation. See a comprehensive online source on the subject at http://www.cis.upenn.edu/~giorgi/cl.html . The present paper contains a soundness and completeness proof for the deductive system CL3 which axiomatizes the most basic first-order fragment of computability logic called the finite-depth, elementary-base fragment. Among the potential application areas for this result are the theory of interactive computation, constructive applied theories, knowledgebase systems, systems for resource-bound planning and action. This paper is self-contained as it reintroduces all relevant definitions as well as main motivations.


title: PELCR: Parallel Environment for Optimal Lambda-Calculus Reduction

abstract: In this article we present the implementation of an environment supporting L\'evy's \emph{optimal reduction} for the $\lambda$-calculus \cite{Lev78} on parallel (or distributed) computing systems. In a similar approach to Lamping's one in \cite{Lamping90}, we base our work on a graph reduction technique known as \emph{directed virtual reduction} \cite{DPR97} which is actually a restriction of Danos-Regnier virtual reduction \cite{DanosRegnier93}. The environment, which we refer to as PELCR (Parallel Environment for optimal Lambda-Calculus Reduction) relies on a strategy for directed virtual reduction, namely {\em half combustion}, which we introduce in this article. While developing PELCR we have adopted both a message aggregation technique, allowing a reduction of the communication overhead, and a fair policy for distributing dynamically originated load among processors. We also present an experimental study demonstrating the ability of PELCR to definitely exploit parallelism intrinsic to $\lambda$-terms while performing the reduction. By the results we show how PELCR allows achieving up to 70/80% of the ideal speedup on last generation multiprocessor computing systems. As a last note, the software modules have been developed with the {\tt C} language and using a standard interface for message passing, i.e. MPI, thus making PELCR itself a highly portable software package.


title: On the hardness of distinguishing mixed-state quantum computations

abstract: This paper considers the following problem. Two mixed-state quantum circuits Q and R are given, and the goal is to determine which of two possibilities holds: (i) Q and R act nearly identically on all possible quantum state inputs, or (ii) there exists some input state that Q and R transform into almost perfectly distinguishable outputs. This problem may be viewed as an abstraction of the following problem: given two physical processes described by sequences of local interactions, are the processes effectively the same or are they different? We prove that this problem is a complete promise problem for the class QIP of problems having quantum interactive proof systems, and is therefore PSPACE-hard. This is in sharp contrast to the fact that the analogous problem for classical (probabilistic) circuits is in AM, and for unitary quantum circuits is in QMA.


title: Universal Convergence of Semimeasures on Individual Random Sequences

abstract: Solomonoff's central result on induction is that the posterior of a universal semimeasure M converges rapidly and with probability 1 to the true sequence generating posterior mu, if the latter is computable. Hence, M is eligible as a universal sequence predictor in case of unknown mu. Despite some nearby results and proofs in the literature, the stronger result of convergence for all (Martin-Loef) random sequences remained open. Such a convergence result would be particularly interesting and natural, since randomness can be defined in terms of M itself. We show that there are universal semimeasures M which do not converge for all random sequences, i.e. we give a partial negative answer to the open problem. We also provide a positive answer for some non-universal semimeasures. We define the incomputable measure D as a mixture over all computable measures and the enumerable semimeasure W as a mixture over all enumerable nearly-measures. We show that W converges to D and D to mu on all random sequences. The Hellinger distance measuring closeness of two distributions plays a central role.


title: Communication-Aware Processor Allocation for Supercomputers

abstract: This paper gives processor-allocation algorithms for minimizing the average number of communication hops between the assigned processors for grid architectures, in the presence of occupied cells. The simpler problem of assigning processors on a free grid has been studied by Karp, McKellar, and Wong who show that the solutions have nontrivial structure; they left open the complexity of the problem. The associated clustering problem is as follows: Given n points in Re^d, find k points that minimize their average pairwise L1 distance. We present a natural approximation algorithm and show that it is a 7/4-approximation for 2D grids. For d-dimensional space, the approximation guarantee is 2-(1/2d), which is tight. We also give a polynomial-time approximation scheme (PTAS) for constant dimension d, and report on experimental results.


title: On rational definite summation

abstract: We present a partial proof of van Hoeij-Abramov conjecture about the algorithmic possibility of computation of finite sums of rational functions. The theoretical results proved in this paper provide an algorithm for computation of a large class of sums $ S(n) = \sum_{k=0}^{n-1}R(k,n)$.


title: Tight bounds for LDPC and LDGM codes under MAP decoding

abstract: A new method for analyzing low density parity check (LDPC) codes and low density generator matrix (LDGM) codes under bit maximum a posteriori probability (MAP) decoding is introduced. The method is based on a rigorous approach to spin glasses developed by Francesco Guerra. It allows to construct lower bounds on the entropy of the transmitted message conditional to the received one. Based on heuristic statistical mechanics calculations, we conjecture such bounds to be tight. The result holds for standard irregular ensembles when used over binary input output symmetric channels. The method is first developed for Tanner graph ensembles with Poisson left degree distribution. It is then generalized to `multi-Poisson' graphs, and, by a completion procedure, to arbitrary degree distribution.


title: A measure of similarity between graph vertices

abstract: We introduce a concept of similarity between vertices of directed graphs. Let G_A and G_B be two directed graphs. We define a similarity matrix whose (i, j)-th real entry expresses how similar vertex j (in G_A) is to vertex i (in G_B. The similarity matrix can be obtained as the limit of the normalized even iterates of a linear transformation. In the special case where G_A=G_B=G, the matrix is square and the (i, j)-th entry is the similarity score between the vertices i and j of G. We point out that Kleinberg's "hub and authority" method to identify web-pages relevant to a given query can be viewed as a special case of our definition in the case where one of the graphs has two vertices and a unique directed edge between them. In analogy to Kleinberg, we show that our similarity scores are given by the components of a dominant eigenvector of a non-negative matrix. Potential applications of our similarity concept are numerous. We illustrate an application for the automatic extraction of synonyms in a monolingual dictionary.

categories: cs.IR cond-mat.dis-nn cs.DM physics.data-an


title: Performance Analysis of the Globus Toolkit Monitoring and Discovery Service, MDS2

abstract: Monitoring and information services form a key component of a distributed system, or Grid. A quantitative study of such services can aid in understanding the performance limitations, advise in the deployment of the monitoring system, and help evaluate future development work. To this end, we examined the performance of the Globus Toolkit(reg. trdmrk) Monitoring and Discovery Service (MDS2) by instrumenting its main services using NetLogger. Our study shows a strong advantage to caching or prefetching the data, as well as the need to have primary components at well-connected sites.


title: Unfolding Smooth Prismatoids

abstract: We define a notion for unfolding smooth, ruled surfaces, and prove that every smooth prismatoid (the convex hull of two smooth curves lying in parallel planes), has a nonoverlapping "volcano unfolding." These unfoldings keep the base intact, unfold the sides outward, splayed around the base, and attach the top to the tip of some side rib. Our result answers a question for smooth prismatoids whose analog for polyhedral prismatoids remains unsolved.


title: A Sequent Calculus and a Theorem Prover for Standard Conditional Logics

abstract: In this paper we present a cut-free sequent calculus, called SeqS, for some standard conditional logics, namely CK, CK+ID, CK+MP and CK+MP+ID. The calculus uses labels and transition formulas and can be used to prove decidability and space complexity bounds for the respective logics. We also present CondLean, a theorem prover for these logics implementing SeqS calculi written in SICStus Prolog.


title: Word Sense Disambiguation by Web Mining for Word Co-occurrence Probabilities

abstract: This paper describes the National Research Council (NRC) Word Sense Disambiguation (WSD) system, as applied to the English Lexical Sample (ELS) task in Senseval-3. The NRC system approaches WSD as a classical supervised machine learning problem, using familiar tools such as the Weka machine learning software and Brill's rule-based part-of-speech tagger. Head words are represented as feature vectors with several hundred features. Approximately half of the features are syntactic and the other half are semantic. The main novelty in the system is the method for generating the semantic features, based on word \hbox{co-occurrence} probabilities. The probabilities are estimated using the Waterloo MultiText System with a corpus of about one terabyte of unlabeled text, collected by a web crawler.


title: ParFORM: Parallel Version of the Symbolic Manipulation Program FORM

abstract: After an introduction to the sequential version of FORM and the mechanisms behind, we report on the status of our project of parallelization. We have now a parallel version of FORM running on Cluster- and SMP-architectures. This version can be used to run arbitrary FORM programs in parallel.


title: Semantic Linking - a Context-Based Approach to Interactivity in Hypermedia

abstract: The semantic Web initiates new, high level access schemes to online content and applications. One area of superior need for a redefined content exploration is given by on-line educational applications and their concepts of interactivity in the framework of open hypermedia systems. In the present paper we discuss aspects and opportunities of gaining interactivity schemes from semantic notions of components. A transition from standard educational annotation to semantic statements of hyperlinks is discussed. Further on we introduce the concept of semantic link contexts as an approach to manage a coherent rhetoric of linking. A practical implementation is introduced, as well. Our semantic hyperlink implementation is based on the more general Multimedia Information Repository MIR, an open hypermedia system supporting the standards XML, Corba and JNDI.


title: Roaming Real-Time Applications - Mobility Services in IPv6 Networks

abstract: Emerging mobility standards within the next generation Internet Protocol, IPv6, promise to continuously operate devices roaming between IP networks. Associated with the paradigm of ubiquitous computing and communication, network technology is on the spot to deliver voice and videoconferencing as a standard internet solution. However, current roaming procedures are too slow, to remain seamless for real-time applications. Multicast mobility still waits for a convincing design. This paper investigates the temporal behaviour of mobile IPv6 with dedicated focus on topological impacts. Extending the hierarchical mobile IPv6 approach we suggest protocol improvements for a continuous handover, which may serve bidirectional multicast communication, as well. Along this line a multicast mobility concept is introduced as a service for clients and sources, as they are of dedicated importance in multipoint conferencing applications. The mechanisms introduced do not rely on assumptions of any specific multicast routing protocol in use.


title: Multi-Embedding of Metric Spaces

abstract: Metric embedding has become a common technique in the design of algorithms. Its applicability is often dependent on how high the embedding's distortion is. For example, embedding finite metric space into trees may require linear distortion as a function of its size. Using probabilistic metric embeddings, the bound on the distortion reduces to logarithmic in the size. We make a step in the direction of bypassing the lower bound on the distortion in terms of the size of the metric. We define "multi-embeddings" of metric spaces in which a point is mapped onto a set of points, while keeping the target metric of polynomial size and preserving the distortion of paths. The distortion obtained with such multi-embeddings into ultrametrics is at most O(log Delta loglog Delta) where Delta is the aspect ratio of the metric. In particular, for expander graphs, we are able to obtain constant distortion embeddings into trees in contrast with the Omega(log n) lower bound for all previous notions of embeddings. We demonstrate the algorithmic application of the new embeddings for two optimization problems: group Steiner tree and metrical task systems.


title: Hypermedia Learning Objects System - On the Way to a Semantic Educational Web

abstract: While eLearning systems become more and more popular in daily education, available applications lack opportunities to structure, annotate and manage their contents in a high-level fashion. General efforts to improve these deficits are taken by initiatives to define rich meta data sets and a semanticWeb layer. In the present paper we introduce Hylos, an online learning system. Hylos is based on a cellular eLearning Object (ELO) information model encapsulating meta data conforming to the LOM standard. Content management is provisioned on this semantic meta data level and allows for variable, dynamically adaptable access structures. Context aware multifunctional links permit a systematic navigation depending on the learners and didactic needs, thereby exploring the capabilities of the semantic web. Hylos is built upon the more general Multimedia Information Repository (MIR) and the MIR adaptive context linking environment (MIRaCLE), its linking extension. MIR is an open system supporting the standards XML, Corba and JNDI. Hylos benefits from manageable information structures, sophisticated access logic and high-level authoring tools like the ELO editor responsible for the semi-manual creation of meta data and WYSIWYG like content editing.


title: Educational Content Management - A Cellular Approach

abstract: In recent times online educational applications more and more are requested to provide self-consistent learning offers for students at the university level. Consequently they need to cope with the wide range of complexity and interrelations university course teaching brings along. An urgent need to overcome simplistically linked HTMLc ontent pages becomes apparent. In the present paper we discuss a schematic concept of educational content construction from information cells and introduce its implementation on the storage and runtime layer. Starting from cells content is annotated according to didactic needs, structured for dynamic arrangement, dynamically decorated with hyperlinks and, as all works are based on XML, open to any presentation layer. Data can be variably accessed through URIs built on semantic path-names and edited via an adaptive authoring toolbox. Our content management approach is based on the more general Multimedia Information Repository MIR. and allows for personalisation, as well. MIR is an open system supporting the standards XML, Corba and JNDI.


title: Why Two Sexes?

abstract: Evolutionary role of the separation into two sexes from a cyberneticist's point of view. [I translated this 1965 article from Russian "Nauka i Zhizn" (Science and Life) in 1988. In a popular form, the article puts forward several useful ideas not all of which even today are necessarily well known or widely accepted. Boris Lubachevsky, bdl@bell-labs.com ]


title: Online convex optimization in the bandit setting: gradient descent without a gradient

abstract: We consider a the general online convex optimization framework introduced by Zinkevich. In this setting, there is a sequence of convex functions. Each period, we must choose a signle point (from some feasible set) and pay a cost equal to the value of the next function on our chosen point. Zinkevich shows that, if the each function is revealed after the choice is made, then one can achieve vanishingly small regret relative the best single decision chosen in hindsight. We extend this to the bandit setting where we do not find out the entire functions but rather just their value at our chosen point. We show how to get vanishingly small regret in this setting. Our approach uses a simple approximation of the gradient that is computed from evaluating a function at a single (random) point. We show that this estimate is sufficient to mimic Zinkevich's gradient descent online analysis, with access to the gradient (only being able to evaluate the function at a single point).


title: Iterative Quantization Using Codes On Graphs

abstract: We study codes on graphs combined with an iterative message passing algorithm for quantization. Specifically, we consider the binary erasure quantization (BEQ) problem which is the dual of the binary erasure channel (BEC) coding problem. We show that duals of capacity achieving codes for the BEC yield codes which approach the minimum possible rate for the BEQ. In contrast, low density parity check codes cannot achieve the minimum rate unless their density grows at least logarithmically with block length. Furthermore, we show that duals of efficient iterative decoding algorithms for the BEC yield efficient encoding algorithms for the BEQ. Hence our results suggest that graphical models may yield near optimal codes in source coding as well as in channel coding and that duality plays a key role in such constructions.


title: Performance Analysis of Multicast Mobility in a Hierarchical Mobile IP Proxy Environment

abstract: Mobility support in IPv6 networks is ready for release as an RFC, stimulating major discussions on improvements to meet real-time communication requirements. Sprawling hot spots of IP-only wireless networks at the same time await voice and videoconferencing as standard mobile Internet services, thereby adding the request for multicast support to real-time mobility. This paper briefly introduces current approaches for seamless multicast extensions to Mobile IPv6. Key issues of multicast mobility are discussed. Both analytically and in simulations comparisons are drawn between handover performance characteristics, dedicating special focus on the M-HMIPv6 approach.


title: A Simple Proportional Conflict Redistribution Rule

abstract: One proposes a first alternative rule of combination to WAO (Weighted Average Operator) proposed recently by Josang, Daniel and Vannoorenberghe, called Proportional Conflict Redistribution rule (denoted PCR1). PCR1 and WAO are particular cases of WO (the Weighted Operator) because the conflicting mass is redistributed with respect to some weighting factors. In this first PCR rule, the proportionalization is done for each non-empty set with respect to the non-zero sum of its corresponding mass matrix - instead of its mass column average as in WAO, but the results are the same as Ph. Smets has pointed out. Also, we extend WAO (which herein gives no solution) for the degenerate case when all column sums of all non-empty sets are zero, and then the conflicting mass is transferred to the non-empty disjunctive form of all non-empty sets together; but if this disjunctive form happens to be empty, then one considers an open world (i.e. the frame of discernment might contain new hypotheses) and thus all conflicting mass is transferred to the empty set. In addition to WAO, we propose a general formula for PCR1 (WAO for non-degenerate cases).


title: The asymptotic number of binary codes and binary matroids

abstract: The asyptotic number of nonequivalent binary n-codes is determined. This is also the asymptotic number of nonisomorphic binary n-matroids. The connection to a result of Lefmann, Roedl, Phelps is explored. The latter states that almost all binary n-codes have a trivial automorphism group.


title: Three-Dimensional Face Orientation and Gaze Detection from a Single Image

abstract: Gaze detection and head orientation are an important part of many advanced human-machine interaction applications. Many systems have been proposed for gaze detection. Typically, they require some form of user cooperation and calibration. Additionally, they may require multiple cameras and/or restricted head positions. We present a new approach for inference of both face orientation and gaze direction from a single image with no restrictions on the head position. Our algorithm is based on a face and eye model, deduced from anthropometric data. This approach allows us to use a single camera and requires no cooperation from the user. Using a single image avoids the complexities associated with of a multi-camera system. Evaluation tests show that our system is accurate, fast and can be used in a variety of applications, including ones where the user is unaware of the system.


title: Roles Are Really Great!

abstract: We present a new role system for specifying changing referencing relationships of heap objects. The role of an object depends, in large part, on its aliasing relationships with other objects, with the role of each object changing as its aliasing relationships change. Roles therefore capture important object and data structure properties and provide useful information about how the actions of the program interact with these properties. Our role system enables the programmer to specify the legal aliasing relationships that define the set of roles that objects may play, the roles of procedure parameters and object fields, and the role changes that procedures perform while manipulating objects. We present an interprocedural, compositional, and context-sensitive role analysis algorithm that verifies that a program respects the role constraints.


title: Typestate Checking and Regular Graph Constraints

abstract: We introduce regular graph constraints and explore their decidability properties. The motivation for regular graph constraints is 1) type checking of changing types of objects in the presence of linked data structures, 2) shape analysis techniques, and 3) generalization of similar constraints over trees and grids. We define a subclass of graphs called heaps as an abstraction of the data structures that a program constructs during its execution. We prove that determining the validity of implication for regular graph constraints over the class of heaps is undecidable. We show undecidability by exhibiting a characterization of certain "corresponder graphs" in terms of presence and absence of homomorphisms to a finite number of fixed graphs. The undecidability of implication of regular graph constraints implies that there is no algorithm that will verify that procedure preconditions are met or that the invariants are maintained when these properties are expressed in any specification language at least as expressive as regular graph constraints.


title: On the Theory of Structural Subtyping

abstract: We show that the first-order theory of structural subtyping of non-recursive types is decidable. Let $\Sigma$ be a language consisting of function symbols (representing type constructors) and $C$ a decidable structure in the relational language $L$ containing a binary relation $\leq$. $C$ represents primitive types; $\leq$ represents a subtype ordering. We introduce the notion of $\Sigma$-term-power of $C$, which generalizes the structure arising in structural subtyping. The domain of the $\Sigma$-term-power of $C$ is the set of $\Sigma$-terms over the set of elements of $C$. We show that the decidability of the first-order theory of $C$ implies the decidability of the first-order theory of the $\Sigma$-term-power of $C$. Our decision procedure makes use of quantifier elimination for term algebras and Feferman-Vaught theorem. Our result implies the decidability of the first-order theory of structural subtyping of non-recursive types.


title: Lock-Free and Practical Deques using Single-Word Compare-And-Swap

abstract: We present an efficient and practical lock-free implementation of a concurrent deque that is disjoint-parallel accessible and uses atomic primitives which are available in modern computer systems. Previously known lock-free algorithms of deques are either based on non-available atomic synchronization primitives, only implement a subset of the functionality, or are not designed for disjoint accesses. Our algorithm is based on a doubly linked list, and only requires single-word compare-and-swap atomic primitives, even for dynamic memory sizes. We have performed an empirical study using full implementations of the most efficient algorithms of lock-free deques known. For systems with low concurrency, the algorithm by Michael shows the best performance. However, as our algorithm is designed for disjoint accesses, it performs significantly better on systems with high concurrency and non-uniform memory architecture.


title: Improved Upper Bound for the Redundancy of Fix-Free Codes

abstract: A variable-length code is a fix-free code if no codeword is a prefix or a suffix of any other codeword. In a fix-free code any finite sequence of codewords can be decoded in both directions, which can improve the robustness to channel noise and speed up the decoding process. In this paper we prove a new sufficient condition of the existence of fix-free codes and improve the upper bound on the redundancy of optimal fix-free codes.


title: On Role Logic

abstract: We present role logic, a notation for describing properties of relational structures in shape analysis, databases, and knowledge bases. We construct role logic using the ideas of de Bruijn's notation for lambda calculus, an encoding of first-order logic in lambda calculus, and a simple rule for implicit arguments of unary and binary predicates. The unrestricted version of role logic has the expressive power of first-order logic with transitive closure. Using a syntactic restriction on role logic formulas, we identify a natural fragment RL^2 of role logic. We show that the RL^2 fragment has the same expressive power as two-variable logic with counting C^2 and is therefore decidable. We present a translation of an imperative language into the decidable fragment RL^2, which allows compositional verification of programs that manipulate relational structures. In addition, we show how RL^2 encodes boolean shape analysis constraints and an expressive description logic.


title: On Generalized Records and Spatial Conjunction in Role Logic

abstract: We have previously introduced role logic as a notation for describing properties of relational structures in shape analysis, databases and knowledge bases. A natural fragment of role logic corresponds to two-variable logic with counting and is therefore decidable. We show how to use role logic to describe open and closed records, as well the dual of records, inverse records. We observe that the spatial conjunction operation of separation logic naturally models record concatenation. Moreover, we show how to eliminate the spatial conjunction of formulas of quantifier depth one in first-order logic with counting. As a result, allowing spatial conjunction of formulas of quantifier depth one preserves the decidability of two-variable logic with counting. This result applies to two-variable role logic fragment as well. The resulting logic smoothly integrates type system and predicate calculus notation and can be viewed as a natural generalization of the notation for constraints arising in role analysis and similar shape analysis approaches.


title: Collaborative Storage Management In Sensor Networks

abstract: In this paper, we consider a class of sensor networks where the data is not required in real-time by an observer; for example, a sensor network monitoring a scientific phenomenon for later play back and analysis. In such networks, the data must be stored in the network. Thus, in addition to battery power, storage is a primary resource: the useful lifetime of the network is constrained by its ability to store the generated data samples. We explore the use of collaborative storage technique to efficiently manage data in storage constrained sensor networks. The proposed collaborative storage technique takes advantage of spatial correlation among the data collected by nearby sensors to significantly reduce the size of the data near the data sources. We show that the proposed approach provides significant savings in the size of the stored data vs. local buffering, allowing the network to run for a longer time without running out of storage space and reducing the amount of data that will eventually be relayed to the observer. In addition, collaborative storage performs load balancing of the available storage space if data generation rates are not uniform across sensors (as would be the case in an event driven sensor network), or if the available storage varies across the network.


title: An Algorithm for Quasi-Associative and Quasi-Markovian Rules of Combination in Information Fusion

abstract: In this paper one proposes a simple algorithm of combining the fusion rules, those rules which first use the conjunctive rule and then the transfer of conflicting mass to the non-empty sets, in such a way that they gain the property of associativity and fulfill the Markovian requirement for dynamic fusion. Also, a new rule, SDL-improved, is presented.


title: Diagnosabilities of regular networks

abstract: In this paper, we study diagnosabilities of multiprocessor systems under two diagnosis models: the PMC model and the comparison model. In each model, we further consider two different diagnosis strategies: the precise diagnosis strategy proposed by Preparata et al. and the pessimistic diagnosis strategy proposed by Friedman. The main result of this paper is to determine diagnosabilities of regular networks with certain conditions, which include several widely used multiprocessor systems such as variants of hypercubes and many others.


title: On Global Warming (Softening Global Constraints)

abstract: We describe soft versions of the global cardinality constraint and the regular constraint, with efficient filtering algorithms maintaining domain consistency. For both constraints, the softening is achieved by augmenting the underlying graph. The softened constraints can be used to extend the meta-constraint framework for over-constrained problems proposed by Petit, Regin and Bessiere.


title: Non-uniform Information Dissemination for Sensor Networks

abstract: Future smart environments will be characterized by multiple nodes that sense, collect, and disseminate information about environmental phenomena through a wireless network. In this paper, we define a set of applications that require a new form of distributed knowledge about the environment, referred to as non-uniform information granularity. By non-uniform information granularity we mean that the required accuracy or precision of information is proportional to the distance between a source node (information producer) and current sink node (information consumer). That is, as the distance between the source node and sink node increases, loss in information precision is acceptable. Applications that can benefit from this type of knowledge range from battlefield scenarios to rescue operations. The main objectives of this paper are two-fold: first, we will precisely define non-uniform information granularity, and second, we will describe different protocols that achieve non-uniform information dissemination and analyze these protocols based on complexity, energy consumption, and accuracy of information.


title: Optimizing compilation of constraint handling rules in HAL

abstract: In this paper we discuss the optimizing compilation of Constraint Handling Rules (CHRs). CHRs are a multi-headed committed choice constraint language, commonly applied for writing incremental constraint solvers. CHRs are usually implemented as a language extension that compiles to the underlying language. In this paper we show how we can use different kinds of information in the compilation of CHRs in order to obtain access efficiency, and a better translation of the CHR rules into the underlying language, which in this case is HAL. The kinds of information used include the types, modes, determinism, functional dependencies and symmetries of the CHR constraints. We also show how to analyze CHR programs to determine this information about functional dependencies, symmetries and other kinds of information supporting optimizations.


title: Incremental Construction of Minimal Acyclic Sequential Transducers from Unsorted Data

abstract: This paper presents an efficient algorithm for the incremental construction of a minimal acyclic sequential transducer (ST) for a dictionary consisting of a list of input and output strings. The algorithm generalises a known method of constructing minimal finite-state automata (Daciuk et al. 2000). Unlike the algorithm published by Mihov and Maurel (2001), it does not require the input strings to be sorted. The new method is illustrated by an application to pronunciation dictionaries.


title: CHR Grammars

abstract: A grammar formalism based upon CHR is proposed analogously to the way Definite Clause Grammars are defined and implemented on top of Prolog. These grammars execute as robust bottom-up parsers with an inherent treatment of ambiguity and a high flexibility to model various linguistic phenomena. The formalism extends previous logic programming based grammars with a form of context-sensitive rules and the possibility to include extra-grammatical hypotheses in both head and body of grammar rules. Among the applications are straightforward implementations of Assumption Grammars and abduction under integrity constraints for language analysis. CHR grammars appear as a powerful tool for specification and implementation of language processors and may be proposed as a new standard for bottom-up grammars in logic programming. To appear in Theory and Practice of Logic Programming (TPLP), 2005


title: Calculus on Graphs

abstract: The purpose of this paper is to develop a "calculus" on graphs that allows graph theory to have new connections to analysis. For example, our framework gives rise to many new partial differential equations on graphs, most notably a new (Laplacian based) wave equation; this wave equation gives rise to a partial improvement on the Chung-Faber-Manteuffel diameter/eigenvalue bound in graph theory, and the Chung-Grigoryan-Yau and (in a certain case) Bobkov-Ledoux distance/eigenvalue bounds in analysis. Our framework also allows most techniques for the non-linear p-Laplacian in analysis to be easily carried over to graph theory.


title: Tsnnls: A solver for large sparse least squares problems with non-negative variables

abstract: The solution of large, sparse constrained least-squares problems is a staple in scientific and engineering applications. However, currently available codes for such problems are proprietary or based on MATLAB. We announce a freely available C implementation of the fast block pivoting algorithm of Portugal, Judice, and Vicente. Our version is several times faster than Matstoms' MATLAB implementation of the same algorithm. Further, our code matches the accuracy of MATLAB's built-in lsqnonneg function.


title: The Revolution In Database System Architecture

abstract: Database system architectures are undergoing revolutionary changes. Algorithms and data are being unified by integrating programming languages with the database system. This gives an extensible object-relational system where non-procedural relational operators manipulate object sets. Coupled with this, each DBMS is now a web service. This has huge implications for how we structure applications. DBMSs are now object containers. Queues are the first objects to be added. These queues are the basis for transaction processing and workflow applica-tions. Future workflow systems are likely to be built on this core. Data cubes and online analytic processing are now baked into most DBMSs. Beyond that, DBMSs have a framework for data mining and machine learning algorithms. Decision trees, Bayes nets, clustering, and time series analysis are built in; new algorithms can be added. Text, temporal, and spatial data access methods, along with their probabilistic reasoning have been added to database systems. Allowing approximate and probabilistic answers is essential for many applications. Many believe that XML and xQuery will be the main data structure and access pattern. Database systems must accommodate that perspective.These changes mandate a much more dynamic query optimization strategy. Intelligence is moving to the periphery of the network. Each disk and each sensor will be a competent database machine. Relational algebra is a convenient way to program these systems. Database systems are now expected to be self-managing, self-healing, and always-up.


title: There Goes the Neighborhood: Relational Algebra for Spatial Data Search

abstract: We explored ways of doing spatial search within a relational database: (1) hierarchical triangular mesh (a tessellation of the sphere), (2) a zoned bucketing system, and (3) representing areas as disjunctive-normal form constraints. Each of these approaches has merits. They all allow efficient point-in-region queries. A relational representation for regions allows Boolean operations among them and allows quick tests for point-in-region, regions-containing-point, and region-overlap. The speed of these algorithms is much improved by a zone and multi-scale zone-pyramid scheme. The approach has the virtue that the zone mechanism works well on B-Trees native to all SQL systems and integrates naturally with current query optimizers - rather than requiring a new spatial access method and concomitant query optimizer extensions. Over the last 5 years, we have used these techniques extensively in our work on SkyServer.sdss.org, and SkyQuery.net.


title: Performance Characterisation of Intra-Cluster Collective Communications

abstract: Although recent works try to improve collective communication in grid systems by separating intra and inter-cluster communication, the optimisation of communications focus only on inter-cluster communications. We believe, instead, that the overall performance of the application may be improved if intra-cluster collective communications performance is known in advance. Hence, it is important to have an accurate model of the intra-cluster collective communications, which provides the necessary evidences to tune and to predict their performance correctly. In this paper we present our experience on modelling such communication strategies. We describe and compare different implementation strategies with their communication models, evaluating the models' accuracy and describing the practical challenges that can be found when modelling collective communications.


title: Identifying Logical Homogeneous Clusters for Efficient Wide-area Communications

abstract: Recently, many works focus on the implementation of collective communication operations adapted to wide area computational systems, like computational Grids or global-computing. Due to the inherently heterogeneity of such environments, most works separate "clusters" in different hierarchy levels. to better model the communication. However, in our opinion, such works do not give enough attention to the delimitation of such clusters, as they normally use the locality or the IP subnet from the machines to delimit a cluster without verifying the "homogeneity" of such clusters. In this paper, we describe a strategy to gather network information from different local-area networks and to construct "logical homogeneous clusters", better suited to the performance modelling.


title: Fast Tuning of Intra-Cluster Collective Communications

abstract: Recent works try to optimise collective communication in grid systems focusing mostly on the optimisation of communications among different clusters. We believe that intra-cluster collective communications should also be optimised, as a way to improve the overall efficiency and to allow the construction of multi-level collective operations. Indeed, inside homogeneous clusters, a simple optimisation approach rely on the comparison from different implementation strategies, through their communication models. In this paper we evaluate this approach, comparing different implementation strategies with their predicted performances. As a result, we are able to choose the communication strategy that better adapts to each network environment.


title: Monitoring, Analyzing, and Controlling Internet-scale Systems with ACME

abstract: Analyzing and controlling large distributed services under a wide range of conditions is difficult. Yet these capabilities are essential to a number of important development and operational tasks such as benchmarking, testing, and system management. To facilitate these tasks, we have built the Application Control and Monitoring Environment (ACME), a scalable, flexible infrastructure for monitoring, analyzing, and controlling Internet-scale systems. ACME consists of two parts. ISING, the Internet Sensor In-Network agGregator, queries sensors and aggregates the results as they are routed through an overlay network. ENTRIE, the ENgine for TRiggering Internet Events, uses the data streams supplied by ISING, in combination with a user's XML configuration file, to trigger actuators such as killing processes during a robustness benchmark or paging a system administrator when predefined anomalous conditions are observed. In this paper we describe the design, implementation, and evaluation of ACME and its constituent parts. We find that for a 512-node system running atop an emulated Internet topology, ISING's use of in-network aggregation can reduce end-to-end query-response latency by more than 50% compared to using either direct network connections or the same overlay network without aggregation. We also find that an untuned implementation of ACME can invoke an actuator on one or all nodes in response to a discrete or aggregate event in less than four seconds, and we illustrate ACME's applicability to concrete benchmarking and monitoring scenarios.


title: Consensus on Transaction Commit

abstract: The distributed transaction commit problem requires reaching agreement on whether a transaction is committed or aborted. The classic Two-Phase Commit protocol blocks if the coordinator fails. Fault-tolerant consensus algorithms also reach agreement, but do not block whenever any majority of the processes are working. Running a Paxos consensus algorithm on the commit/abort decision of each participant yields a transaction commit protocol that uses 2F +1 coordinators and makes progress if at least F +1 of them are working. In the fault-free case, this algorithm requires one extra message delay but has the same stable-storage write delay as Two-Phase Commit. The classic Two-Phase Commit algorithm is obtained as the special F = 0 case of the general Paxos Commit algorithm.


title: Multi-dimensional Type Theory: Rules, Categories, and Combinators for Syntax and Semantics

abstract: We investigate the possibility of modelling the syntax and semantics of natural language by constraints, or rules, imposed by the multi-dimensional type theory Nabla. The only multiplicity we explicitly consider is two, namely one dimension for the syntax and one dimension for the semantics, but the general perspective is important. For example, issues of pragmatics could be handled as additional dimensions. One of the main problems addressed is the rather complicated repertoire of operations that exists besides the notion of categories in traditional Montague grammar. For the syntax we use a categorial grammar along the lines of Lambek. For the semantics we use so-called lexical and logical combinators inspired by work in natural logic. Nabla provides a concise interpretation and a sequent calculus as the basis for implementations.


title: The Dynamics of Group Codes: Dual Abelian Group Codes and Systems

abstract: Fundamental results concerning the dynamics of abelian group codes (behaviors) and their duals are developed. Duals of sequence spaces over locally compact abelian groups may be defined via Pontryagin duality; dual group codes are orthogonal subgroups of dual sequence spaces. The dual of a complete code or system is finite, and the dual of a Laurent code or system is (anti-)Laurent. If C and C^\perp are dual codes, then the state spaces of C act as the character groups of the state spaces of C^\perp. The controllability properties of C are the observability properties of C^\perp. In particular, C is (strongly) controllable if and only if C^\perp is (strongly) observable, and the controller memory of C is the observer memory of C^\perp. The controller granules of C act as the character groups of the observer granules of C^\perp. Examples of minimal observer-form encoder and syndrome-former constructions are given. Finally, every observer granule of C is an "end-around" controller granule of C.


title: Medians and Beyond: New Aggregation Techniques for Sensor Networks

abstract: Wireless sensor networks offer the potential to span and monitor large geographical areas inexpensively. Sensors, however, have significant power constraint (battery life), making communication very expensive. Another important issue in the context of sensor-based information systems is that individual sensor readings are inherently unreliable. In order to address these two aspects, sensor database systems like TinyDB and Cougar enable in-network data aggregation to reduce the communication cost and improve reliability. The existing data aggregation techniques, however, are limited to relatively simple types of queries such as SUM, COUNT, AVG, and MIN/MAX. In this paper we propose a data aggregation scheme that significantly extends the class of queries that can be answered using sensor networks. These queries include (approximate) quantiles, such as the median, the most frequent data values, such as the consensus value, a histogram of the data distribution, as well as range queries. In our scheme, each sensor aggregates the data it has received from other sensors into a fixed (user specified) size message. We provide strict theoretical guarantees on the approximation quality of the queries in terms of the message size. We evaluate the performance of our aggregation scheme by simulation and demonstrate its accuracy, scalability and low resource utilization for highly variable input data sets.


title: Hash sort: A linear time complexity multiple-dimensional sort algorithm

abstract: Sorting and hashing are two completely different concepts in computer science, and appear mutually exclusive to one another. Hashing is a search method using the data as a key to map to the location within memory, and is used for rapid storage and retrieval. Sorting is a process of organizing data from a random permutation into an ordered arrangement, and is a common activity performed frequently in a variety of applications. Almost all conventional sorting algorithms work by comparison, and in doing so have a linearithmic greatest lower bound on the algorithmic time complexity. Any improvement in the theoretical time complexity of a sorting algorithm can result in overall larger gains in implementation performance.. A gain in algorithmic performance leads to much larger gains in speed for the application that uses the sort algorithm. Such a sort algorithm needs to use an alternative method for ordering the data than comparison, to exceed the linearithmic time complexity boundary on algorithmic performance. The hash sort is a general purpose non-comparison based sorting algorithm by hashing, which has some interesting features not found in conventional sorting algorithms. The hash sort asymptotically outperforms the fastest traditional sorting algorithm, the quick sort. The hash sort algorithm has a linear time complexity factor -- even in the worst case. The hash sort opens an area for further work and investigation into alternative means of sorting.


title: Fractal geometry of literature: first attempt to Shakespeare's works

abstract: It was demonstrated that there is a geometrical order in the structure of literature. Fractal geometry as a modern mathematical approach and a new geometrical viewpoint on natural objects including both processes and structures was employed for analysis of literature. As the first study, the works of William Shakespeare were chosen as the most important items in western literature. By counting the number of letters applied in a manuscript, it is possible to study the whole manuscript statistically. A novel method based on basic assumption of fractal geometry was proposed for the calculation of fractal dimensions of the literature. The results were compared with Zipf's law. Zipf's law was successfully used for letters instead of words. Two new concepts namely Zipf's dimension and Zipf's order were also introduced. It was found that changes of both fractal dimension and Zipf's dimension are similar and dependent on the manuscript length. Interestingly, direct plotting the data obtained in semi-logarithmic and logarithmic forms also led to a power-law.


title: Dynamic Localization Protocols for Mobile Sensor Networks

abstract: The ability of a sensor node to determine its physical location within a network (Localization) is of fundamental importance in sensor networks. Interpretating data from sensors will not be possible unless the context of the data is known; this is most often accomplished by tracking its physical location. Existing research has focused on localization in static sensor networks where localization is a one-time (or low frequency) activity. In contrast, this paper considers localization for mobile sensors: when sensors are mobile, localization must be invoked periodically to enable the sensors to track their location. The higher the frequency of localization, the lower the error introduced because of mobility. However, localization is a costly operation since it involves both communication and computation. In this paper, we propose and investigate adaptive and predictive protocols that control the frequency of localization based on sensor mobility behavior to reduce the energy requirements for localization while bounding the localization error. We show that such protocols can significantly reduce the localization energy without sacrificing accuracy (in fact, improving accuracy for most situations). Using simulation and analysis we explore the tradeoff between energy efficiency and localization error due to mobility for several protocols.


title: The Arithmetical Complexity of Dimension and Randomness

abstract: Constructive dimension and constructive strong dimension are effectivizations of the Hausdorff and packing dimensions, respectively. Each infinite binary sequence A is assigned a dimension dim(A) in [0,1] and a strong dimension Dim(A) in [0,1]. Let DIM^alpha and DIMstr^alpha be the classes of all sequences of dimension alpha and of strong dimension alpha, respectively. We show that DIM^0 is properly Pi^0_2, and that for all Delta^0_2-computable alpha in (0,1], DIM^alpha is properly Pi^0_3. To classify the strong dimension classes, we use a more powerful effective Borel hierarchy where a co-enumerable predicate is used rather than a enumerable predicate in the definition of the Sigma^0_1 level. For all Delta^0_2-computable alpha in [0,1), we show that DIMstr^alpha is properly in the Pi^0_3 level of this hierarchy. We show that DIMstr^1 is properly in the Pi^0_2 level of this hierarchy. We also prove that the class of Schnorr random sequences and the class of computably random sequences are properly Pi^0_3.


title: FLUX: A Logic Programming Method for Reasoning Agents

abstract: FLUX is a programming method for the design of agents that reason logically about their actions and sensor information in the presence of incomplete knowledge. The core of FLUX is a system of Constraint Handling Rules, which enables agents to maintain an internal model of their environment by which they control their own behavior. The general action representation formalism of the fluent calculus provides the formal semantics for the constraint solver. FLUX exhibits excellent computational behavior due to both a carefully restricted expressiveness and the inference paradigm of progression.


title: On computing the fixpoint of a set of boolean equations

abstract: This paper presents a method for computing a least fixpoint of a system of equations over booleans. The resulting computation can be significantly shorter than the result of iteratively evaluating the entire system until a fixpoint is reached.


title: Authenticated tree parity machine key exchange

abstract: The synchronisation of Tree Parity Machines (TPMs), has proven to provide a valuable alternative concept for secure symmetric key exchange. Yet, from a cryptographer's point of view, authentication is at least as important as a secure exchange of keys. Adding an authentication via hashing e.g. is straightforward but with no relation to Neural Cryptography. We consequently formulate an authenticated key exchange within this concept. Another alternative, integrating a Zero-Knowledge protocol into the synchronisation, is also presented. A Man-In-The-Middle attack and even all currently known attacks, that are based on using identically structured TPMs and synchronisation as well, can so be averted. This in turn has practical consequences on using the trajectory in weight space. Both suggestions have the advantage of not affecting the previously observed physics of this interacting system at all.


title: Pervasive Service Architecture for a Digital Business Ecosystem

abstract: In this paper we present ideas and architectural principles upon which we are basing the development of a distributed, open-source infrastructure that, in turn, will support the expression of business models, the dynamic composition of software services, and the optimisation of service chains through automatic self-organising and evolutionary algorithms derived from biology. The target users are small and medium-sized enterprises (SMEs). We call the collection of the infrastructure, the software services, and the SMEs a Digital Business Ecosystem (DBE).


title: Journal of New Democratic Methods: An Introduction

abstract: This paper describes a new breed of academic journals that use statistical machine learning techniques to make them more democratic. In particular, not only can anyone submit an article, but anyone can also become a reviewer. Machine learning is used to decide which reviewers accurately represent the views of the journal's readers and thus deserve to have their opinions carry more weight. The paper concentrates on describing a specific experimental prototype of a democratic journal called the Journal of New Democratic Methods (JNDM). The paper also mentions the wider implications that machine learning and the techniques used in the JNDM may have for representative democracy in general.


title: Using Stochastic Encoders to Discover Structure in Data

abstract: In this paper a stochastic generalisation of the standard Linde-Buzo-Gray (LBG) approach to vector quantiser (VQ) design is presented, in which the encoder is implemented as the sampling of a vector of code indices from a probability distribution derived from the input vector, and the decoder is implemented as a superposition of reconstruction vectors. This stochastic VQ (SVQ) is optimised using a minimum mean Euclidean reconstruction distortion criterion, as in the LBG case. Numerical simulations are used to demonstrate how this leads to self-organisation of the SVQ, where different stochastically sampled code indices become associated with different input subspaces.


title: Invariant Stochastic Encoders

abstract: The theory of stochastic vector quantisers (SVQ) has been extended to allow the quantiser to develop invariances, so that only "large" degrees of freedom in the input vector are represented in the code. This has been applied to the problem of encoding data vectors which are a superposition of a "large" jammer and a "small" signal, so that only the jammer is represented in the code. This allows the jammer to be subtracted from the total input vector (i.e. the jammer is nulled), leaving a residual that contains only the underlying signal. The main advantage of this approach to jammer nulling is that little prior knowledge of the jammer is assumed, because these properties are automatically discovered by the SVQ as it is trained on examples of input vectors.


title: Scalable XSLT Evaluation

abstract: XSLT is an increasingly popular language for processing XML data. It is widely supported by application platform software. However, little optimization effort has been made inside the current XSLT processing engines. Evaluating a very simple XSLT program on a large XML document with a simple schema may result in extensive usage of memory. In this paper, we present a novel notion of \emph{Streaming Processing Model} (\emph{SPM}) to evaluate a subset of XSLT programs on XML documents, especially large ones. With SPM, an XSLT processor can transform an XML source document to other formats without extra memory buffers required. Therefore, our approach can not only tackle large source documents, but also produce large results. We demonstrate with a performance study the advantages of the SPM approach. Experimental results clearly confirm that SPM improves XSLT evaluation typically 2 to 10 times better than the existing approaches. Moreover, the SPM approach also features high scalability.


title: Application of the Double Metaphone Algorithm to Amharic Orthography

abstract: The Metaphone algorithm applies the phonetic encoding of orthographic sequences to simplify words prior to comparison. While Metaphone has been highly successful for the English language, for which it was designed, it may not be applied directly to Ethiopian languages. The paper details how the principles of Metaphone can be applied to Ethiopic script and uses Amharic as a case study. Match results improve as specific considerations are made for Amharic writing practices. Results are shown to improve further when common errors from Amharic input methods are considered.


title: Weighted average finite difference methods for fractional diffusion equations

abstract: Weighted averaged finite difference methods for solving fractional diffusion equations are discussed and different formulae of the discretization of the Riemann-Liouville derivative are considered. The stability analysis of the different numerical schemes is carried out by means of a procedure close to the well-known von Neumann method of ordinary diffusion equations. The stability bounds are easily found and checked in some representative examples.


title: Providing Authentic Long-term Archival Access to Complex Relational Data

abstract: We discuss long-term preservation of and access to relational databases. The focus is on national archives and science data archives which have to ingest and integrate data from a broad spectrum of vendor-specific relational database management systems (RDBMS). Furthermore, we present our solution SIARD which analyzes and extracts data and data logic from almost any RDBMS. It enables, to a reasonable level of authenticity, complete detachment of databases from their vendor-specific environment. The user can add archival descriptive metadata according to a customizable schema. A SIARD database archive integrates data, data logic, technical metadata, and archival descriptive information in one archival information package, independent of any specific software and hardware, based upon plain text files and the standardized languages SQL and XML. For usage purposes, a SIARD archive can be reloaded into any current or future RDBMS which supports standard SQL. In addition, SIARD contains a client that enables 'on demand' reload of archives into a target RDBMS, and multi-user remote access for querying and browsing the data together with its technical and descriptive metadata in one graphical user interface.


title: Cauchy Annealing Schedule: An Annealing Schedule for Boltzmann Selection Scheme in Evolutionary Algorithms

abstract: Boltzmann selection is an important selection mechanism in evolutionary algorithms as it has theoretical properties which help in theoretical analysis. However, Boltzmann selection is not used in practice because a good annealing schedule for the `inverse temperature' parameter is lacking. In this paper we propose a Cauchy annealing schedule for Boltzmann selection scheme based on a hypothesis that selection-strength should increase as evolutionary process goes on and distance between two selection strengths should decrease for the process to converge. To formalize these aspects, we develop formalism for selection mechanisms using fitness distributions and give an appropriate measure for selection-strength. In this paper, we prove an important result, by which we derive an annealing schedule called Cauchy annealing schedule. We demonstrate the novelty of proposed annealing schedule using simulations in the framework of genetic algorithms.


title: A CHR-based Implementation of Known Arc-Consistency

abstract: In classical CLP(FD) systems, domains of variables are completely known at the beginning of the constraint propagation process. However, in systems interacting with an external environment, acquiring the whole domains of variables before the beginning of constraint propagation may cause waste of computation time, or even obsolescence of the acquired data at the time of use. For such cases, the Interactive Constraint Satisfaction Problem (ICSP) model has been proposed as an extension of the CSP model, to make it possible to start constraint propagation even when domains are not fully known, performing acquisition of domain elements only when necessary, and without the need for restarting the propagation after every acquisition. In this paper, we show how a solver for the two sorted CLP language, defined in previous work, to express ICSPs, has been implemented in the Constraint Handling Rules (CHR) language, a declarative language particularly suitable for high level implementation of constraint solvers.


title: The role of robust semantic analysis in spoken language dialogue systems

abstract: In this paper we summarized a framework for designing grammar-based procedure for the automatic extraction of the semantic content from spoken queries. Starting with a case study and following an approach which combines the notions of fuzziness and robustness in sentence parsing, we showed we built practical domain-dependent rules which can be applied whenever it is possible to superimpose a sentence-level semantic structure to a text without relying on a previous deep syntactical analysis. This kind of procedure can be also profitably used as a pre-processing tool in order to cut out part of the sentence which have been recognized to have no relevance in the understanding process. In the case of particular dialogue applications where there is no need to build a complex semantic structure (e.g. word spotting or excerpting) the presented methodology may represent an efficient alternative solution to a sequential composition of deep linguistic analysis modules. Even if the query generation problem may not seem a critical application it should be held in mind that the sentence processing must be done on-line. Having this kind of constraints we cannot design our system without caring for efficiency and thus provide an immediate response. Another critical issue is related to whole robustness of the system. In our case study we tried to make experiences on how it is possible to deal with an unreliable and noisy input without asking the user for any repetition or clarification. This may correspond to a similar problem one may have when processing text coming from informal writing such as e-mails, news and in many cases Web pages where it is often the case to have irrelevant surrounding information.


title: Non-negative matrix factorization with sparseness constraints

abstract: Non-negative matrix factorization (NMF) is a recently developed technique for finding parts-based, linear representations of non-negative data. Although it has successfully been applied in several applications, it does not always result in parts-based representations. In this paper, we show how explicitly incorporating the notion of `sparseness' improves the found decompositions. Additionally, we provide complete MATLAB code both for standard NMF and for our extension. Our hope is that this will further the application of these methods to solving novel data-analysis problems.


title: Proofing Tools Technology at Neurosoft S.A.

abstract: The aim of this paper is to present the R&D activities carried out at Neurosoft S.A. regarding the development of proofing tools for Modern Greek. Firstly, we focus on infrastructure issues that we faced during our initial steps. Subsequently, we describe the most important insights of three proofing tools developed by Neurosoft, i.e. the spelling checker, the hyphenator and the thesaurus, outlining their efficiencies and inefficiencies. Finally, we discuss some improvement ideas and give our future directions.


title: Verbal chunk extraction in French using limited resources

abstract: A way of extracting French verbal chunks, inflected and infinitive, is explored and tested on effective corpus. Declarative morphological and local grammar rules specifying chunks and some simple contextual structures are used, relying on limited lexical information and some simple heuristic/statistic properties obtained from restricted corpora. The specific goals, the architecture and the formalism of the system, the linguistic information on which it relies and the obtained results on effective corpus are presented.


title: An electronic dictionary as a basis for NLP tools: The Greek case

abstract: The existence of a Dictionary in electronic form for Modern Greek (MG) is mandatory if one is to process MG at the morphological and syntactic levels since MG is a highly inflectional language with marked stress and a spelling system with many characteristics carried over from Ancient Greek. Moreover, such a tool becomes necessary if one is to create efficient and sophisticated NLP applications with substantial linguistic backing and coverage. The present paper will focus on the deployment of such an electronic dictionary for Modern Greek, which was built in two phases: first it was constructed to be the basis for a spelling correction schema and then it was reconstructed in order to become the platform for the deployment of a wider spectrum of NLP tools.


title: Source Coding With Distortion Side Information At The Encoder

abstract: We consider lossy source coding when side information affecting the distortion measure may be available at the encoder, decoder, both, or neither. For example, such distortion side information can model reliabilities for noisy measurements, sensor calibration information, or perceptual effects like masking and sensitivity to context. When the distortion side information is statistically independent of the source, we show that in many cases (e.g, for additive or multiplicative distortion side information) there is no penalty for knowing the side information only at the encoder, and there is no advantage to knowing it at the decoder. Furthermore, for quadratic distortion measures scaled by the distortion side information, we evaluate the penalty for lack of encoder knowledge and show that it can be arbitrarily large. In this scenario, we also sketch transform based quantizers constructions which efficiently exploit encoder side information in the high-resolution limit.


title: Analysis and Visualization of Index Words from Audio Transcripts of Instructional Videos

abstract: We introduce new techniques for extracting, analyzing, and visualizing textual contents from instructional videos of low production quality. Using Automatic Speech Recognition, approximate transcripts (H75% Word Error Rate) are obtained from the originally highly compressed videos of university courses, each comprising between 10 to 30 lectures. Text material in the form of books or papers that accompany the course are then used to filter meaningful phrases from the seemingly incoherent transcripts. The resulting index into the transcripts is tied together and visualized in 3 experimental graphs that help in understanding the overall course structure and provide a tool for localizing certain topics for indexing. We specifically discuss a Transcript Index Map, which graphically lays out key phrases for a course, a Textbook Chapter to Transcript Match, and finally a Lecture Transcript Similarity graph, which clusters semantically similar lectures. We test our methods and tools on 7 full courses with 230 hours of video and 273 transcripts. We are able to extract up to 98 unique key terms for a given transcript and up to 347 unique key terms for an entire course. The accuracy of the Textbook Chapter to Transcript Match exceeds 70% on average. The methods used can be applied to genres of video in which there are recurrent thematic words (news, sports, meetings,...)