0

According to this StackOverflow question, probabilistic data structures are data structures that give approximate, as opposed to precise, answers. In particular, they have very low time and space complexities and are easily parallelizable, making them very efficient structures to use. Examples provided include Bloom Filters, Count-Min Sketch, and HyperLogLog.

However, all of these data structures are also known as "sketch" data structures - structures that approximate a large set via a compact representation for more efficient (but less precise) operation.

I don't see the difference between a "sketch" and a "probabilistic" data structure.

Shuklaswag
  • 1,003
  • 1
  • 10
  • 27

1 Answers1

0

There are probabilistic data structures that are not approximations, for example the Skip list.

Thomas Mueller
  • 48,905
  • 14
  • 116
  • 132