Re: [boost] Review managers wanted for augmented data structures

Subject: Re: [boost] Review managers wanted for augmented data structures
From: Vadim Stadnik (vadimstdk_at_[hidden])
Date: 2013-04-06 09:20:00

On Sat, Apr 6, 2013 at 1:39 AM, James Hirschorn <james.hirschorn_at_[hidden]
> wrote:

> Vadim Stadnik wrote
>
...

> >
> > Augmented trees are non-standard due to different performance guarantees.
> > At the same these data structures are beneficial for complex algorithms,
> > since they offer a wider set of more efficient operations compared to
> > standard containers. The typical performance improvement for one
> operation
> > is O(log N) against O(N). For less efficient operations these trees
> > normally provide running time O(log N) against O(1), which is good enough
> > for many applications.
>
> This is very similar to a project I have been working on, with the
> intention
> of submitting to boost. The new data structure I have implemented is called
> a skip list. They can be used in place of balanced trees, and according to
> the inventor, insertion and deletion are significantly faster than for
> balanced trees (I have not tested this yet). See, e.g.
>
> William Pugh. 1990. Skip lists: a probabilistic alternative to balanced
> trees. Commun. ACM 33, 6 (June 1990), 668-676. DOI=10.1145/78973.78977
> http://doi.acm.org/10.1145/78973.78977
>
> The difference in performance guarantees are much more subtle than you
> describe above. For example, skip lists have expected O(log n) insert,
> delete and search, versus O(log n). In practice, the expected O(log n) time
> is just as good as true O(log n), unless a performance bound is required
> with certainty, because the probability of the skip list having height much
> larger than log n is extremely low. I also implemented what I called
> augmented skip lists, which allow for expected O(log n) rank lookup (i.e.
> random access). I wasn't aware of the counter tree library, or else I would
> probably have just used it instead of implementing skip lists.
>
> I used skip lists to provide "drop in" STL replacements. Now I have
> skip_list::set and skip_list::multiset, and I could similarly make
> skip_list::map and skip_list::multimap. There is also
> augmented_skip_list::set and augmented_skip_list::multiset. For now the
> augmented versions have an additional member function nth_element providing
> E[O(log n)] random access.
>
> Hopefully, this will be helpful towards the goals you have described.
>

IMO, the basic and augmented skip lists that support interfaces of STL
containers would be a valuable addition to Boost library. Skip lists have
an important advantage of relatively simple search and update operations.

Quite obviously, you when you propose these data structures, you will have
the problem of explaining the usefulness of these data structures as they
have non-standard computational complexities of some STL interface
functions.

I am interested in performance of various augmented data structures.
Comparison of deterministic data structures with randomized should be
particularly interesting. Please let me know when you finish and publish
your project. I will be happy to analyze your data structures and test
their performance.

...

> > Are there Boost experts who could volunteer to take responsibility of
> > review manager for any of these two libraries?
>
> Data structures are very interesting to me, and I am in between jobs, so I
> have time to review one of these.
>
> If I take the time to review, I hope someone will be willing to review my
> skip list library, if I complete it and submit it to boost.
>
>
If you mean the role of the review manager, then I really appreciate that
you agreed. However, there are Boost rules for a formal review and I am not
sure if you are eligible for this role. Hopefully, one of experienced Boost
members will help answer this question.

As for just review, I am interested in any helpful comments and suggestions
concerning advanced data structures.

Regards,
Vadim Stadnik