Archives for 2002

Today I read a paper titled “Random Shuffling to Reduce Disorder in Adaptive Sorting Scheme”

The abstract is:
In this paper we present a random shuffling scheme to apply with adaptive sorting algorithms.

Adaptive sorting algorithms utilize the presortedness present in a given sequence.

We have probabilistically increased the amount of presortedness present in a sequence by using a random shuffling technique that requires little computation.

Theoretical analysis suggests that the proposed scheme can improve the performance of adaptive sorting.

Experimental results show that it significantly reduces the amount of disorder present in a given sequence and improves the execution time of adaptive sorting algorithm as well.

Today I read a paper titled “Connectivity Compression for Irregular Quadrilateral Meshes”

The abstract is:
Applications that require Internet access to remote 3D datasets are often limited by the storage costs of 3D models.

Several compression methods are available to address these limits for objects represented by triangle meshes.

Many CAD and VRML models, however, are represented as quadrilateral meshes or mixed triangle/quadrilateral meshes, and these models may also require compression.

We present an algorithm for encoding the connectivity of such quadrilateral meshes, and we demonstrate that by preserving and exploiting the original quad structure, our approach achieves encodings 30 – 80% smaller than an approach based on randomly splitting quads into triangles.

We present both a code with a proven worst-case cost of 3 bits per vertex (or 2.75 bits per vertex for meshes without valence-two vertices) and entropy-coding results for typical meshes ranging from 0.3 to 0.9 bits per vertex, depending on the regularity of the mesh.

Our method may be implemented by a rule for a particular splitting of quads into triangles and by using the compression and decompression algorithms introduced in [Rossignac99] and [Rossignac&Szymczak99].

We also present extensions to the algorithm to compress meshes with holes and handles and meshes containing triangles and other polygons as well as quads..

Today I read a paper titled “Time and Space Bounds for Reversible Simulation”

The abstract is:
We prove a general upper bound on the tradeoff between time and space that suffices for the reversible simulation of irreversible computation.

Previously, only simulations using exponential time or quadratic space were known.

The tradeoff shows for the first time that we can simultaneously achieve subexponential time and subquadratic space.

The boundary values are the exponential time with hardly any extra space required by the Lange-McKenzie-Tapp method and the ($\log 3$)th power time with square space required by the Bennett method.

We also give the first general lower bound on the extra storage space required by general reversible simulation.

This lower bound is optimal in that it is achieved by some reversible simulations.

Today I read a paper titled “Document Archiving, Replication and Migration Container for Mobile Web Users”

The abstract is:
With the increasing use of mobile workstations for a wide variety of tasks and associated information needs, and with many variations of available networks, access to data becomes a prime consideration.

This paper discusses issues of workstation mobility and proposes a solution wherein the data structures are accessed in an encapsulated form – through the Portable File System (PFS) wrapper.

The paper discusses an implementation of the Portable File System, highlighting the architecture and commenting upon performance of an experimental system.

Although investigations have been focused upon mobile access of WWW documents, this technique could be applied to any mobile data access situation.