OpenRaiser/Intern-Atlas huggingface dataset:
Business Intelligence from Web Usage Mining
Venue: arXiv cs.AI 2004
Year: 2004

The rapid e-commerce growth has made both business community and customers face a new situation. Due to intense competition on one hand and the customer's option to choose from several alternatives business community has realized the necessity of intelligent marketing strategies and relationship management. Web usage mining attempts to discover useful knowledge from the secondary data obtained from the interactions of the users with the Web. Web usage mining has become very critical for effective Web site management, creating adaptive Web sites, business and support services, personalization, network traffic flow analysis and so on. In this paper, we present the important concepts of Web usage mining and its various practical applications. We further present a novel approach 'intelligent-miner' (i-Miner) to optimize the concurrent architecture of a fuzzy clustering algorithm (to discover web data clusters) and a fuzzy inference system to analyze the Web site visitor trends. A hybrid evolutionary fuzzy clustering algorithm is proposed in this paper to optimally segregate similar user interests. The clustered data is then used to analyze the trends using a Takagi-Sugeno fuzzy inference system learned using a combination of evolutionary algorithm and neural network learning. Proposed approach is compared with self-organizing maps (to discover patterns) and several function approximation techniques like neural networks, linear genetic programming and Takagi-Sugeno fuzzy inference system (to analyze the clusters). The results are graphically illustrated and the practical significance is discussed in detail. Empirical results clearly show that the proposed Web usage-mining framework is efficient.
Corpus structure, language models, and ad hoc information retrieval
Venue: arXiv cs.IR 2004
Year: 2004

Most previous work on the recently developed language-modeling approach to information retrieval focuses on document-specific characteristics, and therefore does not take into account the structure of the surrounding corpus. We propose a novel algorithmic framework in which information provided by document-based language models is enhanced by the incorporation of information drawn from clusters of similar documents. Using this framework, we develop a suite of new algorithms. Even the simplest typically outperforms the standard language-modeling approach in precision and recall, and our new interpolation algorithm posts statistically significant improvements for both metrics over all three corpora tested.
Efficiency Enhancement of Genetic Algorithms via Building-Block-Wise Fitness Estimation
Venue: arXiv cs.NE 2004
Year: 2004

This paper studies fitness inheritance as an efficiency enhancement technique for a class of competent genetic algorithms called estimation distribution algorithms. Probabilistic models of important sub-solutions are developed to estimate the fitness of a proportion of individuals in the population, thereby avoiding computationally expensive function evaluations. The effect of fitness inheritance on the convergence time and population sizing are modeled and the speed-up obtained through inheritance is predicted. The results show that a fitness-inheritance mechanism which utilizes information on building-block fitnesses provides significant efficiency enhancement. For additively separable problems, fitness inheritance reduces the number of function evaluations to about half and yields a speed-up of about 1.75--2.25.
A Logic for Reasoning about Digital Rights
Venue: arXiv cs.CR 2004
Year: 2004

We present a logic for reasoning about licenses, which are ``terms of use'' for digital resources. The logic provides a language for writing both properties of licenses and specifications that govern a client's actions. We discuss the complexity of checking properties and specifications written in our logic and propose a technique for verification. A key feature of our approach is that it is essentially parameterized by the language in which the licenses are written, provided that this language can be given a trace-based semantics. We consider two license languages to illustrate this flexibility.
Traffic-driven model of the World Wide Web graph
Venue: arXiv cs.NI 2004
Year: 2004

We propose a model for the World Wide Web graph that couples the topological growth with the traffic's dynamical evolution. The model is based on a simple traffic-driven dynamics and generates weighted directed graphs exhibiting the statistical properties observed in the Web. In particular, the model yields a non-trivial time evolution of vertices and heavy-tail distributions for the topological and traffic properties. The generated graphs exhibit a complex architecture with a hierarchy of cohesiveness levels similar to those observed in the analysis of real data.
A New Dynamical Domain Decomposition Method for Parallel Molecular Dynamics Simulation on Grid
Venue: arXiv cs.DC 2004
Year: 2004

We develop a new Lagrangian material particle -- dynamical domain decomposition method (MPD^3) for large scale parallel molecular dynamics (MD) simulation of nonstationary heterogeneous systems on a heterogeneous computing net. MPD^3 is based on Voronoi decomposition of simulated matter. The map of Voronoi polygons is known as the Dirichlet tessellation and used for grid generation in computational fluid dynamics. From the hydrodynamics point of view the moving Voronoi polygon looks as a material particle (MP). MPs can exchange particles and information. To balance heterogeneous computing conditions the MP centers should be dependent on timing data. We propose a simple and efficient iterative algorithm which based on definition of the timing-dependent balancing displacement of MP center for next simulation step. The MPD^3 program was tested in various computing environments and physical problems. We have demonstrated that MPD^3 is a high-adaptive decomposition algorithm for MD simulation. It was shown that the well-balanced decomposition can result from dynamical Voronoi polygon tessellation. One would expect the similar approach can be successfully applied for other particle methods like Monte Carlo, particle-in-cell, and smooth-particle-hydrodynamics.
A Grid Information Infrastructure for Medical Image Analysis
Venue: arXiv cs.DB 2004
Year: 2004

