k²-tree

(data structure)

Definition: A compact representation of a sparse directed graph. It requires 1 to 3 bits per edge. Many access functions, like successor(s), predecessor(s), and range (all links from a range of vertices to another range of vertices), have very efficient implementations.

Generalization (I am a kind of ...)
compact data structure.

Aggregate child (... is a part of or used in me.)
adjacency-matrix representation, quadtree.

Note: A k²-tree is particularly useful for Web graphs, which are very sparse. This needs (N + o(N))/N bits per edge, where N is the number of edges. Checking if there is an edge from any vertex to another takes O(log_k N), where k is the branching factor.

Author: PEB

More information

Nieves R. Brisaboa, Susana Ladra, and Gonzalo Navarro, Compact representation of Web graphs with extended functionality, Information Systems vol 39, pages 152-174, 2014. doi 10.1016/j.is.2013.08.003

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 8 June 2023.
HTML page formatted Thu Jun 8 11:24:36 2023.

Cite this as:
Paul E. Black, "k²-tree", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 8 June 2023. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/k2tree.html