OpenRaiser/Intern-Atlas huggingface dataset:
Algorithms for Rewriting Aggregate Queries Using Views
Venue: arXiv cs.DB 2000
Year: 2000

Queries involving aggregation are typical in database applications. One of the main ideas to optimize the execution of an aggregate query is to reuse results of previously answered queries. This leads to the problem of rewriting aggregate queries using views. Due to a lack of theory, algorithms for this problem were rather ad-hoc. They were sound, but were not proven to be complete. Recently we have given syntactic characterizations for the equivalence of aggregate queries and applied them to decide when there exist rewritings. However, these decision procedures do not lend themselves immediately to an implementation. In this paper, we present practical algorithms for rewriting queries with $\COUNT$ and $\SUM$. Our algorithms are sound. They are also complete for important cases. Our techniques can be used to improve well-known procedures for rewriting non-aggregate queries. These procedures can then be adapted to obtain algorithms for rewriting queries with $\MIN$ and $\MAX$. The algorithms presented are a basis for realizing optimizers that rewrite queries using views.
Web Mining Research: A Survey
Venue: arXiv cs.LG 2000
Year: 2000

With the huge amount of information available online, the World Wide Web is a fertile area for data mining research. The Web mining research is at the cross road of research from several research communities, such as database, information retrieval, and within AI, especially the sub-areas of machine learning and natural language processing. However, there is a lot of confusions when comparing research efforts from different point of views. In this paper, we survey the research in the area of Web mining, point out some confusions regarded the usage of the term Web mining and suggest three Web mining categories. Then we situate some of the research with respect to these three categories. We also explore the connection between the Web mining categories and the related agent paradigm. For the survey, we focus on representation issues, on the process, on the learning algorithm, and on the application of the recent works as the criteria. We conclude the paper with some research issues.
Rewriting Calculus: Foundations and Applications
Venue: arXiv cs.SC 2000
Year: 2000

This thesis is devoted to the study of a calculus that describes the application of conditional rewriting rules and the obtained results at the same level of representation. We introduce the rewriting calculus, also called the rho-calculus, which generalizes the first order term rewriting and lambda-calculus, and makes possible the representation of the non-determinism. In our approach the abstraction operator as well as the application operator are objects of calculus. The result of a reduction in the rewriting calculus is either an empty set representing the application failure, or a singleton representing a deterministic result, or a set having several elements representing a not-deterministic choice of results. In this thesis we concentrate on the properties of the rewriting calculus where a syntactic matching is used in order to bind the variables to their current values. We define evaluation strategies ensuring the confluence of the calculus and we show that these strategies become trivial for restrictions of the general rewriting calculus to simpler calculi like the lambda-calculus. The rewriting calculus is not terminating in the untyped case but the strong normalization is obtained for the simply typed calculus. In the rewriting calculus extended with an operator allowing to test the application failure we define terms representing innermost and outermost normalizations with respect to a set of rewriting rules. By using these terms, we obtain a natural and concise description of the conditional rewriting. Finally, starting from the representation of the conditional rewriting rules, we show how the rewriting calculus can be used to give a semantics to ELAN, a language based on the application of rewriting rules controlled by strategies.
Index Assignment for Multichannel Communication under Failure
Venue: arXiv cs.DS 2000
Year: 2000

We consider the problem of multiple description scalar quantizers and describing the achievable rate-distortion tuples in that setting. We formulate it as a combinatorial optimization problem of arranging numbers in a matrix to minimize the maximum difference between the largest and the smallest number in any row or column. We develop a technique for deriving lower bounds on the distortion at given channel rates. The approach is constructive, thus allowing an algorithm that gives a closely matching upper bound. For the case of two communication channels with equal rates, the bounds coincide, thus giving the precise lowest achievable distortion at fixed rates. The bounds are within a small constant for higher number of channels. To the best of our knowledge, this is the first result concerning systems with more than two communication channels. The problem is also equivalent to the bandwidth minimization problem of Hamming graphs.
Improving Performance of heavily loaded agents
Venue: arXiv cs.MA 2000
Year: 2000

