Do folk genuinely get asked problems like that in technical interviews these days? I can&#x27;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?

I recently learned about monotonic stacks thanks to this LeetCode problem: <a href="https:&#x2F;&#x2F;leetcode.com&#x2F;problems&#x2F;sum-of-total-strength-of-wizards&#x2F;" rel="nofollow">https:&#x2F;&#x2F;leetcode.com&#x2F;problems&#x2F;sum-of-total-strength-of-wizar...</a>I feel like they&#x27;re quite possibly the most deceptively simple data structure I&#x27;ve yet to encounter. That is to say that for me at least there was&#x2F;is a wide gulf between simply understanding what the data structure is (doesn&#x27;t get much simpler than a stack!) and when&#x2F;how to actually apply it.

You may be interested in the work myself and some coauthors have done on data structures and algorithms for streaming aggregation. GitHub repo for the code, which high level descriptions of their properties and pointers to papers: <a href="https:&#x2F;&#x2F;github.com&#x2F;IBM&#x2F;sliding-window-aggregators" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;IBM&#x2F;sliding-window-aggregators</a>

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.

I got stung by this for a test engineering role. Apparently implementing them from scratch is a pre-req to building out test infrastructure!

I wouldn&#x27;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.<a href="https:&#x2F;&#x2F;leetcode.com&#x2F;discuss&#x2F;general-discussion&#x2F;931977&#x2F;beginner-friendly-guide-to-trie-tutorial-practice-problems" rel="nofollow">https:&#x2F;&#x2F;leetcode.com&#x2F;discuss&#x2F;general-discussion&#x2F;931977&#x2F;begin...</a>

There&#x27;s not much about it online. They do mention it in the docs, they call this &quot;prefix compression&quot; [0], so you can search for that. This article describes it [1], although it is somewhat high level.They only use this for indexes. It works really well for internal mongo ids (they all start with timestamps if I remember correctly). It also works well for compound indexes. Pro tip: for compound indexes always go from low-cardinality attribute to high-cardinality attribute to get the best results from prefix compression (it&#x27;s also good for speed of queries).[0] <a href="https:&#x2F;&#x2F;www.mongodb.com&#x2F;docs&#x2F;manual&#x2F;reference&#x2F;glossary&#x2F;#std-term-prefix-compression" rel="nofollow">https:&#x2F;&#x2F;www.mongodb.com&#x2F;docs&#x2F;manual&#x2F;reference&#x2F;glossary&#x2F;#std-...</a>[1] <a href="https:&#x2F;&#x2F;medium.com&#x2F;swlh&#x2F;mongodb-indexes-deep-dive-understanding-indexes-9bcec6ed7aa6" rel="nofollow">https:&#x2F;&#x2F;medium.com&#x2F;swlh&#x2F;mongodb-indexes-deep-dive-understand...</a>

Do you have any documentation about how tries are used in mongo indexes? Or could you point to the source?

Even though a trie is pretty standard and expected (to be known) these days, I will vote for this. It was my first deep dive into more exotic data structures after an interview question about implementing T9 that stumped me many years ago.<a href="https:&#x2F;&#x2F;github.com&#x2F;Azeem112&#x2F;tries-T9-Prediction" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;Azeem112&#x2F;tries-T9-Prediction</a>

Indeed, but it took a while for me to appreciate Tries.Originally, i thought &quot;nice idea&quot;, but I rarely ever encountered a problem where I really needed a prefix tree.But while reading into HAMT and Clojure&#x27;s datastructure implementations, it dawned on me that prefix trees aren&#x27;t only useful for strings (or arbitrary byte sequences): Hashes in a dictionary, for example, are sequences of bits, too. And the design of a HAMT is exactly such that it doesn&#x27;t concern itself with bytes but any blocks of N bits (determined by the branching factor; i.e. a factor of 32 implies 6-bit-blocks). And if you know the length of each sequence (hash), you know the maximum Trie depth, which also works for you, not against you.That was rather eye opening for me at the time.

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&#x2F;iOS Mach-O format are compressed using tries).We have an article with some animations that illustrate the concept in case anyone&#x27;s interested [0].[0] <a href="https:&#x2F;&#x2F;github.com&#x2F;pyroscope-io&#x2F;pyroscope&#x2F;blob&#x2F;main&#x2F;docs&#x2F;storage-design.md" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;pyroscope-io&#x2F;pyroscope&#x2F;blob&#x2F;main&#x2F;docs&#x2F;sto...</a>

Is it the same thing? I&#x27;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.

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 &quot;friend&quot;.

How do you implement it? Do you do a scan with every insert or do you hash or use a tree for indexing?

Sounds similar to the behavior of Guava&#x27;s LoadingCache. If you try to fetch a key that&#x27;s not in the cache, the supplied callback is used to fetch it. While the value is being loaded, other threads can access the cache concurrently, but if a second thread asks for the same key, it will wait for the first load to complete instead of redundantly fetching the same value.

There is a great (always busy) sandwich shop in Boston called Darwin&#x27;s that I used to go to a lot that worked that way. When a customer placed an order they would call down the long line, &quot;anyone else for an X?&quot;, then make make the sandwiches with the inner loop over sandwich and the outer loop over ingredient.I took much delight in the efficiency as well as the incentive structure: If you are not picky and you can help us increase throughput then we&#x27;ll reduce your latency :)

Sounds like a priority queue with a sidecar hashmap or some kind of notify mechanism for when &quot;order&#x27;s up!&quot;

Reminds me a little bit of a &quot;delta queue&quot; used in efficient discrete time based scheduling, for example, in an OS scheduler. Imagine you want to implement a scheduler that accepts jobs and runs them at some point in the future. Instead of keeping a list and scanning through the list at each clock tick, implement a linked list with (time delta, job) at each node. Now, handling a tick() simply requires decrementing the head node and popping items until you see a non-zero delta. Inserting is done like a normal list, except as you iterate through the list, you decrement the desired time interval as you see deltas in the list. It goes like this:insert(job1, 1)
# (job1, 1) -&gt; null
insert(job2, 1)
# (job1, 1) -&gt; (job2, 0) -&gt; null
insert(job3, 2)
# (job1, 1) -&gt; (job2, 0) -&gt; (job3, 1) -&gt; null
tick()
-&gt; job1, job2
# (job3, 0) -&gt; null
tick
-&gt; job3
# -&gt; null

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&#x27;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&#x27;s totally true :)

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.<a href="https:&#x2F;&#x2F;en.m.wikipedia.org&#x2F;wiki&#x2F;Ackermann_function" rel="nofollow">https:&#x2F;&#x2F;en.m.wikipedia.org&#x2F;wiki&#x2F;Ackermann_function</a>

I&#x27;ve been told to consider it constant for all practical purposes

Use the idea[1] at work to make large NP-complete problems more tractable by breaking the problem up into disjoint subsets.[1] doesn&#x27;t implement the inverse-ackermann algorithm but still implemented as union&#x2F;find.

aka &quot;union find&quot; — some other comments in the thread call it that

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.<a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Disjoint-set_data_structure" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Disjoint-set_data_structure</a>

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.

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.

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.

<a href="https:&#x2F;&#x2F;en.m.wikipedia.org&#x2F;wiki&#x2F;Nested_set_model" rel="nofollow">https:&#x2F;&#x2F;en.m.wikipedia.org&#x2F;wiki&#x2F;Nested_set_model</a>?

Nice!  I&#x27;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.

