Sofian Maabout: Computation of Borders and Applications

14.00, Room 445 at PCRI

Abstract
Given a set of objects O and a boolean interest function q:2^O-> {true, false}, the border of 2^O is the set of extremal (minimal or maximal) subsets o of O s.t. q(o)=true. This concept is present in many contexts, e.g., maximal frequent
itemsets, functional dependencies and partial matrialization of data cubes. We present a parallel algorithm for computing borders when q is anti-monotonic and show its performance from theoretical and experimental point of views. Some extensions will be discussed s.t. distributed data and map reduce.

Resumé
Etant donnés un ensemble d’objets O et une fonction booléenne d’intérêt q: 2^O-> {vrai, faux}, la bordure de 2^O est l’ensemble des éléments o de 2^O extrémaux (minimaux ou maximaux) tels que q(o)=vrai. On retrouve le concept de bordures dans plusieurs applications, ex: les itemsets fréquents maximaux, les dépendances fonctionnelles approximatives et le stockage
partiel des cubes de données. Nous présentons un algorithme parallèle pour le calcul des bordures lorsque q est anti-monotone, en discutons ses performances théoriques et expérimentales. Quelques extensions seront abordées comme le cas des données distribuées et son utilisation sous le paradigme map reduce.

Permanent link to this article: https://team.inria.fr/oak/2012/02/10/sofian-maabout-computation-of-borders-and-applications/