The popularity of web-based mapping services such as Google Earth/Maps and Microsoft Virtual Earth (Bing), has led to an increasing awareness of the importance of spatial data and its incorporation into both web-based search and the databases that support it, whereas in the past attention to spatial data had been primarily limited to geographic information systems (GIS). An immediate byproduct of this awareness is the expectation of a real time response as is the experience of users of spreadsheets. Spatial data is distinguished from conventional data by having extent, which means that rather than being limited to locations, it also includes collections of locations [and, most importantly in both cases, their attributes].

This leads us to the main topic of this workshop which is the representation of multidimensional and spatial data. This is an important issue in applications of spatial databases, geographic information systems (GIS), and location-based services. 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 which are based on object hierarchies. Their key advantage 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.

We describe hierarchical representations of points, lines, collections of small rectangles, regions, surfaces, and volumes. For region data, we point out the dimension-reduction property of the region quadtree and octree. We also demonstrate how to use them for both raster and vector data. For all of the representations, we show how they can be used to compute nearest objects in an incremental fashion so that the number of objects need not be known in advance. The VASCO JAVA applet is presented that illustrates these methods (found at http://www.cs.umd.edu/~hjs/quadtree/index.html).

Suggested Readings:

H. Samet. A sorting approach to indexing spatial data. International Journal on Shape Modeling, 14(1):15-37, June 2008. Categories: [spatial data structures, survey] http://www.cs.umd.edu/~hjs/pubs/ijsm08.pdf

H. Samet. Database and representation issues in Geographic Information systems (GIS). In J. D. Carswell, A. S. Fotheringham, and G. McArdle, editors, Proceedings of the 9th Symposium on Web and Wireless Geographical Information Systems, vol. 5886 of Springer-Verlag Lecture Notes in Computer Science, pages 1-6, Maynooth, Ireland, December 2009.[link] Categories: [spatial data structures, survey] http://www.cs.umd.edu/~hjs/pubs/w2gis-2009.pdf

H. Samet. Foundations of Multidimensional and Metric Data Structures. Morgan-Kaufmann, San Francisco, 2006.[link] Categories: [spatial data structures, metric data structures, book] http://www.cs.umd.edu/~hjs/multidimensional-book-flyer.pdf