In this talk we show how to maintain a dynamic set of N elements in sorted order in a O(N)-sized array in memory or on disk. The idea is to intersperse O(N) gaps so that only a small number of elements need to be moved on an insert or delete.

Because the elements are stored physically in sorted order in memory or on disk, the structure supports extremely efficient data scans or range queries.

We show how to maintain the structure with a small (polylogarithmic) number of element moves even in the worst case. We then present an adaptive structure that performs even better for common insertion patterns. We give theoretical analysis and experimental results.

Joint work with Haodong Hu.

Bio:
Michael A. Bender is an associate professor of computer science at Stony Brook University. His research interests include analysis of algorithms, scheduling, parallel computing, data structures, and cache- and I/O-efficient computing.

Bender has coauthored over 80 articles on these and other topics in computer science. He has received several awards, including an R&D 100 Award for his work on scheduling in parallel computers and three awards for both graduate and undergraduate teaching.

Bender founded in startup Tokutek in 2006, where he serves as VP of Engineering. He has also held Visiting Scientist positions at both MIT and King's College London.

Bender received his B.A. in Applied Mathematics from Harvard University in 1992 and obtained a D.E.A. in Computer Science from the Ecole Normale Superieure de Lyon, France in 1993. He completed a Ph.D. on Scheduling Algorithms from Harvard University in 1998.