August 16 - 20
2010

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