I/O-Optimal Node Ordering Schemes for Set-Based Navigations in Trees

摘要

There are many applications in which users interactivelyaccess large tree data by repeating set-based navigations,i.e., by repeatedly selecting one (or several) node,retrieving a set of nodes connected to it, and again selectingone (or several) node among them. In this paper, we focus onthe eight most fundamental operations in set-based navigation,which include neighbor/reachable, label-specific/wildcard, andforward/backward navigations. For efficient processing of theseoperations for large data stored on a disk, we need a storagescheme that clusters nodes that are accessed together by thoseoperations. In this paper, (1) we show no storage scheme can beI/O-optimal for all these operations, (2) we show several nodeordering schemes, each of which is I/O-optimal for some subsetof them, (3) we show that one of the schemes can process all theforward operations with sequential access to a constant-boundednumber of regions on the disk without accessing irrelevant nodes,and (4) backward operations can be efficiently processed onthat scheme by using a standard cache technique. We alsoshow that our storage scheme is compatible with several knowntechniques, such as, those for updates, that are important inpractical applications. Finally, we give experimental results withsynthesized and real data that confirm our theoretical results.