Searching in Succintly Encoded Structures

The concept of Succinct Data Structure was introduced in 1985 by Jacobson, mainly to reduce the space used to encode trees. It has been successfully applied since to the encoding of suffix trees and related variants. Adaptive algorithms have been studied for convex-hull cover, sorting, union and intersection. Those algorithms perform optimally not only = on the worst case among instances of same size, but also among instances of same difficulty, where the definition of the difficulty of an instance depends of the problem and of the analysis. We combine those techniques to encode efficiently binary relations such as the one associating web-pages references to keywords in the index of a search engine, and to solve conjunctive queries (i.e. Google-like queries) much faster than previously. Extending further those techniques, we propose an index = for file systems, and an algorithm to search in it in almost non-deterministic time.