4 ms·

This builds on Vadim Tropashko's work related to nested intervals and is related to the Stern-Brocot and Farey sequence and Calkin-Wilf tree: Nested Intervals

by espeed 10y ago

This builds on Vadim Tropashko's work related to nested intervals and is related to the Stern-Brocot and Farey sequence and Calkin-Wilf tree: Nested Intervals Tree Encoding with Continued Fractions https://arxiv.org/pdf/cs/0402051.pdf https://arxiv.org/pdf/cs/0402051.pdf Nested Intervals Tree Encoding in SQL http://www09.sigmod.org/sigmod/record/issues/0506/p47-article-tropashko.pdf http://www09.sigmod.org/sigmod/record/issues/0506/p47-articl... Nested Set Model https://en.wikipedia.org/wiki/Nested_set_model https://en.wikipedia.org/wiki/Nested_set_model Farey sequence https://en.wikipedia.org/wiki/Farey_sequence https://en.wikipedia.org/wiki/Farey_sequence Stern–Brocot tree https://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree https://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree Calkin–Wilf tree https://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree https://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree Recounting the rationals https://www.math.upenn.edu/~wilf/website/recounting.pdf https://www.math.upenn.edu/~wilf/website/recounting.pdf The Stern-Brocot or Farey Tree http://oeis.org/stern_brocot.html http://oeis.org/stern_brocot.html Infinite Fractions - Numberphile [video] https://www.youtube.com/watch?v=DpwUVExX27E https://www.youtube.com/watch?v=DpwUVExX27E part 2: https://www.youtube.com/watch?v=zv5M9zuZiXo https://www.youtube.com/watch?v=zv5M9zuZiXo

grzm 10y ago
I explored Tropashko's work in PostgreSQL back in 2004: http://seespotcode.net/2016/04/30/static-trees/ http://seespotcode.net/2016/04/30/static-trees/ I updated it in April 2016 to then-current PostgreSQL versions. It was interesting to me to notice not only the improvements in PostgreSQL over those 12 years, but also how my own practices had changed.
jakeogh 10y ago
Supercool. I tried to wrap my head around the reverse continued fractions technique a few years ago [1] and got lost evaluating the other methods. Is it reasonable to call this a bidirectional version of Tro05? Skipping the inequality flips and the "lowest index last" by/and encoding snv and sdv (all of them, before they exist, in order) with their parent seems like a very useful improvement to only being able to calc the parents from a sibling and having to count down as the tree grows. Hopefully I didn't butcher that, corrections appreciated. Predicates 2.5 and 2.6 intuitively are more descriptive and easier to visualize than the Cel04 nested sets 1.1 and 1.2. numberphile and all of Brady's chans[2] are pure platinum. [1] http://911datasets.org/index.php/Help:Tree_Structures http://911datasets.org/index.php/Help:Tree_Structures [2] https://www.youtube.com/user/BradyStuff https://www.youtube.com/user/BradyStuff

by espeed 10y ago

grzm 10y ago

I explored Tropashko's work in PostgreSQL back in 2004: http://seespotcode.net/2016/04/30/static-trees/ http://seespotcode.net/2016/04/30/static-trees/ I updated it in April 2016 to then-current PostgreSQL versions. It was interesting to me to notice not only the improvements in PostgreSQL over those 12 years, but also how my own practices had changed.

jakeogh 10y ago

Supercool. I tried to wrap my head around the reverse continued fractions technique a few years ago [1] and got lost evaluating the other methods. Is it reasonable to call this a bidirectional version of Tro05? Skipping the inequality flips and the "lowest index last" by/and encoding snv and sdv (all of them, before they exist, in order) with their parent seems like a very useful improvement to only being able to calc the parents from a sibling and having to count down as the tree grows. Hopefully I didn't butcher that, corrections appreciated. Predicates 2.5 and 2.6 intuitively are more descriptive and easier to visualize than the Cel04 nested sets 1.1 and 1.2. numberphile and all of Brady's chans[2] are pure platinum. [1] http://911datasets.org/index.php/Help:Tree_Structures http://911datasets.org/index.php/Help:Tree_Structures [2] https://www.youtube.com/user/BradyStuff https://www.youtube.com/user/BradyStuff