IMSE graduate student Pan Xu was the first author on a paper that was accepted to the Symposium on the Principles of Database Systems (PODS) this year. The PODS Symposium is an annual symposium organized by the Association of Computing Machinery (ACM), and is a leading international forum for database researchers, practitioners, developers, and users to explore cutting-edge ideas and results, and to exchange techniques, tools, and experiences. It is considered to be the top venue for database algorithms. For a paper to get accepted to PODS, it must pass through a detailed reviewing phase, where four to six experts review the paper, and the top ranked papers are accepted into the conference. This year, PODS accepted 26 papers out of a total of 101 submissions.
Pan was the first author on the paper “On Optimality of Clustering Through a Space Filling Curve,” which was accepted to PODS this year. Space filling curves are mappings from a high dimensional universe to a one-dimensional universe. These are widely used tools for developing database software for spatial data, and have been used in commercial products such as Oracle Spatial and OpenGIS. This work proved that the Hilbert curve was optimal for the class of queries of a constant size. This finding answered a 15-year standing question posed by Jagadish in 1997, and also presented results that characterized the class of optimal space filling curves. This work can lead to a precise understanding of the power and limitation of the space filing curve technique, and also give insight into how to construct the “best” space filling curve for a given task.
Pan was a significant contributor to this work, and brought a very keen mathematical insight into these problems. He had the key idea behind the lower bound that was at the heart of the paper. This paper would not be written without his contribution. Pan works with IMSE Assistant Professor Lizhi Wang.