String Mining
In vielen Anwendungen (z.B. in Computational Biology) möchte man in Daten interessante String- oder Sequence-Pattern finden. Anwendungsgebiete sind unter anderem das Finden von discriminative Features for Sequence Classification or Segmentation, das Entdecken neuer Binding Motifs of Transcription Factors oder Probe Design. Wir schlagen einen neuen algorithmischen Framework vor, der in Datenbanken häufigkeitsbezogene Data Mining Anfragen auf Strings in optimaler Zeit auflöst, dass heißt linear in der Ein- und Ausgabe. Der zusätzliche Speicher ist linear in der Größe der Eingabe. Unser Framework kann dazu benutzt werden verschiedene Arten von Strings, wie frequent Strings, emerging Strings und Strings, die andere statistische Test bestehen (z.B. ein Chi-Quadrat-Test), zu minen. Im Gegensatz zu den präsentierten Ergebnissen für Strings, sind keine optimalen Algorithmen für andere Pattern-Domänen (wie zum Beispiel Itemsets) bekannt. Für unseren Ansatz verwenden wir einige neuere Ergebnisse über Indexstrukturen für Strings, darunter Suffix-Arrays, lcp-Arrays und neue Preprocessing Schemes für Range Minimum Queries. Im Vergleich zu dynamischen Datenstrukturen wie Bäumen ist der Vorteil von Array-basierten Datenstrukturen ein gutes lokales Verhalten und die Erweiterbarkeit auf den Sekundärspeicher. Unseren Algorithmus haben wir auf Real-Daten aus der Computational Biology getestet und gezeigt, dass der Ansatz in der Praxis gut funktioniert.
Publikationen
Fischer, J, Heun, V, and Kramer, S
(2005).
Fast Frequent String Mining Using Suffix Arrays
In: ICDM '05: Proceedings of the Fifth IEEE International Conference on Data Mining, pp. 609-612, Washington, DC, USA, IEEE Computer Society Press.
Fischer, J, Heun, V, and Kramer, S
(2006).
Optimal String Mining Under Frequency Constraints
In: Proc. of the 10th European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD 2006), pp. 139-150.
Software
Das C++ source package wurde von Johannes Fischer online gestellt. Bitte zitieren Sie [FHK06], wenn Sie die Software in einer Publikation verwenden.
Computergrafik und Animation (Vorlesung/Übung)
