Archives for 2006

Today I read a paper titled “A New Computational Framework For 2D Shape-Enclosing Contours”

The abstract is:
In this paper, a new framework for one-dimensional contour extraction from discrete two-dimensional data sets is presented.

Contour extraction is important in many scientific fields such as digital image processing, computer vision, pattern recognition, etc.

This novel framework includes (but is not limited to) algorithms for dilated contour extraction, contour displacement, shape skeleton extraction, contour continuation, shape feature based contour refinement and contour simplification.

Many of the new techniques depend strongly on the application of a Delaunay tessellation.

In order to demonstrate the versatility of this novel toolbox approach, the contour extraction techniques presented here are applied to scientific problems in material science, biology and heavy ion physics.

Today I read a paper titled “Collaborative Storage Management In Sensor Networks”

The abstract is:
In this paper, we consider a class of sensor networks where the data is not required in real-time by an observer; for example, a sensor network monitoring a scientific phenomenon for later play back and analysis.

In such networks, the data must be stored in the network.

Thus, in addition to battery power, storage is a primary resource: the useful lifetime of the network is constrained by its ability to store the generated data samples.

We explore the use of collaborative storage technique to efficiently manage data in storage constrained sensor networks.

The proposed collaborative storage technique takes advantage of spatial correlation among the data collected by nearby sensors to significantly reduce the size of the data near the data sources.

We show that the proposed approach provides significant savings in the size of the stored data vs.

local buffering, allowing the network to run for a longer time without running out of storage space and reducing the amount of data that will eventually be relayed to the observer.

In addition, collaborative storage performs load balancing of the available storage space if data generation rates are not uniform across sensors (as would be the case in an event driven sensor network), or if the available storage varies across the network.

Today I read a paper titled “Specifying Intonation from Context for Speech Synthesis”

The abstract is:
This paper presents a theory and a computational implementation for generating prosodically appropriate synthetic speech in response to database queries.

Proper distinctions of contrast and emphasis are expressed in an intonation contour that is synthesized by rule under the control of a grammar, a discourse model, and a knowledge base.

The theory is based on Combinatory Categorial Grammar, a formalism which easily integrates the notions of syntactic constituency, semantics, prosodic phrasing and information structure.

Results from our current implementation demonstrate the system’s ability to generate a variety of intonational possibilities for a given sentence depending on the discourse context..

Today I read a paper titled “On the Cell-based Complexity of Recognition of Bounded Configurations by Finite Dynamic Cellular Automata”

The abstract is:
This paper studies complexity of recognition of classes of bounded configurations by a generalization of conventional cellular automata (CA) — finite dynamic cellular automata (FDCA).

Inspired by the CA-based models of biological and computer vision, this study attempts to derive the properties of a complexity measure and of the classes of input configurations that make it beneficial to realize the recognition via a two-layered automaton as compared to a one-layered automaton.

A formalized model of an image pattern recognition task is utilized to demonstrate that the derived conditions can be satisfied for a non-empty set of practical problems.

Today I read a paper titled “Distributed Selfish Load Balancing”

The abstract is:
Suppose that a set of $m$ tasks are to be shared as equally as possible amongst a set of $n$ resources.

A game-theoretic mechanism to find a suitable allocation is to associate each task with a “selfish agent”, and require each agent to select a resource, with the cost of a resource being the number of agents to select it.

Agents would then be expected to migrate from overloaded to underloaded resources, until the allocation becomes balanced.

Recent work has studied the question of how this can take place within a distributed setting in which agents migrate selfishly without any centralized control.

In this paper we discuss a natural protocol for the agents which combines the following desirable features: It can be implemented in a strongly distributed setting, uses no central control, and has good convergence properties.

For $m\gg n$, the system becomes approximately balanced (an $\epsilon$-Nash equilibrium) in expected time $O(\log\log m)$.

We show using a martingale technique that the process converges to a perfectly balanced allocation in expected time $O(\log\log m+n^4)$.

