  Natural language text corpora are often available as sets of syntactically
parsed trees. A wide range of expressive tree queries are possible over such
parsed trees that open a new avenue in searching over natural language text.
They not only allow for querying roles and relationships within sentences, but
also improve search effectiveness compared to flat keyword queries. One major
drawback of current systems supporting querying over parsed text is the
performance of evaluating queries over large data. In this paper we propose a
novel indexing scheme over unique subtrees as index keys. We also propose a
novel root-split coding scheme that stores subtree structural information only
partially, thus reducing index size and improving querying performance. Our
extensive set of experiments show that root-split coding reduces the index size
of any interval coding which stores individual node numbers by a factor of 50%
to 80%, depending on the sizes of subtrees indexed. Moreover, We show that our
index using root-split coding, outperforms previous approaches by at least an
order of magnitude in terms of the response time of queries.
