Dan Alcantara's homepage >> Research

Inadequately caffeinated

E-mail

Research

Résumé

Projects

Scraps

Photos

ECS 10 (Python)

>> Research

	Real-time Parallel Hashing on the GPU
We demonstrate an efficient data-parallel algorithm for building large hash tables of millions of elements in real-time. We consider two parallel algorithms for the construction: a classical sparse perfect hashing approach, and cuckoo hashing, which packs elements densely by allowing an element to be stored in one of multiple possible locations. Our construction is a hybrid approach that uses both algorithms. We measure the construction time, access time, and memory usage of our implementations and demonstrate real-time performance on large datasets: for 5 million key-value pairs, we construct a hash table in 35.7 ms using 1.42 times as much memory as the input data itself, and we can access all the elements in that hash table in 15.3 ms. For comparison, sorting the same data requires 36.6 ms, but accessing all the elements via binary search requires 79.5 ms. Furthermore, we show how our hashing methods can be applied to two graphics applications: 3D surface intersection for moving data and geometric hashing for image matching.

Real-time Parallel Hashing on the GPU

We demonstrate an efficient data-parallel algorithm for building large hash tables of millions of elements in real-time. We consider two parallel algorithms for the construction: a classical sparse perfect hashing approach, and cuckoo hashing, which packs elements densely by allowing an element to be stored in one of multiple possible locations. Our construction is a hybrid approach that uses both algorithms. We measure the construction time, access time, and memory usage of our implementations and demonstrate real-time performance on large datasets: for 5 million key-value pairs, we construct a hash table in 35.7 ms using 1.42 times as much memory as the input data itself, and we can access all the elements in that hash table in 15.3 ms. For comparison, sorting the same data requires 36.6 ms, but accessing all the elements via binary search requires 79.5 ms. Furthermore, we show how our hashing methods can be applied to two graphics applications: 3D surface intersection for moving data and geometric hashing for image matching.

	Space-time Surface Reconstruction Using Incompressible Flow
We introduce a volumetric space-time technique for the reconstruction of moving and deforming objects from point data. The output of our method is a four-dimensional space-time solid, made up of spatial slices, each of which is a three-dimensional solid bounded by a watertight manifold. The motion of the object is described as an incompressible flow of material through time. We optimize the flow so that the distance material moves from one time frame to the next is bounded, the density of material remains constant, and the object remains compact. This formulation overcomes deficiencies in the acquired data, such as persistent occlusions, errors, and missing frames. We demonstrate the performance of our flow-based technique by reconstructing coherent sequences of watertight models from incomplete scanner data.

Space-time Surface Reconstruction Using Incompressible Flow

We introduce a volumetric space-time technique for the reconstruction of moving and deforming objects from point data. The output of our method is a four-dimensional space-time solid, made up of spatial slices, each of which is a three-dimensional solid bounded by a watertight manifold. The motion of the object is described as an incompressible flow of material through time. We optimize the flow so that the distance material moves from one time frame to the next is bounded, the density of material remains constant, and the object remains compact. This formulation overcomes deficiencies in the acquired data, such as persistent occlusions, errors, and missing frames. We demonstrate the performance of our flow-based technique by reconstructing coherent sequences of watertight models from incomplete scanner data.

	Localized Components Analysis
We introduce Localized Components Analysis (LoCA) for describing surface shape variation in an ensemble of biomedical objects using a linear subspace of spatially localized shape components. In contrast to earlier methods, LoCA optimizes explicitly for localized components and allows a flexible trade-off between localized and concise representations. Experiments comparing LoCA to a variety of competing shape representation methods on 2D and 3D shape ensembles establish the superior ability of LoCA to modulate the locality-conciseness tradeoff and generate shape components corresponding to intuitive modes of shape variation. Our formulation of locality in terms of compatibility between pairs of surface points is shown to be flexible enough to enable spatially-localized shape descriptions with attractive higher-order properties such as spatial symmetry.

Localized Components Analysis

We introduce Localized Components Analysis (LoCA) for describing surface shape variation in an ensemble of biomedical objects using a linear subspace of spatially localized shape components. In contrast to earlier methods, LoCA optimizes explicitly for localized components and allows a flexible trade-off between localized and concise representations. Experiments comparing LoCA to a variety of competing shape representation methods on 2D and 3D shape ensembles establish the superior ability of LoCA to modulate the locality-conciseness tradeoff and generate shape components corresponding to intuitive modes of shape variation. Our formulation of locality in terms of compatibility between pairs of surface points is shown to be flexible enough to enable spatially-localized shape descriptions with attractive higher-order properties such as spatial symmetry.

	Evolutionary Morphing
We introduce a technique to visualize the gradual evolutionary change of the shapes of living things as a morph between known three-dimensional shapes. Given geometric computer models of anatomical shapes for some collection of specimens - here the skulls of the some of the extant members of a family of monkeys - an evolutionary tree for the group implies a hypothesis about the way in which the shape changed through time. We use a statistical model which expresses the value of some continuous variable at an internal point in the tree as a weighted average of the values at the leaves. The framework of geometric morphometrics can then be used to define a shape-space, based on the correspondences of landmark points on the surfaces, within which these weighted averages can be realized as actual surfaces.

Evolutionary Morphing

We introduce a technique to visualize the gradual evolutionary change of the shapes of living things as a morph between known three-dimensional shapes. Given geometric computer models of anatomical shapes for some collection of specimens - here the skulls of the some of the extant members of a family of monkeys - an evolutionary tree for the group implies a hypothesis about the way in which the shape changed through time. We use a statistical model which expresses the value of some continuous variable at an internal point in the tree as a weighted average of the values at the leaves. The framework of geometric morphometrics can then be used to define a shape-space, based on the correspondences of landmark points on the surfaces, within which these weighted averages can be realized as actual surfaces.

You've stumbled upon the website of Dan Anthony Alcantara, a Ph.D candidate in the UC Davis Computer Science department. You are likely to be eaten by a grue.