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

11–20 of 89 posts

Re: Topics in Advanced Data Structures [pdf]

#11

Post by oplav »

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.

It's not as interesting as some of the structures in the PDF, but we are working on a problem where we have lots of timestamped data and need to quickly and frequently access the nearest data point from a given input timestamp. We ended up using a tree-like structure but that said, we ended up using whatever tree-like structure was available in the language.

Re: Topics in Advanced Data Structures [pdf]

#12

Post by jhayward »

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!

Re: Topics in Advanced Data Structures [pdf]

#13

Post by [deleted] »

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.

[deleted]

Re: Topics in Advanced Data Structures [pdf]

#14

Post by ska »

lichtenberger wrote: post #10
danharaj wrote: post #7

Earlier quoted context omitted.

I've seen it used in blockchain analysis and calculating the base for a three way merge operation.

So much stuff you can learn in the computer science world. For me the blockchain still is more or less a black box, should read a book about this stuff, as it seems to be hyped everywhere ;-) Thanks :)

Perhaps worth starting with Merkel trees before digging into blockchain implementations.

Re: Topics in Advanced Data Structures [pdf]

#15

Post by robmaister »

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.

Gamedev, but even then actually implementing the data structures is rare. And nothing outside of geometric/parallel data structures listed towards the end.

I've had to use a concurrent priority queue once (locking a regular priority queue was too slow, dropped in a concurrent implementation), implemented kd trees a few times, and I've used half-edge once (a cousin of quadedges). Mainly doing graphics work.

Often the naive data structures work better because there's less indirection and it's easier to vectorize. In my case, depending on how much GPU budget you have available, you can also just scrap the CPU implementation and throw it in a compute shader.

Re: Topics in Advanced Data Structures [pdf]

#16

Post by urbanslug »

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'm a Bioinformatics student, so it's not for work, but I have been looking into Suffix Arrays, BWTs and FM indexes for my project.

I've seen them applied to some real world next gen genomic tools for example this one https://github.com/vgteam/odgi implements a multi string BWT. Technically they're in academia and not making money afaik but it's interesting stuff.

Re: Topics in Advanced Data Structures [pdf]

#18

Post by vsef »

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.

Work in speech recognition, from this list use lots of advanced automata algorithms, bloomier filters, interesting types of hashing, fancy priority queues.

Re: Topics in Advanced Data Structures [pdf]

#19

Post by nestorD »

beeforpork wrote: post #17

The list is great, but unfortunately has no pointers to documentation. I find nothing online for some of the topics. Where can I find the description and discussion of 'ravel trees'?

They also caught my eyes. I finally found a paper here (the correct denomination seems to be RAVL tree) : http://sidsen.azurewebsites.net/papers/ravl-trees-journal.pd...
Post reply on HN