OpenRaiser/Intern-Atlas huggingface dataset:
A Data Mining Framework for Optimal Product Selection in Retail Supermarket Data: The Generalized PROFSET Model
Venue: arXiv cs.DB 2001
Year: 2001

In recent years, data mining researchers have developed efficient association rule algorithms for retail market basket analysis. Still, retailers often complain about how to adopt association rules to optimize concrete retail marketing-mix decisions. It is in this context that, in a previous paper, the authors have introduced a product selection model called PROFSET. This model selects the most interesting products from a product assortment based on their cross-selling potential given some retailer defined constraints. However this model suffered from an important deficiency: it could not deal effectively with supermarket data, and no provisions were taken to include retail category management principles. Therefore, in this paper, the authors present an important generalization of the existing model in order to make it suitable for supermarket data as well, and to enable retailers to add category restrictions to the model. Experiments on real world data obtained from a Belgian supermarket chain produce very promising results and demonstrate the effectiveness of the generalized PROFSET model.
Lower Bound on the Chromatic Number by Spectra of Weighted Adjacency Matrices
Venue: arXiv cs.DM 2001
Year: 2001

A lower bound on the chromatic number of a graph is derived by majorization of spectra of weighted adjacency matrices. These matrices are given by Hadamard products of the adjacency matrix and arbitrary Hermitian matrices.
Mechanizing Set Theory: Cardinal Arithmetic and the Axiom of Choice.
Venue: arXiv cs.LO 2001
Year: 2001

Fairly deep results of Zermelo-Frenkel (ZF) set theory have been mechanized using the proof assistant Isabelle. The results concern cardinal arithmetic and the Axiom of Choice (AC). A key result about cardinal multiplication is K*K = K, where K is any infinite cardinal. Proving this result required developing theories of orders, order-isomorphisms, order types, ordinal arithmetic, cardinals, etc.; this covers most of Kunen, Set Theory, Chapter I. Furthermore, we have proved the equivalence of 7 formulations of the Well-ordering Theorem and 20 formulations of AC; this covers the first two chapters of Rubin and Rubin, Equivalents of the Axiom of Choice, and involves highly technical material. The definitions used in the proofs are largely faithful in style to the original mathematics.
New Error Bounds for Solomonoff Prediction
Venue: arXiv cs.AI 2001
Year: 2001

Solomonoff sequence prediction is a scheme to predict digits of binary strings without knowing the underlying probability distribution. We call a prediction scheme informed when it knows the true probability distribution of the sequence. Several new relations between universal Solomonoff sequence prediction and informed prediction and general probabilistic prediction schemes will be proved. Among others, they show that the number of errors in Solomonoff prediction is finite for computable distributions, if finite in the informed case. Deterministic variants will also be studied. The most interesting result is that the deterministic variant of Solomonoff prediction is optimal compared to any other probabilistic or deterministic prediction scheme apart from additive square root corrections only. This makes it well suited even for difficult prediction problems, where it does not suffice when the number of errors is minimal to within some factor greater than one. Solomonoff's original bound and the ones presented here complement each other in a useful way.
The Limits of Horn Logic Programs
Venue: arXiv cs.LO 2002
Year: 2002

Given a sequence $\{Π_n\}$ of Horn logic programs, the limit $Π$ of $\{Π_n\}$ is the set of the clauses such that every clause in $Π$ belongs to almost every $Π_n$ and every clause in infinitely many $Π_n$'s belongs to $Π$ also. The limit program $Π$ is still Horn but may be infinite. In this paper, we consider if the least Herbrand model of the limit of a given Horn logic program sequence $\{Π_n\}$ equals the limit of the least Herbrand models of each logic program $Π_n$. It is proved that this property is not true in general but holds if Horn logic programs satisfy an assumption which can be syntactically checked and be satisfied by a class of Horn logic programs. Thus, under this assumption we can approach the least Herbrand model of the limit $Π$ by the sequence of the least Herbrand models of each finite program $Π_n$. We also prove that if a finite Horn logic program satisfies this assumption, then the least Herbrand model of this program is recursive. Finally, by use of the concept of stability from dynamical systems, we prove that this assumption is exactly a sufficient condition to guarantee the stability of fixed points for Horn logic programs.
Anaphora and Discourse Structure
Venue: arXiv cs.CL 2002
Year: 2002