With the increase in agent-based applications, there are now agent systems that support \emph{concurrent} client accesses. The ability to process large volumes of simultaneous requests is critical in many such applications. In such a setting, the traditional approach of serving these requests one at a time via queues (e.g. \textsf{FIFO} queues, priority queues) is insufficient. Alternative models are essential to improve the performance of such \emph{heavily loaded} agents. In this paper, we propose a set of \emph{cost-based algorithms} to \emph{optimize} and \emph{merge} multiple requests submitted to an agent. In order to merge a set of requests, one first needs to identify commonalities among such requests. First, we provide an \emph{application independent framework} within which an agent developer may specify relationships (called \emph{invariants}) between requests. Second, we provide two algorithms (and various accompanying heuristics) which allow an agent to automatically rewrite requests so as to avoid redundant work---these algorithms take invariants associated with the agent into account. Our algorithms are independent of any specific agent framework. For an implementation, we implemented both these algorithms on top of the \impact agent development platform, and on top of a (non-\impact) geographic database agent. Based on these implementations, we conducted experiments and show that our algorithms are considerably more efficient than methods that use the $A^*$ algorithm.
Finding Failure Causes through Automated Testing
Venue: arXiv cs.SE 2000
Year: 2000

A program fails. Under which circumstances does this failure occur? One single algorithm, the delta debugging algorithm, suffices to determine these failure-inducing circumstances. Delta debugging tests a program systematically and automatically to isolate failure-inducing circumstances such as the program input, changes to the program code, or executed statements.
The Role of Commutativity in Constraint Propagation Algorithms
Venue: arXiv cs.PF 2000
Year: 2000

Constraint propagation algorithms form an important part of most of the constraint programming systems. We provide here a simple, yet very general framework that allows us to explain several constraint propagation algorithms in a systematic way. In this framework we proceed in two steps. First, we introduce a generic iteration algorithm on partial orderings and prove its correctness in an abstract setting. Then we instantiate this algorithm with specific partial orderings and functions to obtain specific constraint propagation algorithms. In particular, using the notions commutativity and semi-commutativity, we show that the {\tt AC-3}, {\tt PC-2}, {\tt DAC} and {\tt DPC} algorithms for achieving (directional) arc consistency and (directional) path consistency are instances of a single generic algorithm. The work reported here extends and simplifies that of Apt \citeyear{Apt99b}.
A brief overview of the MAD debugging activities
Venue: arXiv cs.SE 2000
Year: 2000

Debugging parallel and distributed programs is a difficult activitiy due to the multiplicity of sequential bugs, the existence of malign effects like race conditions and deadlocks, and the huge amounts of data that have to be processed. These problems are addressed by the Monitoring And Debugging environment MAD, which offers debugging functionality based on a graphical representation of a program's execution. The target applications of MAD are parallel programs applying the standard Message-Passing Interface MPI, which is used extensively in the high-performance computing domain. The highlights of MAD are interactive inspection mechanisms including visualization of distributed arrays, the possibility to graphically place breakpoints, a mechanism for monitor overhead removal, and the evaluation of racing messages occuring due to nondeterminism in the code.
Creativity and Delusions: A Neurocomputational Approach
Venue: arXiv cs.NE 2000
Year: 2000

Thinking is one of the most interesting mental processes. Its complexity is sometimes simplified and its different manifestations are classified into normal and abnormal, like the delusional and disorganized thought or the creative one. The boundaries between these facets of thinking are fuzzy causing difficulties in medical, academic, and philosophical discussions. Considering the dopaminergic signal-to-noise neuronal modulation in the central nervous system, and the existence of semantic maps in human brain, a self-organizing neural network model was developed to unify the different thought processes into a single neurocomputational substrate. Simulations were performed varying the dopaminergic modulation and observing the different patterns that emerged at the semantic map. Assuming that the thought process is the total pattern elicited at the output layer of the neural network, the model shows how the normal and abnormal thinking are generated and that there are no borders between their different manifestations. Actually, a continuum of different qualitative reasoning, ranging from delusion to disorganization of thought, and passing through the normal and the creative thinking, seems to be more plausible. The model is far from explaining the complexities of human thinking but, at least, it seems to be a good metaphorical and unifying view of the many facets of this phenomenon usually studied in separated settings.
Performance and Scalability Models for a Hypergrowth e-Commerce Web Site
Venue: arXiv cs.PF 2000
Year: 2000

The performance of successful Web-based e-commerce services has all the allure of a roller-coaster ride: accelerated fiscal growth combined with the ever-present danger of running out of server capacity. This chapter presents a case study based on the author's own capacity planning engagement with one of the hottest e-commerce Web sites in the world. Several spreadsheet techniques are presented for forecasting both short-term and long-term trends in the consumption of server capacity. Two new performance metrics are introduced for site planning and procurement: the effective demand, and the doubling period.
Reducing Randomness via Irrational Numbers
Venue: arXiv cs.DS 2000
Year: 2000

