REU: Fast and Compact Data Structures, ALADDIN Center

This project is studying and developing data structures for storing very large collections of data in compressed form while allowing fast dynamic access to the data. Example applications of such compact data structures include running algorithms on the graph representing the hyperlinks structure of the World-Wide Web, or running advanced string searches on very large collections of DNA data. Recent data structures have been developed for compactly storing graphs while allowing fast access, and compactly representing suffix trees for fast searching on strings. There are many open problems in this area. In this project, we are studying techniques for compactly representing dictionary structures. We are considering techniques that are theoretically efficient, and also implementing the ideas to see how well they work in practice.

Preliminary Presentation (ppt)
Final Presentation (ppt)

Other REUs for Summer 2004

Algorithms for Dynamic Point Location with Good Practical Performance
A Bezier-Based Approach to Unstructured Moving Meshes
Evaluation of Algorithms for the List Update Problem
Exploring PLS-Completeness of Simple Stochastic Game (or Stable Circuit Problem)
Fast and Compact Data Structures
The Game of NimG (Nim on Graphs)
Random Graph Models of Large Real-World Networks
Solving Partial Differential Equations Numerically
Traceable Anonymity

Back to the REU page