Foundations of multidimensional and metric data structures

What Hacker News says

1. markstockApr 2026
   Then you want Foundations of Multidimensional and Metric Data Structures by Samet. Unless you already have it, then enjoy some pretty (organic) trees.
   thread
2. lemonwaterlimeDec 2025
   I like to do data-oriented programming, and was just thinking about how I want to organize (and search through) the primary data structures/concepts for a project I'm working on. Part of that involved thinking about things like what 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 similar at a cursory glance.

   Show morethread
3. markstockDec 2025
   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.
   thread
4. davidcuddebackJul 2024
   Sure thing! I'd reframe this as a nearest neighbor search over (start time, duration) 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 that opens more possibilities. The ordered map is going to give you good memory locality. It might be that you'll only beat that when searching for larger durations (that require you to iterate over more of your ordered map). There will probably be an inflection point somewhere, depending on the distribution of your data and queries.

   Hope that helps!

   Show morethread
5. aguynamedbenJul 2024
   An interesting variant of space-filling curves + dimensionality reduction is Geohash (https://en.wikipedia.org/wiki/Geohash, http://geohash.org/) which takes a lon/lat and uses a Z-curve approach to produce a hash such as `u4pruydqqvj` representing the location. This hash value is basically "how far along the space-filling curve is the lon/lat located". You're reducing two dimensions (lon/lat) into one dimension (how far along the space-filling curve).

   There's a unique side-effect to Geohashes in that the value (`u4pruydqqvj`) can have it's end "lopped off" (i.e. cut down to `u4pru`) and it still represents a less precise, but generally accurate representation of the original lon/lat in most cases (when the curve isn't near the edge of the 2d map!). This allows you to index locations (lat/lon) using a string ('u4pru') which opens you up to doing b-tree, range 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.

   Show morethread
6. xelxebarJul 2024
   > [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 every point brought up in the comments so far:

   - Peano-Hilbert curve of OP

   - Z-order curve mentioned

   - "Reverse locality" issues

   - Performance considerations of the mapping function

   - Even 11 exercises for this section alone!

   What a beastly reference. Thank you for sharing.

   Show morethread