When streaming semi-structured data is processed by a well-designed query processor, parsing constitutes a significant portion of the
running time. Further improvements in performance therefore require some method to overcome the high cost of parsing. We have designed a general-purpose mechanism by which a producer of streaming data may augment the data stream with {hints} that permit a downstream processor to skip parsing parts of the stream. Inserting such hints requires additional processing by the producer of data; however, the resulting stream is more valuable to consumers (since they have to perform less processing) , making such processing worthwhile. We present a set of hint schemes and describe how they are used by query engines. We demonstrate the benefits of our approach using an experimental study based on a hints-aware XPath query engine. Our
results show that XHints can improve the performance of XPath query engines by as much as 100%. (UMIACS-TR-2004-11)