Methods and systems for multi-dimensional data labeling. A structured data set having a plurality of rows is obtained, the structured data set comprising a set of data attributes, each data attribute having a data value for each of the plurality of rows of the structured data set. The structured data set is decomposed into a plurality of dimensions, each dimension defining a proper subset of the data attributes based on coherence criterion. A dimension label is obtained for each dimension of at least a portion of the plurality of rows of the structured data set and the dimension labels for a given one of the rows of the structured data set are consolidated into at least one row label for the given one of the rows.