Succinct data structures in general are interesting. They use close to the information theoretic bound for a given problem and still support fast operations -- a decent mental model is that they're able to jump to a roughly correct place and (de)compress the data locally.
A good example is a wavelet tree. Suppose you have a text of length N comprised of an alphabet with C characters and wish to execute full-text pattern searches for patterns of length P. Once the tree is created, you can do your full-text search in O(P log C) time, and you use less space than any constant multiplicative factor of the information theoretic lower bound. Note that the runtime is independent of the original string's length.
Another example is distance oracles. A distance oracle is a two stage object, in one stage creates a cache of distances, and in the other it allows us to query the cache. The oracle gives an approximate solution to the distance between any two nodes while avoiding the quadratic memory requirement to something in order of nlogk with k query steps.
A good example is a wavelet tree. Suppose you have a text of length N comprised of an alphabet with C characters and wish to execute full-text pattern searches for patterns of length P. Once the tree is created, you can do your full-text search in O(P log C) time, and you use less space than any constant multiplicative factor of the information theoretic lower bound. Note that the runtime is independent of the original string's length.