Title: FIFO Indexes for Decomposable Problems

Speaker: Yufei Tao, CUHK

Time/Date:  Friday, April 1, 2:30-3:30p
Location: Room 5487

Abstract:
This paper studies first-in-first-out (FIFO) indexes, each of which manages
a dataset where objects are deleted in the same order as their insertions.
We give a technique that converts a static data structure to a FIFO index
for all decomposable problems, provided that the static structure can be
constructed efficiently. We present FIFO access methods to solve several
problems including half-plane search, nearest neighbor search, and extreme
-point search. All of our structures consume linear space, and have
optimal or near-optimal query cost.

Bio:
Yufei Tao is a Professor in the Department of Computer Science and
Engineering, Chinese University of Hong Kong (CUHK). Before joining
CUHK in 2006, he was a Visiting Scientist at the Carnegie Mellon
University during 2002-2003, and an Assistant Professor at the City
University of Hong Kong during 2003-2006. He regularly serves the
programming committees of SIGMOD, VLDB, ICDE, and is currently an
associate editor of ACM Transactions on Database Systems (TODS). He
was the PC chair of the demonstration track in SIGMOD 2010, a PC
co-chair of International Symposium on Spatial and Temporal Databases
(SSTD) 2011, an area PC chair of ICDE 2011, and a senior PC member of
International Conference of Information and Knowledge (CIKM) 2010.