Foundations of Multidimensional and Metric Data Structures (The Morgan Kaufmann Series in Computer Graphics) [Hardcover]

Hanan Samet (Author)

Book Description

Publication Date: August 22, 2006 | ISBN-10: 0123694469 | ISBN-13: 978-0123694461 | Edition: 1

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

* 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

Editorial Reviews

Review

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

Book Description

THE thorough and authoritative treatment on multidimensional data structures.

See all Editorial Reviews

Product Details

• Hardcover: 1024 pages
• Publisher: Morgan Kaufmann; 1 edition (August 22, 2006)
• Language: English
• ISBN-10: 0123694469
• ISBN-13: 978-0123694461
• Product Dimensions: 11 x 8.7 x 1.5 inches
• Shipping Weight: 5.5 pounds (View shipping rates and policies)
• Average Customer Review: 4.9 out of 5 stars  See all reviews (7 customer reviews)
• Amazon Best Sellers Rank: #369,806 in Books (See Top 100 in Books)

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

18 of 18 people found the following review helpful:

5.0 out of 5 stars Encyclopedia of Spatial , Multidimensional, and Metric Data Structures and Algorithms, September 1, 2006

By 

David K. Scott - See all my reviews
(REAL NAME)   

Amazon Verified Purchase

This review is from: Foundations of Multidimensional and Metric Data Structures (The Morgan Kaufmann Series in Computer Graphics) (Hardcover)

A stunning 1000 page encyclopedia of spatial, multidimensional, and metric data structures and algorithms presented in the Knuth tradition. The general coverage is broader than an older, now out of print and expensive: "Design and Analysis of Spatial Data Structures". In a surprise, the new book is not only the size of a telephone directory, but it has double the number of useful pages. 4 extensive chapters cover data structures and algorithms for: points, objects and images, intervals and small rectangles, and the same data types in higher +dimensions. Within each chapter, the algorithms and clearly presented and are accompanied by an extensive use of figures. The algorithms which run from the expected to the exotic are summarized by the table of contents at the publisher's web site. Unexpected algorithms are also covered including: nearest neighbor finding which is useful for clustering applications, image pyramids, and object pyramids or hierarchies such as R-trees.


The book has a textbook flavor with exercises at the end of each section where specifics are left for the student; however, solutions and pseudo-code for many of the exercises are in a 300+ page appendix maintaining the book as a useful reference. This book is comprehensive, inexpensive, and in my mind - a must have.

7 of 7 people found the following review helpful:

5.0 out of 5 stars A true classic, seminal and authoritative, January 17, 2007

By 

Richard Snodgrass (Tucson, AZ USA) - See all my reviews
(REAL NAME)   

This review is from: Foundations of Multidimensional and Metric Data Structures (The Morgan Kaufmann Series in Computer Graphics) (Hardcover)

Hanan Samet, the world-reknown authority on multi-dimensional data, has written a comprehensive and stunningly beautiful book. The illustrations that appear in the margins of almost every page serve to wonderfully augment the text and convey the essence of the topic under discussion. If you enjoy the clarity and broad coverage of Knuth's classics, or the elegance and wonder of Tufte's monographs, you will love this book.

Samet has distilled a lifetime of work understanding the algorithms of others and inventing major new algorithms and data structures into this very readable survey. The annotated bibliography and multiple indexes are amazing accomplishments in their own right. The book is very reasonably priced, making it accessible. This delightful book deserves to be on the bookshelf of every computer science scholar and programmer. X. Hao is right: this is truly a masterpiece.

5 of 5 people found the following review helpful:

5.0 out of 5 stars As good as it gets, September 27, 2007

By 

mathboy (San Diego, CA) - See all my reviews

Amazon Verified Purchase

This review is from: Foundations of Multidimensional and Metric Data Structures (The Morgan Kaufmann Series in Computer Graphics) (Hardcover)

The best possible scenario for a reader buying a tech book is to have

1) a single author, rather than an "editor" so the conceptual presentation and perspective of the product is consistent throughout

2) an author that knows the field inside out and can speak and think about it naturally with no hint in the presentation that he or she has hit upon a topic they're shaky with, and needs to resort to "high concept hand waving" to skate over the subject.

3) an author whose command of language is first rate - precise without being pedantic, and whose tone and level of exposition remains consistent throughout.

4) an author who spares himself nothing in terms of effort, cuts no corners and leaves nothing out for the student to "fill in" when explaining difficult concepts.

In this book, you get all that and more.

It's an encyclopedia of multi-d DS, written by a top researcher in the field, and addresses the subject matter at every level, from the panoramic to the implementation details. This book is on par with Jim Gray's near-perfect Transaction Processing.

If you think you don't need to know the subject matter in this book, you might want to think again. If you're developing anything that needs to find, index or classify information of any sort, graphic, text or otherwise and you're developing the basic technology, then this book is going to pay you the following dividends:

-save you time by getting you firmly grounded in the field,
-confirm and elevate your existing approach,
-make you aware of approaches, concepts and results that you just can't live in ignorance of and succeed.