Efficient indexing technique for answering reachability queiries on time-evolving hierarchies
Akella, Venkata Sri Ram
MetadataShow full item record
There are many applications involving tree structures. In these applications, trees are subject to discrete changes such as insertions and deletions of vertices or edges. In the last two decades there has been growing interest in such dynamically changing hierarchies. Time-evolving Hierarchies (TEH) is nothing but series of snapshots that change time-dependently. A hierarchy is called time-dependent when relationship between nodes or edges doesn’t remain constant with respect to time. A hierarchy in our case is a collection of one or more trees. Collection of trees is one particular case of collection of graphs. There are different hierarchical structures such as XML documents, JDK Classes, Geographic Information Systems, Social Network, Ontologies and Bioinformatics that are represented in the form of a graph or collection of graphs. Hierarchical structures such as XML documents, JDK Classes can be considered as a collection of one or more trees. One of the characteristic features of most of these hierarchies is that their properties are not static and they change over time. Due to the changes that frequently occur on these kinds of applications, it is often important to test reachability between given pair of vertices (reachability query) in a particular snapshot of the hierarchy. We present NCI indexing (non-contiguous interval based indexing), which is an interval indexing method designed to suit time-evolving environment. NCI indexing technique breaks the inherent brittleness of the static indexing approaches, reducing average indexing costs. We have also implemented a technique to answer reachability queries efficiently in time-evolving hierarchies. Towards balancing the trade-off between query latency and index costs, we have implemented SCISSORS (selective snapshot indexing with progressive solution refinement) paradigm.