We propose a general methodology for testing whether a given polynomial with integer coefficients is identically zero. The methodology evaluates the polynomial at efficiently computable approximations of suitable irrational points. In contrast to the classical technique of DeMillo, Lipton, Schwartz, and Zippel, this methodology can decrease the error probability by increasing the precision of the approximations instead of using more random bits. Consequently, randomized algorithms that use the classical technique can generally be improved using the new methodology. To demonstrate the methodology, we discuss two nontrivial applications. The first is to decide whether a graph has a perfect matching in parallel. Our new NC algorithm uses fewer random bits while doing less work than the previously best NC algorithm by Chari, Rohatgi, and Srinivasan. The second application is to test the equality of two multisets of integers. Our new algorithm improves upon the previously best algorithms by Blum and Kannan and can speed up their checking algorithm for sorting programs on a large range of inputs.
Not Just a Matter of Time: Field Differences and the Shaping of Electronic Media in Supporting Scientific Communication
Venue: arXiv cs.CY 2000
Year: 2000

The shift towards the use of electronic media in scholarly communication appears to be an inescapable imperative. However, these shifts are uneven, both with respect to field and with respect to the form of communication. Different scientific fields have developed and use distinctly different communicative forums, both in the paper and electronic arenas, and these forums play different communicative roles within the field. One common claim is that we are in the early stages of an electronic revolution, that it is only a matter of time before other fields catch up with the early adopters, and that all fields converge on a stable set of electronic forums. A social shaping of technology (SST) perspective helps us to identify important social forces centered around disciplinary constructions of trust and of legitimate communication that pull against convergence. This analysis concludes that communicative plurality and communicative heterogeneity are durable features of the scholarly landscape, and that we are likely to see field differences in the use of and meaning ascribed to communications forums persist, even as overall use of electronic communications technologies both in science and in society as a whole increases.
SLT-Resolution for the Well-Founded Semantics
Venue: arXiv cs.AI 2001
Year: 2001

Global SLS-resolution and SLG-resolution are two representative mechanisms for top-down evaluation of the well-founded semantics of general logic programs. Global SLS-resolution is linear for query evaluation but suffers from infinite loops and redundant computations. In contrast, SLG-resolution resolves infinite loops and redundant computations by means of tabling, but it is not linear. The principal disadvantage of a non-linear approach is that it cannot be implemented using a simple, efficient stack-based memory structure nor can it be easily extended to handle some strictly sequential operators such as cuts in Prolog. In this paper, we present a linear tabling method, called SLT-resolution, for top-down evaluation of the well-founded semantics. SLT-resolution is a substantial extension of SLDNF-resolution with tabling. Its main features include: (1) It resolves infinite loops and redundant computations while preserving the linearity. (2) It is terminating, and sound and complete w.r.t. the well-founded semantics for programs with the bounded-term-size property with non-floundering queries. Its time complexity is comparable with SLG-resolution and polynomial for function-free logic programs. (3) Because of its linearity for query evaluation, SLT-resolution bridges the gap between the well-founded semantics and standard Prolog implementation techniques. It can be implemented by an extension to any existing Prolog abstract machines such as WAM or ATOAM.
Introduction to the GiNaC Framework for Symbolic Computation within the C++ Programming Language
Venue: arXiv cs.SC 2001
Year: 2001

The traditional split-up into a low level language and a high level language in the design of computer algebra systems may become obsolete with the advent of more versatile computer languages. We describe GiNaC, a special-purpose system that deliberately denies the need for such a distinction. It is entirely written in C++ and the user can interact with it directly in that language. It was designed to provide efficient handling of multivariate polynomials, algebras and special functions that are needed for loop calculations in theoretical quantum field theory. It also bears some potential to become a more general purpose symbolic package.
Generalization of a 3-D resonator model for the simulation of spherical enclosures
Venue: arXiv cs.SD 2001
Year: 2001

A rectangular enclosure has such an even distribution of resonances that it can be accurately and efficiently modelled using a feedback delay network. Conversely, a non rectangular shape such as a sphere has a distribution of resonances that challenges the construction of an efficient model. This work proposes an extension of the already known feedback delay network structure to model the resonant properties of a sphere. A specific frequency distribution of resonances can be approximated, up to a certain frequency, by inserting an allpass filter of moderate order after each delay line of a feedback delay network. The structure used for rectangular boxes is therefore augmented with a set of allpass filters allowing parametric control over the enclosure size and the boundary properties. This work was motivated by informal listening tests which have shown that it is possible to identify a basic shape just from the distribution of its audible resonances.
Decomposing Finite Abelian Groups
Venue: arXiv cs.DS 2001
Year: 2001

