4 ms·

Thank you! Absolutely, the problem I'm solving is closer to the resource-constrained project scheduling problem (RCPSP) but it's also closely related to job sho

Thank you! Absolutely, the problem I'm solving is closer to the resource-constrained project scheduling problem (RCPSP) but it's also closely related to job shop scheduling. I've mostly focused on reducing the search space so far, but I've always wondered if there's a way to significantly accelerate range queries. My B-tree map implementation is already very fast in practice, but intuitively it seems like a data structure should be able to advantage of the fact that intervals are disjoint to greatly improve performance. For example, inversion lists take advantage of disjointedness to reduce storage cost - I'd like to do the same but for performance. Many range queries also have a minimum duration requirement, so it could be useful if a data structure could take advantage of this to quickly exclude intervals during the search.

davidcuddeback 2y ago
> Many range queries also have a minimum duration requirement, so it could be useful if a data structure could take advantage of this to quickly exclude intervals during the search. Check out priority search trees. They search two dimensions, one of them being half-open (that would be your minimum duration requirement). Depends if the other half of your queries fits the closed dimension of a priority tree or if you can adapt it to fit your needs.
eru 2y ago
The representation I suggested in https://news.ycombinator.com/item?id=41053437 https://news.ycombinator.com/item?id=41053437 takes advantage of intervals being disjoint.
brudgers 2y ago
Thanks I hadn't heard of RCPSP, but that's not surprising. My first thought was "can RCPSP be expressed as job shop scheduling?" because I have a mild interest in scheduling problems. The mathematics of scheduling provides insight into why-are-things-that-way questions when when it seems like there ought to be something better than that-way...anyway... My intuition is that "available ranges" sounds like a sorted index and that suggests "SQLite" (or "SQLserver" etc.) as data structure. I mean if you are already building on B-trees, you're conceptually on the way to a RDBMS, just without the robust tooling and low level IO optimizations and tuning interfaces already built and tested and supported with maintenance contracts. Or to put it another way data is always snowflake. RDBMS's are a great tool for handling snowflakes. And reasoning about them. Of course I might be wrong about the particulars of your use case and in any organization there's NIH and politics. And maybe an RDBMS was where you started, etc. etc. It's a brownfield project.

davidcuddeback 2y ago

> Many range queries also have a minimum duration requirement, so it could be useful if a data structure could take advantage of this to quickly exclude intervals during the search. Check out priority search trees. They search two dimensions, one of them being half-open (that would be your minimum duration requirement). Depends if the other half of your queries fits the closed dimension of a priority tree or if you can adapt it to fit your needs.

eru 2y ago

The representation I suggested in https://news.ycombinator.com/item?id=41053437 https://news.ycombinator.com/item?id=41053437 takes advantage of intervals being disjoint.

brudgers 2y ago

Thanks I hadn't heard of RCPSP, but that's not surprising. My first thought was "can RCPSP be expressed as job shop scheduling?" because I have a mild interest in scheduling problems. The mathematics of scheduling provides insight into why-are-things-that-way questions when when it seems like there ought to be something better than that-way...anyway... My intuition is that "available ranges" sounds like a sorted index and that suggests "SQLite" (or "SQLserver" etc.) as data structure. I mean if you are already building on B-trees, you're conceptually on the way to a RDBMS, just without the robust tooling and low level IO optimizations and tuning interfaces already built and tested and supported with maintenance contracts. Or to put it another way data is always snowflake. RDBMS's are a great tool for handling snowflakes. And reasoning about them. Of course I might be wrong about the particulars of your use case and in any organization there's NIH and politics. And maybe an RDBMS was where you started, etc. etc. It's a brownfield project.