OpenRaiser/Intern-Atlas huggingface dataset:
Conformal Geometry, Euclidean Space and Geometric Algebra
Venue: arXiv cs.CG 2002
Year: 2002

Projective geometry provides the preferred framework for most implementations of Euclidean space in graphics applications. Translations and rotations are both linear transformations in projective geometry, which helps when it comes to programming complicated geometrical operations. But there is a fundamental weakness in this approach - the Euclidean distance between points is not handled in a straightforward manner. Here we discuss a solution to this problem, based on conformal geometry. The language of geometric algebra is best suited to exploiting this geometry, as it handles the interior and exterior products in a single, unified framework. A number of applications are discussed, including a compact formula for reflecting a line off a general spherical surface.
The Algorithms of Updating Sequential Patterns
Venue: arXiv cs.DB 2002
Year: 2002

Because the data being mined in the temporal database will evolve with time, many researchers have focused on the incremental mining of frequent sequences in temporal database. In this paper, we propose an algorithm called IUS, using the frequent and negative border sequences in the original database for incremental sequence mining. To deal with the case where some data need to be updated from the original database, we present an algorithm called DUS to maintain sequential patterns in the updated database. We also define the negative border sequence threshold: Min_nbd_supp to control the number of sequences in the negative border.
Coin-Moving Puzzles
Venue: arXiv cs.DM 2002
Year: 2002

We introduce a new family of one-player games, involving the movement of coins from one configuration to another. Moves are restricted so that a coin can be placed only in a position that is adjacent to at least two other coins. The goal of this paper is to specify exactly which of these games are solvable. By introducing the notion of a constant number of extra coins, we give tight theorems characterizing solvable puzzles on the square grid and equilateral-triangle grid. These existence results are supplemented by polynomial-time algorithms for finding a solution.
New Results on Monotone Dualization and Generating Hypergraph Transversals
Venue: arXiv cs.DS 2002
Year: 2002

We consider the problem of dualizing a monotone CNF (equivalently, computing all minimal transversals of a hypergraph), whose associated decision problem is a prominent open problem in NP-completeness. We present a number of new polynomial time resp. output-polynomial time results for significant cases, which largely advance the tractability frontier and improve on previous results. Furthermore, we show that duality of two monotone CNFs can be disproved with limited nondeterminism. More precisely, this is feasible in polynomial time with O(chi(n) * log n) suitably guessed bits, where chi(n) is given by χ(n)^chi(n) = n; note that chi(n) = o(log n). This result sheds new light on the complexity of this important problem.
Fair Stateless Aggregate Traffic Marking using Active Queue Management Techniques
Venue: arXiv cs.NI 2002
Year: 2002

In heterogeneous networks such as today's Internet, the differentiated services architecture promises to provide QoS guarantees through scalable service differentiation. Traffic marking is an important component of this framework. In this paper, we propose two new aggregate markers that are stateless, scalable and fair. We leverage stateless Active Queue Management (AQM) algorithms to enable fair and efficient token distribution among individual flows of an aggregate. The first marker, Probabilistic Aggregate Marker (PAM), uses the Token Bucket burst size to probabilistically mark incoming packets to ensure TCP-friendly and proportionally fair marking. The second marker, Stateless Aggregate Fair Marker (F-SAM) approximates fair queueing techniques to isolate flows while marking packets of the aggregate. It distributes tokens evenly among the flows without maintaining per-flow state. Our simulation results show that our marking strategies show upto 30% improvement over other commonly used markers while marking flow aggregates. These improvements are in terms of better average throughput and fairness indices, in scenarios containing heterogeneous traffic consisting of TCP (both long lived elephants and short lived mice) and misbehaving UDP flows. As a bonus, F-SAM helps the mice to win the war against elephants.
Computational Phonology
Venue: arXiv cs.CL 2002
Year: 2002

