Archives for 2004

Today I read a paper titled “Automatically Generating Interfaces for Personalized Interaction with Digital Libraries”

The abstract is:
We present an approach to automatically generate interfaces supporting personalized interaction with digital libraries; these interfaces augment the user-DL dialog by empowering the user to (optionally) supply out-of-turn information during an interaction, flatten or restructure the dialog, and enquire about dialog options.

Interfaces generated using this approach for CITIDEL are described.

Today I read a paper titled “The Freeze-Tag Problem: How to Wake Up a Swarm of Robots”

The abstract is:
An optimization problem that naturally arises in the study of swarm robotics is the Freeze-Tag Problem (FTP) of how to awaken a set of “asleep” robots, by having an awakened robot move to their locations.

Once a robot is awake, it can assist in awakening other slumbering robots.The objective is to have all robots awake as early as possible.

While the FTP bears some resemblance to problems from areas in combinatorial optimization such as routing, broadcasting, scheduling, and covering, its algorithmic characteristics are surprisingly different.

We consider both scenarios on graphs and in geometric environments.In graphs, robots sleep at vertices and there is a length function on the edges.

Awake robots travel along edges, with time depending on edge length.

For most scenarios, we consider the offline version of the problem, in which each awake robot knows the position of all other robots.

We prove that the problem is NP-hard, even for the special case of star graphs.

We also establish hardness of approximation, showing that it is NP-hard to obtain an approximation factor better than 5/3, even for graphs of bounded degree.These lower bounds are complemented with several positive algorithmic results, including: (1) We show that the natural greedy strategy on star graphs has a tight worst-case performance of 7/3 and give a polynomial-time approximation scheme (PTAS) for star graphs.

(2) We give a simple O(log D)-competitive online algorithm for graphs with maximum degree D and locally bounded edge weights.

(3) We give a PTAS, running in nearly linear time, for geometrically embedded instances.

Today I read a paper titled “The Interactive Minority Game: a Web-based investigation of human market interactions”

The abstract is:
The unprecedented access offered by the World Wide Web brings with it the potential to gather huge amounts of data on human activities.

Here we exploit this by using a toy model of financial markets, the Minority Game (MG), to investigate human speculative trading behaviour and information capacity.

Hundreds of individuals have played a total of tens of thousands of game turns against computer-controlled agents in the Web-based_Interactive Minority Game_.

The analytical understanding of the MG permits fine-tuning of the market situations encountered, allowing for investigation of human behaviour in a variety of controlled environments.

In particular, our results indicate a transition in players’ decision-making, as the markets become more difficult, between deductive behaviour making use of short-term trends in the market, and highly repetitive behaviour that ignores entirely the market history, yet outperforms random decision-making.

PACS: 02.50.Le; 89.65.Gh; 89.70.+c Keywords: Decision theory and game theory; Economics and financial markets; Information theory .

Today I read a paper titled “Algorithmic Clustering of Music”

The abstract is:
We present a fully automatic method for music classification, based only on compression of strings that represent the music pieces.

The method uses no background knowledge about music whatsoever: it is completely general and can, without change, be used in different areas like linguistic classification and genomics.

It is based on an ideal theory of the information content in individual objects (Kolmogorov complexity), information distance, and a universal similarity metric.

Experiments show that the method distinguishes reasonably well between various musical genres and can even cluster pieces by composer.

Today I read a paper titled “The one-round Voronoi game replayed”

The abstract is:
We consider the one-round Voronoi game, where player one (“White”, called “Wilma”) places a set of n points in a rectangular area of aspect ratio r <=1, followed by the second player (``Black'', called ``Barney''), who places the same number of points.

Each player wins the fraction of the board closest to one of his points, and the goal is to win more than half of the total area.

This problem has been studied by Cheong et al., who showed that for large enough $n$ and r=1, Barney has a strategy that guarantees a fraction of 1/2+a, for some small fixed a.

We resolve a number of open problems raised by that paper.

In particular, we give a precise characterization of the outcome of the game for optimal play: We show that Barney has a winning strategy for n>2 and r>sqrt{2}/n, and for n=2 and r>sqrt{3}/2.

Wilma wins in all remaining cases, i.e., for n>=3 and r<=sqrt{2}/n, for n=2 and r<=sqrt{3}/2, and for n=1.

We also discuss complexity aspects of the game on more general boards, by proving that for a polygon with holes, it is NP-hard to maximize the area Barney can win against a given set of points by Wilma.

Today I read a paper titled “Cyborg Systems as Platforms for Computer-Vision Algorithm-Development for Astrobiology”

