carsonfarmer (u/carsonfarmer)

carsonfarmer commented on Geometric Search Trees g-trees.github.io/g_trees... · Posted by u/fanf2

yorwba · a year ago

Hmmm... if you need to go deeper (because 1/4 of all hashes have zero leading zeros and zero trailing zeros), you can generalize this by converting the hash into its run-length encoding to get a sequence of rank functions where finding values with the same rank for all rank functions is equivalent to finding hash collisions. Very nice.

carsonfarmer · a year ago

Whoah, I totally hadn't taken the thought experiment this far. This is fantastic! I'd like to explore this further, interested in a quick research chat/sync some time? My email is linked from the paper.

carsonfarmer commented on Geometric Search Trees g-trees.github.io/g_trees... · Posted by u/fanf2

carsonfarmer · a year ago

Pretty cool to see this here. My co-author and I haven't actually officially "released" this yet, so quite neat to see where it is organically showing up! Feedback appreciated y'all!

carsonfarmer commented on Geometric Search Trees g-trees.github.io/g_trees... · Posted by u/fanf2

zermelo44 · 2 years ago

The presentation of the webpage is really really nice. Especially the highlighting/linking of mathematical definitions and bound variables.

How did you achieve this?

carsonfarmer · a year ago

Thanks, that's all due to my co-author. Here's what we used: https://news.ycombinator.com/item?id=41589728 (link is to a post from @msy)

carsonfarmer commented on Geometric Search Trees g-trees.github.io/g_trees... · Posted by u/fanf2

EdSchouten · 2 years ago

Exactly. But my concern is that this is not any stronger/better than what Prolly trees already offer, which is why I'm disappointed that they are mentioned under "related work", but not discussed/compared in more detail.

carsonfarmer · a year ago

You're right, we should delve into a comparison more with respect to prolly trees. We actually have a lot of experience with prolly trees, and have found, in practice, that you need to do a lot of the things that folks like dolt have had to do to make them work nicely. Whereas with G-trees, the basic implementation turns out to be quite nice (and extremely easy to reason about).

One of the biggest benefits of G-trees in my mind, is their ease of implementation. Additionally, we did a lot of work to explore their statistical properties, which doesn't exist for prolly trees (though in hindsight, we have done this, so should probably write it up formally).

carsonfarmer commented on Geometric Search Trees g-trees.github.io/g_trees... · Posted by u/fanf2

yorwba · a year ago

Generating arbitrarily many values of the minimum rank is very easy for an attacker. Since the rank is geometrically distributed with parameter p = 1 - 1/k and k ≥ 2, randomly sampling a value will give you one of minimum rank with probability p ≥ 1/2 and it only gets easier for larger k.

If you want to break that up with dummy elements, you now have the problem of choosing those dummies in a history-independent manner efficiently.

But I think their recursive construction with G-trees of G-trees of ... might work if nodes with too many elements are stored as G-trees with a different, independent rank function (e.g. using a hash function with different salt). Producing many nodes with the same ranks should then get exponentially harder as the number of independent rank functions increases.

carsonfarmer · a year ago

Yes this exactly. Another really simple way to do this, is to use alternating leading and trailing zero counts in the hash in your nested G-trees. Simple, and pretty effective.

carsonfarmer commented on Geometric Search Trees g-trees.github.io/g_trees... · Posted by u/fanf2

randomizedalgs · a year ago

Cool paper!

As a small comment, this seems closely related to another recent paper: History-Independent Dynamic Partitioning: Operation-Order Privacy in Ordered Data Structures (PODS 2024, Best Paper).

I'm not sure how they compare, since neither paper seems to know about the other. And I'm also not sure which paper came first, since the geometric search paper does not seem to post a publication date.

carsonfarmer · a year ago

Whoah, cool. I'm one of the authors of the geometric search tree paper, and we totally hadn't see that paper, but will for sure dig in! Thanks for mentioning it.

carsonfarmer commented on Dumb Pipe dumbpipe.dev/... · Posted by u/b_fiive

carsonfarmer · 2 years ago

Ok, this is quite cool. Also love the name.

carsonfarmer commented on Show HN: Lean customer development methodology simulated by AutoGPT epiphany.fireproof.storag... · Posted by u/jchrisa

carsonfarmer · 3 years ago

Super fun example of the combination of AI and DB. You want to get back exactly what you put in, use a DB! You want something extrapolated from what you put in, AI is pretty great! Also Fireproof is :fire:

carsonfarmer commented on Textile Hub: databases, storage, and remote IPFS for app builders blog.textile.io/announcin... · Posted by u/andrewxhill

floren · 6 years ago

Thanks! I've been looking for a distributed key-value store where any node can update or delete any object in the store, and which can handle partitioning in some fashion... I'm hoping ThreadsDB might be it! Perusing the docs to see if that's true :)

carsonfarmer · 6 years ago

That's awesome, dig right in! And don't hesitate to reach out on our slack: slack.textile.io. We're under active development, so if there's something missing, or a feature that's lacking in documentation (there are, but we're working on it!) let us know.

carsonfarmer commented on Remote for small teams: Coronavirus work from home tips blog.textile.io/remote-fo... · Posted by u/carsonfarmer

carsonfarmer · 6 years ago

Just a bunch of useful tools and ideas our team has picked up along the way while being remote only for the past few years.