Sorting in Space

Multidimensional, Spatial, and Metric Data Structures

PhD Course at Department of Computer Science, University of Genova

Introduction

The representation of spatial data is an important issue in game programming, computer graphics, visualization, solid modeling, and related areas including computer vision and geographic information systems (GIS). It has also taken on an increasing level of importance as a result of the popularity of web-based mapping services such as Bing Maps, Google Maps, Google Earth, and Yahoo Maps, as well as the increasing importance of location-based services. Operations on spatial data are facilitated by building an index on it. The traditional role of the index is to sort the data. However, since no ordering exists in dimensions greater than one without a transformation of the data to one dimension, the role of the sorting process consists of differentiating between the data, and what is usually done is to sort (i.e., order) the spatial objects with respect to the space that they occupy. The resulting ordering is usually implicit rather than explicit so that the data do not need to be resorted (i.e., the index needs not be rebuilt) when the queries change (e.g., the query reference objects).

There are many representations (i.e., indexes) currently in use. Recently, there has been much interest in hierarchical data structures such as quadtrees, octrees, and pyramids, which are based on image hierarchies, as well methods that make use of bounding boxes or volumes, which are based on object hierarchies. The key advantage of these representations is that all of them provide a way to index into space. 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.

Course Description

In this course we provide a brief overview of hierarchical spatial data structures and related algorithms that make use of them.
We describe hierarchical representations of points, lines, collections of small rectangles, regions, surfaces, and volumes. For region data, we point out the nodes in the same tree, thereby leading to the popularity of these representations in ray tracing applications.
We also demonstrate how to use these representations for both raster and vector data. In the case of non-region data, we show how these data structures can be used to compute nearest objects in an incremental fashion so that the number of objects need not be known in advance. We point out that these algorithms can also be used in an environment where the distance is measured along a spatial network rather than being constrained to `"as the crow flies" (i.e., the Euclidean distance).
We also review a number of different tessellations and show why hierarchical decomposition into squares instead of triangles or hexagons is preferred. In addition, we briefly show how to represent data that lies only in a metric space rather than a vector space and point out the relationship of these representations to those that assume that the data lies in a vector space. In particular, we show that the difference is that the partitions are implicit in the metric space in contrast to being explicit in the vector space.

Biography

Hanan Samet (http://www.cs.umd.edu/~hjs/) is a Professor of Computer Science at the University of Maryland, College Park and is a member of the Institute for Computer Studies. He is also a member of the Computer Vision Laboratory at the Center for Automation Research where he leads a number of research projects on the use of hierarchical data structures for database applications involving spatial data. He has a Ph.D from Stanford University.
He is the author of the recent book "Foundations of Multidimensional and Metric Data Structures" published by Morgan-Kaufmann, San Francisco, CA, in 2006 (http://www.mkp.com/multidimensional), 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" published by Addison-Wesley, Reading, MA, 1990.
He is the founding chair of ACM SIGSPATIAL, a recipient of the 2009 UCGIS Research Award and the 2010 CMPS Board of Visitors Award at the University of Maryland, a Fellow of the ACM, IEEE, AAAS, and IAPR (International Association for Pattern Recognition), and an ACM Distinguished Speaker.