Optimizing hypergraph transversal computation with an anti-monotone constraint

ABSTRACT

Finding hypergraph transversals is a major algorithmic issue having many relationships with the data mining area. By defining a new Galois connection, we show how it is possible to use data mining results on pattern condensed representations and the levelwise framework to improve the hypergraph transversals computation. We present a new algorithm MTMINER and experiments showing its efficiency.

REFERENCES

• 1: C. Berge. Hypergraphs. North Holland, Amsterdam, 1989.
• 2: E. Boros, K. Elbassioni, V. Gurvich, and L. Khachiyan. An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals. In 11th Annual European Symposium on Algorithms, LNCS 2832, pages 556--567, 2003.
• 3: Jean-François Boulicaut , Artur Bykowski , Christophe Rigotti, Free-Sets: A Condensed Representation of Boolean Data for the Approximation of Frequency Queries, Data Mining and Knowledge Discovery, v.7 n.1, p.5-22, January 2003 [doi>10.1023/A:1021571501451]
• 4: Klaus Denecke , Shelly L. Wismath, Universal Algebra and Applications in Theoretical Computer Science, CRC/C&H, 2002
• 5: Michael L. Fredman , Leonid Khachiyan, On the complexity of dualization of monotone disjunctive normal forms, Journal of Algorithms, v.21 n.3, p.618-628, Nov. 1996 [doi>10.1006/jagm.1996.0062]
• 6: Dimitrios Gunopulos , Roni Khardon , Heikki Mannila , Sanjeev Saluja , Hannu Toivonen , Ram Sewak Sharma, Discovering all most specific sentences, ACM Transactions on Database Systems (TODS), v.28 n.2, p.140-174, June 2003 [doi>10.1145/777943.777945]
• 7: D. J. Kavvadias and E. C. Stavropoulos. An efficient algorithm for the transversal hypergraph generation. J. Graph Algorithms Appl., 9(2):239--264, 2005.
• 8: Francois Rioult , Arnaud Soulet, Average Number of Frequent (Closed) Patterns in Bernouilli and Markovian Databases, Proceedings of the Fifth IEEE International Conference on Data Mining, p.713-716, November 27-30, 2005 [doi>10.1109/ICDM.2005.31]
• 9: K. Satoh and T. Uno. Enumerating maximal frequent sets using irredundant dualization. In G. Grieser, Y. Tanaka, and A. Yamamoto, editors, Discovery Science, volume 2843 of Lecture Notes in Computer Science, pages 256--268. Springer, 2003.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

General Terms:
Algorithms, Theory