Answering order-based queries over XML data. Zografoula Vagena, Nick Koudas, Divesh Srivastava and Vassilis J. Tsotras. Order-based queries over XML data include XPath navigation axes such as following-sibling and following. In this paper, we present holistic algorithms that evaluate such order-based queries. An experimental comparison with previous approaches shows the performance benefits of our algorithms.