ICS Theory Group

ICS 269, Winter 2004: Theory Seminar


06 Feb 2004:
Reducing the Space Requirements of an Ordered Set
Josiah Carlson

In recent years there have been various papers that provide algorithms to store sets in a compressed fashion. This presentation will cover a paper by Blandford and Blelloch that provides a method for representing an ordered set within a constant factor of the theoretical lower bound. While not improving significantly on previous space bounds, it does provide a larger set of useful functionality over previous compressed set storage methods.