We argue in this paper that many common adverbial phrases generally taken to signal a discourse relation between syntactically connected units within discourse structure, instead work anaphorically to contribute relational meaning, with only indirect dependence on discourse structure. This allows a simpler discourse structure to provide scaffolding for compositional semantics, and reveals multiple ways in which the relational meaning conveyed by adverbial connectives can interact with that associated with discourse structure. We conclude by sketching out a lexicalised grammar for discourse that facilitates discourse interpretation as a product of compositional rules, anaphor resolution and inference.
Open Access to Monopoly Cable Platforms Versus Direct Access To Competitive International Telecommunications Satellite Facilities: A Study In Contrasts
Venue: arXiv cs.CY 2002
Year: 2002

In 1999, the FCC authorized direct access to INTELSAT, allowing INTELSAT's U.S. customers and competitors to bypass INTELSAT's U.S. retail affiliate (COMSAT), and to take satellite capacity at wholesale prices directly from INTELSAT. This policy was modeled in many respects on the access and unbundling requirements applicable to domestic incumbent local exchange carriers (ILECs) under the Telecommunications Act of 1996. At the same time, incumbent domestic cable TV system operators have not been required to provide wholesale open access to competitive Internet Service Providers (ISPs) seeking to provide residential broadband Internet service through existing proprietary cable facilities. Yet the policy arguments favoring open access to incumbent domestic cable systems appear to be stronger than those favoring direct access to INTELSAT. For example, it may be fairly debated whether entrenched cable system operators are now positioned to unfairly leverage their dominance in the multichannel video programming distribution (MVPD) market to thwart competition in the broadband ISP market, as some cable open access advocates assert. In contrast, it is clear that no analogous issues of tying were implicated by INTELSAT in 1999, when its position in the international telecommunications market was substantially nondominant and, in any event, it had no new product to tie to its established offerings. Similarly, while it may be debated whether or not a cable plant is a bottleneck facility that gatekeeps broadband Internet for many residential users, it is beyond cavil that INTELSAT in 1999 controlled virtually no such bottleneck facilities.
ICANN as Regulator
Venue: arXiv cs.CY 2002
Year: 2002

This paper tells the story leading to ICANN's selection of seven new Internet top level domains in November 2000. In implementing proposals to expand the name space, ICANN adopted an approach far different from Jon Postel's lightweight proposals. ICANN staff, in setting the ground rules for considering new gTLDs, emphasized that only a few applicants would be allowed in, and imposed strict threshold requirements. Staff determined that the Board should pick TLDs by looking at all relevant aspects of every proposal, and deciding which ones presented the best overall combination of a variety of incommensurable factors. Aspects of the resulting process were predictable: Anyone familiar with the FCC comparative hearing process for broadcast licenses can attest that this sort of ad hoc comparison is necessarily subjective, lending itself to arbitrariness and biased application. Yet the process had advantages that appealed to ICANN decision-makers. The Board members would be free to take their best shots, in a situationally sensitive manner, at advancing the policies they thought important. The approach allowed ICANN to maintain the greatest degree of control. The end result, though, was a process stunning in its arbitrariness, a bad parody of fact-bound, situationally sensitive (rather than rules-based) decision-making.
Some Facets of Complexity Theory and Cryptography: A Five-Lectures Tutorial
Venue: arXiv cs.CC 2002
Year: 2002

