Seminar: John Iacono, NYU, “The geometry of data structures”

Thursday, Sept 3, 4:30pm, POST 126

The geometry of data structures
John Iacono
Professor, Computer Science and Engineering
NYU Polytechnic School of Engineering

Abstract: A technique has been developed to study and analyze data structures called the geometric view. In this view the execution of a data structure is plotted in two dimensions. The vertical dimension is the time axis, where the j-th row corresponds to the execution of the j-th operation during the lifetime of the data structure. The horizontal axis is the space axis, where every column corresponds to an element in the structure and the ordering of the columns follows some natural ordering among the items in the underlying data structure.

Three examples of the use of this view will be presented: rotation-based binary search tree data structure, cache-oblivious persistence, and disjoint sets.

In all of these examples the main theme is that by moving to the geometric view, details of the data structure that seem cumbersome and hard to approach are abstracted in such a way that allows a simple, yet equivalent, view.