3 ms·
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-
by davidcuddeback 2y 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-Structures-Kaufmann-Computer/dp/0123694469 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.
- grovesNL 2y agoThanks! 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.
- davidcuddeback 2y agoElsewhere 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.