Phonology, as it is practiced, is deeply computational. Phonological analysis is data-intensive and the resulting models are nothing other than specialized data structures and algorithms. In the past, phonological computation - managing data and developing analyses - was done manually with pencil and paper. Increasingly, with the proliferation of affordable computers, IPA fonts and drawing software, phonologists are seeking to move their computation work online. Computational Phonology provides the theoretical and technological framework for this migration, building on methodologies and tools from computational linguistics. This piece consists of an apology for computational phonology, a history, and an overview of current research.
Phonology
Venue: arXiv cs.CL 2002
Year: 2002

Phonology is the systematic study of the sounds used in language, their internal structure, and their composition into syllables, words and phrases. Computational phonology is the application of formal and computational techniques to the representation and processing of phonological information. This chapter will present the fundamentals of descriptive phonology along with a brief overview of computational phonology.
The Basque task: did systems perform in the upperbound?
Venue: arXiv cs.CL 2002
Year: 2002

In this paper we describe the Senseval 2 Basque lexical-sample task. The task comprised 40 words (15 nouns, 15 verbs and 10 adjectives) selected from Euskal Hiztegia, the main Basque dictionary. Most examples were taken from the Egunkaria newspaper. The method used to hand-tag the examples produced low inter-tagger agreement (75%) before arbitration. The four competing systems attained results well above the most frequent baseline and the best system scored 75% precision at 100% coverage. The paper includes an analysis of the tagging procedure used, as well as the performance of the competing systems. In particular, we argue that inter-tagger agreement is not a real upperbound for the Basque WSD task.
Fast Hands-free Writing by Gaze Direction
Venue: arXiv cs.HC 2002
Year: 2002

We describe a method for text entry based on inverse arithmetic coding that relies on gaze direction and which is faster and more accurate than using an on-screen keyboard. These benefits are derived from two innovations: the writing task is matched to the capabilities of the eye, and a language model is used to make predictable words and phrases easier to write.
Trust Brokerage Systems for the Internet
Venue: arXiv cs.CR 2002
Year: 2002

This thesis addresses the problem of providing trusted individuals with confidential information about other individuals, in particular, granting access to databases of personal records using the World-Wide Web. It proposes an access rights management system for distributed databases which aims to create and implement organisation structures based on the wishes of the owners and of demands of the users of the databases. The dissertation describes how current software components could be used to implement this system; it re-examines the theory of collective choice to develop mechanisms for generating hierarchies of authorities; it analyses organisational processes for stability and develops a means of measuring the similarity of their hierarchies.
Some applications of logic to feasibility in higher types
Venue: arXiv cs.LO 2002
Year: 2002

In this paper we demonstrate that the class of basic feasible functionals has recursion theoretic properties which naturally generalize the corresponding properties of the class of feasible functions. We also improve the Kapron - Cook result on mashine representation of basic feasible functionals. Our proofs are based on essential applications of logic. We introduce a weak fragment of second order arithmetic with second order variables ranging over functions from N into N which suitably characterizes basic feasible functionals, and show that it is a useful tool for investigating the properties of basic feasible functionals. In particular, we provide an example how one can extract feasible "programs" from mathematical proofs which use non-feasible functionals (like second order polynomials).
Sampling Strategies for Mining in Data-Scarce Domains
Venue: arXiv cs.CE 2002
Year: 2002

Data mining has traditionally focused on the task of drawing inferences from large datasets. However, many scientific and engineering domains, such as fluid dynamics and aircraft design, are characterized by scarce data, due to the expense and complexity of associated experiments and simulations. In such data-scarce domains, it is advantageous to focus the data collection effort on only those regions deemed most important to support a particular data mining objective. This paper describes a mechanism that interleaves bottom-up data mining, to uncover multi-level structures in spatial data, with top-down sampling, to clarify difficult decisions in the mining process. The mechanism exploits relevant physical properties, such as continuity, correspondence, and locality, in a unified framework. This leads to effective mining and sampling decisions that are explainable in terms of domain knowledge and data characteristics. This approach is demonstrated in two diverse applications -- mining pockets in spatial data, and qualitative determination of Jordan forms of matrices.
Economic-based Distributed Resource Management and Scheduling for Grid Computing
Venue: arXiv cs.DC 2002
Year: 2002