I made <a href="https:&#x2F;&#x2F;github.com&#x2F;mamcx&#x2F;tree-flat" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;mamcx&#x2F;tree-flat</a> as flattened stored tree in pre-order that allows for very fast iterations even for childs&#x2F;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: <a href="https:&#x2F;&#x2F;tablam.org" rel="nofollow">https:&#x2F;&#x2F;tablam.org</a>.

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.<a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Category:Probabilistic_data_structures" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Category:Probabilistic_data_st...</a>

Never heard of this one until it came up in a google interview. Totally botched it. I couldn&#x27;t think of any way to do it to their liking that doesn&#x27;t require a dynamic cast.

rope - <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Rope_%28data_structure%29" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Rope_%28data_structure%29</a>
skip list - <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Skip_list" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Skip_list</a>

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 &quot;[...] 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).&quot; [1].[1] A Conflict-Free Replicated JSON Datatype (<a href="https:&#x2F;&#x2F;arxiv.org&#x2F;abs&#x2F;1608.03960" rel="nofollow">https:&#x2F;&#x2F;arxiv.org&#x2F;abs&#x2F;1608.03960</a>) b Martin Kleppmann and Alastair R. Beresford.

Three of my favorite probabilistic data structures are: Skip Lists, Bloom Filters, and SimHashes.

Very interesting! Sounds similar to a segment tree: <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Segment_tree" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Segment_tree</a>

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.

Very interested in your idea. How does concurrent updates work with the augumented trees? I have been thinking about the same for a while something like CouchDB but segment aggregations (monoid) augumented so we can do interval queries over time too. But the only thing bothering is augumented trees are notorious of contention on concurrent updates. Do you have any ideas on merging back if we have multiple versions of augumented trees.

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, <a href="https:&#x2F;&#x2F;www.scott-a-s.com&#x2F;files&#x2F;vldb2019_fiba.pdf" rel="nofollow">https:&#x2F;&#x2F;www.scott-a-s.com&#x2F;files&#x2F;vldb2019_fiba.pdf</a>Slides from the conference talk: <a href="https:&#x2F;&#x2F;www.scott-a-s.com&#x2F;files&#x2F;vldb2019_fiba_slides.pdf" rel="nofollow">https:&#x2F;&#x2F;www.scott-a-s.com&#x2F;files&#x2F;vldb2019_fiba_slides.pdf</a>

A variation on 32 wide Bagwell hashed tries last time I looked. Scala was too. Those are much more annoying to implement without garbage collection fwiw.

If I&#x27;m not mistaken, Clojure&#x27;s data structures are (or used to be) implemented using finger trees.

Finger Trees Explained Anew is a great derivation of the data structure: <a href="https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=ip92VMpf_-A" rel="nofollow">https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=ip92VMpf_-A</a>

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 &quot;block list&quot; structure.In this structure each block has a particular width and they&#x27;re all stacked side by side.I want to perform a query, &quot;which box is at position X&quot;. 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)<a href="https:&#x2F;&#x2F;andrew.gibiansky.com&#x2F;blog&#x2F;haskell&#x2F;finger-trees&#x2F;" rel="nofollow">https:&#x2F;&#x2F;andrew.gibiansky.com&#x2F;blog&#x2F;haskell&#x2F;finger-trees&#x2F;</a>

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.

You can do this without a linked list and it can be quite performant, like python’s newest dictionary implementation (appeared around Python 3.6 or 3.7 from memory).

Modulo the snark, you&#x27;re completely right.  Iteration order = insertion order is super valuable for a bunch of reasons (this one included).

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&#x27;t know why this is important then maybe you haven&#x27;t worked on large systems that undergo rigorous evaluation)

Hence the &quot;simple but good&quot;.  It&#x27;s not really obscure, but also not on the common path.  I&#x27;ve lost track of the number of times I&#x27;ve pointed this one out to a colleague or student.

Why would Linked Hash Map be a obscure one? It&#x27;s been a part of java collection framework for over 20y. It&#x27;s a standard for LRU caches as well.

Linked Hash&#x2F;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.

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.

All probabilistic structures are fascinating to me. I&#x27;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 :)

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.

I&#x27;ve used quadtrees for some cool stuff I can&#x27;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.

Yep, that&#x27;s what I used it for! Intersections. Hard to make concurrent though. Ended up with concurrent map backed geohash.

Yes, R-tree turned out to be a godsend when working with larger geospatial data and calculating intersections.

Structures good for Geospatial information like rtrees, quadtrees.<a href="https:&#x2F;&#x2F;en.m.wikipedia.org&#x2F;wiki&#x2F;R-tree" rel="nofollow">https:&#x2F;&#x2F;en.m.wikipedia.org&#x2F;wiki&#x2F;R-tree</a>Also concurrent data structures.<a href="https:&#x2F;&#x2F;youtu.be&#x2F;jcqGSehrMGU" rel="nofollow">https:&#x2F;&#x2F;youtu.be&#x2F;jcqGSehrMGU</a>

+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, …)

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.

I second this.. very useful for vector NLP and other ML tasks.

HNSW, or Hierarchical Navigable Small World is a graph data structure for approximate nearest neighbor search of vectors.<a href="https:&#x2F;&#x2F;arxiv.org&#x2F;abs&#x2F;1603.09320" rel="nofollow">https:&#x2F;&#x2F;arxiv.org&#x2F;abs&#x2F;1603.09320</a>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 <a href="http:&#x2F;&#x2F;ann-benchmarks.com&#x2F;" rel="nofollow">http:&#x2F;&#x2F;ann-benchmarks.com&#x2F;</a> for a comparison. HNSW is not “the best” but it’s easy to understand and is quite effective.

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&#x27;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:
<a href="https:&#x2F;&#x2F;github.com&#x2F;RoaringBitmap&#x2F;RoaringBitmap" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;RoaringBitmap&#x2F;RoaringBitmap</a>

I often recommend this book, RTCD, as a &quot;better intro to data structures and algorithms&quot; (sometimes as &quot;the best&quot;).
The advice often falls on deaf ears, unfortunately.

Seconding the RTCD recommendation. Handy code examples, and my favorite part is that the book is real-world-performance-conscious (hence the &quot;real-time&quot; in the title).

It&#x27;s a stellar book. I work on a commercial realtime physics engine, the &quot;orange book&quot; is practically required reading here.

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 &quot;data structures&quot; book which is very much in theme with this thread.[1] <a href="https:&#x2F;&#x2F;www.amazon.com&#x2F;Real-Time-Collision-Detection-Interactive-Technology&#x2F;dp&#x2F;1558607323" rel="nofollow">https:&#x2F;&#x2F;www.amazon.com&#x2F;Real-Time-Collision-Detection-Interac...</a>

To an extent, the B-Tree data structure (and its variants) are cache oblivious. They smoothly improve in performance with more and more cache memory, and can scale down to just megabytes of cache over terabytes of disk.The issue is that the last tree level tends to break this model because with some caching models it is &quot;all or nothing&quot; and is the biggest chunk of the data by far.There are workarounds which make it more truly cache oblivious. How often this is used in production software? Who knows...

Cache-obliviousness is an important part of the whole array-of-structs vs structs-of-arrays. One of the advantages of the struct-of-arrays strategy is that it is cache-oblivious.

Cache oblivious data structures are absolutely used in every serious database.From what I remember&#x2F;can find online (don&#x27;t take this as a reference):
B-tree: relational DB, SQLite, Postgres, MySQL, MongoDB.
B+-tree: LMDB, filesystems, maybe some relational DBs.
LSM trees (Log-structured merge tree, very cool) for high write performance: LevelDB, Bigtable, RocksDB, Cassandra, ScyllaDB, TiKV&#x2F;TiDB.
B-epsilon tree: TokuDB, not sure if it exists anymore.
COLA (Cache-oblivious lookahead array): I don&#x27;t know where it&#x27;s used.Maybe modern dict implementations can qualify too, e.g. Python.

