Foundations of multidimensional and metric data structures
by Hanan Samet · first published 2006
12mentions
11recommended by
11HN commenters
2009–2026first – last mentioned
100% recommend
Why HN recommends it
Comprehensive, very dense reference on multidimensional point and spatial data structures, including quadtrees, k-d trees, R-trees and metric trees; often called the standard reference for readers who need depth.
Summarised by Claude from recommending comments
Affiliate links. As an Amazon Associate I earn from qualifying purchases.
I came here to say this. Not just graphics, but indexing arrays in general on the GPU for use in OpenCL or CUDA. We are working on optimizing our neighbor searches using this. A good book: Foundations of Multidimensional and Metric Data Structures by Hanan Samet 2006 A good paper: Interactive SPH Simulation and Rendering on the GPU by Goswami
on “A practical use for space-filling curves” ↗If you want an overview, the bible right now is Samet's Foundations of Multidimensional and Metric Data Structures: http://www.amazon.com/Foundations-Multidimensional-Structure...
on “Ask HN: Getting started with geospatial data?” ↗+1 on all of those books. If you are interested in multi-dimensional indices (R-Trees, M-Trees, and many more exotic ones). You should checkout "Foundations of Multidimensional and Metric Data Structures" by Hanan Samet. Very comprehensive! "Database Systems: The Complete Book" is fantastic (pick up the previous version it is cheaper!) but it only touches on multidimensional indexing. Also if you are…
on “Michael Stonebraker wins Turing Award” ↗…queries, etc. in traditional database, with one field. Just a rad math quirk! I'm not an expert, and it's a very dense book, but if someone really wants to get into this kind of stuff the "Bible" is "Foundations of Multidimensional and Metric Data Structures" by Hanan Samet.
on “Space-filling curves, constructively” ↗> [I]t's a very dense book, but if someone really wants to get into this kind of stuff the "Bible" is "Foundations of Multidimensional and Metric Data Structures" by Hanan Samet. You're not Kidding! 1022 pages, with a TOC that nests 4 layers deep. In particular, section 2.1.1.2 "Ordering Space" covers space-filling curves, and true to your description it covers…
on “Space-filling curves, constructively” ↗…information I might cache and what representations data might take. That lead me to looking into the nuances of things like B-Trees, AVL Trees, Quadtrees, k-d trees and so forth. I've found the book "Foundations of Multidimensional and Metric Data Structures" by Hanan Samet to be an excellent resource when looking for a slightly deeper dive than a more introductory algorithms course. It goes in depth on the nuances of these approaches, many of which are highly…
on “Functional Quadtrees” ↗Quadtrees and octrees are themselves quite deep research areas. If the acceleration data structures interest you, I highly recommend Hanan Samet's book "Foundations of Multidimensional and Metric Data Structures". It's from 2006, but is basically the bible for the field.
on “Functional Flocking Quadtree in ClojureScript” ↗Then you want Foundations of Multidimensional and Metric Data Structures by Samet. Unless you already have it, then enjoy some pretty (organic) trees.
on “Some Unusual Trees” ↗Foundations of Multidimensional and Metric Data Structures Hanan Samet
on “Ask HN: Programming books that are desk worthy? (reference material)” ↗…Pearls of Functional Algorithm Design, and while it focuses on implementation in Haskell, you don't need to be a functional programming expert to get a lot out of the book. The second book is called Foundations of Multidimensional and Metric Data Structures, and while the name might scare some away, it has a lot of interesting algorithms and accompanying research paper references so you can go off and explore. It took me several years to make my way through…
on “Algorithms, Part I: Kevin Wayne and Robert Sedgewick” ↗…as Z-Order Curve (http://en.wikipedia.org/wiki/Z-order_(curve)). You can quickly get to an index in memory or a cell/location on the map using Morton-Encoding. It is also known as a Linear Quadtree. Foundations of Multidimensional and Metric Data Structures is a great resource! Check it out at http://gisandscience.com/2009/08/21/award-winning-book-by-ha....
on “Z-Quads, a spatial coordinate system” ↗…tuples. KD trees are what I'm most familiar with for that problem, but there are others that would fit. Check out chapters 1 ("Multidimensional Point Data") and 3 ("Intervals and Small Rectangles") of Foundations of Multidimensional and Metric Data Structures: https://books.google.com/books?id=vO-NRRKHG84C&pg=PR9&source... R-trees are more generic in that they can store intervals, shapes, volumes, etc, but (start time, duration) tuples are point-like, and…
on “Ask HN: Fast data structures for disjoint intervals?” ↗