Avec l'avènement de l'informatique et d'Internet, il est devenu primordial de concevoir et d'étudier des structures de données et des algorithmes permettant de manipuler des données de grande taille. En particulier, il est connu que des améliorations considérables peuvent être obtenues en concevant des structures de données munies d'algorithmes qui permettent d'économiser non seulement de l'espace de stockage, mais également de réduire le temps d'exécution d'une requête ou d'une modification des données.

Dans cette perspective, une structure de données appelée binary decision diagram (BDD) a été popularisée par R. E. Bryant vers la fin des années '80. L'importance de ses travaux a été telle que son article compte aujourd'hui plus de 8 500 citations et il a été, pendant un certain temps, le papier le plus cité en informatique. Quelques années plus tard, en 1993, S. Minato a proposé une variante au modèle de Bryant appelée zero-suppressed decision diagram (ZDD), qui s'avère une alternative efficace dans des cas où les BDD sont moins performants.

Bien que les BDD/ZDD soient très puissants, ils ne sont évidemment pas adaptés à toutes les situations. L'objectif de ce projet est d'étudier une structure de données alternative nouvelle appelée « arbre union-cat », en particulier la nature des requêtes et des opérations pouvant agir sur ceux-ci ainsi que les contextes pratiques dans lesquels ils s'avèrent utiles.