Efficient Interactive Fuzzy Keyword Search is a pretty nice paper about a new information-access paradigm, called“interactive, fuzzy search,” in which the system searches the underlying data “on the fly” as the user types in query keywords. This is useful for search suggestion services provided while users are typing search queries.
The underlying data structure is a combination of tries, inverted lists, and smart caching techniques used for achiveving good performance. The basic data-structures are then expanded for supporting ranking and synonims.
I enjoyed the paper, but the index dimensions are so small that all the data-structures can fit in memory (even without compression)