0
$\begingroup$

I've been reading this paper on the persistence algorithm:

https://people.mpi-inf.mpg.de/~mkerber/ck-phcwat-11.pdf

Given a matrix M with columns $M_j$.

it states on page 3 that we may add two columns $M_j+ M_i$ and store it at $M_j$ in time $\#M_i * log(\#M_i + \#M_j)$

where $\#M_i$ is the number of nonzero entries of column j.

using a binary search tree to represent the nonzero entries of each column.

Can anyone explain how the column addition would work? I think I'm just missing something very simple.

$\endgroup$
0
$\begingroup$

see https://www.geeksforgeeks.org/merge-two-balanced-binary-search-trees/

say we have: $M_1 \gets M_1+M_2$

representing each bit vector $M_i$ by a binary tree $T_i$ with nonzero entries as nodes, we may add two bit vectors $M_1$ and $M_2$ by merging binary trees $T_2$ into $T_1$. For each node n $\in T_2$, if $T_1 $and $T_2$ share the node n, we delete that node in $T_1$. otherwise we insert the node n into $T_1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.