Foundations of Multidimensional and Metric Data Structures

Author： Hanan Samet

Publishers： Morgan Kaufmann Publishers Inc

Publishing year： 2006

ISBN： 9780080919072

Subject： [TP311.1 程序设计]

Language： ENG

Introduction

Foundations 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.

Chapter

  • Front Cover

  • Foundations of Multidimensional and Metric Data Structures

  • Copyright Page

  • Contents

  • Foreword

  • Preface

  • Chapter 1. Multidimensional Point Data

  • 1.1 Introduction

  • 1.2 Range Trees

  • 1.3 Priority Search Trees

  • 1.4 Quadtrees

  • 1.5 K-d Trees

  • 1.6 One-Dimensional Orderings

  • 1.7 Bucket Methods

  • 1.8 PK-Trees

  • 1.9 Conclusion

  • Chapter 2. Object-Based and Image-Based Image Representations

  • 2.1 Interior-Based Representations

  • 2.2 Boundary-Based Representations

  • 2.3 Difference-Based Compaction Methods

  • 2.4 Historical Overview

  • Chapter 3. Intervals and Small Rectangles

  • 3.1 Plane-Sweep Methods and the Rectangle Intersection Problem

  • 3.2 Plane-Sweep Methods and the Measure Problem

  • 3.3 Point-Based Methods

  • 3.4 Area-Based Methods

  • Chapter 4. High-Dimensional Data

  • 4.1 Best-First Nearest Neighbor Finding

  • 4.2 The Depth-First K-Nearest Neighbor Algorithm

  • 4.3 Approximate Nearest Neighbor Finding

  • 4.4 Multidimensional Indexing Methods

  • 4.5 Distance-Based Indexing Methods

  • 4.6 Dimension Reduction Methods

  • 4.7 Embedding Methods

  • Appendix A: Overview of B-Trees

  • Appendix B: Linear Hashing

  • Appendix C: Spiral Hashing

  • Appendix D: Description of Pseudocode Language

  • Solutions to Exercises

  • References

  • Reference Keyword Index

  • Author and Credit Index

  • Subject Index

    • 服务邮箱： whx@cnpiec.com.cn

    联系电话：010-65063046；65001305

    京ICP备09090397号-16 京公网安备 11010502049547号