A Hierarchy Navigation Framework: Supporting Scalable Interactive Exploration over Large Databases

Mehta, Nishant K

Etd

A Hierarchy Navigation Framework: Supporting Scalable Interactive Exploration over Large Databases

Public

Modern computer applications from business decision support to scientific data analysis use visualization techniques. However, visual exploration tools do not scale well for large data sets, i.e., the level of clutter on the screen is typically unacceptable. To solve the problem of cluttering at the interface level, visualization tools have recently been extended to support hierarchical views of the data, with support for focusing and drilling-down using interactive selection. To solve the scalability problem, we now investigate how best to couple such a near real-time responsive visualization tool with a database management system. Our solution proposes a framework containing three major components: hierarchy encoding, caching and prefetching. Since the direct implementation of the visual user interactions on hierarchical data sets corresponds to recursive query processing, we have developed a hierarchy encoding method, called the MinMax tree, that pushes the on-line recursive processing step into an off-line precomputation step. The MinMax encoding scheme allows us to map the hierarchy to a 2-dimensional space and the recursive navigation operations at the interface level to 2-dimensional spatial range queries. These queries can then be answered efficiently using spatial indexes. To compliment this encoding scheme we employ a caching strategy that exploits user navigation characteristics to cache the nodes having high probability of being referenced again. Based on user characteristics we choose to implement two replacement policies one which exploits temporal locality (LRU) and the other exploits spatial locality (Distance). Also, to enhance the performance of the cache we propose using a prefetching mechanism that predicts and prefetches future user requests into the cache. Together the components form a comprehensive framework that scales the visualization tool to support navigation operations over large data sets. The techniques have been incorporated into XmdvTool, a free software package for multi-variate data visualization and exploration. Our experimental results quantify the effectiveness of each component and show that collectively the components scale the XmdvTool to support navigation operations over large data sets. Mainly, our experimental results show that together the components can achieve 63\% to 96\%reduction in response time latency even with limited system resources.

Creator