Archives for 2005

Today I read a paper titled “A General, Sound and Efficient Natural Language Parsing Algorithm based on Syntactic Constraints Propagation”

The abstract is:
This paper presents a new context-free parsing algorithm based on a bidirectional strictly horizontal strategy which incorporates strong top-down predictions (derivations and adjacencies).

From a functional point of view, the parser is able to propagate syntactic constraints reducing parsing ambiguity.

From a computational perspective, the algorithm includes different techniques aimed at the improvement of the manipulation and representation of the structures used.

Today I read a paper titled “Exposing Software Defined Radio Functionality To Native Operating System Applications via Virtual Devices”

The abstract is:
Many reconfigurable platforms require that applications be written specifically to take advantage of the reconfigurable hardware.

In a PC-based environment, this presents an undesirable constraint in that the many already available applications cannot leverage on such hardware.

Greatest benefit can only be derived from reconfigurable devices if even native OS applications can transparently utilize reconfigurable devices as they would normal full-fledged hardware devices.

This paper presents how Proteus Virtual Devices are used to expose reconfigurable hardware in a transparent manner for use by typical native OS applications.

Today I read a paper titled “Efficient Tree Layout in a Multilevel Memory Hierarchy”

The abstract is:
We consider the problem of laying out a tree with fixed parent/child structure in hierarchical memory.

The goal is to minimize the expected number of block transfers performed during a search along a root-to-leaf path, subject to a given probability distribution on the leaves.

This problem was previously considered by Gil and Itai, who developed optimal but slow algorithms when the block-transfer size B is known.

We present faster but approximate algorithms for the same problem; the fastest such algorithm runs in linear time and produces a solution that is within an additive constant of optimal.

In addition, we show how to extend any approximately optimal algorithm to the cache-oblivious setting in which the block-transfer size is unknown to the algorithm.

The query performance of the cache-oblivious layout is within a constant factor of the query performance of the optimal known-block-size layout.

Computing the cache-oblivious layout requires only logarithmically many calls to the layout algorithm for known block size; in particular, the cache-oblivious layout can be computed in O(N lg N) time, where N is the number of nodes.

Finally, we analyze two greedy strategies, and show that they have a performance ratio between Omega(lg B / lg lg B) and O(lg B) when compared to the optimal layout.

Today I read a paper titled “Business Intelligence from Web Usage Mining”

The abstract is:
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.

Today I read a paper titled “How many candidates are needed to make elections hard to manipulate?”

The abstract is:
In multiagent settings where the agents have different preferences, preference aggregation is a central issue.

Voting is a general method for preference aggregation, but seminal results have shown that all general voting protocols are manipulable.

One could try to avoid manipulation by using voting protocols where determining a beneficial manipulation is hard computationally.

The complexity of manipulating realistic elections where the number of candidates is a small constant was recently studied (Conitzer 2002), but the emphasis was on the question of whether or not a protocol becomes hard to manipulate for some constant number of candidates.

That work, in many cases, left open the question: How many candidates are needed to make elections hard to manipulate? This is a crucial question when comparing the relative manipulability of different voting protocols.

In this paper we answer that question for the voting protocols of the earlier study: plurality, Borda, STV, Copeland, maximin, regular cup, and randomized cup.

We also answer that question for two voting protocols for which no results on the complexity of manipulation have been derived before: veto and plurality with runoff.

It turns out that the voting protocols under study become hard to manipulate at 3 candidates, 4 candidates, 7 candidates, or never.

Today I read a paper titled “Benchmarking and Implementation of Probability-Based Simulations on Programmable Graphics Cards”

The abstract is:
The latest Graphics Processing Units (GPUs) are reported to reach up to 200 billion floating point operations per second (200 Gflops) and to have price performance of 0.1 cents per M flop.

These facts raise great interest in the plausibility of extending the GPUs’ use to non-graphics applications, in particular numerical simulations on structured grids (lattice).

We review previous work on using GPUs for non-graphics applications, implement probability-based simulations on the GPU, namely the Ising and percolation models, implement vector operation benchmarks for the GPU, and finally compare the CPU’s and GPU’s performance.

A general conclusion from the results obtained is that moving computations from the CPU to the GPU is feasible, yielding good time and price performance, for certain lattice computations.

Preliminary results also show that it is feasible to use them in parallel .

Today I read a paper titled “Surface Triangulation — The Metric Approach”

The abstract is:
We embark in a program of studying the problem of better approximating surfaces by triangulations(triangular meshes) by considering the approximating triangulations as finite metric spaces and the target smooth surface as their Haussdorff-Gromov limit.

This allows us to define in a more natural way the relevant elements, constants and invariants s.a.

principal directions and principal values, Gaussian and Mean curvature, etc.

By a “natural way” we mean an intrinsic, discrete, metric definitions as opposed to approximating or paraphrasing the differentiable notions.

In this way we hope to circumvent computational errors and, indeed, conceptual ones, that are often inherent to the classical, “numerical” approach.

In this first study we consider the problem of determining the Gaussian curvature of a polyhedral surface, by using the {\em embedding curvature} in the sense of Wald (and Menger).

We present two modalities of employing these definitions for the computation of Gaussian curvature.

Today I read a paper titled “Classes of service under perfect competition and technological change: a model for the dynamics of the Internet?”

The abstract is:
Certain services may be provided in a continuous, one-dimensional, ordered range of different qualities and a customer requiring a service of quality q can only be offered a quality superior or equal to q.

Only a discrete set of different qualities will be offered, and a service provider will provide the same service (of fixed quality b) to all customers requesting qualities of service inferior or equal to b.

Assuming all services (of quality b) are priced identically, a monopolist will choose the qualities of service and the prices that maximize profit but, under perfect competition, a service provider will choose the (inferior) quality of service that can be priced at the lowest price.

Assuming significant economies of scale, two fundamentally different regimes are possible: either a number of different classes of service are offered (DC regime), or a unique class of service offers an unbounded quality of service (UC regime).

The DC regime appears in one of two sub-regimes: one, BDC, in which a finite number of classes is offered, the qualities of service offered are bounded and requests for high-quality services are not met, or UDC in which an infinite number of classes of service are offered and every request is met.

The types of the demand curve and of the economies of scale, not the pace of technological change, determine the regime and the class boundaries.

The price structure in the DC regime obeys very general laws..

Today I read a paper titled “Least squares fitting of circles and lines”

The abstract is:
We study theoretical and computational aspects of the least squares fit (LSF) of circles and circular arcs.

First we discuss the existence and uniqueness of LSF and various parametrization schemes.

Then we evaluate several popular circle fitting algorithms and propose a new one that surpasses the existing methods in reliability.

We also discuss and compare direct (algebraic) circle fits.

Today I read a paper titled “An effective Procedure for Speeding up Algorithms”

The abstract is:
The provably asymptotically fastest algorithm within a factor of 5 for formally described problems will be constructed.

The main idea is to enumerate all programs provably equivalent to the original problem by enumerating all proofs.

The algorithm could be interpreted as a generalization and improvement of Levin search, which is, within a multiplicative constant, the fastest algorithm for inverting functions.

Blum’s speed-up theorem is avoided by taking into account only programs for which a correctness proof exists.

Furthermore, it is shown that the fastest program that computes a certain function is also one of the shortest programs provably computing this function.

To quantify this statement, the definition of Kolmogorov complexity is extended, and two new natural measures for the complexity of a function are defined.