Computational Grids, emerging as an infrastructure for next generation computing, enable the sharing, selection, and aggregation of geographically distributed resources for solving large-scale problems in science, engineering, and commerce. As the resources in the Grid are heterogeneous and geographically distributed with varying availability and a variety of usage and cost policies for diverse users at different times and, priorities as well as goals that vary with time. The management of resources and application scheduling in such a large and distributed environment is a complex task. This thesis proposes a distributed computational economy as an effective metaphor for the management of resources and application scheduling. It proposes an architectural framework that supports resource trading and quality of services based scheduling. It enables the regulation of supply and demand for resources and provides an incentive for resource owners for participating in the Grid and motives the users to trade-off between the deadline, budget, and the required level of quality of service. The thesis demonstrates the capability of economic-based systems for peer-to-peer distributed computing by developing users' quality-of-service requirements driven scheduling strategies and algorithms. It demonstrates their effectiveness by performing scheduling experiments on the World-Wide Grid for solving parameter sweep applications.
Parrondo Strategies for Artificial Traders
Venue: arXiv cs.CE 2002
Year: 2002

On markets with receding prices, artificial noise traders may consider alternatives to buy-and-hold. By simulating variations of the Parrondo strategy, using real data from the Swedish stock market, we produce first indications of a buy-low-sell-random Parrondo variation outperforming buy-and-hold. Subject to our assumptions, buy-low-sell-random also outperforms the traditional value and trend investor strategies. We measure the success of the Parrondo variations not only through their performance compared to other kinds of strategies, but also relative to varying levels of perfect information, received through messages within a multi-agent system of artificial traders.
Unsupervised discovery of morphologically related words based on orthographic and semantic similarity
Venue: arXiv cs.CL 2002
Year: 2002

We present an algorithm that takes an unannotated corpus as its input, and returns a ranked list of probable morphologically related pairs as its output. The algorithm tries to discover morphologically related pairs by looking for pairs that are both orthographically and semantically similar, where orthographic similarity is measured in terms of minimum edit distance, and semantic similarity is measured in terms of mutual information. The procedure does not rely on a morpheme concatenation model, nor on distributional properties of word substrings (such as affix frequency). Experiments with German and English input give encouraging results, both in terms of precision (proportion of good pairs found at various cutoff points of the ranked list), and in terms of a qualitative analysis of the types of morphological patterns discovered by the algorithm.
Mostly-Unsupervised Statistical Segmentation of Japanese Kanji Sequences
Venue: arXiv cs.CL 2002
Year: 2002

Given the lack of word delimiters in written Japanese, word segmentation is generally considered a crucial first step in processing Japanese texts. Typical Japanese segmentation algorithms rely either on a lexicon and syntactic analysis or on pre-segmented data; but these are labor-intensive, and the lexico-syntactic techniques are vulnerable to the unknown word problem. In contrast, we introduce a novel, more robust statistical method utilizing unsegmented training data. Despite its simplicity, the algorithm yields performance on long kanji sequences comparable to and sometimes surpassing that of state-of-the-art morphological analyzers over a variety of error metrics. The algorithm also outperforms another mostly-unsupervised statistical algorithm previously proposed for Chinese. Additionally, we present a two-level annotation scheme for Japanese to incorporate multiple segmentation granularities, and introduce two novel evaluation metrics, both based on the notion of a compatible bracket, that can account for multiple granularities simultaneously.
Ultimate approximations in nonmonotonic knowledge representation systems
Venue: arXiv cs.AI 2002
Year: 2002

