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

Applying Textbook Data Structures for Real Life Wins

heap.io

Post reply on HN
Print view View original

11–20 of 33 posts

Re: Applying Textbook Data Structures for Real Life Wins

#11

Post by whoisburbansky »

bunsenmcdubbs wrote: post #5
whoisburbansky wrote: post #2

Somehow "4 hours to 15 minutes" sounds way more impressive than 15x speed up, at least to me. From the article, it's unclear how the hashing mechanism you use actually approximates rank at all; most hashes I'm familiar with are essentially one way functions, ideally preserving no information about the input at all. How are you hashing ID's so that unions result in smaller hashes?

And great question! The hashing heuristic is a bit of a cute trick and I definitely glossed over it a bit in the post. I'll try to elaborate a bit more here... > most hashes ... are essentially one way functions, ideally preserving no information about the input at all You are correct, an individual hash does not preserve any information about the node, nor does it approximate rank in the union-find graph. We only ge…

Ahhh I see now. I was so caught up trying to think of ways to make the hash function give you this property, I didn't realize that it didn't matter and that it emerged as a result of you picking which hash to assign to a tree. Makes sense now, thanks.

Re: Applying Textbook Data Structures for Real Life Wins

#12

Post by eutectic »

bunsenmcdubbs wrote: post #5
whoisburbansky wrote: post #2

Somehow "4 hours to 15 minutes" sounds way more impressive than 15x speed up, at least to me. From the article, it's unclear how the hashing mechanism you use actually approximates rank at all; most hashes I'm familiar with are essentially one way functions, ideally preserving no information about the input at all. How are you hashing ID's so that unions result in smaller hashes?

And great question! The hashing heuristic is a bit of a cute trick and I definitely glossed over it a bit in the post. I'll try to elaborate a bit more here... > most hashes ... are essentially one way functions, ideally preserving no information about the input at all You are correct, an individual hash does not preserve any information about the node, nor does it approximate rank in the union-find graph. We only ge…

I think there's a paper somewhere claiming that completely random linking is just as good as union-by-rank (in expectation).

Re: Applying Textbook Data Structures for Real Life Wins

#13

Post by moab »

eutectic wrote: post #12
bunsenmcdubbs wrote: post #5

Earlier quoted context omitted.

And great question! The hashing heuristic is a bit of a cute trick and I definitely glossed over it a bit in the post. I'll try to elaborate a bit more here... > most hashes ... are essentially one way functions, ideally preserving no information about the input at all You are correct, an individual hash does not preserve any information about the node, nor does it approximate rank in the union-find graph. We only ge…

I think there's a paper somewhere claiming that completely random linking is just as good as union-by-rank (in expectation).

Yes, there's a few papers over the last few years on this, starting with this paper: https://www.cis.upenn.edu/~sanjeev/papers/soda14_disjoint_se...

Here is a more recent paper (from this year) analyzing concurrent union find with random linking: https://arxiv.org/pdf/2003.01203.pdf

Re: Applying Textbook Data Structures for Real Life Wins

#14

Post by bunsenmcdubbs »

moab wrote: post #13
eutectic wrote: post #12

Earlier quoted context omitted.

I think there's a paper somewhere claiming that completely random linking is just as good as union-by-rank (in expectation).

Yes, there's a few papers over the last few years on this, starting with this paper: https://www.cis.upenn.edu/~sanjeev/papers/soda14_disjoint_se... Here is a more recent paper (from this year) analyzing concurrent union find with random linking: https://arxiv.org/pdf/2003.01203.pdf

Woah these look great! Sad I didn't encounter them earlier.

Our team is actively working on improvements in this part of our data infrastructure (hence this project & blog post) so maybe there will be a follow up coming up with the next version of our Identity implementation...

Re: Applying Textbook Data Structures for Real Life Wins

#15

Post by KMag »

eutectic wrote: post #12
bunsenmcdubbs wrote: post #5

Earlier quoted context omitted.

And great question! The hashing heuristic is a bit of a cute trick and I definitely glossed over it a bit in the post. I'll try to elaborate a bit more here... > most hashes ... are essentially one way functions, ideally preserving no information about the input at all You are correct, an individual hash does not preserve any information about the node, nor does it approximate rank in the union-find graph. We only ge…

I think there's a paper somewhere claiming that completely random linking is just as good as union-by-rank (in expectation).

Isn't that expected (within a constant factor of optimal depth, a.k.a. O(log N) tree height)? They're essentially building a treap, minus the in-order traversal of keys restriction.