The storage and manipulation of digital images and the analysis of the information held in those images are essential requirements for next-generation medical information systems. The medical community has been exploring collaborative approaches for managing image data and exchanging knowledge and Grid technology [1] is a promising approach to enabling distributed analysis across medical institutions and for developing new collaborative and cooperative approaches for image analysis without the necessity for clinicians to co-locate. The EU-funded MammoGrid project [2] is one example of this and it aims to develop a Europe-wide database of mammograms to support effective co-working between healthcare professionals across the EU. The MammoGrid prototype comprises a high-quality clinician visualization workstation (for data acquisition and inspection), a DICOM-compliant interface to a set of medical services (annotation, security, image analysis, data storage and querying services) residing on a so-called Grid-box and secure access to a network of other Grid-boxes connected through Grid middleware. One of the main deliverables of the project is a Grid-enabled infrastructure that manages federated mammogram databases across Europe. This paper outlines the MammoGrid Information Infrastructure (MII) for meta-data analysis and knowledge discovery in the medical imaging domain.
The Complexity of Maximum Matroid-Greedoid Intersection and Weighted Greedoid Maximization
Venue: arXiv cs.DS 2004
Year: 2004

The maximum intersection problem for a matroid and a greedoid, given by polynomial-time oracles, is shown $NP$-hard by expressing the satisfiability of boolean formulas in 3-conjunctive normal form as such an intersection. The corresponding approximation problems are shown $NP$-hard for certain approximation performance bounds. Moreover, some natural parameterized variants of the problem are shown $W[P]$-hard. The results are in contrast with the maximum matroid-matroid intersection which is solvable in polynomial time by an old result of Edmonds. We also prove that it is $NP$-hard to approximate the weighted greedoid maximization within $2^{n^{O(1)}}$ where $n$ is the size of the domain of the greedoid. A preliminary version ``The Complexity of Maximum Matroid-Greedoid Intersection'' appeared in Proc. FCT 2001, LNCS 2138, pp. 535--539, Springer-Verlag 2001.
On model checking data-independent systems with arrays without reset
Venue: arXiv cs.LO 2004
Year: 2004

A system is data-independent with respect to a data type X iff the operations it can perform on values of type X are restricted to just equality testing. The system may also store, input and output values of type X. We study model checking of systems which are data-independent with respect to two distinct type variables X and Y, and may in addition use arrays with indices from X and values from Y . Our main interest is the following parameterised model-checking problem: whether a given program satisfies a given temporal-logic formula for all non-empty nite instances of X and Y . Initially, we consider instead the abstraction where X and Y are infinite and where partial functions with finite domains are used to model arrays. Using a translation to data-independent systems without arrays, we show that the u-calculus model-checking problem is decidable for these systems. From this result, we can deduce properties of all systems with finite instances of X and Y . We show that there is a procedure for the above parameterised model-checking problem of the universal fragment of the u-calculus, such that it always terminates but may give false negatives. We also deduce that the parameterised model-checking problem of the universal disjunction-free fragment of the u-calculus is decidable. Practical motivations for model checking data-independent systems with arrays include verification of memory and cache systems, where X is the type of memory addresses, and Y the type of storable values. As an example we verify a fault-tolerant memory interface over a set of unreliable memories.
Side-Information Coding with Turbo Codes and its Application to Quantum Key Distribution
Venue: arXiv cs.IT 2004
Year: 2004

Turbo coding is a powerful class of forward error correcting codes, which can achieve performances close to the Shannon limit. The turbo principle can be applied to the problem of side-information source coding, and we investigate here its application to the reconciliation problem occurring in a continuous-variable quantum key distribution protocol.
Parallel Mixed Bayesian Optimization Algorithm: A Scaleup Analysis
Venue: arXiv cs.NE 2004
Year: 2004

Estimation of Distribution Algorithms have been proposed as a new paradigm for evolutionary optimization. This paper focuses on the parallelization of Estimation of Distribution Algorithms. More specifically, the paper discusses how to predict performance of parallel Mixed Bayesian Optimization Algorithm (MBOA) that is based on parallel construction of Bayesian networks with decision trees. We determine the time complexity of parallel Mixed Bayesian Optimization Algorithm and compare this complexity with experimental results obtained by solving the spin glass optimization problem. The empirical results fit well the theoretical time complexity, so the scalability and efficiency of parallel Mixed Bayesian Optimization Algorithm for unknown instances of spin glass benchmarks can be predicted. Furthermore, we derive the guidelines that can be used to design effective parallel Estimation of Distribution Algorithms with the speedup proportional to the number of variables in the problem.
Optimization of Bound Disjunctive Queries with Constraints
Venue: arXiv cs.LO 2004
Year: 2004

