 |
|
| FOUNDATIONS OF MULTIDIMENSIONAL AND METRIC DATA STRUCTURES
| |
| | |
|
|
To order this title, and for more information, click here
By
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.
Included in series
The Morgan Kaufmann Series in Computer Graphics,
Description
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:
http://www.ucgis.org/summer2009/researchaward.htm
Audience
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.
Contents
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
| Bibliographic details |
Hardbound, 1024 pages, publication date: AUG-2006
ISBN-13: 978-0-12-369446-1
ISBN-10: 0-12-369446-9
Imprint: MORGAN KAUFFMAN
|
| Price and Ordering |
Price:
EUR 48.95
GBP 41.99
USD 68.95
|  |
Books and book related electronic products are priced in US dollars (USD), euro (EUR), and Great Britain Pounds (GBP). USD prices apply to the Americas and Asia Pacific. EUR prices apply in Europe and the Middle East. GBP prices apply to the UK and all other countries.
|
See also information about conditions of sale & ordering procedures, and links to our regional sales offices.
|
077/762
Last update: 5 Sep 2009
|
|
| |
| | |
|
|
| |
Home | Elsevier Sites | Privacy Policy | Terms and Conditions | Feedback | Site Map | A Reed Elsevier Company