41 ms·

Ask HN: What are some cool but obscure data structures you know about?

• m463 4y ago
  patricia trees They are particularly interesting for storing long strings. You can look up all strings with a common prefix quite easily. the lookup function is really interesting, just check the first differing bit.
• jordanmorgan10 4y ago
  So it’s not snazzy, but I also wrote Objective-C a long time without knowing about NSPointerArray. Among other things, it can store nil values, which if you’ve written any Cocoa apps, is an all too common way to crash your software.
• Dowwie 4y ago
  Slotmap seems like a superior data structure to adjacency lists backed by Vec, but still haven't replaced them in graph libraries: https://docs.rs/slotmap/latest/slotmap/ https://docs.rs/slotmap/latest/slotmap/
• valbaca 4y ago
  FYI: https://en.wikipedia.org/wiki/List_of_data_structures https://en.wikipedia.org/wiki/List_of_data_structures
• sgtnoodle 4y ago
  Monotonic stacks are neat. I made up a data structure once, consisting of a pyramid of deques. It lets you efficiently compute any associative function over a streaming window of data.
  • jacamera 4y ago
    I recently learned about monotonic stacks thanks to this LeetCode problem: https://leetcode.com/problems/sum-of-total-strength-of-wizards/ https://leetcode.com/problems/sum-of-total-strength-of-wizar... I feel like they're quite possibly the most deceptively simple data structure I've yet to encounter. That is to say that for me at least there was/is a wide gulf between simply understanding what the data structure is (doesn't get much simpler than a stack!) and when/how to actually apply it.
    • sgtnoodle 4y ago
      Do folk genuinely get asked problems like that in technical interviews these days? I can't think of any plausible reason why anyone would want to do a calculation as contrived as that. I love the required modulo value too. I assume the trick is to somehow leverage the distributive property of multiplication to refactor the data to no longer require as much iteration? Is there supposed to be a linear time solution?
      • jacamera 4y ago
        > Do folk genuinely get asked problems like that in technical interviews these days? No idea! I'm still in interview prep mode though so I'm doing the LeetCode contests every weekend. Even if practicing problems like these is over-preparing I think it's probably a good idea for me because I imagine I'll be much more nervous and less performant during an actual live interview. > Is there supposed to be a linear time solution? Yes! Using a monotonic stack to find the "pivot points" of the contiguous subarray groups as well as both a prefix-sum array and prefix-product array to calculate the sum of all subarrays in each group in O(1) time after initially building the arrays in linear time. There are some great explanations in the discussion section. This is one of the few problems that I got stuck on and wasn't able to solve on my own after a couple days of trying. The LeetCode community is awesome though and getting to see how other people solved the problem is a great educational resource.
• petethepig 4y ago
  Tries (or prefix trees). We use them a lot at Pyroscope for compressing strings that have common prefixes. They are also used in databases (e.g indexes in Mongo) or file formats (e.g debug symbols in macOS/iOS Mach-O format are compressed using tries). We have an article with some animations that illustrate the concept in case anyone's interested [0]. [0] https://github.com/pyroscope-io/pyroscope/blob/main/docs/storage-design.md https://github.com/pyroscope-io/pyroscope/blob/main/docs/sto...
  • NSMutableSet 4y ago
    I wouldn't consider tries to be obscure tbh. They are the recommended solution for many leetcode-style interview problems involving string searching. I think anyone who has done serious interview prep has encountered them. https://leetcode.com/discuss/general-discussion/931977/beginner-friendly-guide-to-trie-tutorial-practice-problems https://leetcode.com/discuss/general-discussion/931977/begin...
    • OJFord 4y ago
      The starting example was Bloom filters.
      • NSMutableSet 4y ago
        I'm not sure what the point of your post is. While bloom filters are heavily used in actual production code throughout the industry, it is very rare for anyone to need to code their own, or make changes to a prior legacy implementation. Not all educational programs will cover bloom filters, and for those that do, there's no guarantee that the students will retain the information, and be able to recall it. I don't know of any common interview question patterns where a bloom filter would be the only optimal solution. If it does share optimality with any other data structures, you would be better off choosing something else unless you are extremely confident in your ability to implement one and explain it clearly and in-depth, since the odds of your interviewer not being familiar with them are high in comparison to other solutions. I only know what a bloom filter is because of HN, and previous submissions like this one that have made it to the front page throughout the years. It's nowhere near as common knowledge as tries, especially if you are sampling younger cohorts.
• llimos 4y ago
  The Israeli queue. Like a regular queue, but if something new that comes in sees its friend in the queue already, it can jump the queue and go and stand next to her. Useful for when something has a big overhead on top of its own processing, but the overhead can be shared between several similar entries. If you're doing it anyway for the one already in the queue, you get to make the most of it for its friends too. I chose it because I live here and it's totally true :)
  • kgeist 4y ago
    Sounds like a priority queue
    • vosper 4y ago
      Is it the same thing? I'm trying to imagine how this would work with a priority queue. I think you need an flexible number of priorities that is equal to the queue length, and the priority values come from an infinite counter that only goes up. Higher values = lower priority. When a unique item comes into the queue you increment the counter and give it that value as a priority. This puts it on the end of the queue. But if the new item is a duplicate of an existing item then you give it the priority of the existing item.
    • deleted 4y ago
      [deleted]
    • Tmpod 4y ago
      Not really. In a priority queue, an item with higher priority gets pulled out before one with lower priority, so you can have items that skip parts of the queue (or all of it) even if there are no items of the same priority in there already. This structure seems to behave differently, in that an item may skip ahead in the queue if and only if another item with some matching characteristic is already contained. This makes it so you can never skip the whole structure, for example, assuming you get put after your "friend".
  • abirch 4y ago
    How do you implement it? Do you do a scan with every insert or do you hash or use a tree for indexing?
• kaymanb 4y ago
  Disjoint-Sets have a very cool implementation whose amortized time complexity is extremely slow growing. It is not quite constant, but even for a disjoint-set with as many elements as there are particles in the universe, the amortized cost of an operation will be less than or equal to 4. https://en.wikipedia.org/wiki/Disjoint-set_data_structure https://en.wikipedia.org/wiki/Disjoint-set_data_structure
  • EnderShadow8 4y ago
    I've been told to consider it constant for all practical purposes
    • pjscott 4y ago
      The inverse Ackermann function is one of the slowest-growing functions that you’re ever likely to encounter in the wild. To say that it’s “constant for all practical purposes” is 100% true but doesn’t do justice to how amazingly slow this function is to grow. https://en.m.wikipedia.org/wiki/Ackermann_function https://en.m.wikipedia.org/wiki/Ackermann_function
  • andreareina 4y ago
    Use the idea[1] at work to make large NP-complete problems more tractable by breaking the problem up into disjoint subsets. [1] doesn't implement the inverse-ackermann algorithm but still implemented as union/find.
  • kragen 4y ago
    aka "union find" — some other comments in the thread call it that
• didip 4y ago
  Do you know about: * HyperLogLog? Convenient for doing approximate counting across huge datasets. * SkipList is another probabilistic data structure that allows you to skip ahead N elements in 1 step. I believe ClickHouse uses it. * Bitmap index organizes database pointers into a matrix of bits. The bitmap scans simply skip over the zeros. This type of index gets in trouble if you have high cardinality, though.
  • pjscott 4y ago
    Lots of companies use skiplists without realizing it because Redis uses them as the implementation of sorted sets. For example, last time I checked, every time someone looks at a playlist on PornHub the software is doing a partial traversal of a skiplist behind the scenes.
• mamcx 4y ago
  I made https://github.com/mamcx/tree-flat https://github.com/mamcx/tree-flat as flattened stored tree in pre-order that allows for very fast iterations even for childs/parent queries. Is based on APL, so not that novel. I also like a lot the relational model, is not that much represented so I making a language on top of it: https://tablam.org https://tablam.org.
  • leeoniya 4y ago
    https://en.m.wikipedia.org/wiki/Nested_set_model https://en.m.wikipedia.org/wiki/Nested_set_model ?
    • mamcx 4y ago
      Yeah, that one is good, but I bet is possible to encode trees efficiently as relations without indirections. That is part of my look at `tree-flat` and I wanna base trees on that for my lang.
  • kragen 4y ago
    Nice! I'm curious to see where you take TablaM. I agree that the relational model is not nearly as well represented as a basis for programming language semantics as one might hope.
• harporoeder 4y ago
  The entire space of probabilistic and sublinear data structures is fascinating. From hyperloglog for high cardinality uniqueness counting, to Cuckoo filters (similar to bloom filters), or Count–min sketch for frequency counting. https://en.wikipedia.org/wiki/Category:Probabilistic_data_structures https://en.wikipedia.org/wiki/Category:Probabilistic_data_st...
• qwerty3344 4y ago
  rope - https://en.wikipedia.org/wiki/Rope_%28data_structure%29 https://en.wikipedia.org/wiki/Rope_%28data_structure%29 skip list - https://en.wikipedia.org/wiki/Skip_list https://en.wikipedia.org/wiki/Skip_list
  • 2OEH8eoCRo0 4y ago
    Never heard of this one until it came up in a google interview. Totally botched it. I couldn't think of any way to do it to their liking that doesn't require a dynamic cast.
• gpestana 4y ago
  Conflict-free replicated data type (CRDT) is super interesting data type (and algorithm), especially when it is implemented for complex data structures like JSON: A JSON CRDT is "[...] an algorithm and formal semantics for a JSON data structure that automatically resolves concurrent modifications such that no updates are lost, and such that all replicas converge towards the same state (a conflict-free replicated datatype or CRDT)." [1]. [1] A Conflict-Free Replicated JSON Datatype (https://arxiv.org/abs/1608.03960 https://arxiv.org/abs/1608.03960) b Martin Kleppmann and Alastair R. Beresford.
• untererdisch 4y ago
  Three of my favorite probabilistic data structures are: Skip Lists, Bloom Filters, and SimHashes.
• anon291 4y ago
  Finger trees allow you to do amazing things. In essence they let you build an index, or multiple indices, for your dataset and then store them in a single structure. When I go from Haskell back to imperative land I find myself greatly missing this ability. Sure I can make multiple hashmaps or trees or whatever but being able to stuff it all in one data structure is amazing. One structure I built with them that is much more difficult with typical structures is a "block list" structure. In this structure each block has a particular width and they're all stacked side by side. I want to perform a query, "which box is at position X". So if my boxes are of widths 7,20,10, then the lookup for 2 yields the first box, the lookup for 12 yields the second, etc. More interestingly, if add a new box between the second and third, the indices covered by the last box is increased. With finger trees you use a sum monoid. This is easy. In other languages you have to roll your own structure either using a list (with o(n) lookup) or a tree with o(log n) lookup, but o(n) inserts (to translate the indices of future blocks) https://andrew.gibiansky.com/blog/haskell/finger-trees/ https://andrew.gibiansky.com/blog/haskell/finger-trees/
  • jacamera 4y ago
    Very interesting! Sounds similar to a segment tree: https://en.wikipedia.org/wiki/Segment_tree https://en.wikipedia.org/wiki/Segment_tree
  • pjscott 4y ago
    You can do this with any tree, finger or otherwise, and the big-O stuff applies as long as the tree is within a constant factor of balanced. For some bizarre reason, though, the concept of caching a monoid in each node doesn’t seem to have spread to the standard libraries of most languages. It’s a pity, since that would be incredibly useful.
  • scott_s 4y ago
    You might enjoy a paper I’m a coauthor on which combines finger trees with B-trees to build a data structure for optimal updates to sliding windows: Optimal and General Out-of-Order Sliding-Window Aggregation, https://www.scott-a-s.com/files/vldb2019_fiba.pdf https://www.scott-a-s.com/files/vldb2019_fiba.pdf Slides from the conference talk: https://www.scott-a-s.com/files/vldb2019_fiba_slides.pdf https://www.scott-a-s.com/files/vldb2019_fiba_slides.pdf
• okennedy 4y ago
  Linked Hash/Tree Maps, simple, but elegant. A Map with its nodes connected in a linked list so you can traverse them in insertion order (and O(n) time). Very useful for window queries over sequential data and other cases where you want FIFO access, but also quick access by a field of the data.
  • H8crilA 4y ago
    You forgot the most important feature over normal hash maps: they offer a deterministic iteration order without incurring the cost of a tree-based ordered map. (If you don't know why this is important then maybe you haven't worked on large systems that undergo rigorous evaluation)
    • ztorkelson 4y ago
      Is (non-)determinism really the right concern here? I’m aware that most hash tables do not have generally predictable iteration orders, but I nevertheless understood them to be deterministic.
      • ilammy 4y ago
        They are deterministic in the sense that provided everything else is the same, iteration order would be the same after each insertion. However, it can change after insertion (if the hash bucket count changes). If the hash function is random-keyed, iteration order would be different for different instances of the hash table even if you insert the same items in the same order. Sometimes you want the order to be consistent every time. Be it insertion order, or some natural order of the items.
      • andyferris 4y ago
        Well, hard/impossible to predict perhaps. Iteration order can depend on the order things were inserted and deleted and may differ from computer to computer (for example in Julia the hash-based dictionary ordering differs between 32 and 64 bit systems, and might change between versions of Julia, etc - you’d see the same thing with C++ unordered maps, etc, etc).
• groby_b 4y ago
  All probabilistic structures are fascinating to me. I'm most enamored with HyperLogLog - estimating the number of distinct elements in extremely large sets of data without having to build a set of seen elements - but the entire field is pretty awesome. The canonical use case for HLL is counting unique visitors. But any large dataset where you only need a good approximation is a valid target :)
  • drinkcocacola 4y ago
    I used to work for a mobile analytics company, and HLL made things SO much easier and fast that at the time we changed all our queries to be based on HLL. At the time, the ability of being able to sum uniques was like black magic, and still to this day I am quite impressed about HyperLogLog.
• contingencies 4y ago
  The LIFO buffer. Also surfaces as the messy desk, the million email inbox, or ten-thousand browser tabs. It really works at progressively sorting frequently accessed items to the top, even accounting for changing or seasonal habits and preferences.
• winrid 4y ago
  Structures good for Geospatial information like rtrees, quadtrees. https://en.m.wikipedia.org/wiki/R-tree https://en.m.wikipedia.org/wiki/R-tree Also concurrent data structures. https://youtu.be/jcqGSehrMGU https://youtu.be/jcqGSehrMGU
  • bragr 4y ago
    I've used quadtrees for some cool stuff I can't really talk about. All the things you think binary trees are good at but with x,y coordinates, or any n-tuple of coordinates as you suggest.
  • winrid 4y ago
    Also LSM trees!
  • TrackerFF 4y ago
    Yes, R-tree turned out to be a godsend when working with larger geospatial data and calculating intersections.
    • winrid 4y ago
      Yep, that's what I used it for! Intersections. Hard to make concurrent though. Ended up with concurrent map backed geohash.
• sairahul82 4y ago
  FST is one underappreciated data structure. Its used in places like speech recognition and synthesis, machine translation, optical character recognition, pattern matching, string processing, machine learning, information extraction. If you know about it you exactly know where to use it.
  • vvrm 4y ago
    +1 if your input and output are both sequences, FSTs can be your best friend…Unless you prefer the company of the flaky cool kids from deep learning (CTC, RNN-T, …)
• binarymax 4y ago
  HNSW, or Hierarchical Navigable Small World is a graph data structure for approximate nearest neighbor search of vectors. https://arxiv.org/abs/1603.09320 https://arxiv.org/abs/1603.09320 The problem space of ANN is one of those really deep holes you can go down. It’s a game of balancing time and space, and it’s got plenty of fascinating algorithms and datastructures. Check out http://ann-benchmarks.com/ http://ann-benchmarks.com/ for a comparison. HNSW is not “the best” but it’s easy to understand and is quite effective.
  • israrkhan 4y ago
    I second this.. very useful for vector NLP and other ML tasks.
• jiggawatts 4y ago
  Cache-Oblivious Data Structures: https://cs.au.dk/~gerth/MassiveData02/notes/demaine.pdf https://cs.au.dk/~gerth/MassiveData02/notes/demaine.pdf A vaguely related notion is that naive analysis of big-O complexity in typical CS texts ignores over the increasing latency/cost of data access as the data size grows. This can't be ignored, no matter how much we would like to hand-wave it away, because physics gets in the way. A way to think about it is that a CPU core is like a central point with "rings" of data arranged around it in a more-or-less a flat plane. The L1 cache is a tiny ring, then L2 is a bit further out physically and has a larger area, then L3 is even bigger and further away, etc... all the way out to permanent storage that's potentially across the building somewhere in a disk array. In essence, as data size 'n' grows, the random access time grows as sqrt(n), because that's the radius of the growing circle with area 'n'. Hence, a lot of algorithms that on paper have identical performance don't in reality, because one of the two may have an extra sqrt(n) factor in there. This is why streaming and array-based data structures and algorithms tend to be faster than random-access, even if the latter is theoretically more efficient. So for example merge join is faster than nested loop join, even though they have the same performance in theory.
  • vvanders 4y ago
    Realtime collision detection[1] has a fantastic chapter in this with some really good practical examples if I remember right. Great book, I used to refer to it as 3D "data structures" book which is very much in theme with this thread. [1] https://www.amazon.com/Real-Time-Collision-Detection-Interactive-Technology/dp/1558607323 https://www.amazon.com/Real-Time-Collision-Detection-Interac...
    • trebcon 4y ago
      The implicit grid data structure from there is a personal favorite of mine. I used it in a game once and it performed incredibly well for our use case. It's a bit too complicated to totally summarize here, but it uses a bit per object in the scene. Then bit-wise operations are used to perform quick set operations on objects. This data structure got me generally interested in algorithms that use bits for set operations. I found the Roaring Bitmap github page has a lot of useful information and references wrt this topic: https://github.com/RoaringBitmap/RoaringBitmap https://github.com/RoaringBitmap/RoaringBitmap
• sebastianconcpt 4y ago
  Good! I got always fascinated by non-boolean indexing (probabilistic instead). I've remember having implemented an OOP indexed version of U.C. Berkeley's Cheshire-II in 2007 with Dolphin Smalltalk. I was using BTrees tho, hence O(log N). The non-boolean part was in the values of the keys which were probability of good match against your search target.
• lizardactivist 4y ago
  The Trie is pretty cool. I think it's a bit obscure because the memory use can grow quite fast.
  • pjscott 4y ago
    That depends very much on how the trie is represented in memory. Something like a burst trie or HAT trie is usually very compact!
• ajjenkins 4y ago
  I recently learned about deques in Python (other languages may have it too) which is like a linked list but it keeps pointers for the first and last elements. This allows you to insert/read/remove elements from the beginning or end of the list in constant time. I’ve never used it, but I could imagine it being useful in certain situations. https://docs.python.org/3/library/collections.html https://docs.python.org/3/library/collections.html
  • sgtnoodle 4y ago
    A deque may be implemented as a linked list, but it's actually more common to be implemented on top of arrays. Python in particular uses arrays under the hood for almost everything because modern computer hardware is so blazingly fast manipulating them.
    • foolswisdom 4y ago
      Arrays aren't efficient when you want to add/remove to the head. Deque in python exists so there is a data structure with constant time pop/push to the head. And it is in fact implemented as a doubly linked list, with various optimizations: https://github.com/python/cpython/blob/v3.8.1/Modules/_collectionsmodule.c#L33-L78 https://github.com/python/cpython/blob/v3.8.1/Modules/_colle....
      • sgtnoodle 4y ago
        Neat, it's always best to look at the source. To be clear, a deque can be implemented on top of an array and still have constant time operations on the head.
        • sicp-enjoyer 4y ago
          If it's not constant time on both ends, it's not a deque. You can already insert items at any index in an array with linear cost.
          • 4y ago
• sgtnoodle 4y ago
  Disruptor queues are also fun. They are lock free multi-producer multi-consumer circular buffers. I figured out the basics on my own in a vacuum out of need, then discovered a relevant white paper. I used one to implement a fast shared memory pub-sub message bus for communicating across dozens of processes in a simulation framework.
  • bmitc 4y ago
    Do you have a link to the white paper you found?
    • sgtnoodle 4y ago
      This doesn't look like I remember, but this sounds right. https://lmax-exchange.github.io/disruptor/disruptor.html#_design_of_the_lmax_disruptor https://lmax-exchange.github.io/disruptor/disruptor.html#_de... The basic idea is that you maintain two atomically incremented counters. You increment one to allocate some buffer space to write your message into, and you increment the other once the message is written in. There's some tricky details to get right when multiple producers have messages staged up at the same time.
      • bmitc 4y ago
        Thank you!
  • xxs 4y ago
    I don't quite see how's that obscure; it's a standard circular buffer. The fast/low latency communication part comes from the busy wait (and L3 cache communication).
    • sgtnoodle 4y ago
      A standard circular buffer is only single-producer single-consumer. The producer manipulates the head and the consumer manipulates the tail. Extending a circular buffer to allow multiple consumers is relatively straight forward; you just give each consumer its own tail and accept the loss of back pressure. Extending it to allow multiple producers without introducing locks is where the complexity shoots up drastically. But yes, the reason why you would want something like this is to have the semantics of message passing with the performance of direct IPC between userspace processes without going through the kernel.
• rockwotj 4y ago
  Interval trees. Really cool trees that allow fast lookups of all the ranges that contain a given point. https://en.wikipedia.org/wiki/Interval_tree https://en.wikipedia.org/wiki/Interval_tree
  • maxFlow 4y ago
    Found out about this DS in AoC 2021 Day 20+ problems if I remember correctly. Pretty interesting.
• glouwbug 4y ago
  Static arrays - when was the last time you used a static array?
  • dahart 4y ago
    What do you mean by “static” exactly? It could be referring to an array that doesn’t change size. Or the contents are read-only. Or do you mean C/C++ static linking? Or something else? In C, C++ and CUDA I use constant fixed-size arrays with lookup tables of specialized data all the time. I also use small arrays to hold temporary results that need to get first collected, and then sorted or processed together. Seems like very common in C++, especially embedded, game, and GPU programming. I’d love to hear about why static arrays seem uncommon in your world.
    • glouwbug 4y ago
      Static arrays as in constant fixed sized arrays. With a static array, O(N) is faster than O(LogN) and even some cases O(1) ahem, hashes when N is small. A contiguous cache is king, and even with modern dynamic languages, the generational GC can even be completely bypassed or highly simplified if the JIT learns that memory access is just dependent on offsets. Simple code runs fast. See Pike on Complexity - Rule 3: https://www.lysator.liu.se/c/pikestyle.html https://www.lysator.liu.se/c/pikestyle.html
  • jhallenworld 4y ago
    I find I use fixed-sized arrays a lot on microcontrollers. You want to avoid the heap (for reliability) and you don't have a lot of RAM, so you must carefully size your fixed-size arrays.
• actually_a_dog 4y ago
  Previously on HN: https://news.ycombinator.com/item?id=1370847 https://news.ycombinator.com/item?id=1370847 (2010) https://news.ycombinator.com/item?id=2363522 https://news.ycombinator.com/item?id=2363522 (2011) https://news.ycombinator.com/item?id=3369454 https://news.ycombinator.com/item?id=3369454 (2011) -- Although not much is in the discussion, it points to a Stack Overflow post with some examples. https://news.ycombinator.com/item?id=7079427 https://news.ycombinator.com/item?id=7079427 (2014) https://news.ycombinator.com/item?id=28758106 https://news.ycombinator.com/item?id=28758106 (2021) -- Not exactly a data structure, but an interesting algorithm.
• kaylynb 4y ago
  Sparse sets. They're often used in Entity Component System architectures since you have O(1) add/remove/find, & O(n) iteration. Iterations are also packed, which is a bonus for cache efficiency. Can be difficult to implement well, but the concept is simple and a neat example of a useful specialty data structure. Take a look at https://github.com/skypjack/entt https://github.com/skypjack/entt
  • hgs3 4y ago
    You can apply the same idea to hash tables: Store hashes and dense-array indices in your sparse array, during lookup use robin hood hashing to cache efficiently probe the sparse array for a matching hash value, and if a match is found use the dense-array indice to lookup the data in the packed/dense array. This approach is both cache efficient and space efficient as the dense array can grow independently of the sparse array.
• RiverBucketShoe 4y ago
  Splay trees: https://en.wikipedia.org/wiki/Splay_tree https://en.wikipedia.org/wiki/Splay_tree recently searched items are always near the top.
  • jonstewart 4y ago
    Nuts! I was going to say splay trees. Completely silly these days, like most trees, given caching hierarchies and bursty memory accesses, but a really neat data structure all the same.
• scottcodie 4y ago
  Reservoir sampling is a statistical technique used to randomly select a finite number of elements from a population. The elements are chosen such that each element has an equal probability of being selected. This technique is often used when it is impractical to select a random sample of elements from a very large population. To do reservoir sampling, you first need to decide how many items you want in your sample. This number is called the size of the reservoir. Once you have the size of the reservoir, you can fill it by selecting items from the population at random. The code is beautifully simple: for i = k to population.length-1 j = random integer between 0 and i, inclusive if j < k reservoir[j] = population[i] return reservoir
  • bhawks 4y ago
    Reservoir sampling is really cool - a slightly optimized version (algorithm L) let's you skip over every record that will not be sampled and it is still pretty simple. If your records are fixed size this can be an awesome speedup. (* S has items to sample, R will contain the result ) ReservoirSample(S[1..n], R[1..k]) // fill the reservoir array for i = 1 to k R[i] := S[i] (* random() generates a uniform (0,1) random number *) W := exp(log(random())/k) while i <= n i := i + floor(log(random())/log(1-W)) + 1 if i <= n (* replace a random item of the reservoir with item i *) R[randomInteger(1,k)] := S[i] // random index between 1 and k, inclusive W := W * exp(log(random())/k) https://en.m.wikipedia.org/wiki/Reservoir_sampling https://en.m.wikipedia.org/wiki/Reservoir_sampling
    • lorenzhs 4y ago
      Indeed! Funny enough, I rewrote that article a few years ago, it previously contained an approximation of something like Algorithm L that some person with a blog came up with, having no idea that an even simpler and provably correct algorithm was published as early as 1994 :) Though others have improved the article a lot since then, adding explanations for how/why it works. Couldn't be happier to see it cited in this list!
  • benou 4y ago
    I was going to mention it too! The really cool thing about reservoir sampling is that it can be done "online" (ie process input incrementally) which makes it super useful when you want to compute statistical properties of something in the field without blowing up your cpu and memory. For example, let's say I have a server serving queries. I want to measure min/max/avg/stdev/99p you name it. You can do it cheaply with reservoir sampling, without having to save all data points.
