# accumulo-user mailing list archives

##### Site index · List index
Message view
Top
From Keith Turner <ke...@deenlo.com>
Subject Re: recursive rollup
Date Tue, 10 Apr 2012 22:21:53 GMT
```Take a look at the
org.apache.accumulo.examples.simple.dirlist.FileCount example,  I
think it does what you are asking.

The way it works it that assume your tree would be stored in accumulo
as follows.

000/A
001/A/B
001/A/C
002/A/B/D
002/A/B/E
002/A/C/F
002/A/C/G

The number before the path is the depth, therefore all data for a
particular depth of the tree is stored contiguously.  The example
program scans each depth, starting with the highest depth, and push
counts up.  This very efficient because there is not a lot of random
to the lower depth.

For example when reading level 002, it would do the following two inserts :

001/A/B count=2
001/A/C count=2

Then it would read level 001 and push the following insert :

000/A count = 5

Keith

On Tue, Apr 10, 2012 at 6:02 PM, Perko, Ralph J <Ralph.Perko@pnnl.gov> wrote:
> Hi, I wish to do a recursive rollup-count and am wondering the best way to
> do this.
>
> What I mean is this ­ in accumulo is a table with data that represents the
> nodes and leafs in a tree.  Each node/leaf in accumulo knows it's parent
> and children and wether it is a node or leaf.  I wish to have a
> rollup-count for any given node to know the combined total of all
> descendants.
>
> For example, given the tree:
>
>                          A
>                          |
>                       --------
>                       |      |
>                       B      C
>                       |      |
>                     -----  -----
>                     |   |  |    |
>                     D   E  F    G
>
> "A" would have 6 descendants.
>
> I can use the SummingCombiner iterator to get a child count, e.g "A" has 2
> children, but I am not sure the best way to recurse down.  The data is
> static so I do not necessarily need a dynamic, on-the-fly solution.
>