The abstract is:
Employing the allegorical imagery from the film “The Matrix”, we motivate and discuss our `Cyborg Astrobiologist’ research program.

In this research program, we are using a wearable computer and video camcorder in order to test and train a computer-vision system to be a field-geologist and field-astrobiologist.

Today I read a paper titled “The Graphics Card as a Streaming Computer”

The abstract is:
Massive data sets have radically changed our understanding of how to design efficient algorithms; the streaming paradigm, whether it in terms of number of passes of an external memory algorithm, or the single pass and limited memory of a stream algorithm, appears to be the dominant method for coping with large data.

A very different kind of massive computation has had the same effect at the level of the CPU.

The most prominent example is that of the computations performed by a graphics card.

The operations themselves are very simple, and require very little memory, but require the ability to perform many computations extremely fast and in parallel to whatever degree possible.

What has resulted is a stream processor that is highly optimized for stream computations.

An intriguing side effect of this is the growing use of a graphics card as a general purpose stream processing engine.

In an ever-increasing array of applications, researchers are discovering that performing a computation on a graphics card is far faster than performing it on a CPU, and so are using a GPU as a stream co-processor..

Today I read a paper titled “Local Community Identification through User Access Patterns”

The abstract is:
Community identification algorithms have been used to enhance the quality of the services perceived by its users.

Although algorithms for community have a widespread use in the Web, their application to portals or specific subsets of the Web has not been much studied.

In this paper, we propose a technique for local community identification that takes into account user access behavior derived from access logs of servers in the Web.

The technique takes a departure from the existing community algorithms since it changes the focus of in terest, moving from authors to users.

Our approach does not use relations imposed by authors (e.g.

hyperlinks in the case of Web pages).

It uses information derived from user accesses to a service in order to infer relationships.

The communities identified are of great interest to content providers since they can be used to improve quality of their services.

We also propose an evaluation methodology for analyzing the results obtained by the algorithm.

We present two case studies based on actual data from two services: an online bookstore and an online radio.

The case of the online radio is particularly relevant, because it emphasizes the contribution of the proposed algorithm to find out communities in an environment (i.e., streaming media service) without links, that represent the relations imposed by authors (e.g.

hyperlinks in the case of Web pages).

Today I read a paper titled “On multiple connectedness of regions visible due to multiple diffuse reflections”

The abstract is:
It is known that the region V(s) of a simple polygon P, directly visible (illuminable) from an internal point s, is simply connected.

Aronov et al.

\cite{addpp981} established that the region V1(s) of a simple polygon visible from an internal point s due to at most one diffuse reflection on the boundary of the polygon P, is also simply connected.

In this paper we establish that the region V2(s), visible from s due to at most two diffuse reflections may be multiply connected; we demonstrate the construction of an n-sided simple polygon with a point s inside it so that and the region of P visible from s after at most two diffuse reflections is multiple connected..

Today I read a paper titled “Towards a Model-Based Framework for Integrating Usability and Software Engineering Life Cycles”

The abstract is:
In this position paper we propose a process model that provides a development infrastructure in which the usability engineering and software engineering life cycles co-exist in complementary roles.

We describe the motivation, hurdles, rationale, arguments, and implementation plan for the need, specification, and the usefulness of such a model.

Today I read a paper titled “Embedded Reflection Mapping”

The abstract is:
Environment maps are used to simulate reflections off curved objects.

We present a technique to reflect a user, or a group of users, in a real environment, onto a virtual object, in a virtual reality application, using the live video feeds from a set of cameras, in real-time.

Our setup can be used in a variety of environments ranging from outdoor or indoor scenes..

Today I read a paper titled “Communities of Practice: Going Virtual”

The abstract is:
With the current trends towards downsizing, outsourcing and globalisation, modern organisations are reducing the numbers of people they employ.

In addition, organisations now have to cope with the increasing internationalisation of business forcing collaboration and knowledge sharing across time and distance simultaneously.

There is a need for new ways of thinking about how knowledge is shared in distributed groups.

In this paper we explore a relatively new approach to knowledge sharing using Lave and Wenger’s (1991) theory of Communities of Practice (CoPs).

We investigate whether CoPs might translate to a geographically distributed international environment through a case study that explores the functioning of a CoP across national boundaries.

Today I read a paper titled “Practical and Robust Stenciled Shadow Volumes for Hardware-Accelerated Rendering”

The abstract is:
Twenty-five years ago, Crow published the shadow volume approach for determining shadowed regions in a scene.

A decade ago, Heidmann described a hardware-accelerated stencil buffer-based shadow volume algorithm.

Unfortunately hardware-accelerated stenciled shadow volume techniques have not been widely adopted by 3D games and applications due in large part to the lack of robustness of described techniques.

This situation persists despite widely available hardware support.

Specifically what has been lacking is a technique that robustly handles various “hard” situations created by near or far plane clipping of shadow volumes.

We describe a robust, artifact-free technique for hardware-accelerated rendering of stenciled shadow volumes.

Assuming existing hardware, we resolve the issues otherwise caused by shadow volume near and far plane clipping through a combination of (1) placing the conventional far clip plane “at infinity”, (2) rasterization with infinite shadow volume polygons via homogeneous coordinates, and (3) adopting a zfail stencil-testing scheme.

Depth clamping, a new rasterization feature provided by NVIDIA’s GeForce3, preserves existing depth precision by not requiring the far plane to be placed at infinity.

We also propose two-sided stencil testing to improve the efficiency of rendering stenciled shadow volumes..

Today I read a paper titled “An evaluation of Naive Bayesian anti-spam filtering”

The abstract is:
It has recently been argued that a Naive Bayesian classifier can be used to filter unsolicited bulk e-mail (“spam”).

We conduct a thorough evaluation of this proposal on a corpus that we make publicly available, contributing towards standard benchmarks.

At the same time we investigate the effect of attribute-set size, training-corpus size, lemmatization, and stop-lists on the filter’s performance, issues that had not been previously explored.

After introducing appropriate cost-sensitive evaluation measures, we reach the conclusion that additional safety nets are needed for the Naive Bayesian anti-spam filter to be viable in practice.