Yes, LSM trees are specifically designed with this propery in mind.

Does anyone actually use cache-oblivious data structure in practice? Not, like, &quot;yes I know there&#x27;s a cache I will write a datastructure for that&quot;, that&#x27;s common, but specifically cache-oblivious data structures?People mention them a lot but I&#x27;ve never heard anyone say they actually used them.

Wouldn&#x27;t you at least be looking at nlog(n) for the sort in the merge join?

Do we mean different things by &quot;merge join&quot; and &quot;nested loop join&quot; ? For me &quot;merge join&quot; is O(n) (but requires the data to be sorted by key) whereas &quot;nested loop join&quot; is O(n^2).

This series of blog posts explains this sqrt behaviour quite nicely, covering both theory (including black holes) and practice:<a href="http:&#x2F;&#x2F;www.ilikebigbits.com&#x2F;2014_04_21_myth_of_ram_1.html" rel="nofollow">http:&#x2F;&#x2F;www.ilikebigbits.com&#x2F;2014_04_21_myth_of_ram_1.html</a>

If its stored far away enough re-doing the calculation is faster. Depending on how much accuracy you need you might as well load a 2022-07-22 07:26:34 earth and have that guy on HN evaluate his thoughts all over again.

The main difficulty with growing computing devices in three dimensions is cooling. All that heat has to be somehow carried away. It&#x27;s already difficult with 2D devices. One would have to incorporate channels for cooling liquids into the design, which takes a bite out of the gains from 3D.<a href="https:&#x2F;&#x2F;www.anandtech.com&#x2F;show&#x2F;12454&#x2F;analyzing-threadripper-cooling-big-base-cooling-wins" rel="nofollow">https:&#x2F;&#x2F;www.anandtech.com&#x2F;show&#x2F;12454&#x2F;analyzing-threadripper-...</a>

How do you accurately include those sqrt(n)’s in your analysis?

&gt; In essence, as data size &#x27;n&#x27; grows, the random access time grows as sqrt(n), because that&#x27;s the radius of the growing circle with area &#x27;n&#x27;.I was about to write a comment suggesting that if we made better use of three dimensional space in constructing our computers and data storage devices, we could get this extra latency factor down to the cube root of n.But then, I decided to imagine an absurdly large computer. For that, one has to take into account a curious fact in black hole physics: the radius of the event horizon is directly proportional to the mass, rather than, as one might expect, the cube root of the mass [1]. In other words, as your storage medium gets really _really_ big, you also have to spread it out thinner and thinner to keep it from collapsing. No fixed density is safe. So, in fact, I think the extra factor for latency in galactic data sets is neither the square root nor cube root, but n itself![1] <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Schwarzschild_radius" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Schwarzschild_radius</a>

Doing a decent job of analysis would include the sqrt(n) memory access factor. Asymptotic analysis ignores constant factors, not factors that depend on data size. It&#x27;s not so much &#x27;on paper&#x27; as &#x27;I decided not to add a significant factor to my paper model&#x27;.Cache oblivious algorithms attempt to make the memory access term insignificant so you could continue to ignore it. They are super neat.

<a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Galactic_algorithm" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Galactic_algorithm</a>

This implementation and associated paper improve the cache locality to make the algorithm more competitive <a href="https:&#x2F;&#x2F;github.com&#x2F;dmalhotra&#x2F;pvfmm" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;dmalhotra&#x2F;pvfmm</a>They compare solving toy problems with different methods here <a href="https:&#x2F;&#x2F;arxiv.org&#x2F;pdf&#x2F;1408.6497.pdf" rel="nofollow">https:&#x2F;&#x2F;arxiv.org&#x2F;pdf&#x2F;1408.6497.pdf</a>But as you mention, this is just fiddling with constants, and it still may be too costly for your problem

Honestly, that is not too uncommon. For top level algorithm choice analysis, &quot;rounding&quot; O(log(n)) to O(1), and O(n*log(n)) to O(n), is often pretty reasonable for algorithm comparison, even though it is strictly incorrect.It is not uncommon for a simple O(n*log(n)) algorithm to beat out a more complex O(n) algorithm for realistic data sizes. If you &quot;round&quot; them to both O(n), then picking the simpler algorithm because the obvious choice, and can easily turn out to have better perf.

I spent a long time looking at an algorithm for long range force calculations called the Fast Multipole Method which is O(N) and found that practically it couldn&#x27;t compete against an O(N log N) method we used that involved FFTs because the coefficient was so large that you&#x27;d need to simulate systems way bigger than is feasible in order for it to pay off because of cache locality, etc.

This is similar to what I&#x27;m working on.I am working on machine sympathetic systems. One of my ideas is concurrent loops.Nested loops are equivalent to the Nth product of the loop × loop × loop or the Cartesian product.<pre><code> for letter in letters:
 for number in numbers:
 for symbol in symbols:
 print(letter + number + symbol)
</code></pre>
If len(letters) == 3, len(numbers) == 3, len(symbols) == 3. If you think of this as loop indexes &quot;i&quot;, &quot;j&quot; and &quot;k&quot; and they begin at 000 and go up in kind of base 3 001, 001, 002, 010, 011, 012, 020, 100 and so on.The formula for &quot;i&quot;, &quot;j&quot; and &quot;k&quot; is<pre><code> N = self.N
 for index, item in enumerate(self.sets):
 N, r = divmod(N, len(item))
 combo.append(r)
</code></pre>
So the self.N is the product number of the nested loops, you can increment this by 1 each time to get each product of the nested loops.We can load balance the loops and schedule the N to not starve the outer loops. We can independently prioritize each inner loop. If you represent your GUI or backend as extremely nested loops, you can write easy to understand code with one abstraction, by acting as if loops were independent processes.So rather than that sequence, we can generate 000, 111, 222, 010, 230, 013 and so on.Load balanced loops means you can progress on multiple items simultaneously, concurrently. I combined concurrent loops with parallel loops with multithreading. I plan it to be a pattern to create incredibly reactive frontends and backends with low latency to processing. Many frontends lag when encrypting, compressing or resizing images, it doesn&#x27;t need to be that slow. IntelliJ doesn&#x27;t need to be slow with concurrent loops and multithreading.See <a href="https:&#x2F;&#x2F;github.com&#x2F;samsquire&#x2F;multiversion-concurrency-control" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;samsquire&#x2F;multiversion-concurrency-contro...</a>Loops are rarely first class citizens in most languages I have used and I plan to change that.I think I can combine your inspiration of gray codes with this idea.I think memory layout and data structure and algorithm can be 3 separate decisions. I am yet to see any developers talk of this. Most of the time the CPU is idling waiting for memory, disk or network. We can arrange and iterate data to be efficient.

I decided to try implement get_gray_xy. I am wondering how you can generalise it to any number of loops and apply it to nested loops of varying sizes, that is if you have three sets and the sizes are 8, 12, 81.Wikipedia says graycodes can be found by num ^ (num &gt;&gt; 1)<pre><code> a = [1, 2, 3, 4]
 b = [2, 4, 8, 16]
 indexes = set()
 correct = set()

 print(&quot;graycode loop indexes&quot;)
 for index in range(0, len(a) * len(b)):
 code = index ^ (index &gt;&gt; 1)
 left = code &amp; 0x0003
 right = code &gt;&gt; 0x0002 &amp; 0x0003
 
 print(left, right)
 indexes.add((left, right))
 
 assert len(indexes) == 16
 
 print(&quot;regular nested loop indexes&quot;)
 
 for x in range(0, len(a)):
 for y in range(0, len(b)):
 correct.add((x,y))
 print(x, y)
 
 
 assert correct == indexes
