|
|
CONTACT: Anne P. Wilson
IMMEDIATE
1999 PARIS KANELLAKIS AWARD Dr. Daniel Sleator, Carnegie Mellon, & Dr. Robert Tarjan, Princeton University Honored New York, April 26, 2000...The Association for Computing Machinery (ACM) today announced that Doctors Daniel Sleator and Robert Tarjan have won the Paris Kanellakis Theory and Practice Award for creating the Splay-Tree Data Structure. Splay-Tree is one of the most widely-used data structures invented in the last 20 years. The Kanellakis award honors accomplishments that have had significant and demonstrable effects on the practice of computing. The Splay-Tree self-adjusting binary search tree can be used to provide fast access to tables and to implement priority queues. It is used in operating systems, compilers, web caches, network routers, text processors, and event simulation. Many products and systems rely on splay-trees, including:
Splay-trees, and the concept of amortized analysis that Drs. Sleator and Tarjan introduced to characterize their performance, have also had a major impact on the general field of algorithm design and analysis. The data structure itself is highlighted in almost every modern algorithms text, and amortized analysis has been immensely influential, by showing that algorithms can still have provably good overall performance even when individual steps might occasionally take a long time. Many useful algorithms of this sort have been developed since Sleator and Tarjan introduced the tools for analyzing them. Dr. Sleator is a Professor of Computer Science at Carnegie Mellon University. In addition to work on the Splay-Tree structure and amortized analysis, Dr. Sleator has contributed to a wide variety of other computer related research projects. He jointly developed the Link Grammar system for parsing English, and the Serioso Music Analyzer for analyzing meter and harmony in written music. He is the founder and President of chessclub.com, a flourishing game-playing site on the internet. Dr. Sleator holds a patent on data compression, and has lectured at such conferences as the Seventh International Conference on Graph Theory and the first Latin American Symposium on Theoretical Information in Sao Paulo, Brazil. His writing on topics like data structures and computing have resulted in more than 30 refereed conference and journal publications. Dr. Tarjan is the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University, as well as the Chief Scientist of InterTrust Technologies Corporation and a Senior Research Fellow in InterTrust's STAR Lab. He has held previous positions at the NEC Research Institute, AT&T Bell Laboratories, New York University, Stanford University, the University of California at Berkeley, and Cornell University. His honors include the A. M. Turing Award of the Association for Computing Machinery, the Nevanlinna Prize of the International Mathematical Union, and membership in the National Academy of Sciences and the National Academy of Engineering. Dr Tarjan is the author of "Data Structures and Network Algorithms" and coauthor of "Notes in Introductory Combinatorics." He jointly holds a patent on data compression. His research on the design and analysis of data structures and combinatorial algorithms has produced nearly 200 publications in refereed journals and conference proceedings. He was Dr. Sleator's Ph.D. thesis advisor. The Paris Kanellakis Theory and Practice Award honors specific theoretical accomplishments that have had a significant and demonstrable effect on the practice of computing. The award is accompanied by a prize of $5,000 and is endowed by contributions from the Kanellakis family, with additional financial support provided by Brooks/Cole Publishing Company, ACM's Special Interest Group on Algorithms and Computational Theory (SIGACT), ACM's Special Interest Group on Design Automaton (SIGDA), ACM's Special Interest Group on Management of Data (SIGMOD), ACM's Special Interest Group on Programming Languages (SIGPLAN), the ACM SIG Discretionary Fund, and individual contributions. About the ACM Founded in 1947, ACM (www.acm.org) is the world's first educational and scientific computing society. With more than 80,000 members worldwide, a dynamic series of authoritative publications, a wide range of special interest groups (SIGs), and an outstanding array of conferences, workshops and forums, ACM is a world-class resource for the entire technology field. |