• EnderShadow8 4y ago
  Treap: https://en.wikipedia.org/wiki/Treap https://en.wikipedia.org/wiki/Treap It's like a Red-Black tree in use case, but much faster to implement, which is good for competitive programming. The average case complexity is the same for all operations, but there's an unlikely degeneration to worst-case linked-list behaviour. Lazy Propagation Segment Tree: https://cp-algorithms.com/data_structures/segment_tree.html https://cp-algorithms.com/data_structures/segment_tree.html Like a segment tree in that it supports range queries in logarithmic time, but supports range updates in log time as well. I know a few more fun ones that I occasionally use in contests, but I've never touched otherwise.
  • cassepipe 4y ago
    Speaking of ease of implementation, I just discovered AA trees. They are probably not "obscure" but I think they are worthy of more fame because they perform jsut as well as red-black trees and are easier to implement. Finding clear comprehensive documentation about them was not easy though, so here is for you, the best I could find : https://www.cs.umd.edu/class/fall2019/cmsc420-0201/Lects/lect06-aa.pdf https://www.cs.umd.edu/class/fall2019/cmsc420-0201/Lects/lec... And the, unhelpful to me, orginal paper : https://user.it.uu.se/~arnea/ps/simp.pdf https://user.it.uu.se/~arnea/ps/simp.pdf
    • kgr 4y ago
      The Wikipedia article on AA-Trees is good: https://en.wikipedia.org/wiki/AA_tree https://en.wikipedia.org/wiki/AA_tree
  • _benedict 4y ago
    The nicest thing about treaps is how easy union/intersection/disjunction are.
• reality_inspctr 4y ago
  Resource Description Framework (RDF) The Resource Description Format (RDF) is the W3C standard for web data. It allows for data the be linked, anywhere, and to be "grounded" in semantic descriptions of the data. The core RDF data model is very simple: It is a set of triples orgainzed into a RDF Graph. https://www.w3.org/egov/wiki/Resource_Description_Format https://www.w3.org/egov/wiki/Resource_Description_Format
• tialaramex 4y ago
  Hazard Pointers are an interesting concurrent data structure. Suppose we've got a lot of Doodads, let's say there's a Graph of ten million Doodads, and a whole bunch (dozens? hundreds?) of threads are poking around in this same graph, maybe looking at Doodads and sometimes (but not often) removing them from the Graph. What happens if my thread is looking at a Doodad, and meanwhile a different thread removes it from the Graph? Is the Doodad destroyed while I was looking at it? That sounds very bad. What if while I'm looking at it, the Doodad is destroyed, but, a nearly identical Doodad appears in its place. How would I know? Not acceptable. We could reference count the Doodads, we'd need atomic reference counts, something like C++ shared_ptr -- but this would work. However now our performance is terrible, because we've got 100 threads increasing and decreasing these reference counts just to look at Doodads and each such change causes a write that must be observed on other threads. So instead Hazard pointers go like this: Every thread who wants to look at Doodads asks for a Hazard Pointer, usually these are never deleted once made because it's much easier. A thread sets this Hazard Pointer to point at a Doodad when it wants to look at one, it checks this was successful (if not the Doodad is gone now), then contemplates the Doodad (it can be in this state for an arbitrarily long period of time) and then it clears the hazard pointer once it is done. It can only point one Hazard Pointer at one Doodad (some schemes allow a thread to have say, two or some finite number of Hazard Pointers each) Somewhere a Linked List of all these hazard pointers is kept. When you want to remove a Doodad, you take it out of the graph, then you check the List of Hazard Pointers. If any of them was pointing at the Doodad you removed, you put the Doodad on a special pile since it can't be deleted yet, otherwise you can delete it immediately because nobody else needs it any more. This is a relatively expensive operation, but you're only doing it for removal, not just reads. Finally there needs to be some mopping up of that pile of "couldn't delete yet" Doodads by trying to delete them again (checking the Hazard Pointers again of course). This can be periodic, it can happen every time somebody tries to delete one, or whatever, the best policy may vary between applications. This approach means reading Doodads costs only two local writes, no waiting around for the cache. Removing them is more expensive, but that's OK because it was rare.
  • jez 4y ago
    Have you used this before? What was the domain?
• dahart 4y ago
  The Suffix Array is surprisingly cool and useful https://en.wikipedia.org/wiki/Suffix_array https://en.wikipedia.org/wiki/Suffix_array The Alias Table for sampling a discrete distribution in O(1) time is a very clever idea https://www.keithschwarz.com/darts-dice-coins/ https://www.keithschwarz.com/darts-dice-coins/
  • dinobones 4y ago
    The fact that suffix trees/suffix arrays can be built in O(n) is IMO the most surprising and "magical" result in computer science. To me, more surprising than median of medians/quick select. There might be more "magical"/surprising things that are obscure and I am unaware of, but to me, this is it. :)
    • adgjlsfhk1 4y ago
      what about randomized O(n) minimum spanning trees?
• zarzavat 4y ago
  Spatial hashing. Say that you have data that is identified with points in 2D or 3D space. The standard way that CS students learn in school to represent this is via a quadtree or octree. However, these tree data structures tend to have a lot of "fluff" (needless allocations and pointer chasing) and need a lot of work to be made efficient. Spatial hashing is the stupidly simple solution of just rounding coordinates to a grid and storing nearby objects together in a hash table. As long as your data is reasonably well behaved then you get many of the advantages of a quadtree, and it's completely trivial to implement.
  • klysm 4y ago
    > reasonably well behaved Curious what this means in this context. No hot spots? Not sparse?
    • evouga 4y ago
      Performance degrades when you get many hash collisions, which will happen if you have a lot of points clumped together in space. Sparsity is fine. For points you expect to be unevenly distributed the more advanced spatial partitioning data structures (kd tree, BVH) perform better.
  • pacaro 4y ago
    TBH even quadkeys are a fun answer to OPs question, many people aren't aware of them. Simple explanation: If you have data with x y coordinates and you know the bounds. To compute the quad key for a point: 1. The key starts as the empty string. (I've also seen it start with "Z" to handle points outside the bounds) 2. Divide the space into 4 quadrants 3. determine which quadrant the point falls in, append a letter (A-D depending on the quadrant) to the key 4. Repeat step 3 using the quadrant bounds (i.e. recursively smaller area) until you have desired accuracy This can then be used to efficiently find points within rectangular bounds.
    • blueblob 4y ago
      From a basic binary search, this is very intuitive. Your explanation was well written.
• ChrisMarshallNY 4y ago
  Ole Begemann and Chris Eidhof wrote Advanced Swift, and, in there, described a really efficient FIFO queue. I implemented a variant of it, in my Generic Swift Toolbox Package[0]. It’s lightning fast. [0] https://github.com/RiftValleySoftware/RVS_Generic_Swift_Toolbox/blob/master/Sources/RVS_Generic_Swift_Toolbox/RVS_Generic_Swift_Toolbox_CollectionTools/RVS_FIFOQueue.swift https://github.com/RiftValleySoftware/RVS_Generic_Swift_Tool...
• b20000 4y ago
  the BroTree. it’s the tree you don’t know about but will inevitably be queried about during a google interview with a googler on a mission to prove supreme smartness.
• jedberg 4y ago
  I saw this and bloom filter was my very first thought, so I'm glad you had it. We used it to check if you had voted on a discussion on reddit. It almost all cases the user had not voted, so it was a lot quicker to check if you hadn't voted than if you had.
• loxias 4y ago
  (Fantastic post idea OP. One of the best I've ever seen :D) Related to bloom filters, xor filters are faster and more memory efficient, but immutable. HyperLogLog is an efficient way to estimate cardinality. Coolest thing I've learned recently was Y-fast trie. If your dataset M is bounded integers (say, the set of all 128 bit numbers), you get membership, predecessor, or successor queries in log log time, not log, like in a normal tree. see: https://www.youtube.com/playlist?list=PLUl4u3cNGP61hsJNdULdudlRL493b-XZf https://www.youtube.com/playlist?list=PLUl4u3cNGP61hsJNdULdu... (6.851 Advanced Data Structures, Erik Demaine) Would love to learn more "stupidly fast at the cost of conceptual complexity" things. edit: (adding) I don't know a name for it, because it's not one thing but a combination, but once can: Use the first N bits from a very quick hash of a key from an unknown distribution (say a file path, or a variable name, or an address, or a binary blob,..) as a way to "shard" this key across M other fast data structures (like a tree) for search/add/remove. By changing M, you can tune the size of the terms in the O(1)+O(log) equation for running time. Trees getting too deep for fast search? Every increase of N moves the computation from the log search of the tree to the space tradeoff of having more trees. Added benefit is you can scale to multiple threads easily. Instead of locking the whole tree, you lock a tiny sub-tree. Very clever. (I first saw in the Aerospike key value store)
  • blueblob 4y ago
    Sounds a bit like radix sort?
    • loxias 4y ago
      AIUI Radix sort "kinda ish" related, yeah :) They both involve looking at your data at a 90 degree angle and slicing on bitplanes.
  • bglazer 4y ago
    I think what you’re describing in the last example is the MinHash algorithm edit: actually I’m not sure, sounds related though
  • champtar 4y ago
    A fantastic thing about HyperLogLog is that it can be merged, so you can split your data between multiple server, precompute HLL for all IPs every minute, and then ask "how many unique IPs was there yesterday". Discovered HLL because it's used in ClickHouse, which employ a ton of cool but obscure data structure.
• andrenotgiant 4y ago
  Can I describe a data queueing problem that I feel like there is a specific data (or queue) structure for, but that I don't know the name is? Let's say you are trying to "synchronize" a secondary data store with a primary data store. Changes in the primary data store are very "bursty", one row will not change for days, then it'll change 300 times in a minute. You are willing to trade a bit of latency (say 10 seconds) to reduce total message throughput. You don't care about capturing every change to the primary, you just want to keep it within 10 seconds. It feels like there should be a clever way to "debounce" an update when another update overrides it 500ms later. I know debounce from the world of front-end UI where you wait a little when doing autocomplete search based on keyboard input so as not to overwhelm the search.
  • nl 4y ago
    If you want everything to be within 10 seconds, then you build a state-change tracker (which only tracks all state changes since last update) and then you send the updates every 10 seconds. Don't worry about debouncing - the state tracker should handle representing the 300 updates as a single state change, and if there are more then they just get sent in the next update 10 seconds later.
  • dabears 4y ago
    Ideally you have a reliable Change Data Capture (CDC) mechanism like a Binlog Reader. Debezium, for example, can write directly to a queue like Kafka. A Kafka consumer picks up the events and writes to your secondary datastore. Something like that can probably handle all of your events without bucketing them, but if you want to cut down the number of messages written to the queue you can add that logic into the Binlog Reader so it emits a burst every 5 seconds or so. During those 5 seconds it buffers the messages in the processes memory or externally in something like Redis using a key so only the latest message is stored for a given record.
  • js2 4y ago
    Sentry used Redis to buffer writes for a similar use case: https://blog.sentry.io/2016/02/23/buffering-sql-writes-with-redis https://blog.sentry.io/2016/02/23/buffering-sql-writes-with-...
• nl 4y ago
  I came here to say Golomb compressed sets except now I see it's part of the question! They are used by default in the OpenMined implementation of Private Set Intersection[1] - a multi-party computation technique. [1] https://github.com/OpenMined/PSI/blob/master/private_set_intersection/javascript/README.md https://github.com/OpenMined/PSI/blob/master/private_set_int...
• mysterydip 4y ago
  Djikstra maps. This page describes it better than I can: http://www.roguebasin.com/index.php/Dijkstra_Maps_Visualized http://www.roguebasin.com/index.php/Dijkstra_Maps_Visualized but it can be a real simple way to add emergent behavior to an AI in a game (my interest in it), among other things.
• JohnDeHope 4y ago
  I always thought the relational calculus was awesome. There’s only one place I’ve seen it in a real world use case, outside of college, and that’s in a database called Suneido.
• Chris_Newton 4y ago
  Piece tables: a persistent data structure used to represent the current document with relatively efficient editing operations in various text editors, word processors, etc. https://en.wikipedia.org/wiki/Piece_table https://en.wikipedia.org/wiki/Piece_table
• silverlake 4y ago
  Most of the data structures posted here are taught in CS classes. Here’s an interesting list of more obscure ones: https://web.stanford.edu/class/cs166/handouts/090%20Suggested%20Project%20Topics.pdf https://web.stanford.edu/class/cs166/handouts/090%20Suggeste...
  • deleted 4y ago
    [deleted]
  • rramadass 4y ago
    This is great! Exactly what this thread is about; everybody should go through this.
  • TristanBall 4y ago
    Not all of us got (cough any) CS degrees though, and while technically the information is all out there for me to find, I wouldn't necessarily have a reason to look, or on those rare occasions where my sysadmin/DBA projects do throw up a problem that one of these algorithms/structures are suited for - I wouldn't know _to_ look, or even how. That's possibly one of the better arguments for doing a CS degree actually, at least for me. But 20 years ago when I might have cared, CS was always advertised as "you'll learn data structures and algorithms" and that's it. ( 20 yr old me: "I know loops and recursion, linked lists, some basic trees and oh look this "perl" thing has hashes, meh I'll be fine" ) If they'd listed out the sort of descriptions I've seen here.. well, I might have had a very different life! So I'm absolutely loving this thread! And thankyou for your link too, added to my list.
• z3t4 4y ago
  A sorted list. It's often cheaper to sort the list after each change, then to search the whole list. Especially when you do collision detection in 3d... (maybe not so obscure, but at least underestimated) When I pair my socks I first place them in color order :)
  • pjscott 4y ago
    Note that re-sorting an array after making a constant number of changes can be done in O(n) and will usually be very fast in practice. Insertion sort will do it, as will Timsort and similar algorithms.
  • jedimastert 4y ago
    I was reading up on C++'s standard library and found out that maps and sets are generally implemented as continually sorted lists
• jhallenworld 4y ago
  Some ones I've used recently: The "golden section search" to find a the minimum (or maximum) of a unimodal function. An actual real-world use case for the golden ratio. Exponentially Weighted Moving Average filters. Or how to have a moving average without saving any data points.. Some of my classic favorites: Skiplists: they are sorted trees, but the algorithms are low complexity which is nice. Boyer-Moore string search is awesome.. Bit twiddling algorithms from Hackers Delight: for example (x &-x) isolates the least significant set bit: basically use the ALU's carry chain to determine priority. Another is compress from Hacker's Delight. It very quickly compresses selected bits (from a bitmask), all to the right of the word. It's useful to make certain hash functions. The humble circular queue. If your circular queue is a power of 2 in size, then the number of bits needed for indexes is at least log2(size) + 1. The + 1 is key- it allows you to distinguish between completely full and completely empty with no effort. So: Empty: (write_index == read_index) Full: (write_index == read_index + size) Count: (write_index - read_index) Insert: queue[write_index++ & (size - 1)] = data Remove: data = queue[read_index++ & (size - 1)]; All lossless data compression algorithms are amazing.
  • chrchang523 4y ago
    Regarding the bit “compress” operation, this is supported in hardware (PEXT instruction) by Haswell and newer processors, though unfortunately most AMD processors have poor implementations. I’ve found it to be quite handy when implementing subsetting operations.
  • jongjong 4y ago
    In case anyone is interested, I wrote a skip list implementation for Node.js here: https://www.npmjs.com/package/proper-skip-list https://www.npmjs.com/package/proper-skip-list I provided the time complexity of each operation as part of the README.
  • vitaminCPP 4y ago
    This is a great selection. Thanks for sharing.
