CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Pairs covered by a sequence of sets

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers))
20th International Symposium on Fundamentals of Computation Theory FCT 2015, Lecture Notes in Computer Science (0302-9743). Vol. 9210 (2015), p. 214-226.
[Konferensbidrag, refereegranskat]

Enumerating minimal new combinations of elements in a sequence of sets is interesting, e.g., for novelty detection in a stream of texts. The sets are the bags of words occuring in the texts. We focus on new pairs of elements as they are abundant. By simple data structures we can enumerate them in quadratic time, in the size of the sets, but large intersections with earlier sets rule out all pairs therein in linear time. The challenge is to use this observation efficiently. We give a greedy heuristic based on the twin graph, a succinct description of the pairs covered by a set family, and on finding good candidate sets by random sampling. The heuristic is motivated and supported by several related complexity results: sample size estimates, hardness of maximal coverage of pairs, and approximation guarantees when a few sets cover almost all pairs.



Denna post skapades 2015-08-21. Senast ändrad 2016-06-03.
CPL Pubid: 220926

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)


Institutioner (Chalmers)

Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers)

Ämnesområden

Teoretisk datalogi

Chalmers infrastruktur