Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

news.ycombinator.com

Post reply on HN
Print view View original

161–170 of 772 posts

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

#161

Post by chriswarbo »

cvoss wrote: post #147
jiggawatts wrote: post #25

Cache-Oblivious Data Structures: 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…

> 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'. 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.…

This series of blog posts explains this sqrt behaviour quite nicely, covering both theory (including black holes) and practice:

http://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html

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

#162

Post by EddySchauHai »

NSMutableSet wrote: post #19
petethepig wrote: post #3

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/sto..…

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/begin...

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

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

#163

Post by pacaro »

yellowflash wrote: post #134
pacaro wrote: post #98

Earlier quoted context omitted.

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-…

That's how mongodb geospatial indexes work IIRC

It's tried and tested for sure, I first encountered them in 94 but I assume they're much older.

A little sleuthing shows that (TIL) they are an application of Z-order curves, which date back to 1906

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

#164

Post by valbaca »

(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

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

#165

Post by vivegi »

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

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

#166

Post by 8note »

andrenotgiant wrote: post #65

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

I'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't add a bad value

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

#167

Post by soren1 »

yellowflash wrote: post #134
pacaro wrote: post #98

Earlier quoted context omitted.

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-…

That's how mongodb geospatial indexes work IIRC

Was about to mention this. If I recall correctly, the 2d-sphere index rounds geospatial coordinates to 5 decimals. Very occasionally, I found it would distort polygon geometries just enough to cause them to become invalid (e.g. overlapping geometries), which causes the index build to fail.

In my recent experience working with collections containing million of documents, each containing a geoJSON-style polygon/multipolygon representing a property (i.e. a block of land), I found invalid geometries to occur for about 1 document in 1 million. For a while, I suspected the data-vendor was the cause, however it became more puzzling when other geospatial software confirmed they were valid. Eventually we traced the issue to the 2d-sphere index.

A very clever workaround was suggested by a colleague of mine, inspired by [1]. It preserved the original geometries. In each document, we added a new field containing the geometry's extent. A 2d-sphere index was then built on the extent field instead of the original geometry field. Invalid geometries were no longer an issue since we were dealing with much simpler geometries that were substantially larger than the max precision of the index.

When running geoIntersects queries on our collection of millions of documents, we did so in 2 steps (aggregation queries):

1. GeoIntersects on the extent field (uses the index).

2. On the result set from the last step, perform geoIntersects on the original geometry field (operates on a much smaller set of records compared to querying the collection directly)

[1] https://www.mongodb.com/docs/manual/tutorial/create-queries-...

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

#168

Post by bhawks »

scottcodie wrote: post #48

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. T…

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
https://en.m.wikipedia.org/wiki/Reservoir_sampling

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

#169

Post by evouga »

klysm wrote: post #79
zarzavat wrote: post #55

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…

> reasonably well behaved Curious what this means in this context. No hot spots? Not sparse?

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.

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

#170

Post by andreareina »

kaymanb wrote: post #5

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

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.

Post reply on HN