The HOPI index, a connection index for XML documents based on the concept
of a 2-hop cover,
provides space- and time-efficient reachability tests along the ancestor,
descendant, and link axes
to support path expressions with wildcards in XML search engines. The talk
presents an efficient
divide-and-conquer algorithm for building HOPI and shows how to augment
the index with distance
information.