[HN Gopher] Ask HN: Fast data structures for disjoint intervals?
___________________________________________________________________
Ask HN: Fast data structures for disjoint intervals?
Over the years I've worked on a few applications that needed to
model time intervals that are disjoint. For example, there's some
kind of equipment available and time slots are booked out. For a
data structure to represent this, you generally need to be able to
insert, remove, and perform range queries (i.e., looking for the
next availability). In the past I've represented these with some
kind of ordered map or tree. In Rust this might look something like
`BTreeMap<u32, 32>` with start being the key and the end being the
value. This works really well in practice, but it's not as fast I'd
like for some real-time applications for really read-heavy range
queries with thousands of intervals. A lot of the specialized
interval libraries I've found don't seem to perform better than a
plain ordered map like I mentioned (many use an ordered map
internally anyway). Many of these also weren't designed with cache-
efficiency or SIMD in mind and spend a lot of time on tree
(pointer) traversal. I spent some time prototyping with some other
data structures that might fit (adaptive radix trees to take
advantage of the small integer key, dense bitsets for small ranges,
applying a spatial index in 1-dimension, fixed grid hierarchies)
but haven't been able to find anything much faster than an ordered
map. I was wondering if anyone has come across any interesting
data structures that handle this well. Approaches that use a
combination of multiple data structures to accelerate reads at the
cost of slightly slower inserts/removals could be interesting.
Author : grovesNL
Score : 37 points
Date : 2024-07-18 23:53 UTC (4 days ago)
| pizza wrote:
| Would this help?
| https://en.wikipedia.org/wiki/Allen%27s_interval_algebra
| grovesNL wrote:
| It seems like a good way to describe a common language around
| interval operations. I'd be interested in data structures that
| were specialized for some of these operations.
| brudgers wrote:
| [Vague response that probably misses the mark]
|
| Your description of the problem smells a bit like job-shop
| scheduling. Optimizing job-shop scheduling is NP-Hard, so at best
| one general purpose algorithm might be better than another, but
| you can't determine which by simple inspection. Efficiency will
| vary based on the actual details of your data.
|
| The standard approach (after managing IO) is to tune for the
| regularities in your data. Regularities are what makes your
| arbitrary data arbitrary data and not random values. Tuning the
| algorithm can get you a long way in the time domain. No data
| structure alone can get you out of NP. Good luck.
| grovesNL wrote:
| 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.
| brudgers wrote:
| 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 wrote:
| > _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.
| davidcuddeback wrote:
| 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.
| grovesNL wrote:
| 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.
| davidcuddeback wrote:
| 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.
| jgraettinger1 wrote:
| The first place I'd look is using binary search over a sorted
| `Vec<(u32, u32)>`. The `superslice` crate is handy for this, or
| just using the built-in binary search methods.
|
| The improved cache behavior alone can make an order-of-magnitude
| difference. The cost you pay, of course, is on inserts and
| removals, but perhaps these can be ammortized in a read-heavy
| workload (build up a list of changes, and then rebuild in one
| go).
| grovesNL wrote:
| Thanks, I had a similar idea and tried this with Meta's
| `sorted_vector_map`
| (https://github.com/facebookexperimental/rust-
| shed/tree/main/...) but found the performance to be slightly
| worse than a `BTreeMap<u32, u32>` for my test case. I did try
| to change it a bit to do fewer binary searches (`range` tried
| to find the end immediately) but the binary searches seemed to
| be slightly worse than finding starting intervals in the map.
| neutrinobro wrote:
| In the past for this sort of thing I've used an interval tree
|
| https://en.wikipedia.org/wiki/Interval_tree
|
| However, that was mainly for the case where I needed to detect
| overlapping intervals. Depending on your application perhaps a
| K-d tree, in this case, K=2 (one dimension for start-time the
| other for the end-time)? If you know that all you intervals are
| entirely disjoint (no overlap at all) I don't think you'll be
| able to do better than just an ordered map or list.
| Roguelazer wrote:
| This is the same problem as `malloc`, right?
|
| I imagine the answer depends on exactly what queries you need. If
| you have a bunch of different standard event sizes, then managing
| multiple different sorted freelists for the next open 1 hour
| slot, the next open 3 hour slot, etc might work. If you need high
| concurrency and "next available slot" is allowed to be fuzzy,
| then managing four distinct "event heaps" and parallelizing
| across them might work.
| grovesNL wrote:
| There are definitely a lot of similarities. I spent some time
| reviewing allocator designs to see if some ideas might carry
| over.
|
| One problem I found is that a lot of allocators benefit from
| being able to track freelists based on some minimum sizes
| needed for allocations (e.g.,
| https://github.com/sebbbi/OffsetAllocator). This problem is a
| bit different in that I want to know the first available block
| even though it might be much bigger than I need. Having
| multiple lists might still be useful though, but it's not as
| effective as how they're used in allocators - you'd usually
| need to search multiple freelists to know the first available
| instead of one.
| hyperpape wrote:
| What if you structure the "lists" so that each "freelist"
| contains all slots >= 2^n units of time? Then you only ever
| need to search the list that's the next size down from your
| target slot?
|
| This will be bad for write performance, but solves the
| problem of needing to do multiple searches to find the next
| available slot, and you mentioned that you might not mind
| sacrificing write performance.
| grovesNL wrote:
| That's definitely possible and could be a reasonable
| tradeoff. I'd be slightly worried about the extent that it
| sacrifices write performance, but it might not be too bad
| if if the number of levels are kept small.
| chc4 wrote:
| LMDB uses https://git.burd.me/greg/sparsemap for storing
| compressed ranges of bitmaps for their page allocator, similar to
| RoaringBitmap or Linux's fdarray, which might be applicable here.
| With compressed bitmaps finding the next free is cheap. If your
| ranges are very sparse then it will have bad performance, however
| grovesNL wrote:
| Thanks for the suggestion! I tried dense bitsets in an earlier
| iteration but the performance wasn't great, so I thought
| something like RoaringBitmap probably wouldn't work out very
| well. The ranges are relatively dense but there also aren't
| that many of them (only a few thousand or so), so the bitset
| seemed to spend a huge amount of time searching within
| elements.
| chc4 wrote:
| This sparsemap uses essentially run-length encoding so it
| might still have slightly better performance. I think
| RoaringBitmap only uses the list of set bits below <1024
| before it uses the compressed representation which you'd be
| over, and then having to do the compressed scan.
| josephg wrote:
| I've run into a similar problem in collaborative text editing. I
| assign an integer to each edit (which is a single character
| insert or delete). But obviously, humans usually type characters
| and delete characters in runs. I needed a fast associative map
| from edit id (integer) to some associated data. But the
| associated data is internally run length encoded so that I can
| assign a single value to an entire sequential run of edit
| operations. For example, set(10..20, X), set(12..15, Y) gives a
| map with 3 values: {10..12: X, 12..15: Y, 15..20: X}. I can do
| lookups by querying individual values, and the query returns the
| maximum run containing a consistent value.
|
| I'm not sure how applicable my solution is to your problem, but
| it might work well. I implemented a custom btree with the
| semantics I needed, since btrees are fast and have great cache
| locality. The trick is making one that understands ranges, not
| just singular keys like std BtreeMap.
|
| The code is here if you're curious. It's implemented on top of a
| pair of vecs - which makes it 100% safe rust, and curiously
| faster than the equivalent tree-of-raw-allocations approach.
| Please forgive the poor documentation - it's an internal only
| type and the code is new enough that the paint hasn't dried yet.
|
| https://github.com/josephg/diamond-types/blob/master/src/ost...
| grovesNL wrote:
| Thanks, I'll take a look! It sounds like they're similar
| problems.
| hackermailman wrote:
| Erik Demaine's DS class has a bunch of range trees and cascading
| method to speed up queries
| https://courses.csail.mit.edu/6.851/spring21/lectures/
| alex5207 wrote:
| His explanations are great and just wanted to +1 on the idea of
| range trees. Adding a reference here to a very lightweight read
| on range trees:
|
| https://courses.csail.mit.edu/6.851/spring10/scribe/lec03.pd...
| grovesNL wrote:
| Thanks, I came across some of Erik's videos in my research but
| I didn't realize they were part of a bigger series focused on
| ranges. Cascading methods are exactly the kind of ideas I'm
| thinking about.
| quadrature wrote:
| >dense bitsets for small ranges
|
| Have you tried roaring bitmaps?, it will internally use either a
| sparse or dense representation based on the bits set and uses
| SIMD for all its operations.
| grovesNL wrote:
| I haven't tried roaring bitmaps on this problem yet. I think
| it's generally fairly dense so that's why I tried dense bitsets
| first, but it's a fair point. It might still be beneficial to
| go with a sparse representation depending on the interval
| lengths for example.
|
| I also didn't have a good way to measure runs from roaring
| bitmap's Rust API (https://github.com/RoaringBitmap/roaring-
| rs/issues/274) which makes it hard to track interval duration,
| but would be interested to compare this approach.
| namibj wrote:
| "range query" is different from "find next availability".
|
| Do consider to explicitly use 16(-ish) bit pointers instead of
| native sized ones, and go for a SIMD-friendly binary trie; with
| some degree of implicitnes where it is addressed as if it was
| storing a set of mutually prefix-free variable-length (capped to
| something though, like 32 in your example) bitstrings (no entry
| is a prefix of another entry), but you're not looking to
| distinguish `{00, 01}` from `{0}`.
|
| Operations are restricted, but it should be able to be very fast
| for "find first empty of at least X large starting at or after Y"
| as well as "clear from X to Y inclusive" and "add/mark from X to
| Y inclusive".
| grovesNL wrote:
| I think this is an interesting idea. It might have some of the
| same problems as the dense bitset designs I've tried so far
| though but I'd like to try it out. Is there a detailed
| description of this anywhere?
| kfrzcode wrote:
| Could you separate out the data structure, i.e. keep your
| BTreeMap<u32, u32> for intervals, but add a Vec<u32> for
| available slots. Update both on insert/remove, then for range
| queries use the Vec<u32>?
|
| Sorry if this is dumb I'm a> not a rustian and b> not really
| a computer scientist lol
| grovesNL wrote:
| Definitely possible! I tried doing something similar which
| stored the ranges in a single `Vec<(u32, u32)>` but found
| the performance a bit worse than just using the ordered
| map.
| shiandow wrote:
| You can come up with all kinds of fancy stuff, but if they're
| disjoint I don't think you're going to to much better than
| storing them in an efficient data structure for ordered data.
|
| Something to look into would be to ensure that the _starts_ of
| intervals are sorted after the _ends_ of intervals if they happen
| to be at the same time. If you got that then the starts and ends
| of intervals simply alternate and most queries easily translate
| to one or two lookups.
| blt wrote:
| Totally agree with other comments that a sorted array will be
| hard to beat. I don't see how binary search could help with the
| "look for the next availability" query, but even a linear search
| could be fast on a strong CPU with cache prefetching, out-of-
| order execution, etc.
|
| A few thousand elements is still small for a computer. I would be
| curious to see a benchmark comparing sorted arrays of intervals
| against the fancier structures.
| grovesNL wrote:
| I did some simple benchmarks of a `Vec<(u32, u32)>` to a
| `BTreeMap<u32, u32>` for the test case and found them to be
| roughly comparable. The intervals are relatively dense so I was
| hoping for the vector to perform better than it did.
|
| The binary search was useful to find the start position if
| there are more than a few hundred elements or so (whatever the
| breakeven point for linear search vs. binary search is on your
| CPU).
| jgautsch wrote:
| Interval trees or ordered segment sets are the "correct" answer
| but sometimes you can accept constraints in your domain that
| radically simplify- for example, with equipment availability and
| time slots, you may have a fixed window and allow for slots to
| only fall on 5 minute marks. With those 2 constraints in place, a
| simple bitmask becomes a viable way to represent a schedule. Each
| bit represents 5 minutes, and 1=avail 0=unavail
| grovesNL wrote:
| I tried a bitmask/bitset/bitvec but found the performance of
| searches to be a worse than the ordered map I'm using.
| Intuitively I expected it to perform slightly better for
| searches because of the cache efficiency, but I guess the way
| my ranges were distributed made it spend a lot of time
| searching within each element of the set. I'd like to revisit
| it eventually though because I think this direction is
| promising.
| ashf023 wrote:
| A few rough ideas for bitsets:
|
| - To find runs of 15+ 1s you can find bytes with the value
| 255 using SIMD eq
|
| - For windows of width N you could AND the bitmap with itself
| shifted by N to find spots where there's an opening at index
| i AND index i+N, then check that those openings are actually
| contiguous
|
| - You can use count-trailing-zeros (generally very fast on
| modern CPUs) to quickly find the positions of set bits. For
| more than 1 searched bit in a word, you can do x = x & (x-1)
| to unset the last bit and find the next one. This would
| require you search for 1's and keep the bitmap reversed. You
| can of course skip any words that are fully 0.
|
| - In general, bitmaps let you use a bunch of bit hacks like
| in https://graphics.stanford.edu/~seander/bithacks.html
| grovesNL wrote:
| Thanks for the ideas! I did try lzcnt/tzcnt with bitshifts
| to find contiguous intervals across elements, but I found
| that it tended to be more expensive than searching the map
| depending on the density. I think it's a really promising
| approach though, and I've like to figure out a way to make
| it work better for my test case.
| ashf023 wrote:
| Gotcha. I wasn't quite sure from your post, are you
| storing free slots in the map, or booked slots? And do
| you know, for the cases that aren't fast enough, how much
| they tend to search through? Like are there just a ton of
| bookings before the first free slot, or are the slow
| cases maybe trying to find very wide slots that are just
| hard to find?
| grovesNL wrote:
| I'm storing free slots right now, but either would be ok
| if a data structure would benefit from the other
| representation.
|
| The slow cases usually tend to be trying to find wider
| slots and skipping through many smaller slots. There are
| often a lot of bookings up to the first wide enough slot
| too though, so it's a little bit of both.
| ashf023 wrote:
| Maybe an additional "lower resolution" index on top of
| the map could help as a heuristic to skip whole regions,
| then using the map to double check possible matches. I
| have a rough idea that I think could possibly work:
|
| Maintain the sum of booked time within each coarser time
| bucket, e.g. 1 hour or something (ideally a power of two
| though so you can use shifts to find the index for a
| timestamp), and keep that in a flat array. If you're
| looking for a slot that's less than 2x the coarser
| interval here, e.g. a 90-minute one, look for look for
| two consecutive buckets with a combined sum <= 30
| minutes. 2 hours or more is guaranteed to fully overlap a
| 1 hour bucket, so look for completely empty buckets, etc.
| These scans can be done with SIMD.
|
| When candidate buckets are found, use the start timestamp
| of the bucket (i*1hr) to jump into map and start scanning
| the map there, up to the end of the possible range of
| buckets. The index can confidently skip too full regions
| but doesn't guarantee there's a contiguous slot of the
| right size. I don't have a great sense of how much this
| would filter out in practice, but maybe there's some
| tuning of the parameters here that works for your case.
|
| Updates should be relatively cheap since the ranges don't
| overlap, just +/- the duration of each booking
| added/removed. But it would have to deal with bookings
| that overlap multiple buckets. But, the logic is just
| arithmetic on newly inserted/deleted values which are
| already in registers at least, rather than scanning parts
| of the map, e.g. if you wanted to maintain the min/max
| value in each bucket and support deletes.
| antimatter15 wrote:
| Maybe look into implicit in-order forests
| (https://thume.ca/2021/03/14/iforests/)
| ajfriend wrote:
| This DuckDB blog post on range joins might be relevant:
| https://duckdb.org/2022/05/27/iejoin.html
| magicalhippo wrote:
| Not my area at all, but having done some work on ray-tracing back
| in the days, it kinda reminded me of the ray-triangle
| acceleration structures there[1], except your entities are 1-D
| lines rather than 3-D triangles.
|
| One which came to mind which possibly might be interesting would
| be the Bounding Interval Hierarchy[2], where you partition the
| space but also keep the min/max intervals of all children in each
| node. The "Instant ray tracing" paper[3] details some interesting
| techniques for speeding up construction.
|
| Or perhaps it's a rubbish idea, haven't really thought it
| through.
|
| [1]: https://en.wikipedia.org/wiki/Binary_space_partitioning
|
| [2]: https://en.wikipedia.org/wiki/Bounding_interval_hierarchy
|
| [3]: http://ainc.de/Research/BIH.pdf
| grovesNL wrote:
| Definitely! It's a great idea and something I've been trying
| out. So far I've tested typical bounding volume hierarchies and
| spatial acceleration structures in 1-d (e.g, some of the cache
| friendly quadtree designs applied to 1d, r-trees, k-d trees)
| but they weren't able to outperform my simple ordered map yet
| unfortunately.
| magicalhippo wrote:
| Since you mentioned SIMD acceleration, did you look at things
| like QBVH[1]? I mean it would be kinda like a B-tree I
| suppose but with the min/max stuff.
|
| [1]: https://jo.dreggn.org/home/2008_qbvh.pdf
| grovesNL wrote:
| I did look at QBVH and flattening it to a single dimension,
| but my understanding is that most specialized BVHs like
| this prefer mostly static geometry because updates are so
| expensive. I'd be happy to be wrong on this though - QBVH
| looked complicated enough that I didn't want to experiment
| with it without some strong signals that it would be the
| right direction.
| magicalhippo wrote:
| Fair point. They mention they do a regular construction
| and then reduce it to the QBVH, so was wondering if the
| BIH approximate sort trick could be used effectively.
|
| Again not put a lot of though into it.
|
| Sounds like a fun challenge though.
| sriram_malhar wrote:
| How about hierarchical timing wheels?
|
| "Hashed and Hierarchical Timing Wheels: Data Structures for the
| Efficient Implementation of a Timer Facility" by George Varghese
| and Tony Lauck
|
| http://www.cs.columbia.edu/~nahum/w6998/papers/sosp87-timing...
| iroddis wrote:
| You mentioned that the intervals are disjoint, but are they
| adjacent? I've had success with maintaining a "coalescing
| interval set" structure, where adjacent intervals are merged into
| a single interval. It's very, very efficient for lookups, and not
| terrible for insertion / removal of intervals. At the very least
| it might work as a view for your read-heavy processes.
|
| You mentioned shop scheduling below as well. If your intervals
| represent booked time, you could also insert 'unavailable' time
| into the coalesced set, so that, when fully booked, the interval
| set is reduced to a single interval.
| grovesNL wrote:
| Exactly, intervals are disjoint and adjacent (automatically
| coalesced). The ordered map I'm using will coalesce them
| together which works pretty well. The problem is that I'd like
| to accelerate range queries even further, probably by excluding
| certain intervals with some acceleration structure on the side
| (e.g., skip any intervals with a duration less than X) at the
| cost of slightly more expensive updates.
| iroddis wrote:
| Can you give any more details about the range queries? e.g.
| are you interested in finding any gap of at least duration X,
| or the number of bookings in a date range?
|
| Put another way, are you more interested in what's been
| consumed, or what's free?
| grovesNL wrote:
| I'm interested in both, but quickly finding the nearest
| gaps of at least duration X is most important.
| iroddis wrote:
| There are so many nuances here, but perhaps you could
| maintain two coalescing structures: what's free and
| what's used, complements one one another. Adding to one
| means removing from the other. One might give you a more
| constrained search space than the other.
|
| An ordered structure feels like the way to go, here,
| since you said "nearest gaps". Once you know the time
| you'll get locality in your search. You could also run
| the search in both directions on two threads.
| davidcuddeback wrote:
| "Nearest gap" doesn't sounds like a range query to me. It
| sounds more like a nearest neighbor query. It sounds like
| you have _(start time, duration)_ tuples and want to
| search for nearest neighbor on start time with an at-
| least-X constraint on duration. _(start time, duration)_
| is more point-like than interval-like (as far as data
| structures go), so anything that can handle nearest
| neighbor on point-like data would be a candidate. If this
| is an accurate mapping for your problem, you might check
| out KD trees. You 'd probably have to write a custom tree
| traversal algorithm to query NN on one dimension and >X
| on the other, but I think it could be done. Sounds kinda
| fun.
| grovesNL wrote:
| I have (start time, duration) tuples but would like to
| find the nearest entries (in either direction) given a
| specific time and minimum duration.
|
| Thanks for the suggestion! I've tried some other spatial
| acceleration structures (e.g., R-tree and some others)
| and applying them in 1-d but they didn't outperform the
| ordered map unfortunately. It could be interesting to try
| out KD trees at some point though.
| davidcuddeback wrote:
| 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!
| emmanueloga_ wrote:
| I think OR-Tools uses a sorted `std::vector` for this in
| `SortedDisjointIntervalList` [1] (if I get your description of
| the problem right).
|
| --
|
| 1: https://or-
| tools.github.io/docs/cpp/classoperations__researc...
| grovesNL wrote:
| Interesting, thanks! It makes sense that OR-Tools would have
| something similar. I wonder if they have an explanation behind
| using `std::vector` vs. some other data structures. I could
| imagine `std::vector` doing pretty well but in practice I found
| vectors (Rust's `Vec` in my case) to be roughly on par with the
| ordered map I'm using. Obviously it can vary depending on how
| widely it has to binary search.
| hyperpape wrote:
| A comment that's orthogonal to the datastructure you're choosing,
| but do you really need u32?
|
| If you need second level precision for scheduling, you probably
| do, but a u16 will cover a 45 day range with minute level
| precision.
| phkahler wrote:
| I'll explain what my preferred 3D method would look like
| collapsed to 1D. This was originally for octtrees.
|
| Make a binary tree where node sizes are powers of 2. I'm assuming
| you can define some "zero" time. To add an interval, first check
| if it exceeds the tree size and if so, double the size of the
| tree until it fits inside. Doubling involves making a new root
| node and inserting the existing tree under it (this was extra fun
| in 3D). Then decide what node size your interval should reside
| in. I would use the first power of 2 less than or equal to the
| interval size. Then insert that interval into all nodes of that
| determined size. Yes, I allow more than one object in a node, as
| well as allowing smaller nodes under one containing an object. An
| object may also span more than one node. In other words the
| objects (intervals) determine their own position in this tree
| regardless of others in the tree. It's not perfectly optimal but
| it allows inserts and deletes in O(logN) as well as intersection
| checks.
|
| If this sounds not too terrible for the 1D case, I can elaborate
| on the data structure a bit.
|
| Edit: From another comment "quickly finding the nearest gaps of
| at least duration X is most important." That possibly invalidates
| this whole approach.
| grovesNL wrote:
| Thanks! This sounds very similar to the experiment I tried with
| sieve-tree (https://github.com/Ralith/sieve-tree/) which can
| store children directly on a node until it reaches some
| threshold. I had some problems with the nearest query as you
| mentioned, because children are in arbitrary order and you
| might have to search multiple tree levels to find the nearest.
| GistNoesis wrote:
| You can probably recast your problem into a 1D multiple particle
| collisions problem.
|
| Each interval is represented by a particle of radius half the
| interval, positioned at the middle of the interval.
|
| Because the radius vary, you can either use adaptive algorithm,
| or split the interval into multiple small particles.
|
| There is not a lot to gain when doing a single query, but when
| you are batching queries, you can share the computation and
| memory accesses. Using radix sort for sorting the integers you
| get a complexity for iterating over all collisions of O( NbKeys +
| NbQueries + NbCollisions ).
| mikewarot wrote:
| I'd recommend a combination of data structures.
|
| 1st - Put all the actual data in a sorted / linked list. Keep
| this updated as you always have
|
| 2nd - As a separate thread, Keep an ordered set of lists, each
| list matching a time in the past, present, future, with
| increasing increments as you move from the present. Each of those
| lists can be all the items available at that time. The past is
| for reporting on old events, etc. -365 days
| -180 days -90 days -45 days -30 days -29
| days... -1 day -23 hours... -1 hour NOW
| +1 hour... +23 hours +1 day... +30 days +45, 90,
| 180, 365 days
|
| In each of those lists, have pointers to all the relevant records
| in the main list.
|
| If there's a pointer error, scan the whole list, the slow but
| reliable way.
| anonymoushn wrote:
| If BTreeMap is insufficient, and you're talking about cache-
| efficiency or SIMD, you probably can't use anything off-the-
| shelf. To design the right thing for your use case, it would help
| to know more about your workload.
|
| BTreeMap should be nearly optimal, up to fiddling with the
| layout, changing the number of entries stored in one node, and
| vectorizing your within-node query function.
|
| For people who need to store sorted sparse records and have
| memory to spare, or who know the keys of their sorted sparse
| records take on few values (like only a few million?), they can
| use a robinhood hash table without any hash function. The whole
| thing may not fit in a relevant cache, but you generally won't
| hit more than 1 cache line for the types of queries described.
| Again, I can't really recommend a library, but it's pretty easy
| to write this yourself.
|
| Edit: Here's a link to one robinhood hash table:
| https://github.com/dendibakh/perf-challenge6/blob/Solution_R...
___________________________________________________________________
(page generated 2024-07-23 23:05 UTC)