Mailing-List: contact user-help@accumulo.apache.org; run by ezmlm
Precedence: bulk
Reply-To: user@accumulo.apache.org
Received-SPF: neutral (nike.apache.org: local policy)
MIME-Version: 1.0
In-Reply-To: <CBA9FC08.2547%ralph.perko@pnnl.gov>
References: <CBA9FC08.2547%ralph.perko@pnnl.gov>
Date: Tue, 10 Apr 2012 18:21:53 -0400
Message-ID: 
 <CAGUtCHq3i6X4-v+APWE2XvVvRfMJDQnYMKv0v7FxC0P4jdj5Jg@mail.gmail.com>
Subject: Re: recursive rollup
From: Keith Turner <keith@deenlo.com>
To: user@accumulo.apache.org
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

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
access, it sequentially reads data for each depth and stream updates
to the lower depth.

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

  001/A/B count=3D2
  001/A/C count=3D2

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

  000/A count =3D 5

Keith

On Tue, Apr 10, 2012 at 6:02 PM, Perko, Ralph J <Ralph.Perko@pnnl.gov> wrot=
e:
> Hi, I wish to do a recursive rollup-count and am wondering the best way t=
o
> do this.
>
> What I mean is this =AD in accumulo is a table with data that represents =
the
> nodes and leafs in a tree. =A0Each node/leaf in accumulo knows it's paren=
t
> and children and wether it is a node or leaf. =A0I wish to have a
> rollup-count for any given node to know the combined total of all
> descendants.
>
> For example, given the tree:
>
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0A
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0|
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 --------
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 | =A0 =A0 =A0|
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 B =A0 =A0 =A0C
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 | =A0 =A0 =A0|
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 ----- =A0-----
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 | =A0 | =A0| =A0 =A0|
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 D =A0 E =A0F =A0 =A0G
>
> "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. =A0The data is
> static so I do not necessarily need a dynamic, on-the-fly solution.
>
> Thanks for your help,
> Ralph
>