Re: [boost] Countertree

Subject: Re: [boost] Countertree
From: Francisco José Tapia (fjtapia_at_[hidden])
Date: 2012-11-22 08:11:42

I have read the Policy- Based Data Structures of GCC and the Boost
Accumulator library. I think the problem is the same for the two.

 The statistical operations are done over current data structures as
arrays, vectors, map , hash... Each data structure have some advantages and
several problems.

 The problem is the number of operations over the data structure. If you
need obtain a statistical value over a collection of data, and need to
obtain only a few times, many data structure can satisfy you requirements.
The problem is when you need to do a lot of times, by example, you have
intervals, and you need to detect the intersection between them in order to
calculate a collision, in a particle simulation.

 With that problem, the solution to the problem pass for to redesign the
data structure used. The augmented trees are a possible solution of many of
these problems. But it is complex.

 The countertrees are augmented data structures. I redesign the insertion
deletion and balanced algorithms. The actual version is around 10% - 15%
slower than the GCC version of red-black
trees.

 I have designed on paper a new algorithms for to insert, delete and
balance the countertree, in order to improve the speed. In the new version
you have a catalog of operations with the nodes. All the insertion,
deletion and balancing can be done combining operations of this catalog.

The node operations have two parts, the pointers and the node color, and
the augmented information.In the countertree the augmented information are
the node counters.

If you design the process to do with your augmented information for all the
operations of the catalog, you can create your augmented balanced tree
mixing the pointer and color operations with your code for each operation.

 You can have augmented trees with several concepts, like the position,
accumulators and statistical operations as are defined in the Policy Based
Data Structures and in the Boost Accumulator library. In the node operation
you mix the pointers and color operations with the process of the catalog
for all the augmented informations added.

 I am working now on the concurrent version of the countertree. When finish
with this , I will begin with the augmented data trees.

 The solution exposed can be combined with the concurrent process, which
can improve a lot the speed of these accumulators, statistical operations
or any other idea.

If you are interested, when I have something useful , I will comment and
offer to you.

Sincerely yours

Francisco

2012/11/22 Andrii Sydorchuk <sydorchuk.andriy_at_[hidden]>

> Hi Francisco,
>
> First of all I think that your library will be a great addition to Boost.
> To make it even better I will suggest to make CounterTree more generic:
>
> 1) Expand CounterTree implementation to RangeTree (the name might be
> different).
> RangeTree is a data structure that supports any operation on its nodes that
> is
> associative ((a*b)*c = a*(b*c)) and commutative (a*b = b*a). The examples
> of such
> an operation are: addition, multiplication, gcd, xor, bit count, etc.
> RangeTree allows to execute the following operations in logarithmic time:
> a) insertion / removal / lookup of the new element by key;
> b) operation evaluation on the tree nodes within the given key range.
>
> 2) Considering above, expand RangeTree to support any type of operation
> argument (I call it property).
> E.g. for the CounterTree this is an integer representing number of elements
> in a subtree,
> for the ColourTree this can be node colour and operation defined as mixing
> all the colours in the subtree.
>
> 3) Considering 1) and 2), it will be possible to implement CounterTree as
> specialization of RangeTree.
> Augmented tree, recently requested by Phil Endecott for dynamic text width
> querying,
> can be implemented as specialization of the RangeTree data structure as
> well.
>
> 4) Summarizing all of the above the RangeTree declaration will look like:
> template <class Key, class Compare, class Property, class Operation, class
> Allocator> class RangeTree;
> Property RangeTree::query(const Key& left, const Key& right); // basic
> query interface
>
> The CounterTree specialization:
> template <class Key, class Compare, class Allocator> class CounterTree :
>   RangeTree<Key, Compare, int, addition<int>, Allocator>;
>
> And even more, the CounterRangeTree specialization:
> template <class Key, class Compare, class Property, class Operation, class
> Allocator> class CounterRangeTree :
>   RangeTree<Key, Compare, pair<int, Property>, operation< addition<int>,
> Operation >, Allocator>;
> Property CounterRangeTree::query(int start_index, int end_index); //
> counter query interface
>
>
> Such a design will widely expand application area of the library and will
> allow to use it
> for the large number of live updating/querying systems.
>
> Regards,
> Andrii
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>