In this tutorial, selected topics of cryptology and of computational complexity theory are presented. We give a brief overview of the history and the foundations of classical cryptography, and then move on to modern public-key cryptography. Particular attention is paid to cryptographic protocols and the problem of constructing the key components of such protocols such as one-way functions. A function is one-way if it is easy to compute, but hard to invert. We discuss the notion of one-way functions both in a cryptographic and in a complexity-theoretic setting. We also consider interactive proof systems and present some interesting zero-knowledge protocols. In a zero-knowledge protocol one party can convince the other party of knowing some secret information without disclosing any bit of this information. Motivated by these protocols, we survey some complexity-theoretic results on interactive proof systems and related complexity classes.
Efficient Groundness Analysis in Prolog
Venue: arXiv cs.PL 2002
Year: 2002

Boolean functions can be used to express the groundness of, and trace grounding dependencies between, program variables in (constraint) logic programs. In this paper, a variety of issues pertaining to the efficient Prolog implementation of groundness analysis are investigated, focusing on the domain of definite Boolean functions, Def. The systematic design of the representation of an abstract domain is discussed in relation to its impact on the algorithmic complexity of the domain operations; the most frequently called operations should be the most lightweight. This methodology is applied to Def, resulting in a new representation, together with new algorithms for its domain operations utilising previously unexploited properties of Def -- for instance, quadratic-time entailment checking. The iteration strategy driving the analysis is also discussed and a simple, but very effective, optimisation of induced magic is described. The analysis can be implemented straightforwardly in Prolog and the use of a non-ground representation results in an efficient, scalable tool which does not require widening to be invoked, even on the largest benchmarks. An extensive experimental evaluation is given
Core Services in the Architecture of the National Digital Library for Science Education (NSDL)
Venue: arXiv cs.DL 2002
Year: 2002

We describe the core components of the architecture for the (NSDL) National Science, Mathematics, Engineering, and Technology Education Digital Library. Over time the NSDL will include heterogeneous users, content, and services. To accommodate this, a design for a technical and organization infrastructure has been formulated based on the notion of a spectrum of interoperability. This paper describes the first phase of the interoperability infrastructure including the metadata repository, search and discovery services, rights management services, and user interface portal facilities.
A Refinement Calculus for Logic Programs
Venue: arXiv cs.SE 2002
Year: 2002

Existing refinement calculi provide frameworks for the stepwise development of imperative programs from specifications. This paper presents a refinement calculus for deriving logic programs. The calculus contains a wide-spectrum logic programming language, including executable constructs such as sequential conjunction, disjunction, and existential quantification, as well as specification constructs such as general predicates, assumptions and universal quantification. A declarative semantics is defined for this wide-spectrum language based on executions. Executions are partial functions from states to states, where a state is represented as a set of bindings. The semantics is used to define the meaning of programs and specifications, including parameters and recursion. To complete the calculus, a notion of correctness-preserving refinement over programs in the wide-spectrum language is defined and refinement laws for developing programs are introduced. The refinement calculus is illustrated using example derivations and prototype tool support is discussed.
CUP: Controlled Update Propagation in Peer-to-Peer Networks
Venue: arXiv cs.NI 2002
Year: 2002

Recently the problem of indexing and locating content in peer-to-peer networks has received much attention. Previous work suggests caching index entries at intermediate nodes that lie on the paths taken by search queries, but until now there has been little focus on how to maintain these intermediate caches. This paper proposes CUP, a new comprehensive architecture for Controlled Update Propagation in peer-to-peer networks. CUP asynchronously builds caches of index entries while answering search queries. It then propagates updates of index entries to maintain these caches. Under unfavorable conditions, when compared with standard caching based on expiration times, CUP reduces the average miss latency by as much as a factor of three. Under favorable conditions, CUP can reduce the average miss latency by more than a factor of ten. CUP refreshes intermediate caches, reduces query latency, and reduces network load by coalescing bursts of queries for the same item. CUP controls and confines propagation to updates whose cost is likely to be recovered by subsequent queries. CUP gives peer-to-peer nodes the flexibility to use their own incentive-based policies to determine when to receive and when to propagate updates. Finally, the small propagation overhead incurred by CUP is more than compensated for by its savings in cache misses.
Non-negative sparse coding
Venue: arXiv cs.NE 2002
Year: 2002

