iTopN: Incremental Extraction of the N Most Visible Objects

Abstract

The visual exploration of large databases calls for a tight coupling of database and visualization systems. Current vi-sualization systems typically fetch all the data and organize it in a scene tree, which is then used to render the visible data. For immersive data explorations, where an observer navigates in a potentially huge data space and explores selected data regions this approach is inadequate. A scalable approach is to make the database system observer-aware and exchange the data that is visible and most relevant to the observer. In this paper we present iTopN an incremental algorithm for extracting the most visible objects relative to the current position of the observer. We implement iTopN and compare it to an improved version of the R-tree that extends LRU with the caching of the top levels of the R-tree (LW-LRU). Our experiments show that iTopN is orders of magnitude faster than LW-LRU given the same amount of memory. Our experiments also show that for LW-LRU to perform as fast as iTopN it needs three times as much memory.