Foundations of Multidimensional and Metric Data Structures


  • Hanan Samet, University of Maryland at College Park, author of the pioneering books in this field, The Design and Analysis of Spatial Data structures, and Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS, both published by Addison-Wesley, 1990.

The field of multidimensional data structures is large and growing very quickly. Here, for the first time, is a thorough treatment of multidimensional point data, object and image-based representations, intervals and small rectangles, and high-dimensional datasets.

The book includes a thorough introduction; a comprehensive survey to spatial and multidimensional data structures and algorithms; and implementation details for the most useful data structures. Along with the hundreds of worked exercises and hundreds of illustrations, the result is an excellent and valuable reference tool for professionals in many areas, including computer graphics, databases, geographic information systems (GIS), game programming, image processing, pattern recognition, solid modeling, similarity retrieval, and VLSI design.

Award Winner in 2006 “Best Book” competition in Professional and Scholarly Publishing from the Association of American Publishers.

Morgan Kaufmann would like to congratulate Hanan Samet on receiving the UCGIS 2009 Research Award!

Read the announcement here:

View full description


This book is for the use of computer scientists who have a need to represent spatial data and as such will appeal to those in data management, computer graphics, game programming, bioinformatics, pattern recognition, GIS, and other non-CS fields like high energy physics, geography, mathematics, and engineering.


Book information

  • Published: August 2006
  • ISBN: 978-0-12-369446-1


Honorable Mention Award in the 2006 best book in Computer and Information Science competition from the Professional and Scholarly Publishers(PSP) Group of the American Publishers Association (AAP) “Hanan Samet is the dean of “spatial indexing”... This book is encyclopedic... this book will be invaluable for those of us who struggle with spatial data, scientific datasets, graphics, vision problems involving volumetric queries, or with higher dimensional datasets common in data mining.” — From the foreword by Jim Gray, Microsoft Research “Samet’s book on multidimensional and metric data structures is the most complete and thorough presentation on this topic. It has broad coverage of material from computational geometry, databases, graphics, GIS, and similarity retrieval literature. Written by the leading authority on hierarchical spatial representations, this book is a “must have” for all instructors, researchers, and developers working and teaching in these areas.” — Dinesh Manocha, University of North Carolina at Chapel Hill “To summarize, this book is excellent! It’s a very comprehensive survey of spatial and multidimensional data structures and algorithms, which is badly needed. The breadth and depth of coverage is astounding and I would consider several parts of it required reading for real time graphics and game developers.” — Bretton Wade, University of Washington and Microsoft Corp. “It’s a truly encyclopedic book on data structures for accelerating all sorts of 3D queries.” — Hector Yee, Hectorgon – A Graphics Programming Blog, October 18, 2006

Table of Contents

