Hacker News new | ask | show | jobs
by davidcuddeback 698 days ago
It's really going to depend on the queries that you want to optimize. I think the best help might be to point you to a book: https://www.amazon.com/Foundations-Multidimensional-Structur...

An RTree is the first structure that comes to mind, but the way you describe the problem, it sounds like the intervals never overlap, so I have my doubts. Sounds like you might be looking to optimize the query "what is the first interval of at least N days?" Maybe look at priority trees. They're good at queries that are bounded in one dimension and half-open in the other.
1 comments
grovesNL 698 days ago
Thanks! I did try a 1-dimension R-tree but the performance tended to be much worse than an ordered map.

Priority trees could be really interesting. I did consider them early on but wasn't sure how well they'd apply here, so I'll take another look.

link
davidcuddeback 698 days ago
Elsewhere is the thread, it sounds like your range queries with inequality constraint might actually be a nearest neighbor query with inequality constraint. I'm not sure off the top of my head how feasible that would be with a priority search tree.
link