Non-negative sparse coding is a method for decomposing multivariate data into non-negative sparse components. In this paper we briefly describe the motivation behind this type of data representation and its relation to standard sparse coding and non-negative matrix factorization. We then give a simple yet efficient multiplicative algorithm for finding the optimal values of the hidden components. In addition, we show how the basis vectors can be learned from the observed data. Simulations demonstrate the effectiveness of the proposed method.
Distance Semantics for Belief Revision
Venue: arXiv cs.AI 2002
Year: 2002

A vast and interesting family of natural semantics for belief revision is defined. Suppose one is given a distance d between any two models. One may then define the revision of a theory K by a formula a as the theory defined by the set of all those models of a that are closest, by d, to the set of models of K. This family is characterized by a set of rationality postulates that extends the AGM postulates. The new postulates describe properties of iterated revisions.
Preferred History Semantics for Iterated Updates
Venue: arXiv cs.AI 2002
Year: 2002

We give a semantics to iterated update by a preference relation on possible developments. An iterated update is a sequence of formulas, giving (incomplete) information about successive states of the world. A development is a sequence of models, describing a possible trajectory through time. We assume a principle of inertia and prefer those developments, which are compatible with the information, and avoid unnecessary changes. The logical properties of the updates defined in this way are considered, and a representation result is proved.
Generalized Qualitative Probability: Savage revisited
Venue: arXiv cs.GT 2002
Year: 2002

Preferences among acts are analyzed in the style of L. Savage, but as partially ordered. The rationality postulates considered are weaker than Savage's on three counts. The Sure Thing Principle is derived in this setting. The postulates are shown to lead to a characterization of generalized qualitative probability that includes and blends both traditional qualitative probability and the ranked structures used in logical approaches.
Optimal Solutions for Multi-Unit Combinatorial Auctions: Branch and Bound Heuristics
Venue: arXiv cs.GT 2002
Year: 2002

Finding optimal solutions for multi-unit combinatorial auctions is a hard problem and finding approximations to the optimal solution is also hard. We investigate the use of Branch-and-Bound techniques: they require both a way to bound from above the value of the best allocation and a good criterion to decide which bids are to be tried first. Different methods for efficiently bounding from above the value of the best allocation are considered. Theoretical original results characterize the best approximation ratio and the ordering criterion that provides it. We suggest to use this criterion.
Sprinkling Selections over Join DAGs for Efficient Query Optimization
Venue: arXiv cs.DB 2002
Year: 2002

In optimizing queries, solutions based on AND/OR DAG can generate all possible join orderings and select placements before searching for optimal query execution strategy. But as the number of joins and selection conditions increase, the space and time complexity to generate optimal query plan increases exponentially. In this paper, we use join graph for a relational database schema to either pre-compute all possible join orderings that can be executed and store it as a join DAG or, extract joins in the queries to incrementally build a history join DAG as and when the queries are executed. The select conditions in the queries are appropriately placed in the retrieved join DAG (or, history join DAG) to generate optimal query execution strategy. We experimentally evaluate our query optimization technique on TPC-D/H query sets to show their effectiveness over AND/OR DAG query optimization strategy. Finally, we illustrate how our technique can be used for efficient multiple query optimization and selection of materialized views in data warehousing environments.
Towards Generic Refactoring
Venue: arXiv cs.PL 2002
Year: 2002

