ArcWatch: Your e-Magazine for GIS News, Views, and Insights

October 2009

Award-Winning Book by Hanan Samet Details Spatial Data Indexing Processes

  photo of Hanan Samet
Hanan Samet, author of Foundations of Multidimensional and Metric Data Structures.

Hanan Samet's latest book Foundations of Multidimensional and Metric Data Structures presents a comprehensive view of spatial data structures and indexing that includes some of his own major algorithms, as well as those of other computer scientists.

Samet is considered an expert on the use of hierarchical tree data structures such as the quadtree and octree. Quadtrees are often used to partition a two-dimensional space by recursively subdividing it into four quadrants, while octrees are applied in a similar way to a three-dimensional space to yield eight octants. Both methods provide a means to index the data that these spaces span.

The book grew out of Samet's longtime research at the University of Maryland's Computer Vision Laboratory, where he investigates the applicability of his work to geographic information systems, computer graphics, image processing, image databases, and visualization. The book also addresses algorithmic issues arising in applications such as the display of point cloud data, finding nearest neighbors in spatial networks, and similarity searching for use in image databases. The book was an award winner in the 2006 Computer and Information Science competition, sponsored by the Professional and Scholarly Publishers Group of the American Publishers Association.

Says Samet, "When multidimensional data corresponds to locational data, we have the additional property that all of the attributes usually have the same unit (possibly with the aid of scaling transformations), which is distance in space. We can therefore combine the distance-denominated attributes and pose queries that involve proximity."

In the book's foreword, Jim Gray, former computer scientist and technical fellow at Microsoft Research, wrote, "This book organizes the bewildering array of spatial and multidimensional indexing methods into a coherent field. Hanan Samet is the dean of 'spatial data indexing.' His two previous books, Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS and Design and Analysis of Spatial Data Structures have been the essential reference works for over a decade. This book unifies those previous books, and places the field in the broader context of indexing and searching for information in any metric space."

Xuejun Hao, associate research scientist at Columbia University, described Foundations of Multidimensional and Metric Data Structures as "the most complete book on the subject to date. In addition to the huge amount of information covered, it also contains a thorough bibliography with over 2,000 entries. The author uses an algorithmic approach with plenty of pseudo-code without resorting to complicated mathematical formulae." The book is easily understood by a wide range of readers who need not be programmers or computer scientists.

At the Computer Vision Laboratory, Samet leads many research projects that focus on the use of hierarchical data structures in GIS. His research on the integration of spatial and nonspatial data into a database management system (DBMS) has resulted in the development of two systems by his research group: QUILT, a GIS based on spatial data structures such as quadtrees and octrees, and SAND (Spatial And Nonspatial Data), which integrates spatial and nonspatial data and enables browsing through a spatial database using a graphical user interface.

He has also been developing the STEWARD (Spatio-Textual Extraction on the Web Aiding the Retrieval of Documents) system, a spatio-textual document search engine that enables the retrieval of documents on the basis of spatial proximity as well as matching keywords. It has been used by the research division of the Department of Housing and Urban Development.

Foundations of Multidimensional and Metric Data Structures, a book in the Morgan Kaufmann Series in Computer Graphics, is published by Morgan Kaufmann, ISBN-13: 978-0123694461, 2006, 1,024 pages, and is available from Elsevier for $68.95. It is also available from

Contact Us | Privacy | Legal | Site Map