In his latest book, Foundations of Multidimensional and Metric Data Structures, Hanan Samet, renowned authority on this topic, 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. He is considered an expert on the use of hierarchical data structures such as the quadtree, which is often used to partition a two-dimensional space by recursively subdividing it into four quadrants, thereby providing a means to index the data that they span.

The book is the result of Samet’s longtime research at the University of Maryland’s Computer Vision Laboratory investigating 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..  It was an award winner in the 2006 best book in Computer and Information Science competition from the Professional and Scholarly Publishers Group of the American Publishers Association.

Comments 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 Foreword to the book Jim Gray at Microsoft Research writes, “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 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, writes “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 2000 entries. The author uses an algorithmic approach with plenty of pseudo-code without resorting to complicated mathematical formulae….The book is easily accessible to a wide range of readers who need not be programmers or computer scientists.”

At the Computer Vision Laboratory Samet leads a number of research projects on the use of hierarchical data structures in GIS.  His research on the integration of spatial and nonspatial data into a 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 Non-spatial Data), which integrates spatial and non-spatial 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, and which has been used for documents of the research division of the Department of Housing and Urban Development.

Foundations of Multidimensional and Metric Data Structures: The Morgan Kaufmann Series in Computer Graphics is published by Morgan Kaufmann, ISBN-13: 978-0123694461, 2006, 1024 pages, and is available from Elsevier for $64.95.

As part of the study A Global Map of Human Impact on Marine Ecosystems by Benjamin S. Halpern et al., published in Science on 15 February 2008, global artisanal fishery data has been generated by the National Center for Ecological Analysis and Synthesis and can be downloaded in a raster format here.”