Re: [boost] [Boost Graph Library] Possible succint data structure addition

9 Feb 2020

      A 2020-02-09 20:09, Mateusz Loskot via Boost escreveu:
...
On Sun, 9 Feb 2020 at 14:18, degski via Boost  
wrote:
...
On Sat, 8 Feb 2020 at 11:43, Joana Modesto Hrotko via Boost 
 wrote:
...
Dear Boost community,
I am a Master's student and currently working on my Master thesis.
My Master Thesis consists in implementing the k2-tree data structure in
C++ and one of the additional proposals for my thesis would be to
integrate my code with the boost graph library.I believe this
integration
would bring great value to the boost library and also it would provide a
better validation for my work.
So my question is if this would be something of interest for the library
to integrate with boost graph library.
INFO ABOUT K2-TREE:
The k2-tree have been proved successful to represent in a very compact
way different kinds of binary relations, such as web graphs, RDFs or
raster data.
Binary relations can be an abstraction to represent the relation between
the objects of two collections of different nature: graphs, trees,
strings, among others. They can be used in several low-level structures
within a more complex information retrieval system, or even replace one
of the most used one: an inverted index can be regarded as a binary
relation
between the vocabulary of terms and the documents where they appear.
Moreover,
it can represent the relation between terms and web pages, or even
social
networks or the connection between the web pages in the Web, which is
normally
represented as a web graph. k2-trees have been also used in other
scenarios,
such as geographical and RDF data, or images.
Brisaboa, Nieves R., et al. "Compressed representation of dynamic binary
relations with applications." Information Systems 69 (2017): 106-123.
Coimbra, Miguel E., et al. "On dynamic succinct graph representations."
arXiv preprint arXiv:1911.03195 (2019).
Great subject for a thesis. Munro, the man of the beap
https://github.com/pfalcon/beap (a dynamic implicit data structure
https://github.com/pfalcon/awesome-implicit-data-structures). I 
don't
really understand why you would like a dynamic k2-tree, you can just 
as
well have a static one
https://github.com/degski/KD-Tree/blob/master/KD-Tree/ikdtree.hpp
By the way, I think k2-tree which is of Joana interest may be one of
the special cases
of the k-ary https://github.com/boostorg/graph/pull/139
Best regards,
Hi

first of all thank you so much for the reply of all of you.

So the k2-tree is a succint data structure and it is equivalent to a web 
graph,
so conceptually is somehow similar to the k-ary tree however, 
implementation wise it is not
the same.

In the k2-tree it is meant to represent the relation between nodes in a 
graph, based
on the matrix representation of the graph. In order to compress the 
information in
the matrix (hopefully sparse), the method consists in subdividing the 
binary matrix
into k rows and k columns, thus producing k2 submatrices of size n/k by 
n/k. Each of
these submatriceswill be a child of the root node and its value will be 
1 iff there
is at least one 1 in the cells of the submatrix. A 0 child means that 
the submatrix
has all 0s and hence the tree decomposition ends there. Once the level 
1, with the
children of the root, has been built, the method proceeds recursively 
for each child
with value 1, until we reach submatrices full of 0s, or we reach the 
cells of the
original matrix.
The k2-ary tree described is represented in a compact way with just two 
bit
arrays: T (tree) and L(leaves). T stores all the bits of the k2-tree 
except
those in the last level following a level-wise traversal. Bitmap L 
stores the last
level of the tree.

 From the pull requests it seems there is no similar data structure to 
the k2-tree
being implemented right now. However how hard is it to be able to 
complete the pull request?
And how is the decision taken?

Best regards,
Joana