We also give a lower bound of $\Omega(\max\{\log\log m,n\})$ for the convergence time.

Today I read a paper titled “Topic Identification in Discourse”

The abstract is:
This paper proposes a corpus-based language model for topic identification.

We analyze the association of noun-noun and noun-verb pairs in LOB Corpus.

The word association norms are based on three factors: 1) word importance, 2) pair co-occurrence, and 3) distance.

They are trained on the paragraph and sentence levels for noun-noun and noun-verb pairs, respectively.

Under the topic coherence postulation, the nouns that have the strongest connectivities with the other nouns and verbs in the discourse form the preferred topic set.

The collocational semantics then is used to identify the topics from paragraphs and to discuss the topic shift phenomenon among paragraphs..

Today I read a paper titled “Analytical formulations of Peer-to-Peer Connection Efficiency”

The abstract is:
Use of Peer-to-Peer (P2P) service networks introduces a new communication paradigm because peers are both clients and servers and so each peer may provide/request services to/from other peers.

Empirical studies of P2P networks have been undertaken and reveal useful characteristics.

However there is to date little analytical work to describe P2P networks with respect to their communication paradigm and their interconnections.

This paper provides an analytical formulation and optimisation of peer connection efficiency, in terms of minimising the fraction of wasted connection time.

Peer connection efficiency is analysed for both a uni- and multi-connected peer.

Given this fundamental optimisation, the paper optimises the number of connections that peers should make use of as a function of network load, in terms of minimising the total queue size that requests in the P2P network experience.

The results of this paper provide a basis for engineering high performance P2P interconnection networks.

The optimisations are useful for reducing bandwidth and power consumption, e.g.

in the case of peers being mobile devices with a limited power supply.

Also these results could be used to determine when a (virtual) circuit should be switched to support a connection.

Today I read a paper titled “A Comparative Study of Fuzzy Classification Methods on Breast Cancer Data”

The abstract is:
In this paper, we examine the performance of four fuzzy rule generation methods on Wisconsin breast cancer data.

The first method generates fuzzy if then rules using the mean and the standard deviation of attribute values.

The second approach generates fuzzy if then rules using the histogram of attributes values.

The third procedure generates fuzzy if then rules with certainty of each attribute into homogeneous fuzzy sets.

In the fourth approach, only overlapping areas are partitioned.

The first two approaches generate a single fuzzy if then rule for each class by specifying the membership function of each antecedent fuzzy set using the information about attribute values of training patterns.

The other two approaches are based on fuzzy grids with homogeneous fuzzy partitions of each attribute.

The performance of each approach is evaluated on breast cancer data sets.

Simulation results show that the Modified grid approach has a high classification rate of 99.73 %.

Today I read a paper titled “Improved randomized selection”

The abstract is:
We show that several versions of Floyd and Rivest’s improved algorithm Select for finding the $k$th smallest of $n$ elements require at most $n+\min\{k,n-k\}+O(n^{1/2}\ln^{1/2}n)$ comparisons on average and with high probability.

This rectifies the analysis of Floyd and Rivest, and extends it to the case of nondistinct elements.

Encouraging computational results on large median-finding problems are reported.

Today I read a paper titled “A Social Network for Societal-Scale Decision-Making Systems”

The abstract is:
In societal-scale decision-making systems the collective is faced with the problem of ensuring that the derived group decision is in accord with the collective’s intention.

In modern systems, political institutions have instatiated representative forms of decision-making to ensure that every individual in the society has a participatory voice in the decision-making behavior of the whole–even if only indirectly through representation.

An agent-based simulation demonstrates that in modern representative systems, as the ratio of representatives increases, there exists an exponential decrease in the ability for the group to behave in accord with the desires of the whole.

To remedy this issue, this paper provides a novel representative power structure for decision-making that utilizes a social network and power distribution algorithm to maintain the collective’s perspective over varying degrees of participation and/or ratios of representation.

This work shows promise for the future development of policy-making systems that are supported by the computer and network infrastructure of our society.

