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

21–30 of 89 posts

Re: Topics in Advanced Data Structures [pdf]

#21

Post by [deleted] »

lichtenberger wrote: post #9
htiek wrote: post #6

Earlier quoted context omitted.

You can use lowest common ancestor queries in conjunction with suffix trees to solve a lot of interesting string problems. For example, take two indices within a string, find their corresponding suffixes in the suffix tree, and then take their LCA. That gives you an internal node corresponding to the longest string that appears starting at both indices (this is called their "longest common extension.") You can use th…

Thanks, great use case and I have to say I have to read about genomics... :-)

[deleted]

Re: Topics in Advanced Data Structures [pdf]

#22

Post by beeforpork »

nestorD wrote: post #19
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...

Super, thanks for being better at searching! (The name makes more sense this way.) :-)

Re: Topics in Advanced Data Structures [pdf]

#23

Post by petschge »

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 do plasma simulations and recently had the problem of finding the distance to the nearest neighbor for every of the particles in the simulation. Doing that naively is O(n^2) and took hours even for small test problems. Building an R-tree once and using if for nearest-neighbor look-ups brought that down to 5 minutes.

libspatialindex lacks documentation, but worked really nicely. The rtree interface in python is much friendlier.

Re: Topics in Advanced Data Structures [pdf]

#24

Post by chrisseaton »

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.

You've answered your own question - the person writing the database you're using, for example.

Re: Topics in Advanced Data Structures [pdf]

#25

Post by kevinventullo »

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 hard to beat an R-Tree for doing in-memory geospatial queries.

Re: Topics in Advanced Data Structures [pdf]

#26

Post by segmondy »

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.

computing is so cheap that most people can delegate to a database. at some point tho, if money is a problem and you don't have the computing resources, you can squeeze more out of that hardware by using more specialized DBs, (graph, doc, column), something like redis, etc, but then at some point those might not map very nice to your problem and in which case custom data structures will get you far. Hence the reason FAANGs are big on algorithm & DS questions during interviews.

Re: Topics in Advanced Data Structures [pdf]

#29

Post by holy_city »

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.

Pro multimedia software here. We deal with fundamentally concurrent architectures with a variety of not-so-soft realtime requirements. So thread safety, lock/wait free guarantees, and cache performance are my key concerns.

Most off-the-shelf data structures are poorly suited for that environment so I need to roll my own or modify existing structures. I'm no data structure expert, so this kind of stuff is really helpful.

Re: Topics in Advanced Data Structures [pdf]

#30

Post by atombender »

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 recently had to store large numbers of geospatial points (lat/lng pairs with data) in RAM for querying. I used a basic quad tree, which is similar to R-trees, but much simpler. Getting a subset of the points based on a bounding box is very fast and simple.
Post reply on HN