Re: [boost] new proposal: order statistics tree

Subject: Re: [boost] new proposal: order statistics tree
From: Vadim Stadnik (vadimstdk_at_[hidden])
Date: 2013-01-08 08:55:01

On Tue, Jan 8, 2013 at 7:31 AM, Gottlob Frege <gottlobfrege_at_[hidden]>wrote:

 Basically both an order statistics tree and boost multi-index are examples
> of containers with multiple indices.  I suspect there may be interesting
> results from a compare/contrast type of study.
>
> Boost MultiIndex allows indexing of a container via any number/type of
> indices.  So you could have a container indexed via key, and also indexed
> via integer.  Now the difference, I think, is that MultiIndex uses
> independent indexes - changing a entry's key from "alpha" to "beta" doesn't
> change its integer index from 1 to 2.
>
> So that is a significant difference.  Might be worth mentioning in docs or
> somewhere, just to avoid confusion.
>
> But furthermore, I could probably implement the same behaviour as a order
> statistics tree by using Boost.MultiIndex internally (and maintaining the
> interrelationships of the indices as needed).  Would that be drastically
> less efficient?
>
>
+1.
This is a very good comment and I think there is no simple answer. I was
asked similar questions during Boost discussion of augmented dynamically
allocated B+ trees, this is why I would like to make a few comments based
on my analysis.

The fact that creates an overlap with Boost.MultIndex and can cause
confusion is that augmented data structures support multiple augmenting.

For example, basic balanced tree provides efficient search of elements by
keys. This tree requires a comparison object. Augmenting of such tree by
counter of elements adds efficient access to elements by rank, which is
equivalent to index value in the subscript operator of an array or
std::vector. This variant of tree has extended functionality and can work
both with and without a comparison object. In other words, it offers
equally efficient operations for both ordered and unordered containers. Yet
another augmenting by the sum of values in children
nodes improves computational complexity of calculation of sum of any number
of consecutive elements from linear to logarithmic. As a result of the
double augmenting, the calculation of the mean value and standard deviation
can be done in O(log N) time only.

Such variants of augmented data structures support STL sequences and
associative containers with improved efficiency of specific member
functions. In applications that require multiple views of a data set
these augmented data structures and containers cannot replace
Boost.MultiIndex functionality.

On the other hand, replacing functionality of augmented data structures
with Boost.MultiIndex should be generally possible. However, this solution
will be less efficient in the case when an augmented data structure offers
a set of more efficient algorithms compared to data structures of
Boost.MultiIndex. The disadvantage of this approach is that one less
efficient operation can cause a performance bottleneck. Normally, augmented
data structures offer the improvement of the running time from O(N) down to
O(log N) for a single operation or an algorithm.

This performance benefit of augmented data structures certainly should not
be ignored by Boost.MultiIndex. Unfortunately, at this stage it is not
possible for a user algorithm to take advantage of Boost.MultiIndex with
advanced data structures. This example shows declaration of a multiset:

    typedef multi_index_container<int,
indexed_by<ordered_non_unique<identity<int>>>>
                multi_set_int ;

The obvious idea of a parameterization of containers used by views of
Boost.MultiIndex is potentially useful, but deeper analysis shows that it
is quite difficult and costly to implement. Boost.MultiIndex has special
non-standard requirements to the view containers. For example, std::vector
cannot be used in place of random access indices, since it does not remain
stable after insertion or erasure operations.

Hope that the discussion helps better understand the complexity of these
issues.

Regards,
Vadim Stadnik