What are the lesser known but useful data structures? • Hacker News Board

Re: What are the lesser known but useful data structures?

#31

Post by chas » Sat, Jan 18, 2014, 7:55 AM UTC

I'm happy to see finger trees got mentioned. Finger trees[0] are extremely useful and general data structure that can be used to implement persistent sequences, priority queues, search trees and priority search queues. (Haskell's Data.Sequence[1] uses specialized 2-3 finger trees internally) They can form the basis of all sorts of interesting custom structures by supplying the appropriate monoid[3], but this does make them harder to approach if you are not familiar with the abstractions.

[3] A monoid is any structure that has members that can combine associatively. In addition, it must have an element that can combine with any other element and result in the other element. Some examples: (strings, string concatenation, the empty string); (integers, addition, 0); (natural numbers, max, 0); (booleans, and, True); (functions, composition, the identity function). The functional pearl[2] that describes the design of Haskell's diagrams library[4] goes into much more detail if you are interested in their application to programming.

[0] http://apfelmus.nfshost.com/articles/monoid-fingertree.html

[1] http://hackage.haskell.org/package/containers-0.5.4.0/docs/D...

[2] http://www.cis.upenn.edu/~byorgey/pub/monoid-pearl.pdf

[4] http://projects.haskell.org/diagrams/

Re: What are the lesser known but useful data structures?

#32

Post by pnathan » Sat, Jan 18, 2014, 7:55 AM UTC

I recently learned about the spatial index tree family in connection with data mining. I hope to implement a data-mining centric X tree (n-dimensional) solution for a data analytics package I'm writing soon. That family is is how you efficiently handle KNN lookups, afaict.

Re: What are the lesser known but useful data structures?

#33

Post by akurtzhs » Sat, Jan 18, 2014, 8:05 AM UTC

WWKong wrote: post #27

Me and my friend were pretty serious about creating a new data structure called "drum". A drum is a one way store. You write to it but can't read from it. We put it off till we figured a practical use.

Backups? People tend to treat them that way anyways.

Re: What are the lesser known but useful data structures?

#34

Post by VexXtreme » Sat, Jan 18, 2014, 8:12 AM UTC

I love how the question was locked because "it is not considered a good, on-topic question for this site". It's crazy. Unless an extremely specific concrete answer can be given, a question immediately gets killed. SO has turned into such a turd of a website.

Re: What are the lesser known but useful data structures?

#35

Post by joelthelion » Sat, Jan 18, 2014, 9:36 AM UTC

VexXtreme wrote: post #34

I love how the question was locked because "it is not considered a good, on-topic question for this site". It's crazy. Unless an extremely specific concrete answer can be given, a question immediately gets killed. SO has turned into such a turd of a website.

Speaking of which, is there a good alternative site for questions that are forbidden on SO?

Re: What are the lesser known but useful data structures?

#36

Post by jzwinck » Sat, Jan 18, 2014, 9:47 AM UTC

joelthelion wrote: post #35

VexXtreme wrote: post #34

I love how the question was locked because "it is not considered a good, on-topic question for this site". It's crazy. Unless an extremely specific concrete answer can be given, a question immediately gets killed. SO has turned into such a turd of a website.

Speaking of which, is there a good alternative site for questions that are forbidden on SO?

There are other sites in the StackExchange network like Programmers and Code Review and some others for math and other things. But I'm not sure which site (SE or otherwise) would be the best for this particular topic.

Re: What are the lesser known but useful data structures?

#37

Post by justforonereply » Sat, Jan 18, 2014, 9:49 AM UTC

WWKong wrote: post #27

Me and my friend were pretty serious about creating a new data structure called "drum". A drum is a one way store. You write to it but can't read from it. We put it off till we figured a practical use.

/dev/null is a nice implementation.

Re: What are the lesser known but useful data structures?

#38

Post by youWontLikeThis » Sat, Jan 18, 2014, 9:53 AM UTC

..............

locked by Robert Harvey♦ Mar 15 '12 at 18:42

This question exists because it has historical significance, but it is not considered a good, on-topic question for this site

..............

Seriously, who's the responsible for putting this kind of guy in charge.

Re: What are the lesser known but useful data structures?

#39

Post by [deleted] » Sat, Jan 18, 2014, 10:07 AM UTC

tikhonj wrote: post #6

There's a whole set of interesting data structures that are not very well known: succinct data structures[1]. The idea is simple: we want to store data in a compressed form, but also perform certain operations quickly without uncompressing. These can be very useful for certain applications. The article on "Cramming 80,000 Words into a JavaScript File"[2] is a nice example. It shows you how you can store a compressed…

[deleted]

Re: What are the lesser known but useful data structures?

#40

Post by ot » Sat, Jan 18, 2014, 10:07 AM UTC

tikhonj wrote: post #6

There's a whole set of interesting data structures that are not very well known: succinct data structures[1]. The idea is simple: we want to store data in a compressed form, but also perform certain operations quickly without uncompressing. These can be very useful for certain applications. The article on "Cramming 80,000 Words into a JavaScript File"[2] is a nice example. It shows you how you can store a compressed…

> Instead of parsing data, it might be better to store it as a blob of some sort with a binary index.

This is exactly something I did for JSON, I call it semi-indexing: instead of parsing it into a tree of pointers, I create a succinct representation of the parsing tree, which is orders of magnitude smaller than the original JSON. Construction is much faster than parsing because there are basically no memory allocations, and access is not that much slower.

About performance of succinct data structures in general, it is true that they have shown poor practical performance, but things are changing, both because we have better CPUs (while memory latency is pretty much unchanged), and better algorithms are being found. I did my Ph.D. on practical succinct data structures. We found that in some applications, the access times are competitive or faster than the non-succinct counterparts, while the space is much smaller. One example is tries: in my thesis [2] there are experiments for string dictionaries, and for query autocompletion (for example for search engines).

Another area where (quasi-)succinct data structures are having some success is inverted indexes: recently proposed posting lists based on Elias-Fano [3] have been shown to outperform standard delta-encoded posting lists for queries with sparse intersection, and are used in Facebook's graph search [4].

Finally, the biggest success story of SDS has historically been molecular biology, because the size of the DNA sequences processed is so large that non-succinct data structures are impractical. Many sequence assemblers/aligners use variants of FM-indexes and Compressed Suffix Arrays, that are self-indexes based on the Burrows-Wheeler Transform and Wavelet Trees.

[1] https://github.com/ot/semi_index

[2] http://www.di.unipi.it/~ottavian/files/phd_thesis.pdf

[3] http://vigna.di.unimi.it/ftp/papers/QuasiSuccinctIndices.pdf

[4] http://www.vldb.org/pvldb/vol6/p1150-curtiss.pdf