• Blahah 4y ago
  1. Probabilistic filtering and matching: Since you mentioned bloom filters - other probabilistic data structures like count-min sketches (roughly, streaming bloom filters) are super useful. Approximate kmer methods like minhash and w-shingling use them in really cool ways. Rolling hash methods like Rabin chunking also work really nicely with probabilistic/streaming hash tables - splitting the data stream into chunks that can be consistently filtered or matched is useful in many circumstances! Think NSA-level data harvesting, or realtime genome/geospatial data classification. 2. Checking for, locating and counting subsequences in giant string datasets: Wavelet trees, FM-indices, suffix arrays more generally - and structures that allow extreme performance in very niche situations with arbitrary encodings like bitvectors and compressed integer vectors. If you have a million books, or all the genomes ever sequenced, you use the first structures to find where a specific phrase can be found, even if you don't quite spell it right. You can use the latter ones to do super fast comparisons of giant datasets - given a million viruses, how similar is each one to the human genome, and where specifically do they most closely match? 3. Reconstructing structured information from (potentially noisy) fragments: De-brujn graphs (and related graphs like string graphs, colored de brujns). This is a way to find all the overlap connections between fragments of information, and then weight the possible traversals of those connections by the evidence. These can be represented using the data structures from #1 (FM-indices for example), and efficiently used in some circumstances with those from #2 to enable some kinds of graph algorithms. If you have a shredded set of documents, or a billion short DNA reads from a genome sequencing experiment, this is how you reconstruct the original. 4. Decentralised coordination structures. Merkle-DAGs and Kademlia DHTs in particular. Being able to compare any trees by root-first hashes, and being able to request the content of the subtree for any node hash from an arbitrary set of peers - these structures enable the p2p web infrastructure. Everything from Limewire to bittorrent, IPFS and blockchains, and, most importantly, Sci-Hub. 1, 2 and 3 together are some of the fundamentals of computational biology. If you're interested in understanding them, https://rosalind.info/problems/list-view/ https://rosalind.info/problems/list-view/ is a great starting place.
  • dundarious 4y ago
    Funny you should mention bloom filters and that use case, I just re-read this post again this morning: https://blog.cloudflare.com/when-bloom-filters-dont-bloom/ https://blog.cloudflare.com/when-bloom-filters-dont-bloom/ Basically, it makes a similar point to https://news.ycombinator.com/item?id=32186837 https://news.ycombinator.com/item?id=32186837 — i.e., cache effects are not modeled in big O analysis, even though most problems that involve large amounts of data (so most problems) are memory bound rather than CPU bound. The blog post makes a good case for a very simple hash table as a better fit for this problem.
• ImJasonH 4y ago
  Nested Set Model: a way to model nested sets of entities and query them in a SQL database. I haven't used it for anything but it seems fun. https://en.m.wikipedia.org/wiki/Nested_set_model https://en.m.wikipedia.org/wiki/Nested_set_model
  • NicoJuicy 4y ago
    Used it for tag hierarchy, liked it a lot!
• markdown 4y ago
  > I'll start You're supposed to post yours as a comment, so it can be voted on like every other type of structure suggested here.
• didip 4y ago
  Have you heard of Geohash? My mind was blown the first time I learned it. https://en.m.wikipedia.org/wiki/Geohash https://en.m.wikipedia.org/wiki/Geohash
  • centur 4y ago
    This one is my favourite concept, bloom filter goes after that. Cool stuff about Geohash that you can expand it's concept into 3 or more dimensions and whole ide just makes you think a bit differently about coding and operating over small tokens of data. fantastic stuff
• dqpb 4y ago
  Type->Value Lattice https://cuelang.org/docs/concepts/logic/ https://cuelang.org/docs/concepts/logic/
• Loranubi 4y ago
  I am trying to compile a list of data structures (and algorithms and other stuff) into a kind of knowledge base: https://github.com/Dobatymo/data-algos/blob/master/data-structures.md https://github.com/Dobatymo/data-algos/blob/master/data-stru.... There are few cool and obscure data structures already. Please feel free to help extend it!
• nicwolff 4y ago
  The Aho-Corasick automaton [0]. You have a bunch of strings, and you want to know if and where they appear in a longer string. You build a search trie from the strings, but add links back from each node to the node representing the longest suffix of the string it represents that is also in the trie, so you can skip backtracking as you scan, yielding linear time complexity in O(length of string being searched + number of results found). [0] https://en.wikipedia.org/wiki/Aho–Corasick_algorithm https://en.wikipedia.org/wiki/Aho–Corasick_algorithm
  • burntsushi 4y ago
    The aho-corasick Rust crate[1] also provides a way to build the automaton in a slightly different way to provide leftmost first or "preference first" match semantics. This matches how popular backtracking regex engines implement alternations of literals, for example. (It also provides leftmost longest semantics, which matches how POSIX regexes implement alternations.) [1]: https://docs.rs/aho-corasick https://docs.rs/aho-corasick
• ffhhj 4y ago
  Latent Dirichlet Allocation (LDA) structure: "LDA represents documents as mixtures of topics that spit out words with certain probabilities." "LDA assumes that each document in a corpus contains a mix of topics that are found throughout the entire corpus. The topic structure is hidden - we can only observe the documents and words, not the topics themselves. Because the structure is hidden (also known as latent), this method seeks to infer the topic structure given the known words and documents." https://cfss.uchicago.edu/notes/topic-modeling/ https://cfss.uchicago.edu/notes/topic-modeling/ I'm making a next-gen search engine.
• raydiatian 4y ago
  I’ve bookmarked this thread. I have a new reading list! Thanks OP!
• freen 4y ago
  Fountain Codes: reconstruct data from random selection of packets. Was deeply patent encumbered until recently. https://en.m.wikipedia.org/wiki/Fountain_code https://en.m.wikipedia.org/wiki/Fountain_code
  • noman-land 4y ago
    I searched this thread far and wide for fountain codes. Surprised they're so low on the list. I find them amazing. Aso, the name is really good. The fact that you can collect any random packets in any order invokes the idea of putting a cup under a fountain and letting it fill up with water. Love it.
• gordaco 4y ago
  Fenwick Trees (which, despite the name, are implemented using an array) allow counting prefix sums AND updating prefix sums in O(log n) time. Very useful when n is in the order of millions. I have used them a few times in Project Euler problems. https://en.wikipedia.org/wiki/Fenwick_tree https://en.wikipedia.org/wiki/Fenwick_tree
  • nyanpasu64 4y ago
    Is it possible to implement a Fenwick tree using a tree, and support quickly adding and removing items as well as quickly shifting the positions of suffixes?
    • pjscott 4y ago
      Yes! This is both possible and fairly easy.
    • kragen 4y ago
      Yes.
  • EnderShadow8 4y ago
    Segment trees are objectively superior in all ways except implementation length
    • almog 4y ago
      Another advantage to Fenwick Tree: while it shares asymptotic space complexity with Segment Tree, it has better constant factors, which can be useful in very restricted environments.
      • silverlake 4y ago
        I used fenwick trees in a smart contract because space/time costs money.
  • almog 4y ago
    Was going to mention Fenwick Tree here as well, but since you've already did, I'll just add that this is IMO a great introduction to Fenwick Trees: https://www.youtube.com/watch?v=kPaJfAUwViY https://www.youtube.com/watch?v=kPaJfAUwViY
