PARSIMONIOUS MULTI-RESOLUTION VALUE-ITEM LISTS

• US 20090259679A1
• Filed: 04/14/2008
• Published: 10/15/2009
• Est. Priority Date: 04/14/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Memisevic, Roland Franz, Thiesson, Bo
• Granted Patent: US 8,015,129 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/904 Browsing; Visualisation therefor for navigating the web G06F16/954; browsing optimisation for the web G06F16/957

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.

Claims

1. 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 value-item list 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 that populate a set of nodes based at least in part on compression performance stemming from the rearrangement of the one or more 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.

2. The method of claim 1, recursively rearranging the set of value-item lists further comprising utilizing a first similarity criterion, and promoting a plurality of value-item elements from the rearranged lists is performed using a second disparate criterion.

3. The method of claim 2, the first and second criteria are inferred based on historic data on previously employed criteria.

4. The method of claim 1, recursively rearranging the set of value-item lists includes pairing lists based at least in part on a greedy matching.

5. The method of claim 1, recursively rearranging the set of value-item lists includes pairing lists based at least in part on a stochastic greedy matching.

6. The method of claim 1, promoting a plurality of value-item elements from the rearranged set of value-item lists into a tree structure comprising evaluating a level of significance for a promotion hypothesis.

7. The method of claim 6, the level of significance is adjusted in Bonferroni-style, wherein the level of significance α

obeys

$\mathrm{\alpha <br><br>}<br><br>\left(D\right)=1-{0.95}^{2^{\frac{1}{\left(D-1\right)}}},$

with D a depth in the inferred hierarchical data structure.

8. The method of claim 1, further comprising trading off semantic similarity with respect to nearness when rearranging the set of value-item lists.

9. The method of claim 8, wherein the semantic similarity criterion includes at least one of a Euclidean distance or a cosine similarity metric.

10. The method of claim 1, further comprising rejecting a trading off of semantic similarity and pairing a set of value-item lists through an optimal method.

11. The method of claim 1, further comprising performing a feature reduction for a set of measure attributes prior to conducting a pairing of a set of lists.

12. The method of claim 11, wherein the feature reduction is a Poisson decomposition.

13. The method of claim 8, further comprising performing a nearness test that constrains the pairing of a set of value-item lists to a set of lists that descend from a same predecessor at a specific depth in a tree structure.

14. The method of claim 8, further comprising performing a nearness test of a set of value-item lists with respect to centers of values for conditioning variables.

15. A computer-implemented system that facilitates generation of a parsimonious multi-resolution representation of a value-item lists, comprising:

a computer-implemented component that recursively infers a hierarchic data structure based at least in part on a set of target variables and a set of conditioning variables;

a computer implemented analysis component that at a step in a recursion pairs a set of value-item lists associated with the received target variables; and

a computer implemented analysis component that at a step in a 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.

16. The computer-implemented system of claim 15, wherein the computer implemented analysis component performs a feature reduction for a set of measure attributes prior to conducting a pairing of a set of lists, the feature reduction comprises a Poisson decomposition

17. The computer-implemented system of claim 15, wherein the computer-implemented analysis component includes a computer-implemented greedy clustering engine.

18. The computer-implemented system of claim 15, wherein the analysis component promotes the paired lists into a tree structure based at least in part on a level of significance of a promotion hypothesis.

19. The computer-implemented system of claim 18, the level of significance α

of a promotion hypothesis obeys

$\mathrm{\alpha <br><br>}<br><br>\left(D\right)=1-{0.95}^{2^{\frac{1}{\left(D-1\right)}}},$

wherein D is a depth in the inferred hierarchical data structure.

20. A computer-implemented apparatus comprising:

computer-implemented means for receiving a set of measure attributes;

computer-implemented means for receiving a set of dimension attributes;

computer-implemented means for inferring a hierarchic data structure based at least in part on the received set of measure attributes and dimension attributes;

computer-implemented means for 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;

computer-implemented means for 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; and

computer-implemented means for 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.