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

Topics in Advanced Data Structures [pdf]

web.stanford.edu

Post reply on HN
Print view View original

61–70 of 89 posts

Re: Topics in Advanced Data Structures [pdf]

#61

Post by jcranmer »

sacheendra wrote: post #59
jcranmer wrote: post #42

Earlier quoted context omitted.

There's a general class of problems to be solved with data structures, which is that you have a collection of records of data, and you're trying to find [1] a record, or collection of records, given some criteria. In essence, you have a database of some kind, so it should not surprise you to learn that databases (and things that are databases but not normally thought of as such--filesystems, for example) rely very he…

Stratos Idreis's team has been working on exactly this. Automatic design of data structures based on workload. Their work has been on HN before: https://news.ycombinator.com/item?id=18314555

I was specifically thinking of https://homes.cs.washington.edu/~mernst/pubs/collection-synt..., but mostly because that's the paper I actually read.

Re: Topics in Advanced Data Structures [pdf]

#62

Post by jwr »

jhayward wrote: post #12

I was going to roll my eyes about stuff no one will ever hear of, much less use in their day job, but there are some really relevant structures here. Finger trees, cache-oblivious structures, R-trees, etc., just to name a couple from a random page or two. The "why they're worth studying" summaries are gold. Thanks!

> much less use in their day job

Yes, some are indeed very relevant. In one of my previous businesses, we built a search engine where we used DAWGs (Directed Acyclic Word Graphs) [I didn't do this part]. And they worked really, really well, in fact they work well to this day.

Re: Topics in Advanced Data Structures [pdf]

#63

Post by jwr »

lame88 wrote: post #5

Does anyone in their work find that they are able to employ data structures like this, and if so, what do you work on? I've almost always had to delegate all my state to a database using default indexes, etc., which is productive, yet a little disappointing, because I'm always applying my brain power instead toward more mundane tasks.

I managed to use DAWGs (Directed Acyclic Word Graphs) in a search engine, and later HyperLogLog+ and a Bloom Filter for a scalable distributed Multi-Armed Bandit implementation.

Otherwise I find that the built-in Clojure data structures are so good for all-round use that it's difficult to justify the time to use anything else, except in extreme cases.

Re: Topics in Advanced Data Structures [pdf]

#65

Post by ivalm »

lame88 wrote: post #5

Does anyone in their work find that they are able to employ data structures like this, and if so, what do you work on? I've almost always had to delegate all my state to a database using default indexes, etc., which is productive, yet a little disappointing, because I'm always applying my brain power instead toward more mundane tasks.

FM-index is super useful for large string collections.

Re: Topics in Advanced Data Structures [pdf]

#66

Post by jbn »

reubenmorais wrote: post #55
copperx wrote: post #51

Earlier quoted context omitted.

It's a pity there are no video lectures. Are there lectures out there for a similar algorithms class?

MIT 6.851 Advanced Data Structures, Spring 2012: https://www.youtube.com/playlist?list=PLUl4u3cNGP61hsJNdULdu...

I took that class that year, one of the best classes I ever took. A ton of work, too.

Re: Topics in Advanced Data Structures [pdf]

#67

Post by dominotw »

amelius wrote: post #41

> Traditional data structures assume a single-threaded execution model and break if multiple operations canbe performed at once. (Just imagine how awful it would be if you tried to access a splay tree with multiplethreads.) Can you design data structures that work safely in a parallel model – or, better yet, take maxi-mum advantage of parallelism? In many cases, the answer is yes, but the data structures look nothing…

would all of scala's default( immutable) datastructures fit the bill?

Re: Topics in Advanced Data Structures [pdf]

#68

Post by bogdanoff_2 »

This kind of stuff fascinates me. General software engineering seems comparatively boring. I was considering going back to university to do a phd in cs and this is making me realize that research in algorithms/data structure would actually be viable (still lots of stuff to discover).

Does anyone here know what it is like doing research in these areas? Any general advice?

Re: Topics in Advanced Data Structures [pdf]

#69

Post by xtracto »

bogdanoff_2 wrote: post #68

This kind of stuff fascinates me. General software engineering seems comparatively boring. I was considering going back to university to do a phd in cs and this is making me realize that research in algorithms/data structure would actually be viable (still lots of stuff to discover). Does anyone here know what it is like doing research in these areas? Any general advice?

I've got a PhD in CS, and these structures fascinate me as well. The Bloomier Filter reads amazing.

Unfortunately, day to day job has almost nothing to do with these algorithms, but mainly software architecture and maintainability.

I think the majority of these algorithms are not really something you will find implementing in day to day work. And at most I can see myself using a library with one of those. Even if you do research, it will have to be very focused on data structures and algorithms to really get deep into some of these.

Still, very enjoyable.

Post reply on HN