LIMITED OFFER
Autumn sale
Save up to 20% on books and eBooks. Free shipping. No promo code needed.
Foundations of Multidimensional and Metric Data Structures
- 1st Edition - August 8, 2006
- Author: Hanan Samet
- Language: English
- Hardback ISBN:9 7 8 - 0 - 1 2 - 3 6 9 4 4 6 - 1
- eBook ISBN:9 7 8 - 0 - 0 8 - 0 9 1 9 0 7 - 2
Foundations of Multidimensional and Metric Data Structures provides a thorough treatment of multidimensional point data, object and image-based representations, intervals and small… Read more
Purchase options
Institutional subscription on ScienceDirect
Request a sales quoteFoundations of Multidimensional and Metric Data Structures provides 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. Each section includes a large number of exercises and solutions to self-test and confirm the reader's understanding and suggest future directions.
The book 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.
- First comprehensive work on multidimensional data structures available, a thorough and authoritative treatment
- An algorithmic rather than mathematical approach, with a liberal use of examples that allows the readers to easily see the possible implementation and use
- Each section includes a large number of exercises and solutions to self-test and confirm the reader's understanding and suggest future directions
- Written by a well-known authority in the area of spatial data structures who has made many significant contributions to the field
- The author's website includes: Spatial Index Demos
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.
Chapter 1: Multidimensional Point Data
1.1 Introduction
1.2 Range Trees
1.3 Priority Search Trees
1.4 Quadtrees
1.4.1 Point Quadtrees
1.4.2 Trie-based Quadtree
1.4.3 Comparison of Point and Trie-based Quadtrees
1.5 K-d Trees
1.5.1 Point K-d Trees
1.5.2 Trie-based K-d Trees
1.5.3 Conjugation Tree
1.6 One-dimensional Orderings
1.7 Bucket Methods
1.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 Utilization
1.8 PK-tree
1.9 Conclusion
Chapter 2: Object-based and Image-based Image Representations
2.1 Interior-based Representations
2.1.1 Unit-size Cells
2.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 Representations
2.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 Methods
2.3.1 Runlength Encoding
2.3.2 Chain Code
2.3.3 Vertex Representation
2.4 Historical Overview
Chapter 3: Intervals and Small Rectangles
3.1 Plane-sweep Methods and the Rectangle Intersection Problem
3.1.1 Segment Tree
3.1.2 Interval Tree
3.1.3 Priority Search Tree
3.1.4 Alternative Solutions and Related Problems
3.2 Plane-sweep Methods and the Measure Problem
3.3 Point-based Methods
3.3.1 Representative Points
3.3.2 Collections of Representative Points
3.3.3 LSD Tree
3.3.4 Summary
3.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 Representations
Chapter 4: High-Dimensional Data
4.1 Best-first Incremental Nearest Neighbor Finding (Ranking)
4.1.1 Motivation
4.1.2 Search Hierarchy
4.1.3 Algorithm
4.1.4 Duplicate Objects
4.1.5 Algorithm Extensions (Farthest Neighbor, Skylines)
4.1.6 Related Work
4.2 The Depth-first K-nearest Neighbor Algorithm
4.2.1 Basic Algorithm
4.2.2 Pruning Rules
4.2.3 Effects of Clustering Methods on Pruning
4.2.4 Ordering the Processing of the Elements of the Active List
4.2.5 Improved Algorithm
4.2.6 Incorporating MaxNearestDist in a Best-first Algorithm
4.2.7 Example
4.2.8 Comparison
4.3 Approximate Nearest Neighbor Finding
4.4 Multidimensional Indexing Methods
4.4.1 X-tree
4.4.2 Bounding Sphere Methods: Sphere Tree, SS-tree, Balltree, and SR-tree
4.4.3 Increasing the Fanout: TV-tree, Hybrid Tree, and A-tree
4.4.4 Methods Based on the Voronoi Diagram: OS-tree
4.4.5 Approximate Voronoi Diagram (AVD)
4.4.6 Avoiding Overlapping All of the Leaf Blocks
4.4.7 Pyramid Technique
4.4.8 Sequential Scan Methods (VA-file, IQ-tree, VA+-file)
4.5 Distance-based Indexing Methods
4.5.1 Distance Metric and Search Pruning
4.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-tree
4.5.5 Sa-tree
4.5.6 kNN Graph
4.5.7 Distance Matrix Methods
4.5.8 SASH - Indexing Without Using the Triangle Inequality
4.6 Dimension-reduction Methods
4.6.1 Searching in the Dimensionally-reduced Space
4.6.2 Using Only One Dimension
4.6.3 Representative Point Methods
4.6.4 Transformation into a Different and Smaller Feature Set (SVD,DFT)
4.6.5 Summary
4.7 Embedding Methods
4.7.1 Introduction
4.7.2 Lipschitz Embeddings
4.7.3 FastMap
4.7.4 Locality Sensitive Hashing (LSH)
Appendix 1: Overview of B-trees
Appendix 2: Linear Hashing
Appendix 3: Spiral Hashing
Appendix 4: Description of Pseudo-Code Language
Solutions to Exercises
Bibliography
Index
1.1 Introduction
1.2 Range Trees
1.3 Priority Search Trees
1.4 Quadtrees
1.4.1 Point Quadtrees
1.4.2 Trie-based Quadtree
1.4.3 Comparison of Point and Trie-based Quadtrees
1.5 K-d Trees
1.5.1 Point K-d Trees
1.5.2 Trie-based K-d Trees
1.5.3 Conjugation Tree
1.6 One-dimensional Orderings
1.7 Bucket Methods
1.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 Utilization
1.8 PK-tree
1.9 Conclusion
Chapter 2: Object-based and Image-based Image Representations
2.1 Interior-based Representations
2.1.1 Unit-size Cells
2.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 Representations
2.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 Methods
2.3.1 Runlength Encoding
2.3.2 Chain Code
2.3.3 Vertex Representation
2.4 Historical Overview
Chapter 3: Intervals and Small Rectangles
3.1 Plane-sweep Methods and the Rectangle Intersection Problem
3.1.1 Segment Tree
3.1.2 Interval Tree
3.1.3 Priority Search Tree
3.1.4 Alternative Solutions and Related Problems
3.2 Plane-sweep Methods and the Measure Problem
3.3 Point-based Methods
3.3.1 Representative Points
3.3.2 Collections of Representative Points
3.3.3 LSD Tree
3.3.4 Summary
3.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 Representations
Chapter 4: High-Dimensional Data
4.1 Best-first Incremental Nearest Neighbor Finding (Ranking)
4.1.1 Motivation
4.1.2 Search Hierarchy
4.1.3 Algorithm
4.1.4 Duplicate Objects
4.1.5 Algorithm Extensions (Farthest Neighbor, Skylines)
4.1.6 Related Work
4.2 The Depth-first K-nearest Neighbor Algorithm
4.2.1 Basic Algorithm
4.2.2 Pruning Rules
4.2.3 Effects of Clustering Methods on Pruning
4.2.4 Ordering the Processing of the Elements of the Active List
4.2.5 Improved Algorithm
4.2.6 Incorporating MaxNearestDist in a Best-first Algorithm
4.2.7 Example
4.2.8 Comparison
4.3 Approximate Nearest Neighbor Finding
4.4 Multidimensional Indexing Methods
4.4.1 X-tree
4.4.2 Bounding Sphere Methods: Sphere Tree, SS-tree, Balltree, and SR-tree
4.4.3 Increasing the Fanout: TV-tree, Hybrid Tree, and A-tree
4.4.4 Methods Based on the Voronoi Diagram: OS-tree
4.4.5 Approximate Voronoi Diagram (AVD)
4.4.6 Avoiding Overlapping All of the Leaf Blocks
4.4.7 Pyramid Technique
4.4.8 Sequential Scan Methods (VA-file, IQ-tree, VA+-file)
4.5 Distance-based Indexing Methods
4.5.1 Distance Metric and Search Pruning
4.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-tree
4.5.5 Sa-tree
4.5.6 kNN Graph
4.5.7 Distance Matrix Methods
4.5.8 SASH - Indexing Without Using the Triangle Inequality
4.6 Dimension-reduction Methods
4.6.1 Searching in the Dimensionally-reduced Space
4.6.2 Using Only One Dimension
4.6.3 Representative Point Methods
4.6.4 Transformation into a Different and Smaller Feature Set (SVD,DFT)
4.6.5 Summary
4.7 Embedding Methods
4.7.1 Introduction
4.7.2 Lipschitz Embeddings
4.7.3 FastMap
4.7.4 Locality Sensitive Hashing (LSH)
Appendix 1: Overview of B-trees
Appendix 2: Linear Hashing
Appendix 3: Spiral Hashing
Appendix 4: Description of Pseudo-Code Language
Solutions to Exercises
Bibliography
Index
- No. of pages: 1024
- Language: English
- Edition: 1
- Published: August 8, 2006
- Imprint: Morgan Kaufmann
- Hardback ISBN: 9780123694461
- eBook ISBN: 9780080919072
HS
Hanan Samet
Hanan Samet is Professor in the Department of Computer Science at the University of Maryland, and a member of the Center for Automation Research and the Institute for Advanced Computer Studies. He is widely published in the fields of spatial databases and data structures, computer graphics, image databases and image processing, and geographic information systems (GIS), and is considered an authority on the use and design of hierarchical spatial data structures such as the quadtree and octree for geographic information systems, image processing, and computer graphics. He is the author of the two books The Design and Analysis of Spatial Data Structures and Applications of Spatial Data Structures: Computer Graphics, Image Processing and GIS. He holds a Ph.D. in computer science from Stanford University.
Affiliations and expertise
University of Maryland at College Park, College Park, MD, USA