</code></pre>
This produces the sequence:<pre><code> graycode loop indexes
 0 0
 1 0
 3 0
 2 0
 2 1
 3 1
 1 1
 0 1
 0 3
 1 3
 3 3
 2 3
 2 2
 3 2
 1 2
 0 2
 regular nested loop indexes
 0 0
 0 1
 0 2
 0 3
 1 0
 1 1
 1 2
 1 3
 2 0
 2 1
 2 2
 2 3
 3 0
 3 1
 3 2
 3 3</code></pre>

While reading your post I kept thinking &quot;de-interleave the bits of a single counter&quot; since I have used that before to great benefit. It does suffer from issues if your sizes are not powers of two, so your grey code modification seems interesting to me. I&#x27;ll be looking in to that.FYI this also extends to higher dimensions. I once used it to split a single loop variable into 3 for a &quot;normal&quot; matrix multiplication to get a huge speedup. Unrolling the inner 3 bits is possible too but a bit painful.Also used it in ray tracing to scan pixels in Z-order, which gave about 10 percent performance improvement at the time.But yes, I must look at this grey code step to see if it makes sense to me and understand why its not helping you even with reduced cache misses.

&gt; but the algorithm didn&#x27;t get fasterCould it be branch predictor at play? <a href="https:&#x2F;&#x2F;stackoverflow.com&#x2F;questions&#x2F;11227809&#x2F;why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array" rel="nofollow">https:&#x2F;&#x2F;stackoverflow.com&#x2F;questions&#x2F;11227809&#x2F;why-is-processi...</a>

I was experimenting a while ago with something that I think is related to this.If you have a quadratic algorithm where you need to compare each pair of objects in a large array of objects, you might use a loop in a loop like this:<pre><code> for (int i = 0; i &lt; size; i++) { for (int j = 0; j &lt; size; j++) { do_something(arr[i], arr[j]); } }
</code></pre>
When this algorithm runs, it will access every cache line or memory page in the array for each item, because j goes through the whole array for each i.I thought that a better algorithm might do all possible comparisons inside the first block of memory before accessing any other memory. I wanted this to work independently of the size of cache lines or pages, so the solution would be that for each power of 2, we access all items in a position lower than that power of 2 before moving to the second half of the next power of 2.This means that we need to first compare indexes (0,0) and then (1,0),(1,1),(0,1) and then all pairs of {0,1,2,3} that haven&#x27;t yet been compared and so on.It turns out that the sequence (0,0),(1,0),(1,1),(0,1) that we went through (bottom-left, bottom-right, top-right, top-left in a coordinate system) can be recursively repeated by assuming that the whole sequence that we have done so far is the first item in the next iteration of the same sequence. So the next step is to do (0,0),(1,0),(1,1),(0,1) again (but backwards this time) starting on the (2,0) block so it becomes (2,1),(3,1),(3,0),(2,0) and then we do it again starting on the (2,2) block and then on the (0,2) block. Now we have done a new complete block that we can repeat again starting on the (4,0) block and then (4,4) and then (0,4). Then we continue like this through the whole array.As you can see, every time we move, only one bit in one index number is changed. What we have here is actually two halves of a gray code that is counting up, half of it in the x coordinate and the other half in y. This means that we can iterate through the whole array in the described way by making only one loop that goes up to the square of the size and then we get the two indexes (x and y) by calculating the gray code of i and then de-interleaving the result so that bits 0,2,4... make the x coordinate and bits 1,3,5... make y. Then we compare indexes x and y:<pre><code> for (int i = 0; i &lt; size * size; i++) { get_gray_xy(i, &amp;x, &amp;y); do_something(arr[x], arr[y]); }
</code></pre>
The result of all this was that the number of cache line&#x2F;page switches went down by orders of magnitude but the algorithm didn&#x27;t get faster. This is probably for two reasons: incremental linear memory access is very fast on modern hardware and calculating the gray code and all that added an overhead.

Is there by any chance a publicly available recording of this presentation on purely functional data structures?

I saw an amazing presentation on Purely Functional Data structures with a really approachable and understandable proof on ho w a particular structure was asymptotically constant or linear time (I believe), and then followed up by saying that in practice none of it worked as well as a mutable version because of caching and data locality.Oh well.

The ratios are mostly correct, but the absolute numbers are wrong these days. For example, memory read latency can be 45ns (not 100) with a decent DDR4 kit and data center latency can be 10us (not 500us) with infiniband.

&gt; the increasing latency&#x2F;cost of data access as the data size growsLatency Numbers Everyone Should Know <a href="https:&#x2F;&#x2F;static.googleusercontent.com&#x2F;media&#x2F;sre.google&#x2F;en&#x2F;&#x2F;static&#x2F;pdf&#x2F;rule-of-thumb-latency-numbers-letter.pdf" rel="nofollow">https:&#x2F;&#x2F;static.googleusercontent.com&#x2F;media&#x2F;sre.google&#x2F;en&#x2F;&#x2F;st...</a>

<a href="http:&#x2F;&#x2F;queue.acm.org&#x2F;detail.cfm?id=1563874" rel="nofollow">http:&#x2F;&#x2F;queue.acm.org&#x2F;detail.cfm?id=1563874</a><a href="http:&#x2F;&#x2F;deliveryimages.acm.org&#x2F;10.1145&#x2F;1570000&#x2F;1563874&#x2F;jacobs3.jpg" rel="nofollow">http:&#x2F;&#x2F;deliveryimages.acm.org&#x2F;10.1145&#x2F;1570000&#x2F;1563874&#x2F;jacobs...</a>

Cache-Oblivious Data Structures: <a href="https:&#x2F;&#x2F;cs.au.dk&#x2F;~gerth&#x2F;MassiveData02&#x2F;notes&#x2F;demaine.pdf" rel="nofollow">https:&#x2F;&#x2F;cs.au.dk&#x2F;~gerth&#x2F;MassiveData02&#x2F;notes&#x2F;demaine.pdf</a>A vaguely related notion is that naive analysis of big-O complexity in typical CS texts ignores over the increasing latency&#x2F;cost of data access as the data size grows. This can&#x27;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 &quot;rings&quot; 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&#x27;s potentially across the building somewhere in a disk array.In essence, as data size &#x27;n&#x27; grows, the random access time grows as sqrt(n), because that&#x27;s the radius of the growing circle with area &#x27;n&#x27;.Hence, a lot of algorithms that on paper have identical performance don&#x27;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.

Good! I got always fascinated by non-boolean indexing (probabilistic instead).I&#x27;ve remember having implemented an OOP indexed version of U.C. Berkeley&#x27;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.

That depends very much on how the trie is represented in memory. Something like a burst trie or HAT trie is usually very compact!

The Trie is pretty cool. I think it&#x27;s a bit obscure because the memory use can grow quite fast.

Arrays aren&#x27;t efficient when you want to add&#x2F;remove to the head. Deque in python exists so there is a data structure with constant time pop&#x2F;push to the head. And it is in fact implemented as a doubly linked list, with various optimizations: <a href="https:&#x2F;&#x2F;github.com&#x2F;python&#x2F;cpython&#x2F;blob&#x2F;v3.8.1&#x2F;Modules&#x2F;_collectionsmodule.c#L33-L78" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;python&#x2F;cpython&#x2F;blob&#x2F;v3.8.1&#x2F;Modules&#x2F;_colle...</a>.