"To Appear in Theory and Practice of Logic Programming (TPLP)" This paper presents a technique for the optimization of bound queries over disjunctive deductive databases with constraints. The proposed approach is an extension of the well-known Magic-Set technique and is well-suited for being integrated in current bottom-up (stable) model inference engines. More specifically, it is based on the exploitation of binding propagation techniques which reduce the size of the data relevant to answer the query and, consequently, reduces both the complexity of computing a single model and the number of models to be considered. The motivation of this work stems from the observation that traditional binding propagation optimization techniques for bottom-up model generator systems, simulating the goal driven evaluation of top-down engines, are only suitable for positive (disjunctive) queries, while hard problems are expressed using unstratified negation. The main contribution of the paper consists in the extension of a previous technique, defined for positive disjunctive queries, to queries containing both disjunctive heads and constraints (a simple and expressive form of unstratified negation). As the usual way of expressing declaratively hard problems is based on the guess-and-check technique, where the guess part is expressed by means of disjunctive rules and the check part is expressed by means of constraints, the technique proposed here is highly relevant for the optimization of queries expressing hard problems. The value of the technique has been proved by several experiments.
Using Self-Organising Mappings to Learn the Structure of Data Manifolds
Venue: arXiv cs.NE 2004
Year: 2004

In this paper it is shown how to map a data manifold into a simpler form by progressively discarding small degrees of freedom. This is the key to self-organising data fusion, where the raw data is embedded in a very high-dimensional space (e.g. the pixel values of one or more images), and the requirement is to isolate the important degrees of freedom which lie on a low-dimensional manifold. A useful advantage of the approach used in this paper is that the computations are arranged as a feed-forward processing chain, where all the details of the processing in each stage of the chain are learnt by self-organisation. This approach is demonstrated using hierarchically correlated data, which causes the processing chain to split the data into separate processing channels, and then to progressively merge these channels wherever they are correlated with each other. This is the key to self-organising data fusion.
Providing Service Guarantees in High-Speed Switching Systems with Feedback Output Queuing
Venue: arXiv cs.NI 2004
Year: 2004

We consider the problem of providing service guarantees in a high-speed packet switch. As basic requirements, the switch should be scalable to high speeds per port, a large number of ports and a large number of traffic flows with independent guarantees. Existing scalable solutions are based on Virtual Output Queuing, which is computationally complex when required to provide service guarantees for a large number of flows. We present a novel architecture for packet switching that provides support for such service guarantees. A cost-effective fabric with small external speedup is combined with a feedback mechanism that enables the fabric to be virtually lossless, thus avoiding packet drops indiscriminate of flows. Through analysis and simulation, we show that this architecture provides accurate support for service guarantees, has low computational complexity and is scalable to very high port speeds.
Notions of Equivalence in Software Design
Venue: arXiv cs.SE 2004
Year: 2004

Design methods in information systems frequently create software descriptions using formal languages. Nonetheless, most software designers prefer to describe software using natural languages. This distinction is not simply a matter of convenience. Natural languages are not the same as formal languages; in particular, natural languages do not follow the notions of equivalence used by formal languages. In this paper, we show both the existence and coexistence of different notions of equivalence by extending the no-tion of oracles used in formal languages. This allows distinctions to be made between the trustworthy oracles assumed by formal languages and the untrust-worthy oracles used by natural languages. By examin-ing the notion of equivalence, we hope to encourage designers of software to rethink the place of ambiguity in software design.
Layout of Graphs with Bounded Tree-Width
Venue: arXiv cs.DM 2004
Year: 2004

A \emph{queue layout} of a graph consists of a total order of the vertices, and a partition of the edges into \emph{queues}, such that no two edges in the same queue are nested. The minimum number of queues in a queue layout of a graph is its \emph{queue-number}. A \emph{three-dimensional (straight-line grid) drawing} of a graph represents the vertices by points in $\mathbb{Z}^3$ and the edges by non-crossing line-segments. This paper contributes three main results: (1) It is proved that the minimum volume of a certain type of three-dimensional drawing of a graph $G$ is closely related to the queue-number of $G$. In particular, if $G$ is an $n$-vertex member of a proper minor-closed family of graphs (such as a planar graph), then $G$ has a $O(1)\times O(1)\times O(n)$ drawing if and only if $G$ has O(1) queue-number. (2) It is proved that queue-number is bounded by tree-width, thus resolving an open problem due to Ganley and Heath (2001), and disproving a conjecture of Pemmaraju (1992). This result provides renewed hope for the positive resolution of a number of open problems in the theory of queue layouts. (3) It is proved that graphs of bounded tree-width have three-dimensional drawings with O(n) volume. This is the most general family of graphs known to admit three-dimensional drawings with O(n) volume. The proofs depend upon our results regarding \emph{track layouts} and \emph{tree-partitions} of graphs, which may be of independent interest.
Ramsey-type theorems for metric spaces with applications to online problems
Venue: arXiv cs.DS 2004
Year: 2004

