Skip to main content
Computer Science

Return to Question

Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
added 411 characters in body
Source Link
ynimous
ynimous
  • 101
  • 1

Using dyadic intervals, I can build a binary tree for $\left[0,+\infty\right)$ by having a node the $i$-th at level $l$ representing the range $\left[i\cdot2^l,(i+1)\cdot2^l\right)$ and has the $(i)$- and $(i+1)$ at level $l-1$ as children.

I would like to build a similar tree for $(-\infty,+\infty)$, but it is not clear to me how this can be done using a single tree. One solution would be to use two binary trees as described above, one for positive and one for negative numbers. Is there a solution that uses a single tree? The tree does not have to be binary, but it would be good if there is a bound on the branching factor.

The intended use of this is to maintain information about floating point values. That is, $l$ can also be negative. It can be used, for example, to do approximate percentile queries. See for example: https://github.com/twitter/algebird/blob/develop/docs/src/main/tut/datatypes/approx/q_tree.md and https://github.com/twitter/algebird/blob/develop/algebird-core/src/main/scala/com/twitter/algebird/QTree.scala.

Using dyadic intervals, I can build a binary tree for $\left[0,+\infty\right)$ by having a node the $i$-th at level $l$ representing the range $\left[i\cdot2^l,(i+1)\cdot2^l\right)$ and has the $(i)$- and $(i+1)$ at level $l-1$ as children.

I would like to build a similar tree for $(-\infty,+\infty)$, but it is not clear to me how this can be done using a single tree. One solution would be to use two binary trees as described above, one for positive and one for negative numbers. Is there a solution that uses a single tree? The tree does not have to be binary, but it would be good if there is a bound on the branching factor.

Using dyadic intervals, I can build a binary tree for $\left[0,+\infty\right)$ by having a node the $i$-th at level $l$ representing the range $\left[i\cdot2^l,(i+1)\cdot2^l\right)$ and has the $(i)$- and $(i+1)$ at level $l-1$ as children.

I would like to build a similar tree for $(-\infty,+\infty)$, but it is not clear to me how this can be done using a single tree. One solution would be to use two binary trees as described above, one for positive and one for negative numbers. Is there a solution that uses a single tree? The tree does not have to be binary, but it would be good if there is a bound on the branching factor.

The intended use of this is to maintain information about floating point values. That is, $l$ can also be negative. It can be used, for example, to do approximate percentile queries. See for example: https://github.com/twitter/algebird/blob/develop/docs/src/main/tut/datatypes/approx/q_tree.md and https://github.com/twitter/algebird/blob/develop/algebird-core/src/main/scala/com/twitter/algebird/QTree.scala.

Source Link
ynimous
ynimous
  • 101
  • 1

Build a tree for $(-\infty,+\infty)$ similar to dyadic interval trees for $\left[0,+\infty\right)$

Using dyadic intervals, I can build a binary tree for $\left[0,+\infty\right)$ by having a node the $i$-th at level $l$ representing the range $\left[i\cdot2^l,(i+1)\cdot2^l\right)$ and has the $(i)$- and $(i+1)$ at level $l-1$ as children.

I would like to build a similar tree for $(-\infty,+\infty)$, but it is not clear to me how this can be done using a single tree. One solution would be to use two binary trees as described above, one for positive and one for negative numbers. Is there a solution that uses a single tree? The tree does not have to be binary, but it would be good if there is a bound on the branching factor.