A deque may be implemented as a linked list, but it&#x27;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.

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&#x2F;read&#x2F;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.<a href="https:&#x2F;&#x2F;docs.python.org&#x2F;3&#x2F;library&#x2F;collections.html" rel="nofollow">https:&#x2F;&#x2F;docs.python.org&#x2F;3&#x2F;library&#x2F;collections.html</a>

This doesn&#x27;t look like I remember, but this sounds right.<a href="https:&#x2F;&#x2F;lmax-exchange.github.io&#x2F;disruptor&#x2F;disruptor.html#_design_of_the_lmax_disruptor" rel="nofollow">https:&#x2F;&#x2F;lmax-exchange.github.io&#x2F;disruptor&#x2F;disruptor.html#_de...</a>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&#x27;s some tricky details to get right when multiple producers have messages staged up at the same time.

Do you have a link to the white paper you found?

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.

I don&#x27;t quite see how&#x27;s that obscure; it&#x27;s a standard circular buffer. The fast&#x2F;low latency communication part comes from the busy wait (and L3 cache communication).

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.

Found out about this DS in AoC 2021 Day 20+ problems if I remember correctly. Pretty interesting.

Interval trees. Really cool trees that allow fast lookups of all the ranges that contain a given point.<a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Interval_tree" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Interval_tree</a>

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:
<a href="https:&#x2F;&#x2F;www.lysator.liu.se&#x2F;c&#x2F;pikestyle.html" rel="nofollow">https:&#x2F;&#x2F;www.lysator.liu.se&#x2F;c&#x2F;pikestyle.html</a>

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&#x2F;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.

I find I use fixed-sized arrays a lot on microcontrollers.  You want to avoid the heap (for reliability) and you don&#x27;t have a lot of RAM, so you must carefully size your fixed-size arrays.

Static arrays - when was the last time you used a static array?

Previously on HN:<a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=1370847" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=1370847</a> (2010)<a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=2363522" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=2363522</a> (2011)<a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=3369454" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=3369454</a> (2011) -- Although not much is in the discussion, it points to a Stack Overflow post with some examples.<a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=7079427" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=7079427</a> (2014)<a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=28758106" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=28758106</a> (2021) -- Not exactly a data structure, but an interesting algorithm.

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&#x2F;dense array. This approach is both cache efficient and space efficient as the dense array can grow independently of the sparse array.

Sparse sets.They&#x27;re often used in Entity Component System architectures since you have O(1) add&#x2F;remove&#x2F;find, &amp; 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 <a href="https:&#x2F;&#x2F;github.com&#x2F;skypjack&#x2F;entt" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;skypjack&#x2F;entt</a>

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.

Splay trees: <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Splay_tree" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Splay_tree</a> recently searched items are always near the top.

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&#x2F;why it works. Couldn&#x27;t be happier to see it cited in this list!