A nearly logarithmic lower bound on the randomized competitive ratio for the metrical task systems problem is presented. This implies a similar lower bound for the extensively studied k-server problem. The proof is based on Ramsey-type theorems for metric spaces, that state that every metric space contains a large subspace which is approximately a hierarchically well-separated tree (and in particular an ultrametric). These Ramsey-type theorems may be of independent interest.
A Public Reference Implementation of the RAP Anaphora Resolution Algorithm
Venue: arXiv cs.CL 2004
Year: 2004

This paper describes a standalone, publicly-available implementation of the Resolution of Anaphora Procedure (RAP) given by Lappin and Leass (1994). The RAP algorithm resolves third person pronouns, lexical anaphors, and identifies pleonastic pronouns. Our implementation, JavaRAP, fills a current need in anaphora resolution research by providing a reference implementation that can be benchmarked against current algorithms. The implementation uses the standard, publicly available Charniak (2000) parser as input, and generates a list of anaphora-antecedent pairs as output. Alternately, an in-place annotation or substitution of the anaphors with their antecedents can be produced. Evaluation on the MUC-6 co-reference task shows that JavaRAP has an accuracy of 57.9%, similar to the performance given previously in the literature (e.g., Preiss 2002).
A Dynamic Clustering-Based Markov Model for Web Usage Mining
Venue: arXiv cs.IR 2004
Year: 2004

Markov models have been widely utilized for modelling user web navigation behaviour. In this work we propose a dynamic clustering-based method to increase a Markov model's accuracy in representing a collection of user web navigation sessions. The method makes use of the state cloning concept to duplicate states in a way that separates in-links whose corresponding second-order probabilities diverge. In addition, the new method incorporates a clustering technique which determines an effcient way to assign in-links with similar second-order probabilities to the same clone. We report on experiments conducted with both real and random data and we provide a comparison with the N-gram Markov concept. The results show that the number of additional states induced by the dynamic clustering method can be controlled through a threshold parameter, and suggest that the method's performance is linear time in the size of the model.
A New Approach to Draw Detection by Move Repetition in Computer Chess Programming
Venue: arXiv cs.AI 2004
Year: 2004

We will try to tackle both the theoretical and practical aspects of a very important problem in chess programming as stated in the title of this article - the issue of draw detection by move repetition. The standard approach that has so far been employed in most chess programs is based on utilising positional matrices in original and compressed format as well as on the implementation of the so-called bitboard format. The new approach that we will be trying to introduce is based on using variant strings generated by the search algorithm (searcher) during the tree expansion in decision making. We hope to prove that this approach is more efficient than the standard treatment of the issue, especially in positions with few pieces (endgames). To illustrate what we have in mind a machine language routine that implements our theoretical assumptions is attached. The routine is part of the Axon chess program, developed by the authors. Axon, in its current incarnation, plays chess at master strength (ca. 2400-2450 Elo, based on both Axon vs computer programs and Axon vs human masters in over 3000 games altogether).
Business Process Measures
Venue: arXiv cs.CE 2004
Year: 2004

The paper proposes a new methodology for defining business process measures and their computation. The approach is based on metamodeling according to MOF. Especially, a metamodel providing precise definitions of typical process measures for UML activity diagram-like notation is proposed, including precise definitions how measures should be aggregated for composite process elements. The proposed approach allows defining values in a natural way, and measurement of data, which are of interest to business, without deep investigation into specific technical solutions. This provides new possibilities for business process measurement, decreasing the gap between technical solutions and asset management methodologies.
A Fast, Vectorizable Algorithm for Producing Single-Precision Sine-Cosine Pairs
Venue: arXiv cs.MS 2004
Year: 2004

This paper presents an algorithm for computing Sine-Cosine pairs to modest accuracy, but in a manner which contains no conditional tests or branching, making it highly amenable to vectorization. An exemplary implementation for PowerPC AltiVec processors is included, but the algorithm should be easily portable to other achitectures, such as Intel SSE.
Modelling the costs and benefits of Honeynets
Venue: arXiv cs.CR 2004
Year: 2004

For many IT-security measures exact costs and benefits are not known. This makes it difficult to allocate resources optimally to different security measures. We present a model for costs and benefits of so called Honeynets. This can foster informed reasoning about the deployment of honeynet technology.