Publications

Refereed papers

1. Kimmo Fredriksson: From nondeterministic suffix automaton to lazy suffix tree. In Algorithms and Applications (Ukkonen Festschrift 2010), Lecture Notes in Computer Science 6060, pages 114-129, Springer, 2010.

   To Appear.

---

2. Kimmo Fredriksson and Szymon Grabowski: Fast convolutions and their applications in approximate string matching. In Proceedings of IWOCA'09, Lecture Notes in Computer Science 5874, pages 254-265, Springer, 2009.

   [BibTeX] [Abstract] [PDF] [Publishers site]

3. Kimmo Fredriksson and Szymon Grabowski: Average-Optimal String Matching. In Journal of Discrete Algorithms (JDA), 7(4):579-594, 2009.

   [BibTeX] [Abstract] [PDF] [Publishers site]

4. Karina Figueroa and Kimmo Fredriksson: Speeding up permutation based indexing with indexing. In Proceedings of SISAP'09, IEEE CS Press, pages 107-114, 2009.

   [BibTeX] [Abstract] [PDF] [Publishers site]

5. Kimmo Fredriksson and Fedor Nikitin: Simple Random Access Compression. In Fundamenta Informaticae (FI), 92(1-2):63-81, 2009.

   [BibTeX] [Abstract] [PDF] [Publishers site]

6. Kimmo Fredriksson and Szymon Grabowski: Nested counters in bit-parallel string matching. In Proceedings of LATA'09, Lecture Notes in Computer Science 5457, pages 338-349, Springer, 2009.

   [BibTeX] [Abstract] [PDF] [Publishers site]

7. Kimmo Fredriksson: Succinct Backward-DAWG-Matching. In ACM Journal of Experimental Algorithmics (JEA), 13(1.8):1-26, 2009.

   [BibTeX] [Abstract] [PDF] [Publishers site]

   ---

8. Kimmo Fredriksson and Szymon Grabowski: Efficient algorithms for pattern matching with general gaps, character classes and transposition invariance. In Information Retrieval, 11(4):335-357, 2008.

   [BibTeX] [Abstract] [PDF]

9. Kimmo Fredriksson and Szymon Grabowski: Efficient Algorithms for (δ, γ, α) and (δ, k_Δ, α)-matching. In International Journal of Foundations of Computer Science (IJFCS), 19(1):163-183, 2008.

   [BibTeX] [Abstract] [PDF]

10. Szymon Grabowski and Kimmo Fredriksson: Bit-parallel string matching under Hamming distance in O(n⌈m/w⌉) worst case time. In Information Processing Letters (IPL), 105(5):182-187, 2008.

    [BibTeX] [Abstract] [PDF]

    ---

11. Karina Figueroa and Kimmo Fredriksson: Simple space-time trade-offs for AESA. In Proceedings of WEA'07, Lecture Notes in Computer Science 4525, pages 229-241, Springer, 2007.

    [BibTeX] [Abstract] [PDF]

12. Kimmo Fredriksson and Fedor Nikitin: Simple compression code supporting random access and fast string matching. In Proceedings of WEA'07, Lecture Notes in Computer Science 4525, pages 203-216, Springer, 2007.

    [BibTeX] [Abstract] [PDF]

13. Kimmo Fredriksson, Veli Mäkinen, and Gonzalo Navarro: Rotation and Lighting Invariant Template Matching. In Information and Computation 205(7):1096-1113, 2007.

    [BibTeX] [Abstract] [PDF]

14. Kimmo Fredriksson: Engineering Efficient Metric Indexes. Pattern Recognition Letters (PRL), 28(1):75-84, 2007.

    [BibTeX] [Abstract] [PDF]

    ---

15. Kimmo Fredriksson, Veli Mäkinen, and Gonzalo Navarro: Flexible Music Retrieval in Sublinear Time. In International Journal of Foundations of Computer Science (IJFCS) 17(6):1345-1364, 2006.

    [BibTeX] [Abstract] [PDF]

16. Kimmo Fredriksson and Szymon Grabowski: A general compression algorithm that supports fast searching. In Information Processing Letters (IPL), 100(6):226-232, 2006.

    [BibTeX] [Abstract] [PDF]

