On Mon, Apr 2, 2018 at 8:02 AM, Derrick Stolee <stolee@xxxxxxxxx> wrote: >>> >>> I would be happy to review any effort to extend the commit-graph >>> format to include such indexes, as long as the performance benefits >>> outweigh the complexity to create them. >>> >>> [2] >>> http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.719.8396&rep=rep1&type=pdf >> >> The complexity of calculating FELINE index is O(|V| log(|V|) + |E|), the >> storage complexity is 2*|V|. >> > > This would be very easy to add as an optional chunk, since it can use one > row per commit. Given this discussion, I wonder if we want to include generation numbers as a first class citizen in the current format. They could also go as an optional chunk and we may want to discuss further if we want generation numbers or FELINE numbers or GRAIL or SCARAB, which are all graph related speedup mechanism AFAICT. In case we decide against generation numbers in the long run, the row of mandatory generation numbers would be dead weight that we'd need to carry. I only glanced at the paper, but it looks like a "more advanced 2d generation number" that seems to be able to answer questions that gen numbers can answer, but that paper also refers to SCARAB as well as GRAIL as the state of the art, so maybe there are even more papers to explore? Stefan