We study program refactoring while considering the language or even the programming paradigm as a parameter. We use typed functional programs, namely Haskell programs, as the specification medium for a corresponding refactoring framework. In order to detach ourselves from language syntax, our specifications adhere to the following style. (I) As for primitive algorithms for program analysis and transformation, we employ generic function combinators supporting generic traversal and polymorphic functions refined by ad-hoc cases. (II) As for the language abstractions involved in refactorings, we design a dedicated multi-parameter class. This class can be instantiated for abstractions as present in various languages, e.g., Java, Prolog or Haskell.
Deductive Nonmonotonic Inference Operations: Antitonic Representations
Venue: arXiv cs.AI 2002
Year: 2002

We provide a characterization of those nonmonotonic inference operations C for which C(X) may be described as the set of all logical consequences of X together with some set of additional assumptions S(X) that depends anti-monotonically on X (i.e., X is a subset of Y implies that S(Y) is a subset of S(X)). The operations represented are exactly characterized in terms of properties most of which have been studied in Freund-Lehmann(cs.AI/0202031). Similar characterizations of right-absorbing and cumulative operations are also provided. For cumulative operations, our results fit in closely with those of Freund. We then discuss extending finitary operations to infinitary operations in a canonical way and discuss co-compactness properties. Our results provide a satisfactory notion of pseudo-compactness, generalizing to deductive nonmonotonic operations the notion of compactness for monotonic operations. They also provide an alternative, more elegant and more general, proof of the existence of an infinitary deductive extension for any finitary deductive operation (Theorem 7.9 of Freund-Lehmann).
Stereotypical Reasoning: Logical Properties
Venue: arXiv cs.AI 2002
Year: 2002

Stereotypical reasoning assumes that the situation at hand is one of a kind and that it enjoys the properties generally associated with that kind of situation. It is one of the most basic forms of nonmonotonic reasoning. A formal model for stereotypical reasoning is proposed and the logical properties of this form of reasoning are studied. Stereotypical reasoning is shown to be cumulative under weak assumptions.
On Learning by Exchanging Advice
Venue: arXiv cs.LG 2002
Year: 2002

One of the main questions concerning learning in Multi-Agent Systems is: (How) can agents benefit from mutual interaction during the learning process?. This paper describes the study of an interactive advice-exchange mechanism as a possible way to improve agents' learning performance. The advice-exchange technique, discussed here, uses supervised learning (backpropagation), where reinforcement is not directly coming from the environment but is based on advice given by peers with better performance score (higher confidence), to enhance the performance of a heterogeneous group of Learning Agents (LAs). The LAs are facing similar problems, in an environment where only reinforcement information is available. Each LA applies a different, well known, learning technique: Random Walk (hill-climbing), Simulated Annealing, Evolutionary Algorithms and Q-Learning. The problem used for evaluation is a simplified traffic-control simulation. Initial results indicate that advice-exchange can improve learning speed, although bad advice and/or blind reliance can disturb the learning performance.
GridSim: A Toolkit for the Modeling and Simulation of Distributed Resource Management and Scheduling for Grid Computing
Venue: arXiv cs.DC 2002
Year: 2002

Clusters, grids, and peer-to-peer (P2P) networks have emerged as popular paradigms for next generation parallel and distributed computing. The management of resources and scheduling of applications in such large-scale distributed systems is a complex undertaking. In order to prove the effectiveness of resource brokers and associated scheduling algorithms, their performance needs to be evaluated under different scenarios such as varying number of resources and users with different requirements. In a grid environment, it is hard and even impossible to perform scheduler performance evaluation in a repeatable and controllable manner as resources and users are distributed across multiple organizations with their own policies. To overcome this limitation, we have developed a Java-based discrete-event grid simulation toolkit called GridSim. The toolkit supports modeling and simulation of heterogeneous grid resources (both time- and space-shared), users and application models. It provides primitives for creation of application tasks, mapping of tasks to resources, and their management. To demonstrate suitability of the GridSim toolkit, we have simulated a Nimrod-G like grid resource broker and evaluated the performance of deadline and budget constrained cost- and time-minimization scheduling algorithms.