17. Kimmo Fredriksson and Szymon Grabowski: Efficient algorithms for pattern matching with general gaps and character classes. In Proceedings of SPIRE'06, Lecture Notes in Computer Science 4209, pages 267-278, Springer, 2006.

    [BibTeX] [Abstract] [PDF] [Award]

18. Kimmo Fredriksson and Szymon Grabowski: Efficient algorithms for (δ, γ, α)-matching. In Proceedings of PSC'06, pages 29-40, Czech Technical University, Prague, 2006.

    [BibTeX] [Abstract] [PDF]

19. Kimmo Fredriksson and Maxim Mozgovoy: Efficient parameterized string matching. In Information Processing Letters (IPL), 100(3):91-96, 2006.

    [BibTeX] [Abstract] [PDF]

20. Kimmo Fredriksson: On-line Approximate String Matching in Natural Language. In Fundamenta Informaticae 72(4):453-466, 2006.

    [BibTeX] [Abstract] [PDF]

21. Kimmo Fredriksson and Szymon Grabowski: Efficient Bit-parallel Algorithms for (δ, α)-matching. In Proceedings of WEA'06, Lecture Notes in Computer Science 4007, pages 170-181, Springer, 2006.

    [BibTeX] [Abstract] [PDF]

    ---

22. Heikki Hyyrö, Kimmo Fredriksson and Gonzalo Navarro: Increased Bit-Parallelism for Approximate and Multiple String Matching. In ACM Journal of Experimental Algorithmics (JEA) 10(2.6):1-27, 2005.

    [BibTeX] [Abstract] [PDF]

23. Kimmo Fredriksson, Gonzalo Navarro and Esko Ukkonen: Sequential and Indexed Two-Dimensional Combinatorial Template Matching Allowing Rotations. In Theoretical Computer Science A (TCS), 347(1-2):239-275, 2005.

    [BibTeX] [Abstract] [PDF]

24. Kimmo Fredriksson and Szymon Grabowski: Practical and Optimal String Matching. In Proceedings of SPIRE'05, Lecture Notes in Computer Science 3772, pages 374-385, Springer, 2005.

    [BibTeX] [Abstract] [PDF]

25. Maxim Mozgovoy, Kimmo Fredriksson, Daniel White, Mike Joy and Erkki Sutinen: Fast Plagiarism Detection System. In Proceedings of SPIRE'05, Lecture Notes in Computer Science 3772, pages 268-271, Springer, 2005.

    [BibTeX] [PDF]

26. Kimmo Fredriksson, Veli Mäkinen and Gonzalo Navarro: Flexible Music Retrieval in Sublinear Time. In Proceedings of PSC'05, pages 174--188, Czech Technical University, Prague, 2005.

    [BibTeX] [Abstract] [PDF]

27. Kimmo Fredriksson: Exploiting distance coherence to speed up range queries in metric indexes. In Information Processing Letters (IPL), 95(1):287-292, 2005.

    [BibTeX] [Abstract] [PDF]

    ---

28. Kimmo Fredriksson and Gonzalo Navarro: Average-Optimal Single and Multiple Approximate String Matching. In ACM Journal of Experimental Algorithmics (JEA) 9(1.4):1-47, 2004.

    [BibTeX] [Abstract] [PDF]

29. Kimmo Fredriksson and Jorma Tarhio: Efficient String Matching in Huffman Compressed Texts. In Fundamenta Informaticae 63(1):1-16, 2004.

    [BibTeX] [Abstract] [PDF]

30. Kimmo Fredriksson: Metric Indexes for Approximate String Matching in a Dictionary. In Proceedings of SPIRE'04, Lecture Notes in Computer Science 3246, pages 212-213, Springer, 2004.

    [BibTeX] [PDF]