This paper describes a quantum algorithm for efficiently decomposing finite Abelian groups. Such a decomposition is needed in order to apply the Abelian hidden subgroup algorithm. Such a decomposition (assuming the Generalized Riemann Hypothesis) also leads to an efficient algorithm for computing class numbers (known to be at least as difficult as factoring).
Assertion checker for the C programming language based on computations over event traces
Venue: arXiv cs.SE 2001
Year: 2001

This paper suggests an approach to the development of software testing and debugging automation tools based on precise program behavior models. The program behavior model is defined as a set of events (event trace) with two basic binary relations over events -- precedence and inclusion, and represents the temporal relationship between actions. A language for the computations over event traces is developed that provides a basis for assertion checking, debugging queries, execution profiles, and performance measurements. The approach is nondestructive, since assertion texts are separated from the target program source code and can be maintained independently. Assertions can capture the dynamic properties of a particular target program and can formalize the general knowledge of typical bugs and debugging strategies. An event grammar provides a sound basis for assertion language implementation via target program automatic instrumentation. An implementation architecture and preliminary experiments with a prototype assertion checker for the C programming language are discussed.
Communities of Practice in the Distributed International Environment
Venue: arXiv cs.HC 2001
Year: 2001

Modern commercial organisations are facing pressures which have caused them to lose personnel. When they lose people, they also lose their knowledge. Organisations also have to cope with the internationalisation of business forcing collaboration and knowledge sharing across time and distance. Knowledge Management (KM) claims to tackle these issues. This paper looks at an area where KM does not offer sufficient support, that is, the sharing of knowledge that is not easy to articulate. The focus in this paper is on Communities of Practice in commercial organisations. We do this by exploring knowledge sharing in Lave and Wenger's [1] theory of Communities of Practice and investigating how Communities of Practice may translate to a distributed international environment. The paper reports on two case studies that explore the functioning of Communities of Practice across international boundaries.
On the problem of computing the well-founded semantics
Venue: arXiv cs.LO 2001
Year: 2001

The well-founded semantics is one of the most widely studied and used semantics of logic programs with negation. In the case of finite propositional programs, it can be computed in polynomial time, more specifically, in O(|At(P)|size(P)) steps, where size(P) denotes the total number of occurrences of atoms in a logic program P. This bound is achieved by an algorithm introduced by Van Gelder and known as the alternating-fixpoint algorithm. Improving on the alternating-fixpoint algorithm turned out to be difficult. In this paper we study extensions and modifications of the alternating-fixpoint approach. We then restrict our attention to the class of programs whose rules have no more than one positive occurrence of an atom in their bodies. For programs in that class we propose a new implementation of the alternating-fixpoint method in which false atoms are computed in a top-down fashion. We show that our algorithm is faster than other known algorithms and that for a wide class of programs it is linear and so, asymptotically optimal.
More Robust Multiparty Protocols with Oblivious Transfer
Venue: arXiv cs.CR 2001
Year: 2001

With oblivious transfer multiparty protocols become possible even in the presence of a faulty majority. But all known protocols can be aborted by just one disruptor. This paper presents more robust solutions for multiparty protocols with oblivious transfer. This additional robustness against disruptors weakens the security of the protocol and the guarantee that the result is correct. We can observe a trade off between robustness against disruption and security and correctness. We give an application to quantum multiparty protocols. These allow the implementation of oblivious transfer and the protocols of this paper relative to temporary assumptions, i.e., the security increases after the termination of the protocol.
On-Line Difference Maximization
Venue: arXiv cs.DS 2001
Year: 2001

In this paper we examine problems motivated by on-line financial problems and stochastic games. In particular, we consider a sequence of entirely arbitrary distinct values arriving in random order, and must devise strategies for selecting low values followed by high values in such a way as to maximize the expected gain in rank from low values to high values. First, we consider a scenario in which only one low value and one high value may be selected. We give an optimal on-line algorithm for this scenario, and analyze it to show that, surprisingly, the expected gain is n-O(1), and so differs from the best possible off-line gain by only a constant additive term (which is, in fact, fairly small -- at most 15). In a second scenario, we allow multiple nonoverlapping low/high selections, where the total gain for our algorithm is the sum of the individual pair gains. We also give an optimal on-line algorithm for this problem, where the expected gain is n^2/8-Θ(n\log n). An analysis shows that the optimal expected off-line gain is n^2/6+Θ(1), so the performance of our on-line algorithm is within a factor of 3/4 of the best off-line strategy.