Parsimonious multi-resolution value-item lists
AssigneeMicrosoft Corporation
InventorsBo Thiesson, Roland Franz Memisevic
Life of this patent
Estimating the term…
Abstract
Systems and methods are provided for parsimonious representation of large sets of multi-resolution value-item lists. A hierarchical data structure associated with the lists and conditioning variables is learnt while exploiting both semantics encoded in target variables and a notion of nearness among nodes at the same detail level in the hierarchical data structure. Such a level of description can be dictated by a depth in a tree data structure. A compression scheme that relies on (i) a similarity metric and (ii) recursive greedy pairing of value-item lists in order to promote elements populating a specific tree node upwards in the tree facilitates a parsimonious representation of the compressed hierarchic structure.
Claims20
A method for generating a parsimonious multi-resolution representation of value-item lists, the method comprising:
- receiving a set of values for a set of measure attributes and a set of values for a set of dimension attributes;
- inferring an initial hierarchic data structure based at least in part on count data associated with the received set of values for dimension attributes;
- distributing the received set of values for the set of measure attributes into a set of value-item lists associated with a portion of leaf nodes in the hierarchic data structure;
- in the hierarchic data structure recursively rearranging from bottom to top the set of value-item lists associated with the portion of leaf nodes based at least in part on compression performance stemming from the rearrangement of the set of value-item lists;
- reducing a number of features in the set of measure attributes, prior to the recursive rearrangement of the set of value-item lists;
- and
- promoting a plurality of value-item elements from the rearranged lists into a tree structure to generate a parsimonious representation of the inferred hierarchic data structure.
A computer-implemented system that facilitates generation of a parsimonious multi-resolution representation of value-item lists, comprising:
- one or more processors;
- a computer-implemented component that is executed by at least one of the processors and that recursively infers a hierarchic data structure based at least in part on a set of target variables and a set of conditioning variables;
- and
- a computer-implemented analysis component that is executed by at least one of the processors and that:
- prior to conducting a pairing of a set of value-item lists, performs a feature reduction for the set of target variables;
- at a step in a recursion, pairs the set of value-item lists associated with the received target variables;
- and
- at the step in the recursion, promotes individual elements from the paired lists into a set of lists at a next level up in a tree structure to generate a parsimonious representation of the inferred hierarchic data structure.
A computer-readable storage medium storing instructions that direct a processor to perform actions for generating a parsimonious multi-resolution representation of value-item lists, the actions comprising:
- receiving a set of measure attributes;
- receiving a set of dimension attributes;
- inferring a hierarchic data structure based at least in part on the received set of measure attributes and dimension attributes;
- distributing the received set of values for the set of measure attributes into a value-item list associated with a portion of leaf nodes in the hierarchic data structure;
- recursively rearranging from bottom to top, in the hierarchic data structure, the set of value-item lists that populate a set of nodes based at least in part on compression performance stemming from the rearrangement of the one or more lists, wherein recursively rearranging the set of value-item lists includes pairing lists based at least in part on a stochastic greedy matching;
- and
- promoting a plurality of value-item elements from the rearranged lists into a tree structure to generate a parsimonious representation of the inferred hierarchic data structure.
Dependencies are inferred from the claim text.