Method of Optimizing Digital History Wins Best Paper Award
This September, research on persistence by three members of the NYU Polytechnic School of Engineering Computer Science and Engineering faculty will receive the best paper award at the European Symposium on Algorithms in Wroclaw, Poland.
Professor John Iacono, Postdoctoral Teaching Fellow Özgür Özkan, and Postdoctoral Researcher Pooya Davoodi authored the paper, along with Jeremy Fineman of Georgetown University. The European Association for Theoretical Computer Science (EATCS) chose their paper, Cache-Oblivious Persistence, from more than 250 submissions to the symposium.
The concept of persistence in the field of computer science was introduced by James R. Driscoll, Neil Sarnak, Daniel D. Sleator, and Robert E. Tarjan in 1989. It is the ability to go back and look at the state of a computing system at any point in the past. Examples in which one can see previous versions appear in many of today's systems including consumer products such as Apple's Time Machine and Dropbox.
This paper presents the first efficient general method, both in terms of time and space usage, of transforming algorithms and data structures optimized for modern computer architectures with multi-level memory hierarchy into ones that support queries into their past states.