We investigate the effectiveness of a predictive interaction animation tool for understanding graph algorithms. We compare performance improvement of students after they have used two different animation tools for the given algorithms, when one of the tools forces a more active, predictive approach while the other is a more traditional animation. Results show significant improvement in performance after students use the predictive tool.

Support for exploratory interaction with databases in applications such as data mining requires that the first few results of an operation be available as quickly as possible. We study the algorithmic side of what can and what cannot be achieved for processing join operations. We develop strategies that modify the strict two-phase processing of the sort-merge paradigm, intermingling join steps with selected merge phases of the sort. We propose an algorithm that produces early join results for a broad class of join problems, including many not addressed well by hash-based algorithms. Our algorithm has no significant increase in the number of I/O operations needed to complete the join compared to standard sort-merge algorithms.

We study the trade-off between storage redundancy and access overhead for range queries, using the framework of [6]. We show that the Fibonacci workload of size n, which is the regular 2-dimensional grid rotated by the golden ratio, does not admit an indexing scheme with access overhead less than the block size B (the worst possible access overhead) , even for storage redundancy as high as c log n, for some constant c. We also show that this bound is tight (up to a constant factor) by providing an indexing scheme with storage redundancy \\Theta(log n) and constant access overhead, for any 2-dimensional workload. We extend the lower bound to random point sets and show that if the maximum storage redundancy is less than cloglog n, the access overhead is B. Finally, we explore the relation between indexability and fractal (Hausdorff) dimension of point sets. 1 Introduction In this paper we continue the work of [6] towards a theory of indexability ---that is, towards a better understandin...