Title: Adaptive Searching in Succinctly Encoded Structures 
Speaker: Srinivasa Rao
IT University of Copenhagen


Date: Friday,  March 10, 2006
Time 11-12 Venue: Room 3464, HKUST   


Abstract 

Title: Adaptive Searching in Succinctly Encoded Structures

Abstract:
  We combine two different techniques, respectively based on data
  structures and algorithms, to solve various problems in databases
  and information retrieval, improving both space and time
  complexities of the known solutions.

  The concept of Succinct Data Structure was introduced in 1985 by
  Jacobson, mainly to reduce the space used to encode trees. It has
  since been successfully applied to succinctly encode various
  combinatorial objects like sets, permutations, functions, trees,
  graphs etc. Adaptive algorithms have been studied for convex-hull
  cover, sorting, union and intersection. These algorithms
  perform optimally in the worst case not only among instances of same
  size, but also among instances of same difficulty, where the
  definition of the difficulty of an instance depends on the problem
  and on the analysis.  We combine these techniques to encode
  efficiently binary relations such as the ones 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
  earlier algorithms. We also give space efficient structures for
  (multi) labeled trees, which can be used to represent XML documents
  and file system indexes, and devise adaptive algorithms to support
  path queries on these trees.

  Joint work with Jeremy Barbay, Alexander Golynski and Ian Munro.