Potentials and Limitations of Visual Methods for the Exploration of Complex Data Structures
Tobias Lauer · FreiDok plus (Universitätsbibliothek Freiburg) · 2007
Visualizations can be used for the analysis of algorithms and data structures as well as for algorithm teaching and learning. If interactive animations or simulations are available, learners can explore the data structures and algorithms on their own. By seeing how an algorithm reacts to different input sets, a deeper understanding and hence, better learning, is expected. Similarly, visualization can be a helpful research tool for the analysis of complex data structures and the algorithms operating on them. For a formal mathematical analysis, the right approach to the problem is often the most decisive step. A suitable visual representation of the structure and the dynamics of the involved algorithms can provide important clues for the initial idea. Using the example of a relatively recent data structure, the priority search pennant, we show how visualizations can support the analysis of algorithms for complex geometric range queries on sets of point in the two-dimensional plane. Priority search pennants are similar to the better-known priority search trees; the structure is interesting since the rigid heap order known from many implementations of priority queues is weakened. As a result, priority search pennants are easier to maintain than priority search trees when the set of points is dynamic, i.e. when points are inserted and deleted and the underlying tree has to be rebalanced. This advantage comes at a cost: certain range queries have been shown to have a higher asymptotic complexity for priority search pennants than for priority search trees. However, it has been unclear whether this is also true for other frequently occurring types of range queries. We analyze the complexity of those operations which, for a given rectangular query range, return the leftmost, rightmost, or bottommost point of the set, respectively. It is shown that these operations enjoy the same asymptotic bounds in priority search pennants as they do in priority search trees. In addition, a sharp upper and lower bound for the actual worst case search path lengths of these queries is established in relation to the height of the underlying tree. As an application, we consider most-specific range queries in IP router tables, where, e.g., for the destination address of an incoming packet the filter containing the most specific range containing that address must be found. It is shown for an existing router table design based on priority search trees that a replacement of the tree by a priority search pennant or an even simpler structure, the min-augmented range tree, boosts the performance of update as well as lookup operations considerably. Moreover, we prove that the original router table design contains a redundant structure which can be omitted at no loss of efficiency, thereby reducing the space requirements and the cost of update operations by approximately 50%. Another goal is to investigate how interactive algorithm visualizations can be effectively employed in teaching and learning, and to provide possible applications. We present the results of an empirical experiment conducted to evaluate the impact of the level of learner engagement with visualizations on the learning outcome. Early experiments on visualization effectiveness have given rise to the hypothesis that algorithm animations are effective only if they are interactive and engaging. Our study was carried out within an established framework. Contrary to the hypothesis, our results showed no significant differences between students who simply viewed algorithm animations, those who could actively choose the input, and those who could even construct the animations visually by assembling the algorithm from "atomic" building blocks. However, a significant influence of the introductory lectures to the topic was found, as well as a strong correlation of test results with the overall performance of the participants in the course. Judging from our own results and those of further studies, we also conclude that some refinements to the research framework may be useful in order to allow for more differentiated results in future evaluations. One main reason why many instructors are reluctant to use algorithm animations in their teaching seems to be the time and effort required to find suitable visualization systems, to learn how to use them, and to create good examples. We propose a "radically simple" approach, which allows instructors to sketch ad-hoc examples during a presentation with a standard pen input device. The sketches are then interpreted as instances of a data structure. Commands (pen gestures) allow users to interact with the data structures, e.g. to carry out operations on them and trigger animations of the resulting actions. The last part of the thesis describes the architecture of the system and outlines its properties with the help of selected examples.