31. Stefan Burkhardt, Kimmo Fredriksson, Tuomas Ojamies, Janne Ravantti and Esko Ukkonen: Local approximate 3D matching of proteins in viral cryo-EM density maps. In Proceedings of 2nd International Symposium on 3D Data Processing, Visualization & Transmission (3DPVT'04), pages 979-986, IEEE CS Press, 2004.

    [BibTeX] [Abstract] [PDF]

32. Gonzalo Navarro and Kimmo Fredriksson: Average Complexity of Exact and Approximate Multiple String Matching. In Theoretical Computer Science A (TCS) 321(2-3):283-290, 2004.

    [BibTeX] [Abstract] [PDF]

33. Kimmo Fredriksson and Gonzalo Navarro: Improved Single and Multiple Approximate String Matching. In Proceedings of CPM'04, Lecture Notes in Computer Science 3109, pages 457-471, Springer, 2004.

    [BibTeX] [Abstract] [PDF]

34. Heikki Hyyrö, Kimmo Fredriksson and Gonzalo Navarro: Increased Bit-Parallelism for Approximate String Matching. In Proceedings of WEA'04, Lecture Notes in Computer Science 3059, pages 285-298, Springer, 2004.

    [BibTeX] [Abstract] [PDF]

35. Kimmo Fredriksson, Veli Mäkinen and Gonzalo Navarro: Rotation and Lighting Invariant Template Matching. In Proceedings of LATIN'04, Lecture Notes in Computer Science 2976, pages 39-48, Springer, 2004.

    [BibTeX] [Abstract] [PDF]

    ---

36. Kimmo Fredriksson: Row-wise tiling for the Myers' bit-parallel approximate string matching algorithm. In Proceedings of SPIRE'03, Lecture Notes in Computer Science 2857, pages 66-79, Springer, 2003.

    [BibTeX] [Abstract] [PDF]

37. Kimmo Fredriksson and Jorma Tarhio: Processing of Huffman Compressed Texts with a Super-Alphabet. In Proceedings of SPIRE'03, Lecture Notes in Computer Science 2857, pages 108-121. Springer, 2003.

    [BibTeX] [Abstract] [PDF]

38. Kimmo Fredriksson: Shift-or string matching with super-alphabets. In Information Processing Letters (IPL), 87(4):201-204, 2003.

    [BibTeX] [Abstract] [PDF]

39. Kimmo Fredriksson and Gonzalo Navarro: Average-Optimal Multiple Approximate String Matching. In Proceedings of CPM'03, Lecture Notes in Computer Science 2676, pages 109-128, Springer, 2003.

    [BibTeX] [Abstract] [PDF]

    ---

40. Kimmo Fredriksson: Faster string matching with super--alphabets. In Proceedings of SPIRE'02, Lecture Notes in Computer Science 2476, pages 44-57, Springer, 2002.

    [BibTeX] [Abstract] [PDF]

41. Kimmo Fredriksson, Gonzalo Navarro and Esko Ukkonen: Optimal Exact and Fast Approximate Two Dimensional Pattern Matching Allowing Rotations. In Proceedings of CPM'02, Lecture Notes in Computer Science 2373, pages 235-248, Springer, 2002.

    [BibTeX] [Abstract] [PDF]

42. Kimmo Fredriksson, Gonzalo Navarro and Esko Ukkonen: Faster than FFT: rotation invariant combinatorial template matching. Recent Research Developments in Pattern Recognition 3, pages 75-112, ISBN 81-7895-050-2, 2002.

    [BibTeX] [Abstract]

    ---

43. Kimmo Fredriksson and Esko Ukkonen: Faster template matching without FFT. In Proceedings of ICIP'01, IEEE CS Press, pages 678-681, 2001.

    [BibTeX] [Abstract] [PDF]

    ---

44. Kimmo Fredriksson and Esko Ukkonen: Combinatorial methods for approximate pattern matching under rotations and translations in 3D arrays. In Proceedings of SPIRE'00, pages 96-104, IEEE CS Press, 2000.

    [BibTeX] [Abstract] [PDF]

45. Kimmo Fredriksson: Rotation invariant histogram filters for similarity and distance measures between digital images. In Proceedings of SPIRE'00, pages 105-115, IEEE CS Press, 2000.

    [BibTeX] [Abstract] [PDF]

46. Kimmo Fredriksson, Gonzalo Navarro and Esko Ukkonen: An index for two dimensional string matching allowing rotations. In Proceedings of IFIP TCS 2000, Lecture Notes in Computer Science 1872, pages 59-75, Springer, 2000.

    [BibTeX] [Abstract] [PDF]

    ---

47. Kimmo Fredriksson and Esko Ukkonen: Combinatorial Methods for Approximate Image Matching Under Translations and Rotations. Pattern Recognition Letters (PRL), 20:1249-1258, November 1999.

    [BibTeX] [Abstract] [PDF]

    ---

48. Kimmo Fredriksson and Esko Ukkonen: Rotation Invariant Filter for Two-dimensional String Matching. In Proceedings of CPM'98, Lecture Notes in Computer Science, pages 118-125, Springer, 1998.

    [BibTeX] [Abstract] [PDF]

    ---

49. Kimmo Fredriksson: Genetic algorithms and generative encoding of neural networks for some benchmark classification problems. In Proceedings of the Third Nordic Workshop on Genetic Algorithms and their Applications (3NWGA), Finnish Artificial Intelligence Society (FAIS), pages 123-134, Helsinki (Finland), 1997.

    [BibTeX] [Abstract] [PDF]

PhD thesis

• Rotation Invariant Template Matching.

  [BibTeX] [Abstract] [PDF]

Technical Reports

• Szymon Grabowski and Kimmo Fredriksson: Bit-parallel string matching under Hamming distance in O(n⌈m/w⌉) worst case time. Technical Report A-2007-2, Department of Computer Science and Statistics, University of Joensuu, May, 2007.
• Kimmo Fredriksson: Succinct pattern matching automata. Technical Report A-2007-1, Department of Computer Science and Statistics, University of Joensuu, May, 2007.
• Kimmo Fredriksson and Fedor Nikitin: Compressed representation of sequences with constant time random access. Technical Report A-2006-3, Department of Computer Science and Statistics, University of Joensuu, October, 2006.
• Kimmo Fredriksson and Maxim Mozgovoy: Sublinear parameterized single and multiple string matching. Technical Report A-2006-2, Department of Computer Science, University of Joensuu, March, 2006.
• Kimmo Fredriksson and Szymon Grabowski: Efficient Algorithms for (δ, α)-matching. Technical Report A-2005-2, Department of Computer Science, University of Joensuu, November, 2005.
• Kimmo Fredriksson, Veli Mäkinen and Gonzalo Navarro: Flexible music retrieval in sublinear time. Technical Report TR/DCC-2005-13, Department of Computer Science, University of Chile, October 2005.
• Kimmo Fredriksson, Veli Mäkinen and Gonzalo Navarro: Rotation and Lighting Invariant Template Matching. Technical Report TR/DCC-2003-3, Department of Computer Science, University of Chile, November 2003.
• Kimmo Fredriksson, Gonzalo Navarro and Esko Ukkonen: Sequential and Indexed Two-Dimensional Pattern Matching Allowing Rotations. Technical Report TR/DCC-2003-2, Department of Computer Science, University of Chile, November 2003.
• Kimmo Fredriksson, Gonzalo Navarro and Esko Ukkonen: Fast Filters for Two Dimensional String Matching Allowing Rotations. Technical Report TR/DCC-99-9, Department of Computer Science, University of Chile, November 1999.
• Kimmo Fredriksson, Gonzalo Navarro and Esko Ukkonen: An Index for Two Dimensional String Matching Allowing Rotations. Technical Report TR/DCC-99-8, Department of Computer Science, University of Chile, November 1999.
• Kimmo Fredriksson: Learning the Structure of Neural Networks with Genetic Algorithms (Master's Thesis, in Finnish). Technical Report C-1997-34, University of Helsinki, Department of Computer Science, 1997.

Some unpublished manuscripts

• Kimmo Fredriksson: Fast algorithms for string matching with and without swaps, 2000. [PDF]
• Kimmo Fredriksson and Esko Ukkonen: Algorithms for 2-D Hamming distance under rotations, 1999. [PDF]

See also...

• (Partial) list of my publications and coauthors in DBLP.