[0] https://en.wikipedia.org/wiki/Treap

Re: Applying Textbook Data Structures for Real Life Wins

#16

Post by KMag »

bunsenmcdubbs wrote: post #5
whoisburbansky wrote: post #2

Somehow "4 hours to 15 minutes" sounds way more impressive than 15x speed up, at least to me. From the article, it's unclear how the hashing mechanism you use actually approximates rank at all; most hashes I'm familiar with are essentially one way functions, ideally preserving no information about the input at all. How are you hashing ID's so that unions result in smaller hashes?

And great question! The hashing heuristic is a bit of a cute trick and I definitely glossed over it a bit in the post. I'll try to elaborate a bit more here... > most hashes ... are essentially one way functions, ideally preserving no information about the input at all You are correct, an individual hash does not preserve any information about the node, nor does it approximate rank in the union-find graph. We only ge…

I think a simplified explanation is that, assuming your hash function is ideal (can be assumed to be random, except for being deterministic), you end up building a treap, minus the treap's restriction on the in-order traversal of keys and restriction on the number of children. The height of a treap is O(log N), so your solution is expected to be within a constant factor of an optimal solution.

[0] https://en.wikipedia.org/wiki/Treap

Re: Applying Textbook Data Structures for Real Life Wins

#17

Post by KMag »

georgewfraser wrote: post #10
bunsenmcdubbs wrote: post #8

Earlier quoted context omitted.

Yes! You are correct. This ensures that we are able to maintain a cohesive view of the entire "user" across all their devices, browsers etc (so long as the Heap customer has a method for identifying their end user). A classic example is pre- and post- signup behavior for a single user. When a user first lands on a page, they will be anonymous and lack a canonical identity. They may come from specific referrers (searc…

It seems to me that under this scheme, if I make a single erroneous identify call, I will irreversibly merge two users. This is a surprising approach. Given that identify calls may occasionally be wrong, I would expect that identify(anonymous_id, new_canonical_id) would map anonymous_id => new_canonical_id, but would leave the rest of the set find(anonymous_id) alone.

Yea, it seems like compared to all of the other data they're logging per user, separately preserving the parent id and canonical id in the tree would have little cost and allow them to fix canonicalization errors later.

Then there's a write throughput vs read latency trade-off for reading statistics aggregated by canonical ID, but my guess is that trade-off can be made in a way they're happy with in exchange for the ability to undo mistakes.

Re: Applying Textbook Data Structures for Real Life Wins

#18

Post by lootsauce »

bunsenmcdubbs wrote: post #4

Hey, author here! I've been working on infrastructure and database-y things at Heap for the last couple years, ranging from improving Postgres performance and availability to building out services (like this one!) and refactoring, encapsulating, and optimizing core systems. I'll try to answer any questions about the post (technical or otherwise). Edit: added more details about me.

You mention the performance issues of the queries in postgres, I'm curious if a graph database would perform significantly batter?

Re: Applying Textbook Data Structures for Real Life Wins

#19

Post by nraynaud »

A few years back I had a traveling salesperson problem, I googled a bit, and somehow didn't find anything interesting, so I just created a random loop, and randomly mutated it until it got better. A few months ago I discovered a neat little heuristic: the best loop never self-intersect. And a few days ago, I found that there is a definite algorithm that gives a result whose worst case is bounded WRT to the optimal.

My question is how do you find all those algorithms? Wikipedia never really feel like a good introductory nor discovery place. In particular, some problems have been perfectly studied by scholars, but you don't find them because you have not found the keywords that will direct google in your search. And I am not a researcher, so I don't keep a tab on a domain, I'm a jack of all trades, I work on a wide set of things.

Re: Applying Textbook Data Structures for Real Life Wins

#20

Post by dlkf »

nraynaud wrote: post #19

A few years back I had a traveling salesperson problem, I googled a bit, and somehow didn't find anything interesting, so I just created a random loop, and randomly mutated it until it got better. A few months ago I discovered a neat little heuristic: the best loop never self-intersect. And a few days ago, I found that there is a definite algorithm that gives a result whose worst case is bounded WRT to the optimal. M…

OOC: how did you create your initial random loop? This was a Kaggle problem about seven years ago. The competitive solutions found a good initial guess by breaking up the domain into a grid. They would solve TSP in each grid cell, and then stitch these solutions together to get a reasonable initial global solution. If you created your initial loop greedily (as I did) you got a garbage solution, and also wasted a lot of time that you could have spent doing random swaps or simulated annealing.
Post reply on HN