orthogonal lists

(data structure)

Definition: Lists that share items, but are structurally independent.

Aggregate parent (I am a part of or used in ...)
sparse matrix.

Aggregate child (... is a part of or used in me.)

Note: The lists are interweaved through items. For instance, we may keep people on three orthogonal lists by hair color, gender, and country of residence or data values in a sparse matrix on two orthogonal lists by row and column. Inserting an item means inserting it into each list as appropriate.

Author: PEB

More information

PowerPoint lecture notes of using orthogonal lists to implement a sparse matrix.

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 19 February 2019.
HTML page formatted Wed Mar 13 12:42:46 2019.

Cite this as:
Paul E. Black, "orthogonal lists", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 19 February 2019. (accessed TODAY) Available from: