By

In modern computer systems, memory accesses and power management are the two major performance limiting factors. Accesses to main memory are very slow when compared to op-erations within a processor chip. Hardware write buffers, caches, out-of-order execution, and prefetch logic, are commonly used to reduce the time spent waiting for main memory accesses. Compiler loop interchange and data layout transformations also can help. Unfortunately, large data structures often have access patterns for which none of the standard approaches are use-ful. Using smaller data structures can significantly improve performance by allowing the data to reside in higher levels of the memory hierarchy. This dissertation proposes using lossy data compression technology called ’Compressive Hashing ’ to create “surrogates”, that can aug-ment original large data structures to yield faster typical data access