• swizzler 4y ago
  I like consistent hashing (https://en.m.wikipedia.org/wiki/Consistent_hashing https://en.m.wikipedia.org/wiki/Consistent_hashing). When a hash table (or load balancing pool) needs to be resized, it usually reduces the number of keys (clients) that need to be remapped.
  • pianoben 4y ago
    Even simpler is Weighted Rendezvous Hashing (https://www.snia.org/sites/default/files/SDC15_presentations/dist_sys/Jason_Resch_New_Consistent_Hashings_Rev.pdf https://www.snia.org/sites/default/files/SDC15_presentations...). It's quite a bit easier to implement and verify than consistent hashing, and carries the same benefits (minimal reshuffling on ring resizes, etc)
    • eru 4y ago
      I recently updated the Python example on the Wikipedia page for Weighted Rendezvous Hashing. (I'm amazed my edit seems to be still there.) https://en.wikipedia.org/wiki/Rendezvous_hashing https://en.wikipedia.org/wiki/Rendezvous_hashing
    • feurio 4y ago
      In a similar vein, Maglev hashing has a more uniform distribution and decent reshuffling. I couldn't get my head around the explainaions that I had seen until I read this one: https://www.usenix.org/sites/default/files/conference/protected-files/nsdi16_slides_eisenbud.pdf https://www.usenix.org/sites/default/files/conference/protec...
• haroldl 4y ago
  In a Scrabble AI coding contest I discovered the GADDAG which is like a trie but indexes all of the words forwards and backwards from any starting point within the words. https://en.wikipedia.org/wiki/GADDAG#:~:text=A%20GADDAG%20is%20a%20data,%22hook%20into%22%20existing%20words https://en.wikipedia.org/wiki/GADDAG#:~:text=A%20GADDAG%20is....
• jillesvangurp 4y ago
  String tries are pretty fun if you need to implement auto completion. I spent some time implementing my own on one project and open sourced it. And then brought it in on a few more projects. I've used bloom filters with in memory caches a few times.
• anmalhot 4y ago
  Since you mentioned Bloom filters, here are ribbon filters: https://engineering.fb.com/2021/07/09/data-infrastructure/ribbon-filter/ https://engineering.fb.com/2021/07/09/data-infrastructure/ri... Edit: another that I enjoyed working with 'Burst Tries': https://dl.acm.org/doi/10.1145/506309.506312 https://dl.acm.org/doi/10.1145/506309.506312
• brightball 4y ago
  Actually came here to say bloom filter but you beat me to it.
• goddstream 4y ago
  Piece tables used in text editors https://www.averylaird.com/programming/the%20text%20editor/2017/09/30/the-piece-table/ https://www.averylaird.com/programming/the%20text%20editor/2...
• epelesis 4y ago
  BW Trees are pretty neat [1][2]. Typically BTrees in database engines need latches to prevent concurrent writes messing up the tree but BW Trees conveniently sidestep that requirement by appending all node updates to a linked list (called a Delta Chain), and having each reader apply the delta of updates by traversing the linked list until it hits the final node in the list. Periodically, these linked lists are compacted back into single nodes. If you like these kinds of data structures, the Database Internals [3] book has a good introduction and explanation of a handful of BTree optimizations like this. 1: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/bw-tree-icde2013-final.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/... 2: https://www.cs.cmu.edu/~huanche1/publications/open_bwtree.pdf https://www.cs.cmu.edu/~huanche1/publications/open_bwtree.pd... 3: https://www.databass.dev/ https://www.databass.dev/
• flobosg 4y ago
  Another use case for Bloom filters: Bioinformatics (see https://en.wikipedia.org/wiki/Bloom_filters_in_bioinformatics https://en.wikipedia.org/wiki/Bloom_filters_in_bioinformatic...)
• nonbirithm 4y ago
  Colonies/hives, which have fast insertion/erasure/iteration and preserve pointers on insertion/erasure. I remember that Cataclysm: DDA used this data structure for keeping track of the items on each map tile. https://plflib.org/colony.htm https://plflib.org/colony.htm
• alfiedotwtf 4y ago
  The XOR Linked List blew my mind when I first read about it. Clever! https://en.wikipedia.org/wiki/XOR_linked_list https://en.wikipedia.org/wiki/XOR_linked_list
  • freemint 4y ago
    Horrible for todays hardware but i also came to say this.
• valbaca 4y ago
  (EDIT: using "mail" because I was using "letter" too much in my description) The way I think of a bloom filter is like at an office mailroom or at post office mailbox where mail is grouped by the letters of people's name. Given someone's name, you can glance and see "Uptrenda? No letters for 'U'" very quickly. This is when a bloom filter returns FALSE. But if they glance and see mail in the "U" box, then they return MAYBE. After a MAYBE, to see if you actually have any mail, they need to actually go through the box (i.e. a bloom filter miss). Mine are a couple that are present in the Java Collections but I'm always disappointed that other language's don't include them: - TreeMap/Set: A RedBlack tree. It keeps keys ordered, either naturally or by using the provided Comparator, but has log(n) time on basic ops. - https://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html - LinkedHashMap/Set: keeps keys ordered by insert order via a linkedlist but can be configured to use access-order making it easy to use as a LRU cache. It keeps O(1) time but is less efficient than HashMap: - https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html
  • dskloet 4y ago
    > other language's don't include them stl::map and stl::set in C++ are actually a tree map and tree set.
• vivegi 4y ago
  1. Merkle-trees. Helps with content-based-retrieval, efficient add/modify/delete/move node operations. Useful in scenarios where you are building a data-serialization format that needs to support efficient updates. 2. Not necessarily a data structure, but SMT solvers (like Z3) provide a very useful abstraction for certain kinds of problems. They also use some cool data structures like disjoint-sets among other things. 3. Lock-free datastructures
• jtolmar 4y ago
  The union-find data structure / algorithm is useful and a lot of fun. The goal is a data structure where you can perform operations like "a and b are in the same set", "b and c are in the same set" and then get answers to questions like "are a and c in the same set?" (yes, in this example.) The implementation starts out pretty obvious - a tree where every element either points at itself or some thing it was merged with. To check if two elements are in the same set, check if they have the same parent. Without analyzing it, it sounds like you'll average findRoot() performance of O(log(n)), worst-case O(n). There are a couple of simple optimizations you can do to this structure, the type of things that seem like they shouldn't end up affecting asymptotic runtime all that much. The first is that, whenever you find a root, you can re-parent all the nodes you visited on the way to that root, so they'll all be quicker to look up next time. The other is that you keep track of the size of sets, and always make the larger set be the parent of the smaller. And neither of those actually do anything impressive alone, but if you use both, the algorithm suddenly becomes incredibly fast, with the slowest-growing (non-constant) complexity I've ever heard of: O(the inverse of the Ackermann function(n)). Or, for any reasonable N, O(4 or less).
  • kizer 4y ago
    If at some point you have a cycle, you can then reparent and remove the cycle, right? This structure in general then can encode transitive relations effectively? Something like “a and b …” “b and c …” “c and a …”.
    • thaumasiotes 4y ago
      > If at some point you have a cycle, you can then reparent and remove the cycle, right? You'd never have a cycle. The way a cycle would theoretically arise would have to be joining something to its own child. But you don't naively join the two objects you're given - you find their root objects, and join those. If - as would be necessary for a cycle to form - they have the same root, you can return without doing anything. If we call unite(a,b) unite(b,c) unite(c,a) then we should end up with this structure: c / \ b a With parents on the right, the structure will be a-b after the first call and a-b-c after the second call. The reason we end up with a shallower tree after the third call is that when a is passed to unite, we call find on it and it gets reparented directly to c. Then, c (the representative for c) and c (the representative for a) are already related, so we don't adjust the structure further. > This structure in general then can encode transitive relations effectively? Well... no. This structure embodies the concept of an equivalence relation. You wouldn't be able to use it to express a general transitive relation, only a transitive relation that is also symmetric and reflexive.
• mgraczyk 4y ago
  Fractional Cascading. A simple and very cool way to speed up searching for the same key in multiple lists. Instead of K binary searches taking time Klog(N), you can do it in log(N) time without using asymptomatically more space. https://en.m.wikipedia.org/wiki/Fractional_cascading https://en.m.wikipedia.org/wiki/Fractional_cascading I wrote a simple demo in Rust a while back to help myself learn the language. https://github.com/mgraczyk/fractional_cascading https://github.com/mgraczyk/fractional_cascading I also think pairing heaps are neat.
• efortis 4y ago
  The humble array but with a twist for accessing its indices in a hardware multiplexer way with 'shift left' and 'or' bitwise operations. /* Bits: selected, hovered */ const colors = [ grey, // 00 green, // 01 blueA, // 10 blueB // 11 ] const color = colors[selected << 1 | hovered] https://blog.uidrafter.com/bitwise-table-lookup https://blog.uidrafter.com/bitwise-table-lookup
  • pjscott 4y ago
    No hardware multipliers here: left shifts are handled by much cheaper hardware [1], and are almost part of the basic arithmetic logic unit taught in school -- it can do addition, subtraction, bitwise operations, shifts by one, and maybe shifts by any number less than their word size. [1] https://en.wikipedia.org/wiki/Barrel_shifter https://en.wikipedia.org/wiki/Barrel_shifter
    • efortis 4y ago
      Multiplexer (not multiplier)
      • pjscott 4y ago
        My mistake! They look so similar.
• anigbrowl 4y ago
  Quadrilateral Simmelian backbones Count quadrangle structures in graphs to derive an embeddedness coefficient for each edge and expand the graph along the most embedded edges, yielding nice clusters. https://jgaa.info/accepted/2015/NocajOrtmannBrandes2015.19.2.pdf https://jgaa.info/accepted/2015/NocajOrtmannBrandes2015.19.2...
• johncalvinyoung 4y ago
  Not crazy obscure, but half-edge mesh data structures are super cool to me.
• cr__ 4y ago
  Huet's zipper. https://en.wikipedia.org/wiki/Zipper_(data_structure) https://en.wikipedia.org/wiki/Zipper_(data_structure). One zipper value represents a regular tree of data, but from the perspective of the "current position". There are traversal operations that take a zipper value and return the same tree from the perspective of an element above/beside/below the current position, and there are operations that return the same structure but with the current element changed, or items deleted or inserted. Huet's paper is an easy read if you've been exposed to OCaml or similar languages: https://www.st.cs.uni-saarland.de/edu/seminare/2005/advanced-fp/docs/huet-zipper.pdf https://www.st.cs.uni-saarland.de/edu/seminare/2005/advanced... . His "returned glove" metaphor is what made it click for me. Clojure includes an implementation of Huet's zippers https://github.com/clojure/clojure/blob/master/src/clj/clojure/zip.clj https://github.com/clojure/clojure/blob/master/src/clj/cloju... that is <300 lines of code. It's very, very clever and broadly useful for dealing with XML or other nested data structures.
• chriswarbo 4y ago
  The Zipper acts like a linked-list with a cursor, or "focused element"; it's implemented as a pair of lists in opposite orders; or, equivalently but more symmetric, as triple of (List[A], A, List[A]) Say we have a zipper containing [0, 1, 2, 3, 4, 5], and we're focusing on the 3. In code this will look like: ([2, 1, 0], 3, [4, 5]) Where [a, b, c] denotes a singly-linked list, with O(1) head (returning a) and tail (returning [b, c]). Notice that the first list is in reverse order. To focus on the next element, we put the currently focused element on the first list, and pull the head off the second list: ([3, 2, 1, 0], 4, [5]) And vice versa to focus on the previous element: ([1, 0], 2, [3, 4, 5]) I like to imagine this as a string of beads, with the focused element held in our fingers and the rest hanging down: 3 / \ 2 4 | | 1 5 | 0 To move the focus forwards and backwards, we move our grip to the next/previous bead. This works nicely as an immutable datastructure, since the tails of both lists can be shared (i.e. we don't need to copy the whole list, just the wrap/unwrap an element on to the head) Zippers were first applied to lists, but have since been generalised: - To trees: focusing on one node, and being able to move the focus up, to the left-child, or to the right child - To having more than one focus - To datastructures more generally, by treating them as 'derivatives' (as in calculus) https://en.wikipedia.org/wiki/Zipper_(data_structure) https://en.wikipedia.org/wiki/Zipper_(data_structure) As an example, the XMonad window manager uses a zipper to keep track of the currently-focused window. I've also used Zippers for window management, e.g. having a list of Displays, with one of them focused (accepting keyboard input); each Display containing a list of Workspaces, with one of them focused (currently shown); and each Workspace containing a list of Windows, with one of them focused (the active window). Keyboard shortcuts could shift between the previous/next Window, Workspace, or Display.
  • mastermedo 4y ago
    I don’t understand why wouldn’t you just use a list and an index. You can always access list[index+1] or list[index-1] or list[0] or list[list.length-1]. What is the benefit here?
    • zachrose 4y ago
      A list and an index creates the possibility that the index is out of bounds, and then your code probably has to check for that scenario and figure out how to handle it. With a zipper such a scenario isn’t possible.
• kcbanner 4y ago
  "This is the story of a clever trick that's been around for at least 35 years, in which array values can be left uninitialized and then read during normal operations, yet the code behaves correctly no matter what garbage is sitting in the array. Like the best programming tricks, this one is the right tool for the job in certain situations. The sleaziness of uninitialized data access is offset by performance improvements: some important operations change from linear to constant time." https://research.swtch.com/sparse https://research.swtch.com/sparse
  • decebalus1 4y ago
    I remember this from Programming Pearls and I was going to post about it after reading the comments. Great stuff.
  • once_inc 4y ago
    Requires numbers inserted to be unsigned, and to have a maximum value within reason, and doubles memory usage. Very nifty trick though!
  • djmips 4y ago
    I've used this type of data structure in the past for things like managing sprite DMA on old consoles. It's very friendly to old systems with simple memory access patterns.
  • 1024core 4y ago
    I was going to mention Sparse Arrays, thanks for mentioning it. One of my favorite data structures.
  • Tao3300 4y ago
    > The sleaziness of uninitialized data access That's the perfect word for this kind of thing. It's not wrong, but it's sleazy alright.
• zeroonetwothree 4y ago
  Fibonacci Heap Famous as the data structure that achieved optimum runtime in Djikstra’s algorithm. In practice it isn’t often used because simpler heaps outperform it except in very specific circumstances. https://en.wikipedia.org/wiki/Fibonacci_heap https://en.wikipedia.org/wiki/Fibonacci_heap Soft heap As far as I know this hasn’t really been implemented. It’s used for the best known minimum spanning tree algorithm. Pretty crazy. https://en.wikipedia.org/wiki/Soft_heap https://en.wikipedia.org/wiki/Soft_heap
• tsujp 4y ago
  Verkle Tree https://vitalik.ca/general/2021/06/18/verkle.html https://vitalik.ca/general/2021/06/18/verkle.html https://blog.ethereum.org/2021/12/02/verkle-tree-structure/ https://blog.ethereum.org/2021/12/02/verkle-tree-structure/
• sidcool 4y ago
  Tim sort.
• carapace 4y ago
  DLX https://en.wikipedia.org/wiki/Dancing_links https://en.wikipedia.org/wiki/Dancing_links Stanford Lecture: Don Knuth — "Dancing Links" (2018) https://www.youtube.com/watch?v=_cR9zDlvP88 https://www.youtube.com/watch?v=_cR9zDlvP88
• filoeleven 4y ago
  HAMT: Hash Array Mapped Trie. This data structure makes efficient immutable data possible. You can update a list of a million items, and keep a reference to the original list, by changing 3 or 4 references and some bytes. This should replace copy-on-write for scripting languages. I really want to see it in a JS spec soon. There are libraries that can do it, but they add translation penalties and extra steps. I’d complain less if I could use Clojurescript professionally, because it and Clojure are built around them. https://en.m.wikipedia.org/wiki/Hash_array_mapped_trie https://en.m.wikipedia.org/wiki/Hash_array_mapped_trie
  • CSMastermind 4y ago
    Isn't this what Sublime Text uses under the hood to give it such good performance?
  • jahewson 4y ago
    That’s what Immutable.js used under the hood.
    • filoeleven 4y ago
      Yes, I evaluated it. The complexity of knowing where to convert from/to plain JS, plus the extra library syntax to learn, plus the performance cost of toJS, made it a poor fit for my particular use case. Nearly as much of a hard sell at work as saying “let’s rebuild the UI in Clojurescript,” and without providing as much benefit. My use case is pretty atypical though, and it’s worth checking out if you have more reliable data shapes/update paths.
      • bhl 4y ago
        Does immer have the same drawbacks as immutable? It uses proxies as opposed to hased array map tries.
        • filoeleven 4y ago
          The key design difference between the two is that immutable.js wants you to keep your stuff in its format (and operate on your stuff with its functions) until you hit some piece of code that needs a plain JS object. Whereas immer is scoped (mostly?) to update functions, and always returns plain JS. Immer seems to be designed to simplify the problem of only changing references to changed objects—and it looks like it does a good job of it. So with immutable.js, you get more powerful data manipulation throughout the app, at the cost of having to know when and where to convert things back to plain JS. With immer, you get tightly-scoped immutable updates to objects, and inside the update function you can treat them as if they’re mutable, letting you write more idiomatic-looking JS. Instead of spreading 4 layers of objects to update one state flag, immer lets you say: const nextState = produce(state, draft) => { draft.view.marketing.annoyingSubscribePopup = false } Every object reference in that path will be updated, but the rest of “state”, “state.view”, etc. will be unchanged. If you can keep everything inside of immutable.js, it is the fastest thing out there. As soon as you have to drop back to plain JS, it gets slower. See this performance graph: https://immerjs.github.io/immer/performance/ https://immerjs.github.io/immer/performance/ Thanks for reminding me of this. We finally dropped IE11 support, so may be able to get some benefits from introducing immer either by itself or by bringing in Redux Toolkit.
• mikewarot 4y ago
  Trivial, but very useful - phase accumulator / numerically controlled oscillator. With two unsigned integers, freq and phase, you get amazingly fine control over timing. You only use the top N bits of phase for output. It's saved my bacon in embedded systems more than once.
• 6510 4y ago
  I did an append only list of URL's with RAW files where each bit says something is true/false about the url at that offset. For example 26x26 RAW files asking if the page contains the letter combination "aa" or "ab" all the way up to "zy" and "zz". When one types a search query after 2 letters a file is pulled, at the 3rd letter we have a second 2 letter combination. Then do the AND operation. It is much like a bloom filter and tells you what is not in the set.
  • compressedgas 4y ago
    That is a form of q-gram indexing.
• agilob 4y ago
  Not super obscure, but I remember that one specific time when circular-linked-list made a lot of sense to use, well I wanted to use it so I used it. I had a bunch of API keys with poor expiry documentation and implementation, so to find out if a key expired it had to be used. I put it in a main "keys.pop loop" and all methods below tried to use the key. If HTTP response was (some another obscure HTTP status code like) 505, I simply called `continue;` in the loop to jump to another, without caring at all where I was before. https://github.com/atedja/gring https://github.com/atedja/gring
• foobiekr 4y ago
  Skew heaps. They aren’t useful but their utter simplicity is really fun.
  • eru 4y ago
    Any data structure based on skew binary numbers is also fun.
• fho 4y ago
  Due to data immutability, a lot of the standard data structures in Haskell are quite interesting. Eg `Data.Sequence` (https://hackage.haskell.org/package/containers-0.6.5.1/docs/Data-Sequence.html https://hackage.haskell.org/package/containers-0.6.5.1/docs/...) is based on Finger Trees (http://staff.city.ac.uk/~ross/papers/FingerTree.html http://staff.city.ac.uk/~ross/papers/FingerTree.html) which allow O(log(min(i,n-i))) inserts (at i) and O(1) inserts at the beginning or end even thou the data structure is basically copy-on-write. In general Haskell gas a lot of specialized data structures. On of my favorites is `Data.IntMap` (https://hackage.haskell.org/package/containers-0.6.5.1/docs/Data-IntMap-Lazy.html https://hackage.haskell.org/package/containers-0.6.5.1/docs/...) which is a specialized map for integer keys (based on Patricia trees iirc). (Man I miss working in Haskell :-( )
• odipar 4y ago
  SeqHash This data structure is an immutable, uniquely represented Sequence ADS (Authenticated Data Structure) with various interesting use cases. It is based on a novel hashing scheme that was first introduced with SeqHash. See http://www.bu.edu/hic/files/2015/01/versum-ccs14.pdf http://www.bu.edu/hic/files/2015/01/versum-ccs14.pdf) by Jelle van den Hooff , a brilliant young researcher back then. SeqHashes are uniquely represented Merkle Trees that also represents a sequence. Concatenation of two SeqHashes is O(log(n)). In turn, the cryptographic signing of SeqHashes is O(1) as each tree node carries a cryptographic hash. Of course, for each node to carry a hash incurs a hefty overhead but that can be alleviated by (lazily) grouping nodes into buckets (turning it in some kind of BTree). SeqHashes also don't support splitting in O(log(n)) like for example AVL trees. I've created an Btree version of SeqHash that also allows splitting SeqHashes in O(log(n)) called SplitHash. See: https://github.com/odipar/spread/blob/master/src/main/scala/org/spread/core/splithash/SplitHash.scala https://github.com/odipar/spread/blob/master/src/main/scala/...
• mzaks 4y ago
  Not a data structure, but a nice concept for very fast search on immutable pre sorted array, eytzinger order. I did some experiments, it is about 2-3x faster then binary search. https://medium.com/swlh/binary-search-vs-eytzinger-order-301f0a9a797d https://medium.com/swlh/binary-search-vs-eytzinger-order-301...
• Arainach 4y ago
  Deterministic acyclic finite state automata. Essentially a compressed trie. Significantly more memory efficient for real world dictionaries. https://en.wikipedia.org/wiki/Deterministic_acyclic_finite_state_automaton https://en.wikipedia.org/wiki/Deterministic_acyclic_finite_s...
• justahuman74 4y ago
  I'll just sit here hoping that all of the above datatypes get a nice rust crate :)
• vbezhenar 4y ago
  Ropes. Something between array and tree.
• throwaway45631 4y ago
  Not obscure by itself, but gifted with obscurity due to its language‘s success: JavaScript‘s Map type. Just because of the Type being introduced very late to the language, and another very successful method named identically makes it almost impossible to google your way out of any situation. You have to rely on core documentation and link lists. Just by using “new Map()” in JS, you’re suddenly ehem mapped 30 years back in time!
• dwaite 4y ago
  Splay trees: These are binary search trees, but when you 'splay' the tree (such as by search) it rebalances the tree so that the search result is on top. This means while it is O(log n) for operations like other self-balancing trees, it optimizes tree depth in the face of non-random access so that recently accessed items are fewer steps into the tree. Piece tables: A bit more common for text editors, where you need to represent a sequence of characters in a form that allows efficient memory use and fast insertions/removals (so editing the first line isn't moving the 10MB of data that follows it). You create a series of references to spans (or pieces) of the document, possibly starting with a single span pointing to a mmap() version. Edits are done by appending/prepending pieces, which are potentially just references to subsequences of items created in fresh memory, appended into a buffer. Saving can create a single sequence (and a single span). This has interesting variations: - Put attributes on the pieces for formatting, such as indicating text should be rendered a different color or bolded. - Create a hierarchy of pieces-of-pieces. With formatting attributes you are then dangerously close to a DOM. - Retain old copies of a piece table - since your original mmap() file hasn't changed and your changes are in an append-only buffer, those piece table copies provide undo/redo state.
  • bob1029 4y ago
    Came here for splay tree. I’ve found some really powerful applications for this in low level database engine work. Being able to incrementally rebalance a tree and keep the set of deltas small each time is really powerful when you are dealing with append only IO abstractions.
  • Nilithus 4y ago
    The VSCode Blog has a great article on Piece Tables talking about their adoption of that data structure https://code.visualstudio.com/blogs/2018/03/23/text-buffer-reimplementation https://code.visualstudio.com/blogs/2018/03/23/text-buffer-r...
• Joel_Mckay 4y ago
  First contact with Functors, multidimensional Kalman filtering abstractions, and Golomb ruler optimized DFT... kind of like meeting the Wizard of Oz, and finding out it was a chicken all along. ;)
• magicalhippo 4y ago
  Not sure you could call it a data structure as such, but Latent Semantic Indexing[1] kinda blew my mind when I learned about it. The fact that you could perform linear algebra on documents and words, to get out a number that somehow quantified how close a document was to another really surprised me back in the day. Grew a new appreciation for what exactly those vectors in linear algebra could represent. Not in the field so don't know how obscure it is though. [1]: https://en.wikipedia.org/wiki/Latent_semantic_analysis#Latent_semantic_indexing https://en.wikipedia.org/wiki/Latent_semantic_analysis#Laten...
• myaccount80 4y ago
  Dancing links https://en.m.wikipedia.org/wiki/Dancing_Links https://en.m.wikipedia.org/wiki/Dancing_Links “ In computer science, dancing links (DLX) is a technique for adding and deleting a node from a circular doubly linked list. It is particularly useful for efficiently implementing backtracking algorithms, such as Donald Knuth's Algorithm X for the exact cover problem.[1] Algorithm X is a recursive, nondeterministic, depth-first, backtracking algorithm that finds all solutions to the exact cover problem. Some of the better-known exact cover problems include tiling, the n queens problem, and Sudoku.”
• nemo1618 4y ago
  My contribution: the Binary Numeral Tree: https://eprint.iacr.org/2021/038 https://eprint.iacr.org/2021/038 This is a tree-like structure where the structure of the tree is fully determined by the number of leaves N. Specifically, each 1-bit in the binary representation of N corresponds to one of the tree's perfect binary subtrees. For that reason, I think of it more as "structure imposed upon a list" rather than a typical mutable tree with pointers and such. What are the applications of this data structure? I am only aware of one: computing the Merkle root of a large amount of data in streaming fashion. The funny thing is that it's been discovered independently multiple times: in BLAKE3, Sia, Utreexo, and more. Maybe someday, someone will find another use for it. :)
  • zachrip 4y ago
    Can you dumb this down for me?
    • nemo1618 4y ago
      It might be easier to think about it as a stack, rather than a tree. Each element of the stack represents a subtree -- a perfect binary tree. If you ever have two subtrees of height k, you merge them together into one subtree of height k+1. Your stack might already have another subtree of height k+1; if so, you repeat the process, until there's at most one subtree of each height. This process is isomorphic to binary addition. Worked example: let's start with a single leaf, i.e. a subtree of height 0. Then we "add" another leaf; since we now have a pair of two equally-sized leaves, we merge them into one subtree of height 1. Then we add a third leaf; now this one doesn't have a sibling to merge with, so we just keep it. Now our "stack" contains two subtrees: one of height 1, and one of height 0. Now the isomorphism: we start with the binary integer 1, i.e. a single bit at index 0. We add another 1 to it, and the 1s "merge" into a single 1 bit at index 1. Then we add another 1, resulting in two 1 bits at different indices: 11. If we add one more bit, we'll get 100; likewise, if we add another leaf to our BNT, we'll get a single subtree of height 2. Thus, the binary representation of the number of leaves "encodes" the structure of the BNT. This isomorphism allows you to do some neat tricks, like calculating the size of a Merkle proof in 3 asm instructions. There's some code here if that helps: https://github.com/lukechampine/us/blob/master/merkle/stack.go https://github.com/lukechampine/us/blob/master/merkle/stack.... You could also check out section 5.1 of the BLAKE3 paper: https://github.com/BLAKE3-team/BLAKE3-specs/blob/master/blake3.pdf https://github.com/BLAKE3-team/BLAKE3-specs/blob/master/blak...
• DeathArrow 4y ago
  >Good use-case: routing. Say you have a list of 1 million IPs that are black listed. A trivial algorithm would be to compare every element of the set with a given IP. The time complexity grows with the number of elements. Not so with a bloom filter! A bloom filter is one of the few data structures whose time complexity does not grow with the number of elements due to the 'keys' not needing to be stored ('search' and 'insert' is based on the number of hash functions.) The easy and efficient way to test if a value is in a list is to use a hash set or dictionary. Complexity is always O(1).
  • kushan2020 4y ago
    OP is probably mentioning bloom filter because it is space efficient. A good filter will use less space than entire hash set making it a good candidate to be kept in RAM to filter out requests and reduce expensive calls to read disk.
• ben__bradley 4y ago
  Bitboards for chess board representation, the fastest and most complex such representation: https://www.chessprogramming.org/Bitboards https://www.chessprogramming.org/Bitboards Other structures for chess are easier to follow and understand: https://www.chessprogramming.org/Board_Representation https://www.chessprogramming.org/Board_Representation
• Dwedit 4y ago
  Here's one I don't know if I've ever seen documented anywhere. If anyone knows a proper name for this one, let me know! Imagine it's for a text editor, and you want to map Line Numbers to Byte Positions. But then you want to insert a byte somewhere, and you need to add 1 to all your Byte Position values. Instead of actually keeping a big array of Byte Position values, you have a hierarchical array. The convention is that whenever you want to read the value, you add the Parent's value, and that parent's value, etc. Number of parents would be logarithmic. So if you want to add 1 to everything past a certain point, you just apply it to some leaf nodes, then the next internal nodes, rather than applying it to every single leaf node.
  • progval 4y ago
    https://en.wikipedia.org/wiki/Rope_(data_structure) https://en.wikipedia.org/wiki/Rope_(data_structure)
    • Dwedit 4y ago
      That's good for representing the text, but I'm more focused on the part about being able to add X to everything past a particular point very quickly by manipulating parent values.
      • progval 4y ago
        Ropes do this too; each node is labeled the size of its subtree. If you want to compute line numbers as well, add them as another label
        • kragen 4y ago
          That kind of thing is a common extension to ropes, because it makes them indexable containers like arrays, but it is not inherent to the definition of ropes. I don't think it's mentioned in the original Cedar rope paper.
  • ant6n 4y ago
    An annotated tree?
• deleted 4y ago
  [deleted]
• bell-cot 4y ago
  > ...bloom filters... Good use-case: routing. Say you have a list of 1 million IPs that are black listed... Seems-needed clarification: Bloom filters suffer from false positives, but not false negatives. So - if BloomFilterBlacklistCheck( $IP ) returns false, your router can safely conclude "not blacklisted". But if it returns true, then you'll need to perform further checks. (And you can't just use a Bloom filter of known false positive - that will also suffer from false positive, potentially letting in traffic from blacklisted IPs.)
• peterhunt 4y ago
  Sketching data structures: count min sketch, hyperloglog, sliding window hyperloglog, t digest Skiplists Locality sensitive hashing Log structured storage (bitcask, lsm)
• smokel 4y ago
  Bitboards, although perhaps not so obscure, allow for some very nice optimization tricks. I've used them to solve Sudoku puzzles really fast.
• boredbot 4y ago
  arrays are pretty underground, theyre like lists but better. C++ offers arrays but unfortunately python doesnt :(
  • progval 4y ago
    It does: what Python calls lists are actually (dynamic) arrays. There is also this module, which provides unboxed arrays: https://docs.python.org/3/library/array.html https://docs.python.org/3/library/array.html
• dskloet 4y ago
  Invertible Bloom Lookup Tables. They're like Bloom filters but you can also remove elements and even reconstruct elements in certain cases. Useful for syncing 2 databases which are almost in-sync, by sending only a small amount of data between them. It's used by Bitcoin nodes to communicate the contents of newly mined blocks.
• imachine1980_ 4y ago
  Use arrayanes instead of matrix efficiently in boardgames like tetris or chess"A bitboard is a specialized bit array data structure commonly used in computer systems that play board games, where each bit corresponds to a game board space or piece. This allows parallel bitwise operations to set or query the game state, or determine moves or plays in the game"
• CreRecombinase 4y ago
  Roaring bitmaps are compressed bitmaps and they're pretty great. https://roaringbitmap.org/about/ https://roaringbitmap.org/about/
• perlgeek 4y ago
  Skip lists. They are useful for checking in O(log(n)) if a number (or string) is in any of n ranges of numbers. You just keep a sorted list of endpoints of the ranges, and when you do a lookup, you do a binary search if the search value is in the list, and if not, between which two indexes. If it's between and even and an odd index, it's in. Very useful if you remember that IP addresses are also integers, and with IPv6 networks become way too huge to enumerate.
• scary-size 4y ago
  Count-min sketch comes to mind [1]. It's a probabilistic data structure similar to the bloom filter. Learnt about it in this system design video "Top K Problem" [2]. [1] https://en.wikipedia.org/wiki/Count–min_sketch https://en.wikipedia.org/wiki/Count–min_sketch [2] https://www.youtube.com/watch?v=kx-XDoPjoHw https://www.youtube.com/watch?v=kx-XDoPjoHw
• pavelboyko 4y ago
  OBDD: Ordered Binary Decision Diagrams. This data structure allows efficient symbolic operations on boolean functions. Widely used in electronic design automation software. [1] https://en.wikipedia.org/wiki/Binary_decision_diagram https://en.wikipedia.org/wiki/Binary_decision_diagram [2] https://apps.dtic.mil/sti/pdfs/ADA470446.pdf https://apps.dtic.mil/sti/pdfs/ADA470446.pdf
• sterlind 4y ago
  Skip lists! Super wacky, super fun to implement. O(log n) insertion/deletion/binary search, maintained sorted. It's probabilistic; you have a number of linked list levels, so you flip k coins to insert a node, and insert into the lowest k linked lists. also, radix heaps are underappreciated.
• ur-whale 4y ago
  Cuckoo hashing: https://en.wikipedia.org/wiki/Cuckoo_hashing https://en.wikipedia.org/wiki/Cuckoo_hashing Hash tables that come with a parameter that lets you control density vs. speed.
• nailer 4y ago
  > Lets you test if a value is definitely NOT in a list of pre-stored values wouldn’t a hashmap / dict / object do this in 0(1)? Input goes in, is hashed, the key exists or doesn’t exist?
  • tomsmeding 4y ago
    The point of a Bloom filter is that it takes constant memory. (The tradeoff is the possibility of false-positives, of course.)
• karsinkk 4y ago
  Lazy Adaptive Trees : https://dl.acm.org/doi/10.14778/1687627.1687669 https://dl.acm.org/doi/10.14778/1687627.1687669 It is a B-Tree where updates to the tree are buffered in the branch nodes and are propagated down to the leaf nodes at a later point in time.
• kragen 4y ago
  Here's a few fun ones: the Burrows–Wheeler transform, suffix arrays in general, Kanerva's fully distributed representation, reduced-affine-arithmetic numbers, LSM trees, binary array sets, sparse array sets, and gap buffers. (I'm not sure how nobody had mentioned gap buffers yet on the thread, but if they did I didn't see it.) — ⁂ — The Burrows-Wheeler transform is the second character of each suffix in a (cyclic) suffix array, and there turns out to be a simple algorithm to recover the original text from this transform; live demo: http://canonical.org/~kragen/sw/bwt http://canonical.org/~kragen/sw/bwt. But the new text is very easily compressible, which is the basis for bzip2. As mentioned by Blahah and dahart, this is only one of many interesting things you can do with suffix arrays; they can also do efficient regular expression search, for example. This is more interesting since three practical linear-time and -space suffix array construction algorithms were discovered in the early 02000s. — ⁂ — Pentti Kanerva devised a "fully distributed representation" in the 01990s, which has some features in common with bloom filters — every association stored in an FDR record is stored to an equal extent (probabilistically) in every bit of the record, so erasing some of the bits erases none of the associations but increases the error probability for all of them. You assign a random or pseudorandom bitvector (of, say, 16384 bits) to every atomic value to be stored, represent an association of two (or more) atoms as their XOR, and then take the bitwise majority rule of all the associations to be stored as the record. To retrieve an association, you XOR the record with an atom, then compute the correlation of the XOR result with all possible atoms; the correlation with the correct atoms will be many standard deviations away from the mean, unless the number of associations stored in the record is high enough that conventional data structures wouldn't have been able to store it either. This and some related work has blossomed into a field called "hyperdimensional computing" and "vector symbolic architectures". But the problem of finding the nearest atom or atoms seems, on its face, to make this impractical: if you have 16384 possible atoms and 16384 bits in your bitvector, you would seem to need at least 16777216 bit operations to compute all the associations. I realized the other night that if you use the rows of a Walsh–Hadamard matrix as the "pseudorandom" atom representations, you can compute all the correlations in linearithmic time with the fast Walsh–Hadamard transform. Moreover, Cohn and Lempel's result from 01977 "on fast M-sequence transforms" is that after a simple transposition you can also use the FWHT to compute all the correlations with the complete output of a maximal LFSR (a so-called "M-sequence") in linearithmic time, so you can also use the cyclic shifts of an LFSR output for your atoms without losing efficiency. Probably someone else has already figured this out previously, but I hadn't found it in the literature. — ⁂ — I'm not sure if the quantities used in reduced affine arithmetic count as a "data structure"? They're a data type, at least, but they're not a container. The idea is that you execute some arbitrary numerical algorithm, not merely on floating-point numbers, or even on dual numbers as in forward-mode automatic differentiation, nor even yet on (min, max) intervals as in ordinary interval arithmetic, but on a vector of coefficients [a₀, a₁, a₂...aₙ], which represents a linear function a₀x₀ + a₁x₁ + a₂x₂ + ... aₙxₙ, where x₀ = 1 and each of the other xᵢ ∈ [-1, 1], so this function is really a representation of an interval. Then you can assign each of the xᵢ (except x₀ and xₙ) to be the unknown error in one of the input parameters to your algorithm, whose magnitude is determined by the aᵢ value in the value of that parameter; and when you introduce rounding error, you increase aₙ enough to account for it. (The non-reduced kind of affine arithmetic just increases n without limit to account for new roundoff errors.) Reduced affine arithmetic has two advantages over the usual kind of interval arithmetic. First, it cancels errors correctly; if you calculate (y+1)(y+2)/(y+3) with interval arithmetic, with some uncertainty in the value of y, you usually get an unnecessarily loose bound on the result because interval arithmetic assumes that the uncertainties in the numerator and the denominator are uncorrelated, when in fact for many values of y they partly cancel out. (You can't apply this cancelation to aₙ, the error stemming from all the roundoffs in your algorithm, just the other aᵢ.) But the more interesting result is that RAA gives you a linear function that approximates the calculation result as a linear function of the inputs, which is pretty similar to calculating the gradient — but with error bounds on the approximation! — ⁂ — LSM trees are only about as "obscure" as bloom filters, since they underlie several prominent filesystems, LevelDB, and most of the world's search engines, but if you don't know about bloom filters, you might not know about LSM trees either. I wrote a tutorial explanation of LSM trees in https://github.com/kragen/500lines/tree/master/search-engine https://github.com/kragen/500lines/tree/master/search-engine, though the name "LSM tree" hadn't yet gone mainstream. Binary array sets, as described in https://www.nayuki.io/page/binary-array-set https://www.nayuki.io/page/binary-array-set, are closely related to LSM trees, to the point that you could describe them as an application of LSM trees. They are a simple data structure for the exact version of the problem bloom filters solve approximately: maintaining a set S of items supporting the operations S.add(item) and S.contains?(item). Insertion (.add) is amortized constant time, and membership testing (.contains?) is O(log² N). — ⁂ — A different and more efficient data structure for the exact set membership problem, limited to the case where the items to be stored are up to M integers in the range [0, N), supports constant-time creation, clearing, insertion, size measurement, and membership testing, and linear-time enumeration, but I think cannot be implemented in modern standard C because of its rules about reading uninitialized data. (By allowing creation to be linear time you can implement it in standard C.) It uses two arrays, A[M] and B[N] and a variable n, and i is a member of the set iff B[i] < n ∧ A[B[i]] == i, from which it is straightforward to work out the other methods. I don't remember what this data structure is called, but I definitely didn't invent it. I described it and some uses for it in https://dercuano.github.io/notes/constant-time-sets-for-pixel-painting.html https://dercuano.github.io/notes/constant-time-sets-for-pixe.... You can associate additional values with this structure to use it as a sparse array. Oh, I see kcbanner posted this one too, with a link to Russ Cox's writeup, which is better than mine and explains that it was published by Briggs and Torczon in 01993, but probably not originally invented because it was an exercise in an Aho, Hopcroft, and Ullman textbook in 01974 and in Programming Pearls: https://research.swtch.com/sparse https://research.swtch.com/sparse — ⁂ — A gap buffer is a data structure sort of similar to Huet's zipper but without the dynamic allocation; Emacs famously uses them for its editing buffers. It consists of an array containing of a leading chunk of text, followed by a gap, followed by a trailing chunk of text. Edits are always made in the gap; to start editing in a different position, you have to move some text from the end of the leading chunk to the beginning of the trailing chunk or vice versa. Suppose you want to edit a 531-byte file; you allocate a larger buffer, say 1024 bytes, and read those 531 bytes into the beginning of the buffer. If the user starts inserting text after byte 200, you begin by moving bytes 201–530 (330 bytes) to the end of the 1024-byte buffer (positions 694–1024); then you can insert the user's text at positions 201, 202, 203, etc., without having to do any more work to move text. If the user moves up to byte 190 and inserts more text, you only have to move bytes 191–203 or whatever to the end of the buffer. A gap buffer is very fast in the usual case of making a sequence of small edits at the same location or close-together locations, and because the constant factor of copying a large block of bytes from one place to another is so small, even moving the gap from one end of a buffer to another is generally plenty fast enough for interactive use. Moreover, operations like string search are very fast in a gap buffer, while they tend to be very slow in fancier data structures with better asymptotic complexity, such as piece tables and ropes; and it uses a predictable and relatively small amount of extra memory. — ⁂ — However, like FORTH, fancy data structures are a bit of an attractive nuisance: they tempt you to get into trouble. When I first came across Sedgewick's Algorithms in C it was a revelation to me: here were so many clever ways of breaking down problems that made apparently impossible problems easy. (I had come across sorting algorithms before but I didn't really understand them.) I immediately and erroneously concluded that this was the knowledge I had been missing to program all the things that I didn't know how to program, and I began my counterproductive data-structure-fetishism phase. Much better advice is found in The Practice of Programming: almost all programs can be written without any data structures but arrays, hash tables, linked lists, and, for things like parsing, symbolic algebra, or filesystems, trees. So just use those if you can. Occasionally, a program is only possible, or is dramatically better, using fancy data structures like LSM-trees, bloom filters, suffix arrays, skip lists, HAMTs, union find, zippers, treaps, BDDs, ropes, gap buffers, Fenwick trees, splay trees, and so on. And that can be super fun! But this situation is pretty rare, and it's important not to get yourself into the position where you're implementing a red-black tree or HAMTs when it would have been a lot easier to write your program in a brute-force way. Or where your successors are fixing bugs in your Fenwick tree implementation. Also, it's important to be aware that, quite aside from the difficulty of writing and understanding the code, fancy data structures often have extra costs at runtime which can outweigh their benefits. It's easy to discover that your splay tree runs slower than sequential search over an unsorted array, for example, and of course it uses much more RAM.
• mkindahl 4y ago
  Tree automata and the BURS (Bottom Up Rewrite System) algorithm are pretty cool.
• ur-whale 4y ago
  The Alias method: O(n) in space and O(1) biased number generator https://en.wikipedia.org/wiki/Alias_method https://en.wikipedia.org/wiki/Alias_method Mind was utterly blown when I first understood the way this works in my late teens.
• zbobet2012 4y ago
  Here is one not on the list so far: Set Sketches. They allow you compute the difference between two sets (for example to see if data has been replicated between two nodes) WITHOUT transmitting all the keys in one set to another. Say you have two sets of the numbers [1, ..., 1million] all 32 bit integers, and you know one set is missing 2 random numbers. Set sketches allow you to send a "set checksum" that is only 64 BITS which allows the other party to compute those missing numbers. A naive algorithm would require 4MB of data be transferred to calculate the same thing. *(in particular pin sketch https://github.com/sipa/minisketch https://github.com/sipa/minisketch).
  • FridgeSeal 4y ago
    Thank you! I always wondered about this problem and never knew what to look up to read more about it!
    • ElCapitanMarkla 4y ago
      I’ve found that a couple of times in this thread. A way to describe a problem and have potentially applicable algorithms suggested would be cool
• berendka 4y ago
  Nested Sets https://en.wikipedia.org/wiki/Nested_set_model https://en.wikipedia.org/wiki/Nested_set_model You can ust to store tree structures in relational databases for faster querying stuff like "all nodes below node x", "How many nodes to the top node" and so on. Querying is easy, but comes at the cost that changes like inserting and deleting are more expensive. I used this for an auth service with roles, user and org units. pretty query heavy, worked very well.
• Dwedit 4y ago
  Here's another one I was thinking about. It's an idea for a hierarchical Free Space Bitmap. I don't know if anything like this has appeared in a real file system or not. At the lowest level, let's have one bit represent if a 4K chunk is free space or occupied. 64 bits at this level tells you the usage of 64 * 4096 bytes (256KB) Then Level 2. Two arrays. One bit at this level represents 64 bits in the level 1 array. One array for All-Bits-Set in level 1, one array for Any-Bit-Set in level 1. 64 bits at Level 2 tells you usage of 64 * 64 * 4096 bytes (16MB). Then Level 3. Two arrays. One bit at this level represents 64 bits in the level 2 array. One array for All-Bits-Set in level 2, one array for Any-Bit-Set in level 2. 64 bits at Level 3 tells you the usage of 1GB. I'd imagine there would be ways to use the hierarchical tables to quickly find a hole of a particular size without checking only the lowest level.
  • zbobet2012 4y ago
    I think you're describing a Van Emde Boas tree (or trie): https://en.wikipedia.org/wiki/Van_Emde_Boas_tree https://en.wikipedia.org/wiki/Van_Emde_Boas_tree
  • compressedgas 4y ago
    This reminds me of libswift's binmaps: https://github.com/gritzko/swift/blob/master/doc/binmaps-alenex.pdf https://github.com/gritzko/swift/blob/master/doc/binmaps-ale...
• rjh29 4y ago
  For routing you can also use a sparse radix tree, also known as a Patricia tree. This allows fast matching against a set prefixes (which is used for IP routing) without taking up a lot of space.
• mkindahl 4y ago
  Also, the algorithms around using Reduced Order Binary Decision Diagrams (ROBDD) to represent sets efficiently. They are used in verification algorithms with very large state spaces, such as "Symbolic Model Checking: 10^20 states and beyond" by Burch, Clarke, and McMillan <http://www.cse.chalmers.se/edu/year/2012/course/TDA956/Papers/SMC.pdf http://www.cse.chalmers.se/edu/year/2012/course/TDA956/Paper...>
• Philip-J-Fry 4y ago
  I want to write a content based pub/sub system. Where a subscriber says "I want messages where field X = A, y = B and z > C". I've looked around and I've seen R+ Trees are potentially a solution but there's very little info on how they're actually created in code. Does anyone know of any nice data structures to do this? Obviously the most basic way is just indexing each field and that works for simple equality but gets harder when you're trying to do other comparators like < and >.
• FullyFunctional 4y ago
  My absolute favorite, Cuckoo hashing, has been mentioned already, but so far (239 comment in) nobody has mention this approach (called?) to store an array A[] of N-bit numbers, most of which are zero or small: use N set of numbers S[N], such that for each A[I] you store I in S[J] where J are the bit positions where A[I] have a set bit. In other words, S[J] are the indices of elements from A that has a set bit in position J. The representation of S can be anything, and even dynamically adapting to the data. I’ve seen trees of bitmaps for example.
  • xxs 4y ago
    In practice Cuckoo sucks, b/c the reading from an unknown index in an array is not a const cost operation. It has an upper bound of course, but its average cost is quite different, depending if you are to hit L1, or L2... or just go for the a cache miss. "Cache misses" is what dominates performance nowadays.
    • FullyFunctional 4y ago
      Where I go there are no cache misses (it’s in hardware)
• Gehinnn 4y ago
  Finger trees. They work on an arbitrary monoid and maintain a list of items. You can insert and remove items in logarithmic time, as well as ask for the sum of items in a given range, also in logarithmic time. This is useful for example when you want to convert between offsets and line/column numbers efficiently, while you also want to efficiently update/insert/replace lines.
• zasdffaa 4y ago
  > Golomb Coded Sets are similar to bloom filters but the storage space is much smaller. Worse performance though. Humm. A link to these would have been good[1], but anyway I understand that an optimally filled bloom filter takes ~1.44 times more space than the optimal theoretic value (which I understand Golomb encoding gives you?), so 'much smaller' is not a helpful measure. Likewise the 'worse performance' is not a helpful phrase, I believe a linear lookup time is needed for decoding, but a small amount of space for an extra indexing structure can speed things up lots. Bloom filters are updatable (addition only in the simplest bloom filter), golomb coded sets practically can't be updated except by rebuilding AIUI. I suppose binary heaps should get a mention <https://en.wikipedia.org/wiki/Binary_heap https://en.wikipedia.org/wiki/Binary_heap> cos they barely seem to figure in other comments here. The neat bit is they are trees but implicit (stored in an array) not explicit (which would use pointers) and are always balanced giving you log access times in a compact form. [1] <https://en.wikipedia.org/wiki/Golomb_coding https://en.wikipedia.org/wiki/Golomb_coding> but there are simpler explanations on the web
• skrebbel 4y ago
  Not a very deep CS-y one, but still one of my favourite data structures: Promise Maps. It only works in languages where promises/futures/tasks are a first-class citizen. Eg JavaScript. When caching the result of an expensive computation or a network call, don't actually cache the result, but cache the promise that awaits the result. Ie don't make a Map<Key, Result> but a Map<Key, Promise<Result>> This way, if a new, uncached key gets requested twice in rapid succession, ie faster than the computation takes, you avoid computing/fetching the same value twice. This trick works because: - promises hold on to their result value indefinitely (until they're GC'ed) - you can await (or .then()) an existing promise as many times as you want - awaiting an already-resolved promise is a very low-overhead operation. In other words, the promise acts as a mutex around the computation, and the resulting code is understandable even by people unfamiliar with mutexes, locks and so on.
  • acoye 4y ago
    I wonder if Swift's AsyncAwait could be used in such a way.
    • Ryuuke5 4y ago
      Sure it's possible, we need to await for the Task if it already exists on the dictionary, for example we could imagine writing something like this inside an actor to make it threadSafe. private var tasksDictionary: Dictionary<String, Task<Data, Error>> func getData(at urlString: String) async throws -> Data { if let currentTask = tasksDictionary[urlString] { return await currentTask.value } let currentTask = Task { return try await URLSession.shared.data(from: URL(string:urlString)!) } tasksDictionary[urlString] = currentTask let result = await currentTask.value tasksDictionary[urlString] = nil return result }
      • afro88 4y ago
        Great! So much nicer than the Combine (or Rx) version.
      • 4y ago
• fulafel 4y ago
  This post: http://www.frankmcsherry.org/graph/scalability/cost/2015/01/15/COST.html http://www.frankmcsherry.org/graph/scalability/cost/2015/01/... "Scalability! But at what COST?" In it Frank McSherry uses a handful of data structure tricks to make graph algorithms like connectivity and PageRank run progressively faster on his laptop, beating distributed cluster implementations. It's actually a version of their HotOS paper with Isard and Murray. Admittedly it's the opposite of obscure, being kind of a myth busting piece about distributed processing being faster and how even largish data sets can fit on a single node (and even your laptop).
  • fulafel 4y ago
    Addenum. Link to paper: https://www.usenix.org/system/files/conference/hotos15/hotos15-paper-mcsherry.pdf https://www.usenix.org/system/files/conference/hotos15/hotos... COST acronym: "Configuration that Outperforms a Single Thread"
• bjoli 4y ago
  We all know about the immutable vectors of clojure (tries, basically). I always preferred the RRB-tree which is the same thing, but relaxes the leftwise dense requirement. This means you have a bit-partitioned trie until you do a split, merge or insert, after which you get a slightly slower operations, but still very competitive. It is actually a quite trivial change until you come to the merge algorithm which is finicky in all the wrong ways. The benefits are (in clojure terminology) O(1)ish splits, inserts and concatenations instead of O(n). I don't know if it can be called obscure anymore, since Scala's vectors are RRB-trees and clojure actually has an implementation of them, but I often see people talk about ropes in situations where an RRB tree should be a no-brainer.
• kqr 4y ago
  Not particularly innovative, but extremely useful: HDRHistograms let you very efficiently create, combine and query empirical probability distributions. If I'm doing anything with random or random-looking variation, I prefer to store the full distribution in a HDRHistogram rather than just the last value, last few values, mean value, or whatever. Opens up so many possibilities for analysis later down the road.
• weinzierl 4y ago
  Nearly 300 comments and no one said Rainbow Tables. Sure, they not used anymore and are not particularly useful nowadays, but I find the idea behind them very beautiful.
• aliceryhl 4y ago
  Link cut trees. They can be used to query information about paths in a forest, while also allowing you to add and remove edges in the forest. For example, you could use them to store the minimum spanning tree of a graph, while supporting updates if edges are added to the graph. They can also be used to speed up max flow algorithms by finding the augmenting path in logarithmic time.
• manuelabeledo 4y ago
  Concurrent tries with non-blocking snapshots [0] Say that you have a dataset that needs to be ordered, easily searchable, but is also updated quite frequently. Fast accesses are a pain if you decide to use traditional read-write locks. Ctries are entirely lock-free, thus there is no waiting for your read operations when an update is happening, i.e. you run lookups on snapshots while updates happen. They are also a lot of fun to implement, especially if you aren't familiar with lock-free algorithms! I did learn a lot doing it myself [1] [0] http://aleksandar-prokopec.com/resources/docs/ctries-snapshot.pdf http://aleksandar-prokopec.com/resources/docs/ctries-snapsho... [1] https://github.com/mabeledo/ctrie-java https://github.com/mabeledo/ctrie-java
  • nly 4y ago
    Sounds like if you want a version of this that doesn't leak memory you need a garbage collected language?
    • manuelabeledo 4y ago
      Yeah, either that or you implement your own. Doing so with reference counts might not be too hard, though.
      • nly 4y ago
        The reference count on each element would presumably require atomic operations that could race with those used to update the actual data structure, and therefore you'd lose all your concurrency guarantees?
        • manuelabeledo 4y ago
          Generally speaking, this shouldn't be an issue if you perform batch collections. Either way, any new mechanism to release memory would need to take into account both the generation and the reference count, and the atomic release should be performed in the same GCAS fashion.
• adontz 4y ago
  Succinct Trie http://stevehanov.ca/blog/?id=120 http://stevehanov.ca/blog/?id=120 Super effective way to store a searchable list of items, like a dictionary of words.
• ablaba 4y ago
  Succinct Data Structures https://courses.csail.mit.edu/6.851/spring12/scribe/L17.pdf https://courses.csail.mit.edu/6.851/spring12/scribe/L17.pdf
• paskozdilar 4y ago
  I've had a situation where I needed to stream blocks of data from a remote computer in soft-realtime, but still needed to share the same data with many different consumers. The code was simple, but effective (Go): import "sync" type Muxer[T any] struct { ret T mut sync.RWMutex } func (c *Muxer[T]) Multiplex(fn func() T) (ret T) { if c.mut.TryLock() { defer c.mut.Unlock() ret = fn() c.ret = ret } else { c.mut.RLock() defer c.mut.RUnlock() ret = c.ret } return ret } The way to use it is to write a non-concurrent nullary get() function, then pass it to the Multiplex() function in as many goroutines as needed: get := func() DataType { ... } muxer := Muxer[DataType]{} // in other goroutines value := muxer.Multiplex(get) The value will be shared across all goroutines, so we get minimum latency with minimum copying.
  • sph 4y ago
    I don't get it. It seems overengineered to me, but I can't formulate my reasoning well enough. Why isn't the original value that you're returning protected by a RWLock, and all goroutines will just need to acquire a read lock, instead of using a write lock for what is basically a getter function? Yeah, I don't get it.
    • paskozdilar 4y ago
      The Multiplex() function serves a double purpose: 1) If no other goroutine is currently executing the Multiplex() function, then Multiplex() acquires a write lock, executes the getter and caches the result. 2) If some other goroutine is currently executing the Multiplex() function, then Multiplex() waits to acquire the read lock, then reads the cached value. So in case of a single goroutine executing the Multiplex() function in a loop, it will be nothing more than a wrapper. But when many goroutines are executing the same Multiplex() function concurrently, only one goroutine will actually execute the getter, and all others will just wait for the first one to finish, then take its cached result. The point is that you don't have to think about who executes the getter and who copies the cached values, how often to execute the getter, how much time will getter take... You just call it like an ordinary function, and every goroutine will get the most recent value it can get. Hopefully this clears things out. I'm willing to elaborate further if you have any more questions.
• slazaro 4y ago
  I don't know whether it already exists or if it has a name, but internally I call it Virtual List. - Reasoning: It's used in cases where you'd ideally use an array because you want contiguous memory (because you'll usually iterate through them in order), but you don't know beforehand how many elements you'll insert. But you can't use a resizeable version like std::vector, because it invalidates any pointers to the elements you've already allocated, and you need to store those pointers. - Implementation: As a black box, it's used like a list: you index elements with an integer, and you can append to the end. But internally it uses different lists. Like a std::vector, it starts with an allocated size, and when it needs a bigger size, it allocates newer blocks that are "added" to the end, but doesn't move the already allocated elements. - Downsides: Data is not all contiguous, at some point there are jumps between elements that should be close together. For performance when iterating, it's negligible since those cache misses happen "rarely" (depends on the block size, bigger block size means better cache performance but more potential wasted allocated memory), and most of the time you're iterating from start to end. But this means that you can't use this structure with algorithms that use "pointer + size", since internally it doesn't work like that. And since internally you can't shrink the lists and invalidate pointers, there's no way to delete elements, but in my case it's not a problem since I'd reuse indices afterwards with an added structure. - Applications: I used it when coding games, when you have a big list of entities/components but you don't know how many beforehand. You access them by index, you might store pointers to elements, and most of the time you'll iterate through the whole list (when updating, drawing, etc.).
  • nly 4y ago
    So like a std::deque? If the block size varies then lookup will be O(log B) where B is the number of blocks.
    • slazaro 4y ago
      I remember checking whether I would use std::deque, and I don't remember exactly why but I decided to implement this other system instead. I think it was because you can invalidate pointers with it if you delete somewhere in the middle, either manually or by calling an algorithm with it. Of course you have the option to just not do that in your code, but it's nice to have a hard guarantee that this can never happen, even by accident. I could have used a deque as a backend and wrapped it in the class, though.
• robertsdionne 4y ago
  Posit numbers (a better floating point representation): https://www.johndcook.com/blog/2018/04/11/anatomy-of-a-posit-number/ https://www.johndcook.com/blog/2018/04/11/anatomy-of-a-posit... https://www.johngustafson.net/pdfs/BeatingFloatingPoint.pdf https://www.johngustafson.net/pdfs/BeatingFloatingPoint.pdf
  • robertsdionne 4y ago
    Also, Learned Indexes Structures: The Case for Learned Index Structures: https://arxiv.org/abs/1712.01208 https://arxiv.org/abs/1712.01208 Learned Indexes for a Google-scale Disk-based Database: https://arxiv.org/abs/2012.12501 https://arxiv.org/abs/2012.12501 And Noms/Dolt Prolly Trees: How to Chunk Your Database into a Merkle Tree: https://dolthub.com/blog/2022-06-27-prolly-chunker/ https://dolthub.com/blog/2022-06-27-prolly-chunker/
• romes 4y ago
  Equality graphs (e-graphs) for theorem proving and equality saturation and other equality-related things. They're awesome data structures that efficiently maintain a congruence relation over many expressions > At a high level, e-graphs extend union-find to compactly represent equivalence classes of expressions while maintaining a key invariant: the equivalence relation is closed under congruence. e.g. If I were to represent "f(x)" and "f(y)" in the e-graph, and then said "x == y" (merged "x" and "y" in the e-graph), then the e-graph, by congruence, would be able to tell me that "f(x) == f(y)" e.g. If I were to represent "a*(2/2)", in the e-graph, then say "2/2 == 1", and "x*1 == x", by congruence the e-graph would know "a*(2/2) == a" ! The most recent description of e-graphs with an added insight on implementation is https://arxiv.org/pdf/2004.03082.pdf https://arxiv.org/pdf/2004.03082.pdf to the best of my knowledge. P.S: I'm currently implementing them in Haskell https://github.com/alt-romes/hegg https://github.com/alt-romes/hegg
  • FnuGk 4y ago
    Isnt that the building blocks of logic based programming languages like Prolog?
    • Twisol 4y ago
      I had a similar thought when I learned about e-graphs. I'm not sure yet, but I think congruence closure is a slightly different problem from the one Prolog unification solves. In particular, if you tell an e-graph that `f(x) = g(y)`, it will take you at your word -- while Prolog would give a unification error. (An e-graph should also handle `X = f(X)`, while this would fail Prolog's admittedly often-ignored occurs check.)
    • superlopuh 4y ago
      Yes, at least these egg-based projects are usign this idea, but it looks like it's just one of the options: https://souffle-lang.github.io/docs.html https://souffle-lang.github.io/docs.html http://www.philipzucker.com/souffle-egg4/ http://www.philipzucker.com/souffle-egg4/ https://arxiv.org/pdf/2004.03082.pdf https://arxiv.org/pdf/2004.03082.pdf
  • 4y ago
• anonymoushn 4y ago
  Robin Hood tables are a common-ish hash map implementation that often shows up on benchmarks for fast inserts. Depending on the implementation, a Robin Hood table is also a sorted sparse array! This could be useful for data that needs random access and sequential access to a subset of the sorted data, like an order book.
• mignato 4y ago
• _trackno5 4y ago
  Not really obscure, but I had never heard of it till recently (and most people I've talked had no idea about it): Difference Arrays. Great for when you need to do ranged updates in constant time. More info: https://codeforces.com/blog/entry/78762 https://codeforces.com/blog/entry/78762
• nvarsj 4y ago
  Probabilistic data structures are pretty cool. Count-min sketch [1] is another one. It gives a reasonably accurate count of different events, even millions of unique events, in a fixed memory size. It shows up a bunch in high volume stream processing, and it's easy to understand like the bloom filter. Another cool data structure is HeavyKeeper [2], which was built as an improvement on count-min sketch for one of its use cases: ranking the most frequent events (like for a leaderboard). It can get 4 nines of accuracy with a small fixed size even for enormous data sets. It's implemented by Redis's topk. [1]: https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch [2]: https://www.usenix.org/system/files/conference/atc18/atc18-gong.pdf https://www.usenix.org/system/files/conference/atc18/atc18-g...
• mijoharas 4y ago
  My favorite one that I've had the chance to use professionally is the Marisa trie[0]. Context is a data scientist had written a service that essentially was just lookups on a trie. He'd left and the service was starting to have memory problems so I dug in and swapped the implementation. Iirc swapping the trie implementation changed memory usage from 8gb to 100mb and sped everything up as well. The actual data structure is equivalent to a trie, but cannot be modified once it's been built (I think it may be the same as a LOUDS trie, I don't remember the specifics) [0] https://github.com/s-yata/marisa-trie https://github.com/s-yata/marisa-trie
• Fiahil 4y ago
  Append-Log. A grow-only linked list where you can only append elements to it. Good use-case: Lock-free concurrent reads are allowed, because there is no way committed content could change. Writes need to be Linearizable (so locking is required). Given this property, this data structure provides faster reads than a Mutex<List<T>> and similar write perfs. Bonus section: Provides broadcast broadcast capabilities if used as channel.
  • charleslmunger 4y ago
    I think this can be done completely lock free with almost same number of memory barriers as a mutex when writing - read the tail pointer (acquire), append your node using CAS(release), then update the tail pointer with CAS (release). For reads, start with an acquire read of the tail pointer, which will make all preceding writes to the list visible to you. Then you can read the list all you want up until you hit the node you read from the tail pointer without synchronization.
    • Fiahil 4y ago
      > read the tail pointer (acquire) > append your node using CAS(release) > update the tail pointer with CAS (release). I thought as well, but, when I wrote that impl there was no way to shortcut the 2 releases into a single atomic operation. That ended up creating forks or loosing blocks. I tested that model and a few variations with loom (https://docs.rs/loom/latest/loom/ https://docs.rs/loom/latest/loom/), so I'm confident that it didn't work. However, I also think that a working design might exist. I just haven't found it yet :)
      • charleslmunger 4y ago
        Another option that makes appends cheaper would be to use a Treiber stack (one acquire, one release!), but maintain a separate path for readers. When pushing, do a read (acquire) of the tail, then set (relaxed) a back link on the second-from-top element pointing to the current top, then CAS (release) to push your node. Since the back link will always write the same value, it's ok for contending writers to submit racing writes. Readers start by reading the tail(acquire) and storing a pointer to the node before it. They then traverse from head until they reach the node before the tail, then skip reading its back link pointer (as they already know it will point to the tail).
• icsa 4y ago
  [Ordered] Minimal Perfect Hash Functions with O(N) construction time. They have been around for 30 years and I don't see them used in practice.
  • HelloNurse 4y ago
    Fixed key sets are uncommon.
    • icsa 4y ago
      Many assets associated with a program or system are fixed/readonly/constant data. Slowly changing key sets can also take advantage of Minimal Perfect Hashing.
• zeugmasyllepsis 4y ago
  A GADDAG[1] is a combination pre-/suffix trie that's used for move generation in Scrabble. Unlike a traditional dictionary to find anagrams for words, a GADDAG makes it easier to identify plays based off of available letters already on the board. I made a little visualization of how they work for a data visualization class a few years back.[2] [1] https://en.wikipedia.org/wiki/GADDAG https://en.wikipedia.org/wiki/GADDAG [2] https://www.axioms.me/gaddag/#?page-5 https://www.axioms.me/gaddag/#?page-5
• mungoman2 4y ago
  Not really a pure data structure, but I like hash tables where the entries expire after some time. This is very useful in interactive situations like in games or chat bots, where for example you want the AI/bot to remember a conversation or piece of information for some time. Simplest to implement is to just wrap a hash table and insert time checks in the accessors.
• turkeywelder 4y ago
  Might not be very obscure but it was new to me. Ended up being really useful for finding out whether dates intersect a particular period and ended up using it quite a bit at work. Range Tree: https://en.wikipedia.org/wiki/Range_tree https://en.wikipedia.org/wiki/Range_tree You give it a range of dates and it'll tell you if any intersect so if you're looking for "how many people are absent in this time period" you can really quickly find out by using a range tree.
• benou 4y ago
  Very good idea! And I love bloom filter too (and their more modern successor cuckoo filter) but I'd challenge the usecase you mention though: 1 million IPv4 is 4MB, and 16MB for IPv6. That's tiny, you're better off using some kind of hashtable, unless you have a fast and small memory, and then a slow and big memory (say embedded processor with small CPU cache and some DRAM). Bloom filters are useful when your working set cannot fit in your fast memory, to allow you to go to the slow memory only for a small number of requests.
  • IanCal 4y ago
    The other use is when the cost of checking the set is high due to something like accessing a remote system. You can pull a small representation of the full set and only do a network request after when it's likely to succeed.
• allanrbo 4y ago
  Frugal streaming. For estimating a median or percentile in a stream, using constant memory. It's very simple: if the current value is higher than our estimate, then increase our estimate by one. Else decrease by one. It will converge over long enough time. This is called the Frugal-1U algorithm. The Frugal-2U is a slightly more advanced version that modifies the step size along the way, plus other optimizations, to converge faster and not oscillate too much. https://pastebin.com/wAcCS8WZ https://pastebin.com/wAcCS8WZ
  • jjgreen 4y ago
    An alternative streaming method due to Arandjelović, Pham, Venkatesh based on maximum entropy: https://ieeexplore.ieee.org/document/6971097 https://ieeexplore.ieee.org/document/6971097 and implementation in C: https://github.com/dressipi/apv-median https://github.com/dressipi/apv-median
  • Lichtso 4y ago
    Isn't that essentially a low-pass filter?
• vuonghv 4y ago
  I like Ring Buffer, it leverages the CPU-cache line and can use to store event queue.
• xyproto 4y ago
  Cuckoo filter "A space-efficient probabilistic data structure that is used to test whether an element is a member of a set, like a Bloom filter does. False positive matches are possible, but false negatives are not – in other words, a query returns either "possibly in set" or "definitely not in set". A cuckoo filter can also delete existing items, which is not supported by Bloom filters. In addition, for applications that store many items and target moderately low false positive rates, cuckoo filters can achieve lower space overhead than space-optimized Bloom filters." https://en.m.wikipedia.org/wiki/Cuckoo_filter https://en.m.wikipedia.org/wiki/Cuckoo_filter
• Linda703 4y ago
  [dead]
• eru 4y ago
  Soft heaps are pretty neat. They are like normal min-heaps, but support all operations you care about in O(1) instead of O(log n) time. The catch is that they are allowed to make a configurable proportion of errors. They are basically only useful in theory, not in practice. They allow construction of some asymptotically optimal algorithms.
• ww520 4y ago
  Extendible hashing allows space efficient growable hashtable on disk, with a maximum of two reads to reach the data page, and an extremely simple and efficient way to grow the hashtable.
• hamilyon2 4y ago
  My attention seems to to be attracted to perfect hash functions. They are typically used for stuff like keywords detection in parsers, but they are an interesting concept, that should be possible to extend to much more.
• stevefan1999 4y ago
  https://en.wikipedia.org/wiki/Fibonacci_heap?wprov=sfla1 https://en.wikipedia.org/wiki/Fibonacci_heap?wprov=sfla1 Fibonacci heap is theoretically better than Binary heap but the cache behavior is terrible https://en.wikipedia.org/wiki/Van_Emde_Boas_tree?wprov=sfla1 https://en.wikipedia.org/wiki/Van_Emde_Boas_tree?wprov=sfla1 Well, I saw this in CLRS tho. Very clever way of abusing bit patterns for quick range query in O(log log M) where M is the integer size. https://en.wikipedia.org/wiki/Suffix_array?wprov=sfla1 https://en.wikipedia.org/wiki/Suffix_array?wprov=sfla1 A simpler way to do text matching since suffix array is the preorder traversal of a suffix trie constructed using the same string. Not heavily used in practice, but I do know bioinfo people used it a lot. https://study.com/academy/lesson/robin-hood-hashing-concepts-algorithms.html https://study.com/academy/lesson/robin-hood-hashing-concepts... Not a data structure, but still very underrated. Robinhood hash basically means you keep the first insertion order and the actual insertion order and compare their distance. Once the difference is bigger than expected, you put it in front to "steal from the rich" to have better expected access distribution, hence Robinhood. Getting more prominent today thanks to Rust popularizing it again, since the default hash table implementation of Rust uses hashbrown which uses Robinhood hashing scheme. https://en.wikipedia.org/wiki/Skip_list?wprov=sfla1 https://en.wikipedia.org/wiki/Skip_list?wprov=sfla1 The ordered linked list with a fast lane every log(n) level. Not used very much, but one of the place I know uses it is Redis https://en.wikipedia.org/wiki/Double-ended_priority_queue?wprov=sfla1 https://en.wikipedia.org/wiki/Double-ended_priority_queue?wp... Basically one priority queue that does two things. Can ironically be implemented with two priority queues (dual)
  • hcs 4y ago
    A suffix array is useful as a part of binary diff, finding a longest matching substring to copy from an old file. Bsdiff makes heavy use of this, it's used in Courgette for patching after preprocessing. And once you have a suffix array, you're on the way to the Burrows-Wheeler Transform for e.g. bzip2 compression! https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transf...
• benhoyt 4y ago
  The BK-Tree, which allows fast querying of "close" matches, such as Hamming distance (number of bits different). http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK... I wrote a Python library implementing them a number of years ago: https://github.com/benhoyt/pybktree https://github.com/benhoyt/pybktree
• nathell 4y ago
  Directed acyclic word graphs (DAWGs)! They’re like tries, but with identical subtrees glued together. They’re capable of encoding real-world dictionaries of millions of words into ~1 byte per word, when stored cleverly (see [0]). They let you do things like efficiently finding a list of words in a dictionary whose Levenshtein’s distance to a given word is less than x. Their cousins, GADDAGs, are _the_ data structure of choice in Scrabble-playing engines. [0]: http://www.jandaciuk.pl/fsa.html http://www.jandaciuk.pl/fsa.html
  • microtonal 4y ago
    Also related: Levenshtein automata -- automata for words that match every word within a given Levenshtein distance. The intersection of a Levenshtein automaton of a word and a DAWG gives you an automaton of all words within the given edit distance. I haven't done any Java in years, but I made a Java package in 2013 that supports: DAWGs, Levenshtein automata and perfect hash automata: https://github.com/danieldk/dictomaton https://github.com/danieldk/dictomaton
• jupiter909 4y ago
  o Fractal Tree Index's are rather nifty as used in Tokudb engine. Basic gist is that you get the speed of Btree but your update are less painful. https://en.wikipedia.org/wiki/Fractal_tree_index https://en.wikipedia.org/wiki/Fractal_tree_index http://www-db.deis.unibo.it/courses/TBD/Lezioni/mysqluc-2010-fractal-trees.pdf http://www-db.deis.unibo.it/courses/TBD/Lezioni/mysqluc-2010... o k-d tree for space partitioning, handy real world applications in mapping and gaming. o Bloom Filters as you mention are great, always a handy one to know.
• yeputons 4y ago
  Eertree. As one can guess from the name, it stores all sub-palindromes of a given string and does stuff to them. Somewhat similar to a suffix tree in spirit, but was only invented in 2015. See https://en.wikipedia.org/wiki/Palindrome_tree https://en.wikipedia.org/wiki/Palindrome_tree and the original paper
• carlopi 4y ago
  Not sure whether they classify as obscure, but I haven't see cited already: - Dominator tree (https://en.wikipedia.org/wiki/Dominator_(graph_theory) https://en.wikipedia.org/wiki/Dominator_(graph_theory)) - Single-Connected-Components-Graph - Deterministic data structures (eg. a set that acts deterministic to the fact that addresses might be somehow randomly assigned, very useful for ensuring reproducibility) Already cited, but it's clearly among the most elegant: - union-find (!!!!) and as a bonus one that is easily overlooked: -std::deque, that when restricted to push_back() or push_front() guarantees not to ever move objects around.
• fulmicoton 4y ago
  pure algorithm & perf stuff... - exponential unrolled linked list: I don't know what they are called, so I called them that way https://fulmicoton.com/posts/tantivy-stacker/ https://fulmicoton.com/posts/tantivy-stacker/. - radix heap. I actually had to use that data structure on a real use case. - radix tree. Actually super useful. - HashMap<String, V> where the string and the value are contiguous in memory. Weirdly I've never seen that one... The hashmap can stores the full hash in its hash table anyway, so false positive are super rare. It will have to check the string anyway... You can improve your locality by keeping the key and the value in the same place in RAM. just practical stuff, in python, I often use a magic dict defined as follows. ``` from collections import defaultdict >>> def MagicDict(): ... return defaultdict(MagicDict) ``` then you can use your MagicDict as a weird json-like map. ``` c = MagicDict() c[3]["aaa"][2] = 5 ```
• unsupp0rted 4y ago
  If somebody made a Youtube channel going over the data structures mentioned in this thread with clear examples of pros/cons, I'd watch the heck out of it and support it on Patreon.
• guuggye 4y ago
  Rope (or Cord) https://en.m.wikipedia.org/wiki/Rope_(data_structure) https://en.m.wikipedia.org/wiki/Rope_(data_structure)
• benreesman 4y ago
  https://github.com/facebook/folly/blob/main/folly/docs/PackedSyncPtr.md https://github.com/facebook/folly/blob/main/folly/docs/Packe... is pretty awesome and I’ve personally gotten big wins from it. The parent mentioned Bloom Filters, HyperLogLog-type stuff is on that family tree and also very interesting and very useful. But the coolest thing lately by far? Swiss table (and the largely equivalent F14). That thing is a game changer in certain scenarios.
• ignoramous 4y ago
  > Good use-case: routing. Say you have a list of 1 million IPs that are [deny listed]. Apparently, bloom filters make for lousy IP membership checks, read: https://blog.cloudflare.com/when-bloom-filters-dont-bloom/ https://blog.cloudflare.com/when-bloom-filters-dont-bloom/ CritBit Trie [0] and possibly Allotment Routing Table (ART) are better suited for IPs [1]. [0] https://github.com/agl/critbit https://github.com/agl/critbit [1] https://web.archive.org/web/20210720162224/https://www.hariguchi.org/art/art.pdf https://web.archive.org/web/20210720162224/https://www.harig...
  • zasdffaa 4y ago
    That over-simplifies what the linked article says, plus there are things like blocked bloom filters and other tricks to speed things up. Plus if he's allocating 128MB, well, just do it as a direct array 1 bit per IP4 address (which can be optimised to remove a few special blocks I guess) and skip any hashing.
  • arein3 4y ago
    Why not a Map? It will have search complexity of 1 If it should take into account ip blocks then just put the ranges in an sorted index and you have logarhytmic complexity for search (if speed is important and the blacklist is not huge, you can also expand the blacklisted ranges by individual ip and put them in a Map so that you get complexity of 1 for ip range search)
• felixr 4y ago
  The SO question "What are the lesser known but useful data structures?" has a good list https://stackoverflow.com/questions/500607/what-are-the-lesser-known-but-useful-data-structures https://stackoverflow.com/questions/500607/what-are-the-less... [edit: the link above has been discussed on HN multiple times https://hn.algolia.com/?dateRange=all&page=0&prefix=false&query=stackoverflow.com%2Fquestions%2F500607&sort=byPopularity&type=story https://hn.algolia.com/?dateRange=all&page=0&prefix=false&qu...]
• pgt 4y ago
  Not technically a data structure, but Reservoir Sampling is an interesting probabilistic sampling technique used to choose a random sample from a population of unknown size N in a single pass, so useful for a data structure that does not fit in memory. https://en.wikipedia.org/wiki/Reservoir_sampling https://en.wikipedia.org/wiki/Reservoir_sampling
• tealpod 4y ago
  Bloom Filter is very clever and simple DataStructure, Thank you.
• amenghra 4y ago
  Purely Functional Data Structures[1] by Chris Okasaki is worth reading. There's a book version if you prefer vs reading a thesis. Even though the domain application is functional programming, these datastructures can come in handy when you want to enable state sharing / keeping old versions around without having to copy data. [1] https://www.cs.cmu.edu/~rwh/students/okasaki.pdf https://www.cs.cmu.edu/~rwh/students/okasaki.pdf
  • dllthomas 4y ago
    I loved the "Numerical Representations" chapter, on deriving new data structures by analogy to number bases.
• motoboi 4y ago
  If you like Bloom Filters, you'll love Cuckoo filter, which allow key deletion.
• earthnail 4y ago
  Vantage-point trees. Great structure for nearest neighbour searches. Bonus tip: When you have a fast distance function (like a hamming distance) and write your tree from scratch in C (which almost automatically means you'll optimise it for your use case), they can become absurdly fast - much faster than the general-purpose nearest neighbour libraries I'm aware of.
• RF_Savage 4y ago
  Low Density Parity Codes (LDPC) (1). So good forward error correction that up toa few years ago it was all under patents. Gold Codes (2) are also very cool in CDMA systems. [1] https://en.m.wikipedia.org/wiki/Low-density_parity-check_code https://en.m.wikipedia.org/wiki/Low-density_parity-check_cod... [2] https://en.m.wikipedia.org/wiki/Gold_code https://en.m.wikipedia.org/wiki/Gold_code
• almog 4y ago
  The Hierarchical Timing Wheels is an efficient data structure/algorithm for managing timers (event scheduling) when: 1. The timers variance is large. 2. Timers are likely to be cancelled. 3. A fixed (configurable) precision is configurable. This talk provides a nice overview of different timing wheels implementations including hierarchial and hashed timing wheels.
  • almog 4y ago
    Too late to edit but I forgot to paste the link to the timing wheels overview talk that I mentioned, so here it is: https://www.youtube.com/watch?v=AftX7rqx-Uc https://www.youtube.com/watch?v=AftX7rqx-Uc
    • beyonddream 4y ago
      Nm, thanks:)
  • beyonddream 4y ago
    I think you had not posted the link to the talk!
• synalx 4y ago
  PR Quadtrees (https://opendsa-server.cs.vt.edu/OpenDSA/Books/CS3/html/PRquadtree.html https://opendsa-server.cs.vt.edu/OpenDSA/Books/CS3/html/PRqu...) got me my current job at Google. One of my interviewers asked basically "how would you design Google Maps?" and I based my answer on this data structure.
  • plank 4y ago
    Looked to see what these things were. Realised it might be the reason I made a career in IT: I used this structure (I called it a box) to calculate residues (https://en.wikipedia.org/wiki/Residue_(complex_analysis) https://en.wikipedia.org/wiki/Residue_(complex_analysis)), which I figured would be simpler using an object-oriented hence I learned myself C++. This was during my PhD (theoretical physics). Off course, never used C++ again (learned object oriented language ‘properly’ using SmallTalk, which I also never used again in real life). Now, 25 years later, seeing the first time that I was using an (adaption of) PR Quadtrees.
  • mkl 4y ago
    Why subdivide so far? I find it better to have leaf nodes contain an array of up to some small number of points, e.g. 20. That reduces the pointer chasing significantly, and a linear search through such a small array is very fast.
• mtlmtlmtlmtl 4y ago
  N-dimensionsonal arrays are pretty cool, and fun to implement. I did one in C for an Advent of Code problem that switched from 3 to 4 dimensions between the two parts.
• noname120 4y ago
  HyperLogLog[1] — approximately count distinct elements from an extremely large set (e.g. 10⁹ elements) super efficiently. → Distinct count time complexity[2]: O(1) See Redis's PFCOUNT[4]. [1] https://en.wikipedia.org/wiki/HyperLogLog https://en.wikipedia.org/wiki/HyperLogLog [2] For a fixed number of registers (e.g. Redis's implementation) [3] https://redis.io/commands/pfcount/ https://redis.io/commands/pfcount/
• s1k3 4y ago
  There’s this one called a binary search tree. I’ve only heard about it a handful of times- during engineering interviews, but is otherwise reserved for the most esoteric of problem/spaces.
• gb 4y ago
  The half-edge data structure, used in computational geometry. I remember when I first discovered it, it drove home the point that choice of data structure can really matter - it made a bunch of problems I'd been working on much easier to solve, as it gave a different way of looking at things.
• beeforpork 4y ago
  Cuckoo hashing is really nice: fast O(1) access, amortized O(1) insert. And really space efficient, and it can be parameterized easily for a space efficiency vs. access time trade-off (it is always O(1), but with larger constants for better space efficiency). It is also very simple: basically just an array (plus an algorithm). Unexpectedly simple in my opinion for its good time and space performance. https://en.wikipedia.org/wiki/Cuckoo_hashing https://en.wikipedia.org/wiki/Cuckoo_hashing
• Hippocrates 4y ago
  Log-structured Merge (LSM) Trees: https://en.wikipedia.org/wiki/Log-structured_merge-tree https://en.wikipedia.org/wiki/Log-structured_merge-tree
• winReInstall 4y ago
  Input, Output Unionnions. basically a input struct into a algorith, layed out in such a way, that the algorithms output, always only overwrites input no longer needed. If done well, this allows for hot-loops that basically go over one array for read & write-backs. After all, its all just memory and to use what you got in situ is the fastet way one can go. No pointers to dereference and wait, just the input, computated, stored back into the same cacheline- to be used for the next part of the hot loop. If the hot-loop is multi staged and the output continously decreases in size, one can even "compress" the data, by packing an array of orgMaxisze/outputSize subunits into the unit.
  • TristanBall 4y ago
    Do you have any references for this? I'd like to understand better
    • winReInstall 4y ago
      https://hackaday.com/2018/03/02/unionize-your-variables-an-introduction-to-advanced-data-types-in-c/ https://hackaday.com/2018/03/02/unionize-your-variables-an-i... https://en.wikipedia.org/wiki/Test-driven_development https://en.wikipedia.org/wiki/Test-driven_development This is unsafe C Code by nature, but test driven development on platform can make it "safe". Now you start with a struct in the union: {inputA, inputB, inputC} and pad the intermediate struct {Padding against Overlap, resultB, result C} and end up with the result struct in the same union. {outputA, outputB, outputC} . The trick is to keep track of the state and validate the "purity" via automated tests. Then you have it all in one L1 Cache Line, pumping through a algo, no dereferences, no huge stack structures, its all there, as long sas the size of input output does not differ wildly. Remember down there its all just bytes accessed by code. There is no such concept as objects or even variables. All those mental pots to grab things out and put things back in, are artificial constructs needed by us. The machine down there, can go to work like a line cooking shiva in a trailer. And doing so and having this in view, makes it faster. PS: Pointers within the struct nullifys the advantages gained here, because every pointer is a memory load and thus "relatively" slow.
• nullc 4y ago
  How about a pinsketch: A pinsketch is a set that takes a specified amount of memory and into which you can insert and remove set members or even add whole sets in time O(memory size). You can insert an unbounded number of entries, and at any time that it has equal or fewer entries than the size you can decode the list of members. For an example usage, say I have a list of ten million IP addresses of people who have DOS attacked my systems recently. I want to send my list to you over an expensive pay as you go iridium connection, so I don't want to just send the 40MiB list since that would cost about $700. (Or 12.7 MiB if you use an optimal set encoding, or somewhat in between if you use the Golomb coded set mentioned in the OP). Fortunately you've been making your own observations (and maybe have stale data from me), and we don't expect our lists to differ by more than 1000 entries. So I make and maintain a pinsketch with size 1000 which takes 4000 bytes (1000 * 4bytes because IP addresses are 32-bits). Then to send you an update I just send it over. You maintain your own pinsketch of addresses, you subtract yours from the one I sent and then you decode it. If the number of entries in the resulting set (the number different between us) is 1000 or fewer you're guaranteed to learn the difference (otherwise the decode will fail, or give a false decode with odds ~= 1/2^(1000)). Bonus: We don't need to know in advance how different our sets are-- I can send the sketch in units as small as one word at a time (32-bits in this case) and stop sending once you've got enough to decode. Implemented that way I could send you exactly the amount of data you're missing without even knowing which entries you're missing. The sketch itself is simple: To insert an element you raise it to a sequence of odd powers (1,3,5,7...) in a finite field and add it to an accumulator for each power. The tricky part is decoding it. :P Here is an implementation I contributed to: https://github.com/sipa/minisketch/ https://github.com/sipa/minisketch/ There is a application related data-structure called an inverted bloom lookup table (IBLT) that accomplishes the same task. Its encoding and especially decoding is much faster, and it has asymptotically the same communications efficiency. However, the constant factors on the communications efficiency are poor so for 'small' in set difference (like the 1000 above) it has a rather high overhead factor, and it can't guarantee decoding. I think that makes it much less magical, though it may be the right tool for some applications. IBLT also has the benefit that it the decoder is a fun bit of code golf to implement. The encoding for IBLT is simple: take your entries, append a checkvalue (can't be a plain CRC). Then hash them with three hash-functions to obtain three locations in a hash table and xor them into those locations (removal works the same way, due to xor's self-inverse property). Decoding an IBLT works by finding entries whos check value passes (which will be true when they are the only entry in their position) and subtracting them from the table (hash them to get their other two positions, and xor them in all three). Decoding is successful when the data structure is all zeros. When the tables are big enough and have a modest amount of slack space the decoding algorithm will be successful (for it to fail there has to be an overlapping cycle, which becomes rare in sufficiently large random graphs). (this description is probably enough for a reader to make a working IBLT implementation though it omits some improvements)
• remorses 4y ago
  Struct of arrays (also called MultiArrayList in Zig), instead of storing big structs in an array you store each field in a separate array and if you need to fetch the full struct you reconstruct it from the arrays. The benefit is that the arrays items memory size is smaller and has no padding, it also increases cache locality.
  • samanator 4y ago
    Sounds like a primitive of columnar databases.
  • fb03 4y ago
    Entity-Component Systems do exactly this for better cache locality
  • FridgeSeal 4y ago
    Now I remember reading a blog post recently, about an Areta library (one of the rust ones maybe?) that were doing both: array-of-struct-of-array. The idea was to split the main arrays up into “chunks” that were structs, themselves containing rows of data (still array oriented). The idea was that you retain the cache/layout/performance benefits of SoA layout, except each chunk is already packaged up into lengths ready for pushing through SIMD. Quite a clever idea. Found it: https://www.rustsim.org/blog/2020/03/23/simd-aosoa-in-nalgebra/ https://www.rustsim.org/blog/2020/03/23/simd-aosoa-in-nalgeb...
  • celeritascelery 4y ago
    Wouldn’t that hurt locality? Since now you need to do multiple access across the entire heap to reconstruct one object.
    • DoubleFree 4y ago
      It depends. For operations or aggregates on a single field, it improves cache locality, whereas if operations act on all, or most, fields of the struct, it hurts cache locality. The exact same tradeoff differentiates OLTP (transactional/row stored) databases and OLAP (analytics/column stored) databases.
• O__________O 4y ago
  Wikipedia’s list of algorithms and data structures is pretty extensive: https://en.m.wikipedia.org/wiki/List_of_algorithms https://en.m.wikipedia.org/wiki/List_of_algorithms https://en.m.wikipedia.org/wiki/List_of_data_structures https://en.m.wikipedia.org/wiki/List_of_data_structures __________________ As for a specific algorithm, this paper covers analysis of HyperLogLog (HLL): http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf TLDR: Calculating the exact cardinality of a multiset requires an amount of memory proportional to the cardinality, which is impractical for very large data sets. Probabilistic cardinality estimators, such as the HyperLogLog algorithm, use significantly less memory than this, at the cost of obtaining only an approximation of the cardinality. The HyperLogLog algorithm is able to estimate cardinalities of > 10^9 with a typical accuracy (standard error) of 2%, using 1.5 kB of memory. Source: https://en.wikipedia.org/wiki/HyperLogLog https://en.wikipedia.org/wiki/HyperLogLog Recent HN coverage of HyperLogLog: https://news.ycombinator.com/item?id=32138790 https://news.ycombinator.com/item?id=32138790
• m12k 4y ago
  The Bag. Also known as a Multiset. I can't believe it took me so many years to learn the name of the most basic data structure imaginable - it basically makes no promises whatsoever about the structure. Think of it like a Set that allows duplicates - you can put stuff in and take stuff out, just like a bag - what more could you want?
  • chirau 4y ago
    How is that any different from a list?
    • Gregam3 4y ago
      Hopefully this java can illustrate the point if you're not a Java lover The bag essentially works like this Map<K, Collection<V>> But looks like this Bag<K, V> I use my own simple "BagSet" which works like this Map<K, Set<V>>
    • joshlemer 4y ago
      Two lists are equal only if they have the same contents and in the same order. Bags don’t have an order, they’re more like sets, so bags are equal so long as they have the same contents.
  • Gregam3 4y ago
    I love the Bag! It's so simple I use it constantly
• dicroce 4y ago
  I came up with a clever one recently. So, I had a stream of records of fixed size where I will receive exactly one per second. I needed to keep approximately two weeks of this data. I would also need to be able to query the records by time. Anyway, the idea is: use modulus on the file creation time to calculate a write position. Use the location of the current write position to locate query starts and stops. The file then has zero space overhead. Is this something known or did I actually invent something here? If this is my invention I'm open to hearing suggestions for a cool name!
  • michaelmior 4y ago
    Sounds like a ring buffer stored in a file.
• jmartrican 4y ago
  Not super obscure, but also not well known... LinkedHashMap. You get the O(1) lookups and ordered iteration.
• lscharen 4y ago
  CDAWGs. Compressed Directed Acyclic Word Graphs. They are like tries but share prefixes and suffixes of a word corpus, can be built in linear time, and since they are graphs, one can define an inner product between two CDAWGs and use them for kernel-based machine learning algorithms. https://hal-upec-upem.archives-ouvertes.fr/hal-00620006/document https://hal-upec-upem.archives-ouvertes.fr/hal-00620006/docu...
• SahAssar 4y ago
  https://en.wikipedia.org/wiki/Macaroons_(computer_science) https://en.wikipedia.org/wiki/Macaroons_(computer_science) are very interesting to me. Think of it as a JWT that you can narrow down the authorizations for without needing to communicate with a server, so if you have read permissions to all your photos you can add a caveat saying `photoid=123456` and share it, and the recipient can only read the photo 123456. The caveats can be anything, including requiring third party authentication via third-party caveats. I've implemented systems with it being validated by a lua module in nginx which worked well, but the whole concept never took off. I still think it seems like one of the most interesting authZ strategies around.
  • FridgeSeal 4y ago
    I’ve heard of these! The fly.io blog has a really cool write-up about them. Definitely an under appreciated concept. IIUC, you can even validate the “sub issued” macaroons offline, provided you know the validity of one of its ancestors up the chain. Is this correct, or am I misunderstanding?
    • SahAssar 4y ago
      I think that's correct since each added caveat builds on the previous one. I don't have the formal knowledge to understand the full underpinnings of it, but it always seemed to me (from implementing validation of them and looking at many authZ systems) that many of the sharing and delegation features of current apps would be so much neater in a macaroon based system.
    • doerig 4y ago
      here is the mentioned blog post for anyone interested (and lazy): https://fly.io/blog/api-tokens-a-tedious-survey/ https://fly.io/blog/api-tokens-a-tedious-survey/
• FridgeSeal 4y ago
  Succinct data structures are one of my favourites. The idea that we can very cleverly pack a collection of information into a much smaller form, but you can query the compressed form with good computational complexity, and without unpacking the data you need to read is amazing.
  • ignoramous 4y ago
    See Steve Hanov's classic article on the topic: http://stevehanov.ca/blog/index.php?id=120 http://stevehanov.ca/blog/index.php?id=120
• nextstepguy 4y ago
  https://en.wikipedia.org/wiki/ZigZag_(software) https://en.wikipedia.org/wiki/ZigZag_(software)
• elromulous 4y ago
  Somewhat straddling pure cs and cryptography/coding theory: one of my absolute favorites: Merkle tree. It's used for easily confirming the integrity of data. E.g. a filesystem. https://en.m.wikipedia.org/wiki/Merkle_tree https://en.m.wikipedia.org/wiki/Merkle_tree
• beached_whale 4y ago
  I find the RTree beautiful. While not as in use these days.
• api 4y ago
  I love the set reconciliation structures like the IBLT (Iterative Bloom Lookup Table) and BCH set digests like minisketch. https://github.com/sipa/minisketch https://github.com/sipa/minisketch Lets say you have a set of a billion items. Someone else has mostly the same set but they differ by 10 items. These let you exchange messages that would fit in one UDP packet to reconcile the sets. Minisketch is more costly in CPU but has deterministic guarantees. IBLTs are very fast but have a chance of failure requiring a randomized iterative procedure.
• JKCalhoun 4y ago
  A certain ePub reader on MacOS used to use a bloom filter for text search. You would decompose an ePub into pages of text and generate a bit array for the text on each page. As the user types in the search field you could often reject large portions of the document — leaving perhaps only a handful of pages where the code would only then have to drop down to the more tedious string matching algorithm. Very cool.
• cl0rkster 4y ago
  How about the current DATE formats based on the EPOCH. Hell, they knew there was nothing to it, but some backstreet performances inspired my Y2K formative years where my normal, kind, religious mother became a hoarder that destroyed everything she touched. Why can Java still not do simple date processing when even M$$ nailed that formula generations ago? Not letting devs communicate cross platform without Linux level religious arguments is ridiculous. Git this, Linus, is the EPOCH the final destination of the post-Christian measure of time (i.e. the common era)
  • TristanBall 4y ago
    I think you managed too lose me about 3 times in there.. what point are you trying to make, and what do you think Linus should do?
    • cl0rkster 4y ago
      I appreciate the comment. Is that supposed to matter to me? What is your purpose?
      • cl0rkster 4y ago
        I think Linus should do what he did when surveillance by horrific regimes came up in interview. Did the NSA force you to introduce backdoors?
      • cl0rkster 4y ago
        Also... I have daddy issues. You're lack of approval makes me want to support Donald Trump. JK... it'd be that easy to destroy your politics, though
    • cl0rkster 4y ago
      I've sought out an isolated community of intellectuals that I respect if I actually exist at all... Your -1 is cute... But perhaps engage someone less intelligent than you who is genuinely trying so others who believe that everything ultimately ends in a violent last stand... Perhaps engage me in a dead thread without your timing advance
• Gravityloss 4y ago
  Don't know if it fills the criteria, but some very basic concept: Circular arrays. This is great for live updated time series data: you never have to expand your arrays, allocate memory etc. It is extremely fast, predictable and resource efficient.
  • Retr0id 4y ago
    Also known as ring buffers
• hackarama 4y ago
  Quadrupley linked lists
• strawhatguy 4y ago
  I actually got to use a k-d tree before, I was naïvely brute forcing tiles together according to their 2d positions, the tiles being part of a larger image, and it was perfect. Would run out of memory on a 96gb machine before, after it could process the tiles as quick as they came in from the camera, only a couple held in memory at a time. When you have the right data structure, man it’s like night and day performance!
• apgwoz 4y ago
  Good old Calendar Queues: https://en.m.wikipedia.org/wiki/Calendar_queue https://en.m.wikipedia.org/wiki/Calendar_queue These things are common in discrete event simulation, but, are useful anytime you have a time based queue.
• philosopher1234 4y ago
  Linked list but where each entry in the list is fixed size array. O(1) inserts into the array. If the array fills you split it into two in the linked list. Amortizes the cost of traversing list pointers.
• simonpure 4y ago
  The BIP buffer. It's a ring buffer compatible with APIs that don't specifically support it. It's a great fit for any network I/O and I believe Android uses it under the hood. https://www.codeproject.com/Articles/3479/The-Bip-Buffer-The-Circular-Buffer-with-a-Twist https://www.codeproject.com/Articles/3479/The-Bip-Buffer-The...
• zbentley 4y ago
  HyperLogLogs! They're extremely useful for cardinality count estimation, and support set operations. https://en.m.wikipedia.org/wiki/HyperLogLog https://en.m.wikipedia.org/wiki/HyperLogLog
  • thebigspacefuck 4y ago
    Reddit’s engineering blog has a good article of how they put HyperLogLog to use https://www.redditinc.com/blog/view-counting-at-reddit https://www.redditinc.com/blog/view-counting-at-reddit
• sam0x17 4y ago
  Years ago as part of my thesis research I created a rather obscure family of data structures called DFI Filters or DFilters for short. The work centers around indexing typed trees such as abstract syntax trees or a web browser DOM such that you can answer arbitrary queries of the form "give me the set of all descendants of node P that are of type T" in something that in practice collapses to O(1) in the number of tree nodes. There are several versions of the data structure, but the general setup is a sort of "tree of trees" where the main tree is a binary search tree organized based on the depth-first indices of the nodes in the tree being indexed, and there are links into each type-specific variant of the main tree (in other words, simplified versions of the main tree containing only one type). The key intuition behind the whole thing, and the reason I called them DFI Filters, is the fact that if you are at some particular node in a tree, and you know ahead of time the depth first indices of your node and it's siblings, you actually already know exactly how many descendents your node has based on the difference in the DFI number between your node and its depth-first successor. Then you can build a variety of indexing approaches and data structures based on this insight -- I came up with ones that do it in truly constant time but are expensive to update as an undergrad, and in grad school I was able to build a version that updates on the fly but still retains ammortized O(1) for querying and ammortized O(m) for updating where m is the size of the update. By the way if you're curious how I can get constant time when I'm returning a set of descendants, it's because I can give you the size and pointers to the first and last elements right off the bat. The link to the original paper seems to be down (looking into it), but you can find the master's thesis covering all variants here: https://github.com/sam0x17/hierarch_old/blob/master/Master's%20Project%20Paper.pdf https://github.com/sam0x17/hierarch_old/blob/master/Master's... I've been working on a rust implementation lately as well. There are a number of applications for DFilters including fast file-system searching, DOM traversal, very fast static analysis on abstract syntax trees, and more.
• lproven 4y ago
  From a prior post: The piece table. https://news.ycombinator.com/item?id=15387672 https://news.ycombinator.com/item?id=15387672 Mirror of original: https://web.archive.org/web/20160308183811/http://1017.songtrellisopml.com/whatsbeenwroughtusingpiecetables https://web.archive.org/web/20160308183811/http://1017.songt...
  • lproven 4y ago
    After that: maybe the Enfilade, from the Xanadu project: https://xanadu.com/tech/ https://xanadu.com/tech/ https://en.wikipedia.org/wiki/Enfilade_(Xanadu) https://en.wikipedia.org/wiki/Enfilade_(Xanadu)
• mcqueenjordan 4y ago
  A Patricia Merkle tree. Sometimes affectionately referred to as a Perkle tree in some large companies.
• whycombagator 4y ago
  I really like this thread, but now I am concerned which of these will show up in a future interview. Edit: forgot to add mine. Not obscure by any means but Fenwick Trees are very cool IMO https://en.m.wikipedia.org/wiki/Fenwick_tree https://en.m.wikipedia.org/wiki/Fenwick_tree
  • pmontra 4y ago
    "I remember a thread on HN about uncommon data structures. Do you also follow that site?" It could be a good answer to start bonding with the interviewer. Then nobody knows everything. Go for a reference and show that you can understand it.
• edem 4y ago
  It must be [CHAMP](https://blog.acolyer.org/2015/11/27/hamt/#:~:text=CHAMP%20stands%20for%20Compressed%20Hash,by%20Scala%20and%20Clojure%20programmers https://blog.acolyer.org/2015/11/27/hamt/#:~:text=CHAMP%20st....). Acronym for Compressed Hash-Array Mapped Prefix-tree. It is a current state of the art persistent hashtable. I'm surprised that no one mentioned this before, because it is super useful!
• hansvm 4y ago
  Succinct data structures in general are interesting. They use close to the information theoretic bound for a given problem and still support fast operations -- a decent mental model is that they're able to jump to a roughly correct place and (de)compress the data locally. A good example is a wavelet tree. Suppose you have a text of length N comprised of an alphabet with C characters and wish to execute full-text pattern searches for patterns of length P. Once the tree is created, you can do your full-text search in O(P log C) time, and you use less space than any constant multiplicative factor of the information theoretic lower bound. Note that the runtime is independent of the original string's length.
  • PartiallyTyped 4y ago
    Another example is distance oracles. A distance oracle is a two stage object, in one stage creates a cache of distances, and in the other it allows us to query the cache. The oracle gives an approximate solution to the distance between any two nodes while avoiding the quadratic memory requirement to something in order of nlogk with k query steps.
• slaymaker1907 4y ago
  I really like the splay tree. It optimizes itself during reads and writes such that it is optimal for a fixed probability distribution of accesses.
• samorozco 4y ago
  It's not a data structure but a really cool algorithm. Locality Sensitive Hashing. It allows like items to be hashed to the same value. So instead of a typical hashing functions that wants to avoid collisions this algorithm tries to optimize for collisions. https://en.wikipedia.org/wiki/Locality-sensitive_hashing https://en.wikipedia.org/wiki/Locality-sensitive_hashing
• 1024core 4y ago
  > Say you have a list of 1 million IPs that are black listed. A trivial algorithm would be to compare every element of the set with a given IP. The time complexity grows with the number of elements. In the case of IPs, you just have to make 4 comparisons (for IPv4), if you store them in a tree.
• kqr 4y ago
  Suffix trees are known to anyone who's done text search, but very neat! Fairly easy idea too: in order to allow quick substring search, build a mapping from all suffixes to documents. This is compressed as a tree, and prefix matching is done by partial traversal.
• chrsig 4y ago
  I'll add: the count-min sketch[0]. Used for streaming top-k, where the set of keys may be too large to fit in memory. It's essentially a composite of a fixed size (k) heap and a counting bloom filter. Instead of using a bit field for membership, use an integer field for tracking count. When querying: take the min of each value in the field location given by the hash functions. When updating: increment each field location given by the hash functions, take the min of new values. if the min is greater than the least value in the heap, push the updated key into the heap [0] https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch
• stevenjgarner 4y ago
  Crit-bit trees [0]. Also known as TRIES, with an interesting use described in "TRASH - A dynamic LC-trie and hash data structure", which combines a trie with a hash function [1]. Also ROPE, a string allowing for prepends, substrings, middle insertions and appends [2] [0] http://cr.yp.to/critbit.html http://cr.yp.to/critbit.html [1] https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.96.2143 https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.96.... [2] https://en.wikipedia.org/wiki/Rope_%28data_structure%29 https://en.wikipedia.org/wiki/Rope_%28data_structure%29
• 3wolf 4y ago
  A minor quibble with your use-case explanation: The advantage of a bloom filter isn't strictly time complexity. For example, a hash table would also have constant lookup time (best case), and would give a definitive answer on set membership. However, to store 1 million IPv6 addresses would take 16 MB. You can see very quickly that this would not scale very well to, say, a billion addresses stored in-memory on a laptop. With a bloom filter, we can shrink the amount of storage space required* while maintaining an acceptable, calculable false positive rate. * IP addresses actually aren't a great use case for basic bloom filters, as they're fairly storage efficient to begin with, as opposed to a url for example. Taking your example, say we need to store 1 million IP addresses in our bloom filter and we're okay with a ~1% false positive rate. Well then, if we use a bloom filter with 2^23 bits (1 MB), the optimal number of hash functions is (2^23)/(10^6)*ln(2) = 6, yielding a false positive rate of (1 - exp(-6* 10^6 /2^23))^6 = ~1.8%. So we're using 6% of the storage space, but with a nearly 2% false positive rate.
• samsquire 4y ago
  I'm trying to create a first class citizen of loops and trying to improve software responsiveness. There's two ideas: concurrent loops and userspace scheduling and preemption. Nested loops can be independently scheduled. I wrote a M:N userspace scheduler[2] and it does something simple. You can interrupt a thread that is in a hot loop by changing its limit variable to the end. You don't need to slow down a hot loop by placing an if statement or checking if X number of statements executed. (Many runtimes do this to implement scheduling and you don't need to do it this way) Golang schedules away from a goroutine by checking during stack expansion if the thread has used its timeslice. I think this simple observation is really powerful. The critical insight is that frontend performance can be drastically improved by reducing latency from the user's perspective. Did you ever notice that the cancel button rarely cancels immediately? Or resizing an image is slow and gives no feedback or encrypting gives no feedback? By having a watching thread interrogate the output buffer, we can create GUIs that visually do things and provide observability to what the computer is doing. Imagine watching a resize operation occur in real time. Or encryption. Or network communication. One of my ideas of concurrent loops is "cancellation trees"[1], if you model every behaviour of a piece of software as a tree of concurrent loops that are reentrant - as in they never block and each call is a loop iteration of a different index, you can create really responsive low latency software. If you cancel a branch of the tree, you can cancel all the loops that are related to that branch. It's a bit like a tree of processes from PID 0 or loops as lightweight green threads/goroutines. So as you're moving around in your text editor or browser, if you invalidate the current action - such as press ESCAPE while Intellisense is trying to find related code, you can interrupt all the loops that fanned out from that GUI operation. Telling the computer to stop doing what it is doing and observability are two key weaknesses of modern computing. GUIs do not always accurately communicate what the computer is doing and you usually need to wait for the computer to finish before it shows you what it is doing. I am sure the cancellation token could be extended to follow this idea. If you liked this comment, check out my profile to links to my ideas documents. 1: https://github.com/samsquire/ideas4/blob/main/README.md#120-cancellation-trees https://github.com/samsquire/ideas4/blob/main/README.md#120-... 2: https://github.com/samsquire/preemptible-thread https://github.com/samsquire/preemptible-thread
• jcadam 4y ago
  How about the R-Tree, used for accessing/searching spatial data: https://en.wikipedia.org/wiki/R-tree https://en.wikipedia.org/wiki/R-tree Maybe not so obscure if you've worked in the geospatial realm. I actually had a job interview once that asked me to implement an R-Tree from scratch in C++ as a homework assignment - I didn't get that job :)
• CharanSriram 4y ago
  This isn’t so much a data structure than an implementation of one, but map-represented trees are great. For context, they were used by Figma to represent its scene-graph (https://www.figma.com/blog/how-figmas-multiplayer-technology-works/ https://www.figma.com/blog/how-figmas-multiplayer-technology...). Essentially, it’s a way to represent a normal tree as a map; keys of the map represent individual nodes on the trees, and one key “ROOT” points to the rootmost node. Each node is connected via the following relationship: parents have an unordered set of their children’s keys (not the actual node reference) and children know their parent’s key. Children also maintain a property to track their index using a technique called fractional indexing. What’s great about this data structure is that you have O(1) transformations for most parts. If you need to change a node’s property, height for instance, (assuming this is a design tool or something), all you need is that nodes key. If you need to reposition a node under a new parent, simply remove the key from the parent’s set, change the node’s parent key, and update the index. This structure plays well with collaborative apps too as most edits to the tree are O(1)— edits are swift and can be communicated to other collaborative instances quite simply with small payloads. Last thing I’ll touch on is fractional indexing. Very crudely put, it forces children nodes to track their position in a list via an “index” that can be a normal float. To reposition a child node, you first find its neighbors and average their indices to find a new index. Ordering the list is a sort from smallest indexes to largest. In an example, say we had 3 nodes A, B, and C. A’s index is 0.1, B’s is 0.3, and C’s is 0.5. To insert an element D between A and B, I average A and B’s index (0.2), set that as the index of D and insert it into the parent node’s children set. At render, the set is ordered and we find A, D, B, C. Shameless plug, but I’m using these techniques to build a multi-framework mobile app builder at phazia.com :). I love nerding out about these things so thanks for the chance to do so @op.
• jonathan-kosgei 4y ago
  Time complexity doesn't seem like a great reason to use a bloom filter. Why not just check if the IP is in a set? Set membership is supposed to be O(1). The reason to use a bloom filter would be to save space.
• kelseyfrog 4y ago
  I am enamored by data structures in the sketch/summary/probabilistic family: t-digest[1], q-digest[2], count-min sketch[3], matrix-sketch[4], graph-sketch[5][6], Misra-Gries sketch[7], top-k/spacesaving sketch[8], &c. What I like about them is that they give me a set of engineering tradeoffs that I typically don't have access to: accuracy-speed[9] or accuracy-space. There have been too many times that I've had to say, "I wish I could do this, but it would take too much time/space to compute." Most of these problems still work even if the accuracy is not 100%. And furthermore, many (if not all of these) can tune accuracy to by parameter adjustment anyways. They tend to have favorable combinatorial properties ie: they form monoids or semigroups under merge operations. In short, a property of data structures that gave me the ability to solve problems I couldn't before. I hope they are as useful or intriguing to you as they are to me. 1. https://github.com/tdunning/t-digest https://github.com/tdunning/t-digest 2. https://pdsa.readthedocs.io/en/latest/rank/qdigest.html https://pdsa.readthedocs.io/en/latest/rank/qdigest.html 3. https://florian.github.io/count-min-sketch/ https://florian.github.io/count-min-sketch/ 4. https://www.cs.yale.edu/homes/el327/papers/simpleMatrixSketching.pdf https://www.cs.yale.edu/homes/el327/papers/simpleMatrixSketc... 5. https://www.juanlopes.net/poly18/poly18-juan-lopes.pdf https://www.juanlopes.net/poly18/poly18-juan-lopes.pdf 6. https://courses.engr.illinois.edu/cs498abd/fa2020/slides/20-lec.pdf https://courses.engr.illinois.edu/cs498abd/fa2020/slides/20-... 7. https://people.csail.mit.edu/rrw/6.045-2017/encalgs-mg.pdf https://people.csail.mit.edu/rrw/6.045-2017/encalgs-mg.pdf 8. https://www.sciencedirect.com/science/article/abs/pii/S002002551000397X https://www.sciencedirect.com/science/article/abs/pii/S00200... 9. It may better be described as error-speed and error-space, but I've avoided the term error because the term for programming audiences typically evokes the idea of logic errors and what I mean is statistical error.
• nathas 4y ago
  Hashed time wheels: https://blog.acolyer.org/2015/11/23/hashed-and-hierarchical-timing-wheels/ https://blog.acolyer.org/2015/11/23/hashed-and-hierarchical-... Great for short-lived values in a cache that are frequently accessed. If all of your values always have the same expiration period (i.e. expires at insert time + N period) then it's super efficient. More or less you have an array with a head and tail. Every "tick" (usually each second but you can customize it) you move the read pointer ahead by 1 array slot. The tail is then evicted. If you have a highly accessed part of your code, you can be lazy and avoid using an extra thread and just tick ahead the read pointer when the time changes.
• demindiro 4y ago
  This isn't a data structure technically but I find it clever: ZFS' space maps. It keeps track of which space is allocated by logging every allocation and deallocation. When initializing an allocator, which can be implemented in any way, this log is replayed. If the map becomes too big it is rewritten so it is equivalent to the old map but with no redundant entries.
• darksaints 4y ago
  The Rete algorithm / graph network, and its variants. You can evaluate infinite rules, with automatic incremental updates (no re-evaluation if not necessary), with O(1) time complexity. The tradeoff being that you have to hold a very large graph which represents your rule set in memory.
• foxyv 4y ago
  For my final project in college Data Structures I wrote a linked hexagonal data structure. To index it I used two different solutions. One was to use a base-6 system to encode a series of hops in the six different directions. Another was to have two coordinates which indicated how far to traverse in two directions to reach the target hex cell.
• cratermoon 4y ago
  Skip lists.
• XCSme 4y ago
  Not a data structure, and not really obscure, but I am still amazed by the concept of solving DP (dynamic-programming) problems in O(log N) instead of O(N) time by writing the solution as a Fast Matrix Exponentiation equation: https://www.geeksforgeeks.org/matrix-exponentiation/ https://www.geeksforgeeks.org/matrix-exponentiation/
• crazybob123 4y ago
  FST: Finite State Transducer. Widely used inside search (Lucene), DB powering prefix, fuzzy search
• vnorilo 4y ago
  One of my favourites is treap [1], which doubles as a great excuse to forget how to balance binary trees. It is similarly "probably efficient" as HAMT, mentioned in other comments; both require a well-behaving distribution in the hash function. 1: https://en.m.wikipedia.org/wiki/Treap https://en.m.wikipedia.org/wiki/Treap
• jll29 4y ago
  Associative memory? Store data in them and they will never complain they are full, but they may "forget" instead. Querying them with slightly wrong keys, they'll auto-correct the keys as long as they are not overloaded. Binary fuse filters? (Xor|Bloom) filters on steroids. Non-deterministic finite state transducers? Reversible, more elegant and more powerful version of non-deterministic finite state recognizers (transitions are labelled with two outputs, which can be interpreted as inputs versus outputs, but these roles can be swapped as they are symmetric). Ropes? What, you are still using strings? Dude, please stop writing that newbie editor. Caches with Time aware least recently used (TLRU) or Segmented LRU (SLRU) cache replacement strategies (Oh, you thought Least recently used (LRU) was cool?)
• vojtah 4y ago
  Fenwick Tree: https://cp-algorithms.com/data_structures/fenwick.html https://cp-algorithms.com/data_structures/fenwick.html
• abetusk 4y ago
  Succinct Data Structures [0] [1]. It encompass many different underlying data structure types but the overarching idea is that you want small data size while still keeping "big O" run time. In other words, data structures that effectively reach a 'practical' entropy lower bound while still keeping asymptotic run time. [0] https://en.wikipedia.org/wiki/Succinct_data_structure https://en.wikipedia.org/wiki/Succinct_data_structure [1] https://github.com/simongog/sdsl-lite https://github.com/simongog/sdsl-lite
• cdelahousse 4y ago
  Min-Max Heaps Think of them as double ended priority queues. O(n) construction with O(lgN) mutations. Both the min and max elements are quick to get O(1). The paper is short and the data structure is elegant. I read it a few years ago in uni and made me appreciate how greatly useful can be implemented very simply. https://dl.acm.org/doi/pdf/10.1145/6617.6621 https://dl.acm.org/doi/pdf/10.1145/6617.6621
• pklausler 4y ago
  Briggs-Torczon sets of small integers (0 <= x < N) deserve to be better known. (Set up two N-element arrays "member" and "index" of ints and an elementCount; set elementCount to zero. You don't have to initialize the arrays if you can live with some valgrind grumbling. The leading "elementCount" entries in "member" are the current members of the set, unordered, and for each of those values x, index[x] is its index in "members". Then isInSet(x) = index[x] >= 0 && index[x] < elementCount && member[index[x]] == x and addToSet(x) = isInSet(x) || (member[index[x] = elementCount++] = x) and rmFromSet() is left as an exercise.)
• fatih-erikli 4y ago
  - Prefix tree (also known as a trie) - Splaytree (Self balancing tree optimized for querying fast for the frequently accessed nodes)
• the-alchemist 4y ago
  Very cool stuff... To take advantage of all these, where would one go to ask "what's the best data structure to use to implement X, Y, and Z?" Is there a stackoverflow tag or something like that that folks use??
• deleted 4y ago
  [deleted]
• MaysonL 4y ago
  Text ropes: https://iq.opengenus.org/rope-data-structure/ https://iq.opengenus.org/rope-data-structure/
• whateveracct 4y ago
  A lazy, immutable rose tree This article shows some really cool stuff you can do with it https://www.well-typed.com/blog/2019/05/integrated-shrinking/ https://www.well-typed.com/blog/2019/05/integrated-shrinking...
• openfuture 4y ago
  I left this thread alone since it is a rabbithole but I was surprised how monotonous it ended up being. The datastructure I am quite interested in these days is 'concept lattices' and object-property (bi)graphs. Although I am less interested in the dynamic side atm and am more thinking about representation of data while being exchanged.
• victor106 4y ago
  Algorithms and Data Structures for Massive Datasets By Manning. Just started reading this. It looks interesting
• KETpXDDzR 4y ago
  Locality-sensitive hashing[0] is similar to bloom filters. It's a hashing function that hashes values into buckets. One interesting application is neutral networks with sparse inputs. [0] https://en.m.wikipedia.org/wiki/Locality-sensitive_hashing https://en.m.wikipedia.org/wiki/Locality-sensitive_hashing
• talideon 4y ago
  Skip lists: 90% of the benefits of more complex tree data structures, with a fraction of the complexity.
• nunez 4y ago
  patricia tries are cool. used them once while working on an infrastructure management tool; makes searching word dictionaries very efficient. also love the Option<T> struct with pattern matching that all of the hippie-dippie functional languages seem to like lol
• fn1 4y ago
  The disruptor ring-buffer for providing lock-free parallelization for multiple readers/writers: https://martinfowler.com/articles/lmax.html https://martinfowler.com/articles/lmax.html