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

Subject: Re: [boost] Review managers wanted for augmented data structures
From: James Hirschorn (james.hirschorn_at_[hidden])
Date: 2013-04-05 11:39:39

Vadim Stadnik wrote
> Hi all,
> 
> 
> At present, neither Boost library nor STL provides containers using
> augmented data structures. I suggest that the Boost community consider
> solving the challenging problem – how to extend STL by integrating
> advanced
> data structures.
> 
> ...
> 
> 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.

> There are two libraries in the Boost review schedule:
> 
> http://www.boost.org/community/review_schedule.html
> 
> "STL Extensions" and "Countertree". None of them has as yet a review
> manager. The order of the reviews may not be significant. It is more
> important that at least one library pass the review. This would help
> integrating other advanced data structures.
> 
> 
> 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.

--
View this message in context: http://boost.2283326.n4.nabble.com/Review-managers-wanted-for-augmented-data-structures-tp4643472p4644887.html
Sent from the Boost - Dev mailing list archive at Nabble.com.