Chapter 1: Multidimensional Point Data1.1 Introduction1.2 Range Trees1.3 Priority Search Trees1.4 Quadtrees1.4.1 Point Quadtrees1.4.2 Trie-based Quadtree1.4.3 Comparison of Point and Trie-based Quadtrees1.5 K-d Trees1.5.1 Point K-d Trees1.5.2 Trie-based K-d Trees1.5.3 Conjugation Tree1.6 One-dimensional Orderings1.7 Bucket Methods1.7.1 Tree Directory Methods (K-d-B-tree, Hybrid Tree, LSD Tree, hB-tree, K-d-B-trie, BV-tree)1.7.2 Grid Directory Methods (Grid File, EXCELL, Linear Hashing, Spiral Hashing)1.7.3 Storage Utilization1.8 PK-tree1.9 ConclusionChapter 2: Object-based and Image-based Image Representations2.1 Interior-based Representations2.1.1 Unit-size Cells2.1.2 Blocks (Medial Axis Transform, Region Quadtree and Octree, Bintree, X-Y Tree)2.1.3 Nonorthogonal Blocks (BSP Tree, Layered DAG)2.1.4 Arbitrary Objects (Loose Octree, Field Tree, PMR Quadtree)2.1.5 Hierarchical Interior-based Representations (Pyramid, R-tree, Hilbert R-tree, R*-tree, R+-tree, Packed R-tree, R-tree, Cell Tree, Bulk Loading)2.2 Boundary-based Representations2.2.1 The Boundary Model (CSG,BREP, Winged-edge, Voronoi Diagram, Delaunay Triangulation, Tetrahedra)2.2.2 Image-based Boundary Representations (PM Quadtree and Octree, Adaptively Sampled Distance Field) 2.2.3 Object-based Boundary Representation (LOD, Strip Tree, Simplification Methods)2.2.4 Surface-based Boundary Representations (TIN)2.3 Difference-based Compaction Methods2.3.1 Runlength Encoding2.3.2 Chain Code2.3.3 Vertex Representation2.4 Historical OverviewChapter 3: Intervals and Small Rectangles3.1 Plane-sweep Methods and the Rectangle Intersection Problem3.1.1 Segment Tree3.1.2 Interval Tree3.1.3 Priority Search Tree3.1.4 Alternative Solutions and Related Problems3.2 Plane-sweep Methods and the Measure Problem3.3 Point-based Methods3.3.1 Representative Points3.3.2 Collections of Representative Points3.3.3 LSD Tree3.3.4 Summary3.4 Area-based Methods 3.4.1 MX-CIF Quadtree 3.4.2 Alternatives to the MX-CIF Quadtree (HV/VH Tree)3.4.3 Multiple Quadtree Block RepresentationsChapter 4: High-Dimensional Data4.1 Best-first Incremental Nearest Neighbor Finding (Ranking)4.1.1 Motivation4.1.2 Search Hierarchy4.1.3 Algorithm4.1.4 Duplicate Objects4.1.5 Algorithm Extensions (Farthest Neighbor, Skylines)4.1.6 Related Work4.2 The Depth-first K-nearest Neighbor Algorithm4.2.1 Basic Algorithm4.2.2 Pruning Rules4.2.3 Effects of Clustering Methods on Pruning4.2.4 Ordering the Processing of the Elements of the Active List4.2.5 Improved Algorithm4.2.6 Incorporating MaxNearestDist in a Best-first Algorithm4.2.7 Example4.2.8 Comparison4.3 Approximate Nearest Neighbor Finding4.4 Multidimensional Indexing Methods4.4.1 X-tree4.4.2 Bounding Sphere Methods: Sphere Tree, SS-tree, Balltree, and SR-tree4.4.3 Increasing the Fanout: TV-tree, Hybrid Tree, and A-tree4.4.4 Methods Based on the Voronoi Diagram: OS-tree4.4.5 Approximate Voronoi Diagram (AVD)4.4.6 Avoiding Overlapping All of the Leaf Blocks4.4.7 Pyramid Technique4.4.8 Sequential Scan Methods (VA-file, IQ-tree, VA+-file)4.5 Distance-based Indexing Methods4.5.1 Distance Metric and Search Pruning4.5.2 Ball Partitioning Methods (VP-tree, MVP-tree) 4.5.3 Generalized Hyperplane Partitioning Methods (GH-tree, GNAT, MB-tree)4.5.4 M-tree4.5.5 Sa-tree4.5.6 kNN Graph4.5.7 Distance Matrix Methods4.5.8 SASH - Indexing Without Using the Triangle Inequality4.6 Dimension-reduction Methods4.6.1 Searching in the Dimensionally-reduced Space4.6.2 Using Only One Dimension4.6.3 Representative Point Methods4.6.4 Transformation into a Different and Smaller Feature Set (SVD,DFT)4.6.5 Summary4.7 Embedding Methods4.7.1 Introduction4.7.2 Lipschitz Embeddings4.7.3 FastMap4.7.4 Locality Sensitive Hashing (LSH)Appendix 1: Overview of B-treesAppendix 2: Linear HashingAppendix 3: Spiral HashingAppendix 4: Description of Pseudo-Code LanguageSolutions to ExercisesBibliographyIndex