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 due to screen clutter. Visualization tools have thus been extended to support hierarchical views of the data, with support for focusing and drilling-down using interactive brushes. We now investigate how best to couple such a near real-time responsive visualization tool with database support. For this, we have developed a tree labeling method, called MinMax tree, that allows the movement of the on-line recursive processing of visual user interactions on hierarchical data sets into an off-line precomputation step. Using MinMax tree we map the recursive processing at the interface level to two dimensional range queries that can be answered efficiently using spatial indexes. We also employ caching and prefetching at the client side to cope with the real-time response requirements. The techniques have been incorporated into XmdvTool, a free software package for multi-variate data visualization and exploration. Our experimental results show 70% to 80% reduction in response time latency even with limited system resources.