ekmett / ekmett/succinct

Implement forwardSearch and backwardSearch

Open
#5 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Haskell
Stars
96
Forks
9
PR merge metrics
No merged PRs in 30d

Description

The `RangeMin` tree is based on the ideas from [Fully-Functional Succinct Trees](https://cs.uwaterloo.ca/~imunro/cs840/ProjectPapers/SODA10_013_sadakanek.pdf) by Sadakane and Navarro.

However, I only store the minima rather than both minima and maxima, based on an observation in [Fast Compressed Tries through Path Decompositions](http://arxiv.org/pdf/1111.5220v2.pdf) by Grossi and Ottaviano.

I also store the encoding of the minima as a delta in order to get a proper monoid.

Since the structure I have is trivially isomorphic to Grossi and Ottaviano's, it should be capable of supporting fwd-search and bwd-search which is necessary for fast balanced-parentheses trees.

Contributor guide

No contributing guide indexed for this repository

Research direction

Start by locating the RangeMin tree and its search operations in the repository, then read the cited papers to understand forward and backward search. Done means the structure supports fwd-search and bwd-search as required for fast balanced-parentheses trees.

Written by the indexing model from the issue text.

Assessment

Tech stack
haskell
Domain
data
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.