Dr. Johannes Fischer

Dr. Johannes Fischer

	Position	PostDoc
	Office	C324b
	Address	Universität Tübingen Algorithms in Bioinformatics Sand 14 72076 Tübingen
	Phone	+49-7071-29-70454
	Fax	+49-89-2180-99-4063
	E-Mail
	Office hours	by appointment via e-mail

Publications

unpublished	Simon Gog, Johannes Fischer:
	Advantages of Shared Data Structures for Sequences of Balanced Parentheses.
	Johannes Fischer:
	Wee LCP.
	Johannes Fischer:
	Optimal Succinctness for Range Minimum Queries.
	Get the presentation. Software can be found at the bottom of this page.
	Johannes Fischer, Daniel Huson:
	New Common Ancestor Problems in Trees and Directed Acyclic Graphs.
2009	Johannes Fischer, Veli Mäkinen, Gonzalo Navarro:
	Faster Entropy-Bounded Compressed Suffix Trees.
	Theoretical Computer Science 410 (51), 5354-5364, 2009.
	Johannes Fischer:
	Short Labels for Lowest Common Ancestors in Trees.
	Proceedings of the 17th Annual European Symposium on Algorithms
	(ESA'09), Lecture Notes in Computer Science 5757, 752-763, Springer-Verlag, 2009.
	Johannes Fischer, Volker Heun:
	Finding Range Minima in the Middle: Approximations and Applications.
	Accepted for publication in Mathematics in Computer Science: Special Issue on Combinatorial Algorithms
2008	Johannes Fischer, Veli Mäkinen, Niko Välimäki:
	Space Efficient String Mining under Frequency Constraints.
	Proceedings of the 8th IEEE International Conference on Data Mining
	(ICDM'08), 193-202, IEEE Computer Society, 2008.
	Get the C++ source package (maintained by the SUDS-group in Helsinki)
	Johannes Fischer, Volker Heun:
	Range Median of Minima Queries, Super-Cartesian Trees, and Text Indexing.
	Proceedings of the 19th International Workshop on Combinatorial Algorithms
	(IWOCA'08), 239-252, College Publications, 2008.
	Johannes Fischer, Veli Mäkinen, Gonzalo Navarro:
	An(other) Entropy Bounded Compressed Suffix Tree.
	Proceedings of the 19th Annual Symposium on Combinatorial Pattern Matching
	(CPM'08), 152-165, Lecture Notes in Computer Science 5029, Springer-Verlag, 2008.
	Johannes Fischer, Volker Heun, Horst Martin Stühler:
	Practical Entropy-Bounded Schemes for O(1)-Range Minimum Queries.
	Proceedings of the 2008 Data Compression Conference
	(DCC'08), 272-281, IEEE Press, 2008.
2007	Johannes Fischer: Data Structures for Efficient String Algorithms. PhD-thesis.
	Hochschulschrift (Dissertation, LMU München), München 2007.
	Paolo Ferragina, Johannes Fischer:
	Suffix Arrays on Words.
	Proceedings of the 18th Annual Symposium on Combinatorial Pattern Matching
	(CPM'07), Lecture Notes in Computer Science 4580, 328-339, Springer-Verlag, 2007.
	The software can be found at the bottom of the page.
	Amihood Amir, Johannes Fischer, Moshe Lewenstein:
	2-Dimensional Range Minimum Queries.
	Proceedings of the 18th Annual Symposium on Combinatorial Pattern Matching
	(CPM'07), Lecture Notes in Computer Science 4580, 286-294, Springer-Verlag, 2007.
	Johannes Fischer, Volker Heun:
	A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array.
	Proceedings of the International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies
	(ESCAPE'07), Lecture Notes in Computer Science 4614, 459-470, Springer-Verlag, 2007.
	The software can be found at the bottom of the page.
2006	Johannes Fischer, Volker Heun, Stefan Kramer:
	Optimal String Mining under Frequency Constraints.
	Proceedings of the 10th European Conference on Principles and Practice of Knowledge Discovery in Databases
	(PKDD'06), Lecture Notes in Artificial Intelligence 4213, 139-150, Springer-Verlag, 2006.
	The software can be found at the bottom of the page.
	Johannes Fischer, Volker Heun:
	Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE.
	Proceedings of the 17th Annual Symposium on Combinatorial Pattern Matching
	(CPM'06), Lecture Notes in Computer Science 4009, 36-48, Springer-Verlag, 2006.
	The software is at the bottom of this page, but check also the more recent "Succinct RMQ"!
	Simon Ginzinger, Johannes Fischer:
	SimShift: Identifying Structural Similarities from NMR Chemical Shifts.
	Bioinformatics 22(4), 460-465, 2006.
	See this page for a new version of the software (maintained by Simon)!
2005	Johannes Fischer, Volker Heun, Stefan Kramer:
	Fast Frequent String Mining Using Suffix Arrays.
	Proceedings of the 5th IEEE International Conference on Data Mining
	(ICDM'05), 609-612, IEEE Computer Society, 2005.
	Appeared also as a Technical Report . Outdated! Use the "Frequent String Miner" from our PKDD'06-paper!
	Johannes Fischer, Simon Ginzinger:
	A 2-Approximation Algorithm for Sorting by Prefix Reversals.
	Proceedings of the 13th Annual European Symposium on Algorithms
	(ESA'05), Lecture Notes in Computer Science 3669, 415-425, Springer-Verlag, 2005.
2004	Johannes Fischer, Luc De Raedt:
	Towards Optimizing Conjunctive Inductive Queries.
	Proceedings of the Eighth Pacific-Asia Conference on Knowledge Discovery and Data Mining
	(PAKDD'04), Lecture Notes in Artificial Intelligence 3056, 625-637, Springer-Verlag, 2004.
2003	Johannes Fischer:
	Version Spaces in Constraint-Based Data Mining, Diploma Thesis, 2003.

Software

• Range Minimum Queries. We have recently shown that the replacement of one component leads to much better time and space for RMQ-schemes. Until now, this has only been done in one RMQ-scheme (integrated in sdsl, Simon Gog's succinct data structure library). If you need RMQs in your algorithms, I therefore strongly encourage you to use class range_minimum_support_succinct_sct from sdsl. If for some reasons you don't want that, you can still use the structure from the paper Optimal Succinctness for Range Minimum Queries: [C++ source package] (last update: 2009/10/29). For yet older implementations, please contact me by e-mail.
• Labeling Trees for LCAs. (ESA'09) (last update: 2009/04/09) [C++ source package]
• Suffix Arrays on Words. (CPM'07) (last update: 2007/03/30) [C++ source package]
• Linear Frequent String Miner and Emerging Substring Miner. (PKDD'06) (last update: 2007/01/04) [C++ source package]