CS Colloquium
December 4, 2008
10:30 a.m., AKW 200

Sign up to meet with speaker.

Speaker: Hanan Samet, Department of Computer Science, University of Maryland
Title: Sorting in Space

Host: Avi Silberschatz

Abstract: The representation of spatial data is an important issue in computer graphics, computer vision, geographic information systems, and robotics. A wide number of representations is currently in use. Recently, there has been much interest in hierarchical data structures such as quadtrees, octrees, R-trees, etc. The key advantage of these representations is that they provide a way to index into space. In fact, they are little more than multidimensional sorts. They are compact and depending on the nature of the spatial data they save space as well as time and also facilitate operations such as search. In this talk we give a brief overview of hierarchical spatial data structures and related research results. In addition we demonstrate the SAND Browser (found at http://www.cs.umd.edu/~brabec/sandjava) and the VASCO JAVA applet which illustrate these methods (found at http://www.cs.umd.edu/~hjs/quadtree/index.html).

Hanan Samet received the B.S. degree in engineering from the University of California, Los Angeles, and the M.S. Degree in operations research and the M.S. and Ph.D. degrees in computer science from Stanford University, Stanford, CA. He is a Fellow of the IEEE, ACM, and IAPR (International Association for Pattern Recognition), and was also elected to the ACM Council in 1989-1991 where he served as the Capital Region Representative.

In 1975 he joined the Computer Science Department at the University of Maryland, College Park, where he is now a Professor. He is a member of the Computer Vision Laboratory of the Center for Automation Research and also has an appointment in the University of Maryland Institute for Advanced Computer Studies. At the Computer Vision Laboratory he leads a number of research projects on the use of hierarchical data structures for geographic information systems. His research group has developed the QUILT system which is a GIS based on hierarchical spatial data structures such as quadtrees and octrees, the SAND system which integrates spatial and non-spatial data, the SAND Browser (http://www.cs.umd.edu/~brabec/sandjava) which enables browsing through a spatial database using a graphical user interface, the VASCO spatial indexing applet (found at http://www.cs.umd.edu/~hjs/quadtree/index.html), and a symbolic image database system (found at http://franang.umiacs.umd.edu:1603/index.html). He is the founding chair of the ACM SIG on Spatial Information (SIGSPATIAL). He has served as the co-general chair of the 2007 and 2008 ACM SIGSPATIAL Conference on Geographic Information Systems (ACM GIS).

His research interests include data structures, computer graphics, geographic information systems, computer vision, robotics, and database management systems, and is the author of over 300 publications on these topics. He is the author of the recent book titled "Foundations of Multidimensional and Metric Data Structures" (http://www.cs.umd.edu/~hjs/multidimensional-book-flyer.pdf) published by Morgan-Kaufmann, an imprint of Elsevier, in 2006, an award winner in the 2006 best book in Computer and Information Science competition of the Professional and Scholarly Publishers (PSP) Group of the American Publishers Association (AAP), and of the first two books on spatial data structures titled "Design and Analysis of Spatial Data Structures", and "Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS", both published by Addison-Wesley in 1990. He received a best paper award in the 2008 ACM SIGMOD Conference.