Reservoir sampling is really cool - a slightly optimized version (algorithm L) let&#x27;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])<pre><code> &#x2F;&#x2F; 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())&#x2F;k)

 while i &lt;= n
 i := i + floor(log(random())&#x2F;log(1-W)) + 1
 if i &lt;= n
 (* replace a random item of the reservoir with item i *)
 R[randomInteger(1,k)] := S[i] &#x2F;&#x2F; random index between 1 and k, inclusive
 W := W * exp(log(random())&#x2F;k)
</code></pre>
<a href="https:&#x2F;&#x2F;en.m.wikipedia.org&#x2F;wiki&#x2F;Reservoir_sampling" rel="nofollow">https:&#x2F;&#x2F;en.m.wikipedia.org&#x2F;wiki&#x2F;Reservoir_sampling</a>

I was going to mention it too! The really cool thing about reservoir sampling is that it can be done &quot;online&quot; (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&#x27;s say I have a server serving queries. I want to measure min&#x2F;max&#x2F;avg&#x2F;stdev&#x2F;99p you name it. You can do it cheaply with reservoir sampling, without having to save all data points.

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:<pre><code> for i = k to population.length-1
 j = random integer between 0 and i, inclusive
 if j &lt; k
 reservoir[j] = population[i]
 return reservoir</code></pre>

The Wikipedia article on AA-Trees is good: <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;AA_tree" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;AA_tree</a>

Speaking of ease of implementation, I just discovered AA trees. They are probably not &quot;obscure&quot; 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 : <a href="https:&#x2F;&#x2F;www.cs.umd.edu&#x2F;class&#x2F;fall2019&#x2F;cmsc420-0201&#x2F;Lects&#x2F;lect06-aa.pdf" rel="nofollow">https:&#x2F;&#x2F;www.cs.umd.edu&#x2F;class&#x2F;fall2019&#x2F;cmsc420-0201&#x2F;Lects&#x2F;lec...</a>And the, unhelpful to me, orginal paper : <a href="https:&#x2F;&#x2F;user.it.uu.se&#x2F;~arnea&#x2F;ps&#x2F;simp.pdf" rel="nofollow">https:&#x2F;&#x2F;user.it.uu.se&#x2F;~arnea&#x2F;ps&#x2F;simp.pdf</a>

The nicest thing about treaps is how easy union&#x2F;intersection&#x2F;disjunction are.

Treap: <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Treap" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Treap</a>It&#x27;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&#x27;s an unlikely degeneration to worst-case linked-list behaviour.Lazy Propagation Segment Tree: <a href="https:&#x2F;&#x2F;cp-algorithms.com&#x2F;data_structures&#x2F;segment_tree.html" rel="nofollow">https:&#x2F;&#x2F;cp-algorithms.com&#x2F;data_structures&#x2F;segment_tree.html</a>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&#x27;ve never touched otherwise.

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 &quot;grounded&quot; 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.<a href="https:&#x2F;&#x2F;www.w3.org&#x2F;egov&#x2F;wiki&#x2F;Resource_Description_Format" rel="nofollow">https:&#x2F;&#x2F;www.w3.org&#x2F;egov&#x2F;wiki&#x2F;Resource_Description_Format</a>

These are not commonly used in application code, but are &quot;commonly&quot; used to implement reclamation in languages without memory management for concurrent mutable data structures.

I have seen this general pattern in several decently large game object systems, although I can’t think of which ones off hand, if I’m recalling correctly it tend to be used in the longer lived (aka 10s of frames) object status&#x2F;object existence checks, and often in AI subsystems, pathing and general decision making queries, etc.

Have you used this before? What was the domain?

Seems to me to be quite similar to the virtual pages in Bw-Trees: <a href="https:&#x2F;&#x2F;www.microsoft.com&#x2F;en-us&#x2F;research&#x2F;publication&#x2F;the-bw-tree-a-b-tree-for-new-hardware&#x2F;" rel="nofollow">https:&#x2F;&#x2F;www.microsoft.com&#x2F;en-us&#x2F;research&#x2F;publication&#x2F;the-bw-...</a>

Hazard Pointers are an interesting concurrent data structure.Suppose we&#x27;ve got a lot of Doodads, let&#x27;s say there&#x27;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&#x27;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&#x27;d need atomic reference counts, something like C++ shared_ptr -- but this would work. However now our performance is terrible, because we&#x27;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&#x27;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&#x27;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&#x27;re only doing it for removal, not just reads.Finally there needs to be some mopping up of that pile of &quot;couldn&#x27;t delete yet&quot; 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&#x27;s OK because it was rare.

what about randomized O(n) minimum spanning trees?

The fact that suffix trees&#x2F;suffix arrays can be built in O(n) is IMO the most surprising and &quot;magical&quot; result in computer science. To me, more surprising than median of medians&#x2F;quick select.There might be more &quot;magical&quot;&#x2F;surprising things that are obscure and I am unaware of, but to me, this is it. :)

The Suffix Array is surprisingly cool and useful <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Suffix_array" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Suffix_array</a>The Alias Table for sampling a discrete distribution in O(1) time is a very clever idea <a href="https:&#x2F;&#x2F;www.keithschwarz.com&#x2F;darts-dice-coins&#x2F;" rel="nofollow">https:&#x2F;&#x2F;www.keithschwarz.com&#x2F;darts-dice-coins&#x2F;</a>

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.

&gt; reasonably well behavedCurious what this means in this context. No hot spots? Not sparse?

From a basic binary search, this is very intuitive. Your explanation was well written.

That&#x27;s how mongodb geospatial indexes work IIRC

A lot of people don&#x27;t know about the related segment and interval trees. Both efficiently allow you to compute all time ranges that overlap a point. This can be generalized to higher dimensional spaces.For example if you have a set of calendar invites with a start and stop time (say tens of millions of them) and you want to find all invites which span 12pm (that is start before 12 and end after 12) you want an interval tree.<a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Interval_tree" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Interval_tree</a>

Hmm... the quad keys end up looking very much like coordinates. In the regular coordinates, the most significant bit divides the space in half, then the next bit divides those spaces in halves etc...You could get a single &quot;key&quot; by just having a sequence of bits with most significant bit of x coordinate, most significant bit if of y coordinate, second most significant bit of x coordinate, second most significant bit of y coordinate, third....

TBH even quadkeys are a fun answer to OPs question, many people aren&#x27;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&#x27;ve also seen it start with &quot;Z&quot; to handle points outside the bounds)2. Divide the space into 4 quadrants3. determine which quadrant the point falls in, append a letter (A-D depending on the quadrant) to the key4. Repeat step 3 using the quadrant bounds (i.e. recursively smaller area) until you have desired accuracyThis can then be used to efficiently find points within rectangular bounds.

Ever heard of geospatial hierarchical Indices?E.g. Uber&#x27;s H3 index or Google&#x27;s S2 index.

Yeah, just reinvented it a few weeks ago and was like “whoa, that’s it?” It worked perfectly for my fast clustering use case.

A variation of this are dynamic spatially-hashed voxel grids, where the outer grid is spatially hashed and the grid elements are stored (as needed) as dense voxel grids. The advantages of this are that you get voxel grid-like behavior over essentially unbounded size, so long as the data is sparse (otherwise you would need to allocate a significant number of grid elements as voxel grids and the memory savings go away).These data structures have been used in 3D reconstruction methods like CHISEL where they can often outperform octrees due to better memory access behavior.

I’ve always found Morton encoding to be a cool approach. There’s an old but good blog post about this: <a href="https:&#x2F;&#x2F;www.forceflow.be&#x2F;2013&#x2F;10&#x2F;07&#x2F;morton-encodingdecoding-through-bit-interleaving-implementations&#x2F;" rel="nofollow">https:&#x2F;&#x2F;www.forceflow.be&#x2F;2013&#x2F;10&#x2F;07&#x2F;morton-encodingdecoding-...</a>This looks like a more modern implementation: <a href="https:&#x2F;&#x2F;crates.io&#x2F;crates&#x2F;lindel" rel="nofollow">https:&#x2F;&#x2F;crates.io&#x2F;crates&#x2F;lindel</a>

I didn&#x27;t think that would be an obscure data structure, but Locality-sensitive hashing [1] helps in so many cases. Like nearest neighbour search, collision detection, etc.[1]: <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Locality-sensitive_hashing" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Locality-sensitive_hashing</a>

Couple some spatial hashing with Morton codes and fast parallel Radix sorting and some binary search derivative and you can do all sorts of fancy queries for collision detection and graphics stuff.

It should be noted that this solution completely fails when the data is anything like real world location data which tends to be clustered in cities, stadiums etc. The strength of quad trees is precisely the fact that the &quot;Alaska&quot; quadrant can have a single child for that crazy outdoors-man using your gadget, while New York can have a million children trees down to every house on the street.

I have a very optimized octree, but one thing I can not use it for is points in space. Mine is built with the assumptions that every object has a finite size, which is used to determine what level of the tree it lives in. Points fail because they have zero size.I&#x27;m still looking for a good spatial index for points. I&#x27;ll think about yours.

Are these similar to space-filling curves like z-order indices? <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Z-order" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Z-order</a>Some more such curves: <a href="https:&#x2F;&#x2F;web.archive.org&#x2F;web&#x2F;20220120151929&#x2F;https:&#x2F;&#x2F;citeseerx.ist.psu.edu&#x2F;viewdoc&#x2F;download?doi=10.1.1.144.505&amp;rep=rep1&amp;type=pdf" rel="nofollow">https:&#x2F;&#x2F;web.archive.org&#x2F;web&#x2F;20220120151929&#x2F;https:&#x2F;&#x2F;citeseerx...</a>

Neat use of these is the &quot;fast multipole method&quot; for stimulating galaxies.If you want to compute the gravitational force on a given star exactly you need to figure out the forces from all other stars and add them up. This will be n^2 and slow. But turns out you can get a good approximation by dividing up space with a kd tree and using the average force from each cell to represent the stars underneath it in the tree. This gets you to nlogn<a href="https:&#x2F;&#x2F;en.m.wikipedia.org&#x2F;wiki&#x2F;Fast_multipole_method" rel="nofollow">https:&#x2F;&#x2F;en.m.wikipedia.org&#x2F;wiki&#x2F;Fast_multipole_method</a>

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 &quot;fluff&quot; (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&#x27;s completely trivial to implement.

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] <a href="https:&#x2F;&#x2F;github.com&#x2F;RiftValleySoftware&#x2F;RVS_Generic_Swift_Toolbox&#x2F;blob&#x2F;master&#x2F;Sources&#x2F;RVS_Generic_Swift_Toolbox&#x2F;RVS_Generic_Swift_Toolbox_CollectionTools&#x2F;RVS_FIFOQueue.swift" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;RiftValleySoftware&#x2F;RVS_Generic_Swift_Tool...</a>

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.

I saw this and bloom filter was my very first thought, so I&#x27;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&#x27;t voted than if you had.

AIUI Radix sort &quot;kinda ish&quot; related, yeah :)  They both involve looking at your data at a 90 degree angle and slicing on bitplanes.

I think what you’re describing in the last example is the MinHash algorithmedit: actually I’m not sure, sounds related though

Works well in analytics cubes since they can be combined.You can retain them across time too, such that you can ask questions like &quot;how many unique users were there over the last N days?&quot; without needing the source data. Great for privacy-aware analytics solutions.

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 &quot;how many unique IPs was there yesterday&quot;.Discovered HLL because it&#x27;s used in ClickHouse, which employ a ton of cool but obscure data structure.

&quot;NAND optimized key value store&quot; doesn&#x27;t do it justice ;-) The fact that it&#x27;s SSD optimized has nothing to do with key sharding across trees, the latter is what gets you the absurdly low latency and near infinite scale out. This link gives an overview: <a href="https:&#x2F;&#x2F;vldb.org&#x2F;pvldb&#x2F;vol9&#x2F;p1389-srinivasan.pdf" rel="nofollow">https:&#x2F;&#x2F;vldb.org&#x2F;pvldb&#x2F;vol9&#x2F;p1389-srinivasan.pdf</a> And it&#x27;s open source...

I forgot about Aerospike. They basically built a NAND optimized key, value store right? I remember reading about how they used the FTL and thinking they were pretty clever. I cant for the life of me find the article now. I think they were really big in the ad tech space? Is that still the case?

I want to hear more, esp about the distributed applications, do you have any useful links, or can I buy you an &quot;e coffee&quot; to pick your brain for a few minutes?

&gt; Also because they divide _space_ not the _data_ they are very amenable to multi-threaded and distributed algorithms.Ha, I was thinking about this idea the other day and couldn’t figure out a good way to search for anything already written on the topic. I suspect there’s quite a lot of ground to be gained in the area.

Y-fast tries are some of my favorites. I think they are heavily under utilized in modern terms. They sat by the the wayside for a long term because datasets where relatively small, at the time they where created ram didn&#x27;t exist, and bitwise operations where inefficient along with many other constant factors.Today; however, a lot of people have datasets on the order of 2^16 or 2^32 keys they need to maintain. And efficient bitwise operations (on upto 512 bits) are the norm. Y-fast tries are faster than b-trees or other datastructures. Also because they divide _space_ not the _data_ they are very amenable to multi-threaded and distributed algorithms. For example the hash-tables in a y-fast trie can actually be a rendezvous hash pointing to a database node. Once in that node you can hash on cores again to get to a local process for example.

On sketches, there is a genre of structure for estimating histogram-like statistics (median, 99th centile, etc) in fixed space, which i really like. Two examples:t-digest <a href="https:&#x2F;&#x2F;github.com&#x2F;tdunning&#x2F;t-digest" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;tdunning&#x2F;t-digest</a>DDSketch <a href="https:&#x2F;&#x2F;github.com&#x2F;DataDog&#x2F;sketches-java" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;DataDog&#x2F;sketches-java</a>

Big fan of HLLApache foundation has a fantastic DataSketches library that includes HLL and many other powerful data analytics algorithms: <a href="https:&#x2F;&#x2F;datasketches.apache.org&#x2F;" rel="nofollow">https:&#x2F;&#x2F;datasketches.apache.org&#x2F;</a>Lee Rhodes has done an excellent introduction to this library - explaining some of the use cases, advantages, and things to be aware of when using these techniques: <a href="https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=nO9pauS-mGQ" rel="nofollow">https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=nO9pauS-mGQ</a>

I like <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Cuckoo_filter" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Cuckoo_filter</a> which allows for delete, unlike Bloom

This made my day, thank you so much. :) Your explanation makes sense and it sounds brilliant&#x2F;clever yet obvious. (like many good ideas are)I&#x27;m reading the paper and looking at your github now, and look forward to &quot;github&#x2F;academia&quot; stalking you in the future. Skimming your list of repositories and seeing a lot of stuff I understand and could possibly use. ;-)(I find it to be a useful strategy to, when I find a clever concept in a paper, or in code on github, then look at all the other things done by the same person, or the works of people they co-author with. &quot;collaborative filtering&quot; for ideas.)

If you enjoyed XOR filters, you might also like ribbon filters, something that I had the pleasure of working on last year. They share the basic idea of using a system of linear equations, but instead of considering 3 random positions per key, the positions to probe are narrowly concentrated along a ribbon with a typical width of 64. This makes them far more cache-efficient to construct and query.By purposefully overloading the data structure by a few per cent and bumping those items that cannot be inserted as a result of this overloading to the next layer (making this a recursive data structure), we can achieve almost arbitrarily small space overheads: &lt;1% is no problem for the fast configurations, and &lt;0.1% overhead with around 50% extra runtime cost. This compares to around 10% for XOR filters and ≥ 44% for Bloom filters.In fact, I&#x27;m going to present them at a conference on Monday - the paper is already out: <a href="https:&#x2F;&#x2F;drops.dagstuhl.de&#x2F;opus&#x2F;volltexte&#x2F;2022&#x2F;16538&#x2F;pdf&#x2F;LIPIcs-SEA-2022-4.pdf" rel="nofollow">https:&#x2F;&#x2F;drops.dagstuhl.de&#x2F;opus&#x2F;volltexte&#x2F;2022&#x2F;16538&#x2F;pdf&#x2F;LIPI...</a> and the implementation is at <a href="https:&#x2F;&#x2F;github.com&#x2F;lorenzhs&#x2F;BuRR&#x2F;" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;lorenzhs&#x2F;BuRR&#x2F;</a>. I hope this isn&#x27;t too much self-promotion for HN, but I&#x27;m super hyped about this :)

(Fantastic post idea OP. One of the best I&#x27;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&#x27;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: <a href="https:&#x2F;&#x2F;www.youtube.com&#x2F;playlist?list=PLUl4u3cNGP61hsJNdULdudlRL493b-XZf" rel="nofollow">https:&#x2F;&#x2F;www.youtube.com&#x2F;playlist?list=PLUl4u3cNGP61hsJNdULdu...</a> (6.851 Advanced Data Structures, Erik Demaine)Would love to learn more &quot;stupidly fast at the cost of conceptual complexity&quot; things.edit:(adding) 
I don&#x27;t know a name for it, because it&#x27;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 &quot;shard&quot; this key across M other fast data structures (like a tree) for search&#x2F;add&#x2F;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)

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&#x27;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.

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.

Sentry used Redis to buffer writes for a similar use case:<a href="https:&#x2F;&#x2F;blog.sentry.io&#x2F;2016&#x2F;02&#x2F;23&#x2F;buffering-sql-writes-with-redis" rel="nofollow">https:&#x2F;&#x2F;blog.sentry.io&#x2F;2016&#x2F;02&#x2F;23&#x2F;buffering-sql-writes-with-...</a>

I&#x27;ve seen this done with kinesis streams.Basically just update a cache, and forward the results every so often.If you put things in a stack, you can keep using the most recent for the update. Compare times and you won&#x27;t add a bad value

There are a variety of solutions to this but CRDTs are a very good one (CRDTs solve your problem (<a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Conflict-free_replicated_data_type" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Conflict-free_replicated_data_...</a>). If the operations you&#x27;re doing commute (that is a ○ b = b ○ a, e.g. the order in which you apply the operations doesn&#x27;t matter) then one could apply all operations in parallel, and only send the final result of doing them all. Casandra uses LWW-Element-Set CRDTS to solve this exact problem (<a href="https:&#x2F;&#x2F;cassandra.apache.org&#x2F;doc&#x2F;latest&#x2F;cassandra&#x2F;architecture&#x2F;dynamo.html" rel="nofollow">https:&#x2F;&#x2F;cassandra.apache.org&#x2F;doc&#x2F;latest&#x2F;cassandra&#x2F;architectu...</a>).

Can I describe a data queueing problem that I feel like there is a specific data (or queue) structure for, but that I don&#x27;t know the name is?Let&#x27;s say you are trying to &quot;synchronize&quot; a secondary data store with a primary data store. Changes in the primary data store are very &quot;bursty&quot;, one row will not change for days, then it&#x27;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&#x27;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 &quot;debounce&quot; 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.

I came here to say Golomb compressed sets except now I see it&#x27;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] <a href="https:&#x2F;&#x2F;github.com&#x2F;OpenMined&#x2F;PSI&#x2F;blob&#x2F;master&#x2F;private_set_intersection&#x2F;javascript&#x2F;README.md" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;OpenMined&#x2F;PSI&#x2F;blob&#x2F;master&#x2F;private_set_int...</a>

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.

Piece tables: a persistent data structure used to represent the current document with relatively efficient editing operations in various text editors, word processors, etc.<a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Piece_table" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Piece_table</a>

This is great!Exactly what this thread is about; everybody should go through this.

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&#x27;t necessarily have a reason to look, or on those rare occasions where my sysadmin&#x2F;DBA projects do throw up a problem that one of these algorithms&#x2F;structures are suited for - I wouldn&#x27;t know _to_ look, or even how.That&#x27;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 &quot;you&#x27;ll learn data structures and algorithms&quot; and that&#x27;s it. ( 20 yr old me: &quot;I know loops and recursion, linked lists, some basic trees and oh look this &quot;perl&quot; thing has hashes, meh I&#x27;ll be fine&quot; )If they&#x27;d listed out the sort of descriptions I&#x27;ve seen here.. well, I might have had a very different life!So I&#x27;m absolutely loving this thread!And thankyou for your link too, added to my list.

Most of the data structures posted here are taught in CS classes. Here’s an interesting list of more obscure ones: <a href="https:&#x2F;&#x2F;web.stanford.edu&#x2F;class&#x2F;cs166&#x2F;handouts&#x2F;090%20Suggested%20Project%20Topics.pdf" rel="nofollow">https:&#x2F;&#x2F;web.stanford.edu&#x2F;class&#x2F;cs166&#x2F;handouts&#x2F;090%20Suggeste...</a>

Djikstra maps. This page describes it better than I can: <a href="http:&#x2F;&#x2F;www.roguebasin.com&#x2F;index.php&#x2F;Dijkstra_Maps_Visualized" rel="nofollow">http:&#x2F;&#x2F;www.roguebasin.com&#x2F;index.php&#x2F;Dijkstra_Maps_Visualized</a> 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.

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.

I was reading up on C++&#x27;s standard library and found out that maps and sets are generally implemented as continually sorted lists

A sorted list. It&#x27;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 :)

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.

In case anyone is interested, I wrote a skip list implementation for Node.js here: <a href="https:&#x2F;&#x2F;www.npmjs.com&#x2F;package&#x2F;proper-skip-list" rel="nofollow">https:&#x2F;&#x2F;www.npmjs.com&#x2F;package&#x2F;proper-skip-list</a>I provided the time complexity of each operation as part of the README.

This is a great selection. Thanks for sharing.

Some ones I&#x27;ve used recently:The &quot;golden section search&quot; 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 &amp;-x) isolates the least significant set bit: basically use the ALU&#x27;s carry chain to determine priority.Another is compress from Hacker&#x27;s Delight. It very quickly compresses selected bits (from a bitmask), all to the right of the word. It&#x27;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:<pre><code> Empty: (write_index == read_index)
 Full: (write_index == read_index + size)
 Count: (write_index - read_index)
 Insert: queue[write_index++ &amp; (size - 1)] = data
 Remove: data = queue[read_index++ &amp; (size - 1)];
</code></pre>
All lossless data compression algorithms are amazing.

If you’re willing to use moderately more memory, you can get much better cache locality using a blocked bloom filter. The basic idea is to use an array of bloom filters that each fit into a cache line, and use some bits of hash to determine which sub-filter each item goes into. Suddenly each lookup or insertion has at most one cache miss!

That Cloudflare article is a little frustrating.&gt; While we could think of more sophisticated data structures like Cuckoo filter, maybe we can be simplerYes, standard Bloom filters fail for large filter sizes and&#x2F;or very small false-positive rates. But we&#x27;ve known this for decades, and tons of other probabilistic filters have come out since then to address the problem. Cuckoo filters in particular are incredible.Was there really no easy way to bring in an open-source Cuckoo filter implementation? They&#x27;re not that complicated. Maybe I&#x27;m just used to modern languages having good package managers.Plus the author&#x27;s solution is basically the idea behind Cuckoo filters: &quot;what if we just use a hash table, but allow for collisions?&quot; Cuckoo hashing is just clever about guaranteeing O(1) worst-case lookup.And for absolute dead-simple filters, a blocked Bloom filter is basically just as easy as a Bloom filter. It&#x27;s like two or three more lines of code. It&#x27;s just changing the indexing operation to be modulo some large &quot;block&quot; size. That said, I don&#x27;t think they&#x27;d work too well in this case, since the author has a pretty small false-positive rate (0.000019), and in my experience small Bloom filters (which is what comprise blocked Bloom filters) don&#x27;t handle small FP rates well.But guess what excel at small FP rates… cuckoo filters.

Funny you should mention bloom filters and that use case, I just re-read this post again this morning: <a href="https:&#x2F;&#x2F;blog.cloudflare.com&#x2F;when-bloom-filters-dont-bloom&#x2F;" rel="nofollow">https:&#x2F;&#x2F;blog.cloudflare.com&#x2F;when-bloom-filters-dont-bloom&#x2F;</a>Basically, it makes a similar point to <a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=32186837" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=32186837</a> — 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.

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&#x2F;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&#x2F;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&#x27;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&#x27;re interested in understanding them, <a href="https:&#x2F;&#x2F;rosalind.info&#x2F;problems&#x2F;list-view&#x2F;" rel="nofollow">https:&#x2F;&#x2F;rosalind.info&#x2F;problems&#x2F;list-view&#x2F;</a> is a great starting place.

Used it for tag hierarchy, liked it a lot!

Nested Set Model: a way to model nested sets of entities and query them in a SQL database. I haven&#x27;t used it for anything but it seems fun.<a href="https:&#x2F;&#x2F;en.m.wikipedia.org&#x2F;wiki&#x2F;Nested_set_model" rel="nofollow">https:&#x2F;&#x2F;en.m.wikipedia.org&#x2F;wiki&#x2F;Nested_set_model</a>

&gt; I&#x27;ll startYou&#x27;re supposed to post yours as a comment, so it can be voted on like every other type of structure suggested here.

This one is my favourite concept, bloom filter goes after that. Cool stuff about Geohash that you can expand it&#x27;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

Have you heard of Geohash? My mind was blown the first time I learned it. <a href="https:&#x2F;&#x2F;en.m.wikipedia.org&#x2F;wiki&#x2F;Geohash" rel="nofollow">https:&#x2F;&#x2F;en.m.wikipedia.org&#x2F;wiki&#x2F;Geohash</a>

I am trying to compile a list of data structures (and algorithms and other stuff) into a kind of knowledge base: <a href="https:&#x2F;&#x2F;github.com&#x2F;Dobatymo&#x2F;data-algos&#x2F;blob&#x2F;master&#x2F;data-structures.md" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;Dobatymo&#x2F;data-algos&#x2F;blob&#x2F;master&#x2F;data-stru...</a>. There are few cool and obscure data structures already. Please feel free to help extend it!

Type-&gt;Value Lattice<a href="https:&#x2F;&#x2F;cuelang.org&#x2F;docs&#x2F;concepts&#x2F;logic&#x2F;" rel="nofollow">https:&#x2F;&#x2F;cuelang.org&#x2F;docs&#x2F;concepts&#x2F;logic&#x2F;</a>

The aho-corasick Rust crate[1] also provides a way to build the automaton in a slightly different way to provide leftmost first or &quot;preference first&quot; 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]: <a href="https:&#x2F;&#x2F;docs.rs&#x2F;aho-corasick" rel="nofollow">https:&#x2F;&#x2F;docs.rs&#x2F;aho-corasick</a>

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] <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Aho–Corasick_algorithm" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Aho–Corasick_algorithm</a>

I&#x27;m very interested in what types of interesting data structures are out there HN. Totally your preference.I&#x27;ll start: bloom filters. Lets you test if a value is definitely NOT in a list of pre-stored values (or POSSIBLY in a list - with adjustable probability that influences storage of the values.)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 &#x27;keys&#x27; not needing to be stored (&#x27;search&#x27; and &#x27;insert&#x27; is based on the number of hash functions.)Bonus section: Golomb Coded Sets are similar to bloom filters but the storage space is much smaller. Worse performance though.

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