We study fixpoints of operators on lattices. To this end we introduce the notion of an approximation of an operator. We order approximations by means of a precision ordering. We show that each lattice operator O has a unique most precise or ultimate approximation. We demonstrate that fixpoints of this ultimate approximation provide useful insights into fixpoints of the operator O. We apply our theory to logic programming and introduce the ultimate Kripke-Kleene, well-founded and stable semantics. We show that the ultimate Kripke-Kleene and well-founded semantics are more precise then their standard counterparts We argue that ultimate semantics for logic programming have attractive epistemological properties and that, while in general they are computationally more complex than the standard semantics, for many classes of theories, their complexity is no worse.
The Traits of the Personable
Venue: arXiv cs.AI 2002
Year: 2002

Information personalization is fertile ground for application of AI techniques. In this article I relate personalization to the ability to capture partial information in an information-seeking interaction. The specific focus is on personalizing interactions at web sites. Using ideas from partial evaluation and explanation-based generalization, I present a modeling methodology for reasoning about personalization. This approach helps identify seven tiers of `personable traits' in web sites.
NLTK: The Natural Language Toolkit
Venue: arXiv cs.CL 2002
Year: 2002

NLTK, the Natural Language Toolkit, is a suite of open source program modules, tutorials and problem sets, providing ready-to-use computational linguistics courseware. NLTK covers symbolic and statistical natural language processing, and is interfaced to annotated corpora. Students augment and replace existing components, learn structured programming by example, and manipulate sophisticated models from the outset.
A Codebook Generation Algorithm for Document Image Compression
Venue: arXiv cs.DS 2002
Year: 2002

Pattern-matching-based document-compression systems (e.g. for faxing) rely on finding a small set of patterns that can be used to represent all of the ink in the document. Finding an optimal set of patterns is NP-hard; previous compression schemes have resorted to heuristics. This paper describes an extension of the cross-entropy approach, used previously for measuring pattern similarity, to this problem. This approach reduces the problem to a k-medians problem, for which the paper gives a new algorithm with a provably good performance guarantee. In comparison to previous heuristics (First Fit, with and without generalized Lloyd's/k-means postprocessing steps), the new algorithm generates a better codebook, resulting in an overall improvement in compression performance of almost 17%.
Data-Collection for the Sloan Digital Sky Survey: a Network-Flow Heuristic
Venue: arXiv cs.DS 2002
Year: 2002

The goal of the Sloan Digital Sky Survey is ``to map in detail one-quarter of the entire sky, determining the positions and absolute brightnesses of more than 100 million celestial objects''. The survey will be performed by taking ``snapshots'' through a large telescope. Each snapshot can capture up to 600 objects from a small circle of the sky. This paper describes the design and implementation of the algorithm that is being used to determine the snapshots so as to minimize their number. The problem is NP-hard in general; the algorithm described is a heuristic, based on Lagriangian-relaxation and min-cost network flow. It gets within 5-15% of a naive lower bound, whereas using a ``uniform'' cover only gets within 25-35%.
Simple Strategies for Large Zero-Sum Games with Applications to Complexity Theory
Venue: arXiv cs.CC 2002
Year: 2002

Von Neumann's Min-Max Theorem guarantees that each player of a zero-sum matrix game has an optimal mixed strategy. This paper gives an elementary proof that each player has a near-optimal mixed strategy that chooses uniformly at random from a multiset of pure strategies of size logarithmic in the number of pure strategies available to the opponent. For exponentially large games, for which even representing an optimal mixed strategy can require exponential space, it follows that there are near-optimal, linear-size strategies. These strategies are easy to play and serve as small witnesses to the approximate value of the game. As a corollary, it follows that every language has small ``hard'' multisets of inputs certifying that small circuits can't decide the language. For example, if SAT does not have polynomial-size circuits, then, for each n and c, there is a set of n^(O(c)) Boolean formulae of size n such that no circuit of size n^c (or algorithm running in time n^c) classifies more than two-thirds of the formulae succesfully.
A Primal-Dual Parallel Approximation Technique Applied to Weighted Set and Vertex Cover
Venue: arXiv cs.DS 2002
Year: 2002

The paper describes a simple deterministic parallel/distributed (2+epsilon)-approximation algorithm for the minimum-weight vertex-cover problem and its dual (edge/element packing).
Orienting Graphs to Optimize Reachability
Venue: arXiv cs.DS 2002
Year: 2002

The paper focuses on two problems: (i) how to orient the edges of an undirected graph in order to maximize the number of ordered vertex pairs (x,y) such that there is a directed path from x to y, and (ii) how to orient the edges so as to minimize the number of such pairs. The paper describes a quadratic-time algorithm for the first problem, and a proof that the second problem is NP-hard to approximate within some constant 1+epsilon > 1. The latter proof also shows that the second problem is equivalent to ``comparability graph completion''; neither problem was previously known to be NP-hard.
The K-Server Dual and Loose Competitiveness for Paging
Venue: arXiv cs.DS 2002
Year: 2002

This paper has two results. The first is based on the surprising observation that the well-known ``least-recently-used'' paging algorithm and the ``balance'' algorithm for weighted caching are linear-programming primal-dual algorithms. This observation leads to a strategy (called ``Greedy-Dual'') that generalizes them both and has an optimal performance guarantee for weighted caching. For the second result, the paper presents empirical studies of paging algorithms, documenting that in practice, on ``typical'' cache sizes and sequences, the performance of paging strategies are much better than their worst-case analyses in the standard model suggest. The paper then presents theoretical results that support and explain this. For example: on any input sequence, with almost all cache sizes, either the performance guarantee of least-recently-used is O(log k) or the fault rate (in an absolute sense) is insignificant. Both of these results are strengthened and generalized in``On-line File Caching'' (1998).
A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees
Venue: arXiv cs.DS 2002
Year: 2002

The problem considered is the following. Given a graph with edge weights satisfying the triangle inequality, and a degree bound for each vertex, compute a low-weight spanning tree such that the degree of each vertex is at most its specified bound. The problem is NP-hard (it generalizes Traveling Salesman (TSP)). This paper describes a network-flow heuristic for modifying a given tree T to meet the constraints. Choosing T to be a minimum spanning tree (MST) yields approximation algorithms with performance guarantee less than 2 for the problem on geometric graphs with L_p-norms. The paper also describes a Euclidean graph whose minimum TSP costs twice the MST, disproving a conjecture made in ``Low-Degree Spanning Trees of Small Weight'' (1996).
Unsupervised Discovery of Morphemes
Venue: arXiv cs.CL 2002
Year: 2002

We present two methods for unsupervised segmentation of words into morpheme-like units. The model utilized is especially suited for languages with a rich morphology, such as Finnish. The first method is based on the Minimum Description Length (MDL) principle and works online. In the second method, Maximum Likelihood (ML) optimization is used. The quality of the segmentations is measured using an evaluation method that compares the segmentations produced to an existing morphological analysis. Experiments on both Finnish and English corpora show that the presented methods perform well compared to a current state-of-the-art system.
Aging, double helix and small world property in genetic algorithms
Venue: arXiv cs.NE 2002
Year: 2002

Over a quarter of century after the invention of genetic algorithms and miriads of their modifications, as well as successful implementations, we are still lacking many essential details of thorough analysis of it's inner working. One of such fundamental questions is: how many generations do we need to solve the optimization problem? This paper tries to answer this question, albeit in a fuzzy way, making use of the double helix concept. As a byproduct we gain better understanding of the ways, in which the genetic algorithm may be fine tuned.
Evaluating the Effectiveness of Ensembles of Decision Trees in Disambiguating Senseval Lexical Samples
Venue: arXiv cs.CL 2002
Year: 2002

This paper presents an evaluation of an ensemble--based system that participated in the English and Spanish lexical sample tasks of Senseval-2. The system combines decision trees of unigrams, bigrams, and co--occurrences into a single classifier. The analysis is extended to include the Senseval-1 data.