Homogeneous.Structures
In general, a hierarchy schema allows an exponential number of homogeneous
structures and we may express them succinctly with dimension constraints. The
situation is analogous to using propositional formulas to specify the truth values
of a set of propositions. In the framework of dimension constraints the propositions
are the atoms that state which parts of the homogeneous structure allowed.
Such structures, called frozen dimensions, are themselves important to support
visualization and to transform heterogeneous dimensions to structural adaptations
previously explained. In addition, they are the basis for an inference algorithm for
dimension constraints.
In previous work (Hurtado et al., 2005), we propose an algorithm to compute the
frozen dimensions that arise in a dimension schema. A dimension schema is a hierarchy
schema along with a set of dimension constraints. The algorithm explores
subgraphs of the hierarchy schema, and tests whether they satisfy the constraints. The
subgraphs are built by traversing the hierarchy schema from the bottom categories,
and using dimension constraints for pruning. The algorithm runs in exponential time
in the size of the schema. An experimental evaluation provided shows that the set
frozen dimensions can be computed in the order of the few seconds for dimension
schemas of around 25 categories and 120.
Pages:
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125