Today I read a paper titled “Media Affordances of a Mobile Push-To-Talk Communication Service”

The abstract is:
This paper presents an exploratory study of college-age students using two-way, push-to-talk cellular radios.

We describe the observed and reported use of cellular radio by the participants, the activities and purposes for which they adopted it, and their responses.

We then examine these empirical results using mediated communication theory.

Cellular radios have a unique combination of affordances relative to other media used by this age group, including instant messaging (IM) and mobile phones; the results of our analysis do suggest explanations for some observed phenomena but also highlight the counter-intuitive nature of other phenomena.

For example, although the radios have many important dissimilarities with IM from the viewpoint of mediated communication theory, the observed use patterns resembled those of IM to a surprising degree.

Today I read a paper titled “Phoneme Recognition Using Acoustic Events”

The abstract is:
This paper presents a new approach to phoneme recognition using nonsequential sub–phoneme units.

These units are called acoustic events and are phonologically meaningful as well as recognizable from speech signals.

Acoustic events form a phonologically incomplete representation as compared to distinctive features.

This problem may partly be overcome by incorporating phonological constraints.

Currently, 24 binary events describing manner and place of articulation, vowel quality and voicing are used to recognize all German phonemes.

Phoneme recognition in this paradigm consists of two steps: After the acoustic events have been determined from the speech signal, a phonological parser is used to generate syllable and phoneme hypotheses from the event lattice.

Results obtained on a speaker–dependent corpus are presented..

Today I read a paper titled “Intelligent search strategies based on adaptive Constraint Handling Rules”

The abstract is:
The most advanced implementation of adaptive constraint processing with Constraint Handling Rules (CHR) allows the application of intelligent search strategies to solve Constraint Satisfaction Problems (CSP).

This presentation compares an improved version of conflict-directed backjumping and two variants of dynamic backtracking with respect to chronological backtracking on some of the AIM instances which are a benchmark set of random 3-SAT problems.

A CHR implementation of a Boolean constraint solver combined with these different search strategies in Java is thus being compared with a CHR implementation of the same Boolean constraint solver combined with chronological backtracking in SICStus Prolog.

This comparison shows that the addition of “intelligence” to the search process may reduce the number of search steps dramatically.

Furthermore, the runtime of their Java implementations is in most cases faster than the implementations of chronological backtracking.

More specifically, conflict-directed backjumping is even faster than the SICStus Prolog implementation of chronological backtracking, although our Java implementation of CHR lacks the optimisations made in the SICStus Prolog system.

To appear in Theory and Practice of Logic Programming (TPLP).

Today I read a paper titled “Decision Sort and its Parallel Implementation”

The abstract is:
In this paper, a sorting technique is presented that takes as input a data set whose primary key domain is known to the sorting algorithm, and works with an time efficiency of O(n+k), where k is the primary key domain.

It is shown that the algorithm has applicability over a wide range of data sets.

Later, a parallel formulation of the same is proposed and its effectiveness is argued.

Though this algorithm is applicable over a wide range of general data sets, it finds special application (much superior to others) in places where sorting information that arrives in parts and in cases where input data is huge in size.

Today I read a paper titled “Lock-Free and Practical Deques using Single-Word Compare-And-Swap”

The abstract is:
We present an efficient and practical lock-free implementation of a concurrent deque that is disjoint-parallel accessible and uses atomic primitives which are available in modern computer systems.

Previously known lock-free algorithms of deques are either based on non-available atomic synchronization primitives, only implement a subset of the functionality, or are not designed for disjoint accesses.

Our algorithm is based on a doubly linked list, and only requires single-word compare-and-swap atomic primitives, even for dynamic memory sizes.

We have performed an empirical study using full implementations of the most efficient algorithms of lock-free deques known.

For systems with low concurrency, the algorithm by Michael shows the best performance.

However, as our algorithm is designed for disjoint accesses, it performs significantly better on systems with high concurrency and non-uniform memory architecture.