4 ms·

Very cool point, and it applies to any tree data in general. I like to represent tree data with parent, type, and data vectors along with a string table, so ev

Very cool point, and it applies to any tree data in general. I like to represent tree data with parent, type, and data vectors along with a string table, so everything else is just small integers. Sending the string table and type info as upfront headers, we can follow with a stream of parent and data vector chunks, batched N nodes at a time. Tye depth- or breadth-first streaming becomes a choice of ordering on the vectors. I'm gonna have to play around with this! Might be a general way to get snappier load time UX on network bound applications.

x-complexity 1y ago
... It might be a pursuit worth making a small library for.
- deleted 1y ago
  [deleted]
thethimble 1y ago
You can even alternate between sending table and node chunks! This will effectively allow you to reveal the tree in any order including revealing children before parents as well as representing arbitrary graphs! Could lead to some interesting applications.
- xelxebar 1y ago
  Good point! The parent vector rep is what allows arbitrary node order, but chunking the table data off chunks of node IDs is brilliant idea. Cheers!
dmkolobov 1y ago
If you send the tree in preorder traversal order with known depth, you can send the tree without node ids or parent ids! You can just send the level for each node and recover the tree structure with a stack.
- xelxebar 1y ago
  Well the whole point is to use a breadth first order here. I don't think there's a depth vector analogue for breadth first traversals. Is there? But, indeed, depth vectors are nice and compact. I find them harder to work with most of the time, though, especially since insertions and deletions become O(n), compared to parent vector O(1). That said, I do often normalize my parent vectors into dfpo order at API boundaries, since a well-defined order makes certain operations, like finding leaf siblings, much nicer.
  - ummonk 1y ago
    I’m not familiar with depth vectors, but wouldn’t the breadth first traversal analogue of each entry specifying its depth (in a depth first format) be each entry specifying the number of immediate children it has?
  - dmkolobov 1y ago
    Yeah, it has its limits for sure. I like it for the streaming aspect. I think you can still have the functionality described in the article: you would send “hole” markers tagged with their level. Then, you could make additional requests when you encounter these markers during the recovery phase, possibly with buffering of holes. It becomes a sort of hybrid DFS/BFS approach where you send as much tree structure at a time as you want.

x-complexity 1y ago

... It might be a pursuit worth making a small library for.

deleted 1y ago
[deleted]

thethimble 1y ago

You can even alternate between sending table and node chunks! This will effectively allow you to reveal the tree in any order including revealing children before parents as well as representing arbitrary graphs! Could lead to some interesting applications.

xelxebar 1y ago
Good point! The parent vector rep is what allows arbitrary node order, but chunking the table data off chunks of node IDs is brilliant idea. Cheers!

dmkolobov 1y ago

If you send the tree in preorder traversal order with known depth, you can send the tree without node ids or parent ids! You can just send the level for each node and recover the tree structure with a stack.

xelxebar 1y ago
Well the whole point is to use a breadth first order here. I don't think there's a depth vector analogue for breadth first traversals. Is there? But, indeed, depth vectors are nice and compact. I find them harder to work with most of the time, though, especially since insertions and deletions become O(n), compared to parent vector O(1). That said, I do often normalize my parent vectors into dfpo order at API boundaries, since a well-defined order makes certain operations, like finding leaf siblings, much nicer.
- ummonk 1y ago
  I’m not familiar with depth vectors, but wouldn’t the breadth first traversal analogue of each entry specifying its depth (in a depth first format) be each entry specifying the number of immediate children it has?
- dmkolobov 1y ago
  Yeah, it has its limits for sure. I like it for the streaming aspect. I think you can still have the functionality described in the article: you would send “hole” markers tagged with their level. Then, you could make additional requests when you encounter these markers during the recovery phase, possibly with buffering of holes. It becomes a sort of hybrid DFS/BFS approach where you send as much tree structure at a time as you want.