Research Groups

Research projects are grouped together to form research areas. Thus the reader can get a clearer view of the research work. Some research groups act as special interest groups (SIG) for the topic. Thus, although the projects involved are independent of each other, members of the whole group have common activities like giving talks and seminars to the group.

Most of the major research project are listed in the separate projects page. More detailed list of all projects within a group can be located in the home page of each group.

Database research

Researchers: Eljas Soisalon-Soininen, Ibrahim Jaluta, Kenneth Oksanen, Riku Saikkonen, Panu Silvasti, Timo Lilja, Seppo Sippu (University of Helsinki), Tatu Ylönen (SSH)

The focus of this research area is in developing algorithms for different topic of database management. One such topic is concurrency control and recovery of database transactions. This is a traditional area of research, but there are still many interesting problems to be solved. This is especially the case when the necessary search structure operations are included in the transaction model. The classical theory of concurrency control and recovery defines transactions as strings of abstract read and write operations. In our new model, the logical database is assumed to consist of records with unique keys taken from a totally ordered domain. The database operations include operations of the forms "fetch the first or next matching record", "insert a record", or "delete a record". Recently, we (I.Jaluta, S.Sippu, E.Soisalon-Soininen) have shown in a paper published in The VLDB Journal how to implement efficient concurrency control and recovery within this model, when the underlying index structure is a B-link tree. We present a new technique to implement a small structure modification, such as a page spit or a page merge as an atomic action, so that interrupted structure modifications are never rolled back (undone). This is in contrast to the previous algorithms, in which an interrupted tree-structure modification always has to be rolled back during restart recovery. Our transaction model has been extended to page-server database systems in an article published in the ACM Transactions on Database Systems. Future research includes further development of the theory, performance studies of the already proposed methods, implementation of the model in the case of multidimensional search structures such as R-trees, as well as introducing bulk updates as new basic operations applied to the index structure. Preliminary results about bulk operations (large amounts of search, insert, or delete operations performed at the same time) will be presented in 2007 at the ICDE (International Conference on Data Engineering) conference, which is a practically oriented top-level conference for database research.

As a new research topic, algorithmic problems related to data stream management will be considered. The focus is especially on problems that are relevant to document filtering and content-based routing. The idea in filtering is that the user defines her interests or profile, and the data producers transmit to the user those documents that match the user's profile. Especially filters defined by regular expressions will be considered. Then the problem is to find for a given document or string x those regular expressions in the filter that match x, i.e. those expressions whose language contains x. A preliminary article in this area has been published by Eljas Soisalon Soininen and Tatu Ylönen, but it seems that results obtained thus far can be considerably improved.

Searching for optimal algorithms

Researchers: Kenneth Oksanen, Eljas Soisalon-Soininen

In some areas of algorithms research the algorithm designer's work can be successfully mechanized by modeling it as a two player game: the algorithm designer (or "oracle") makes a "move" - the choice of the next computational step - with the intent to find the result as efficiently as possible, and the imaginary input-player (or "adversary") counters with another "move" - the result of that computational step - attempting to postpone the solution as late possible. Suitable areas for such mechanized treatment are, for example, the selection problem (finding the i'th largest of n input values) and its many variations, and in finding distributed concurrency control algorithms for given legal schedules. So far we have found improvements to previously known upper or lower bounds for sixteen different selection problem instances, a counter-example to a previously published hypothesis of the exact complexity of selection, and confirmation to a theoretical hypothesis (Yao's hypothesis) up to a certain limit. In addition to results in the problem domain this work has lead us to find several interesting optimizations that speed up the search process and prune irrelevant or isomorphic parts of the search space.

Research on string algorithms

Researchers: Jorma Tarhio, Leena Salmela, Petri Kalsi, Hannu Peltola, Kerttu Pollari-Malmi

We have developed efficient algorithms for information retrieval. We have considered both exact and approximate string searching as well as indexing methods. Our best achievement is a new family of q-gram algorithms for searching multiple patterns where the number of patterns can be up to 500,000. There are well-known algorithms for this problem, but they do not scale very well up to such huge pattern sets. Our algorithms are up to 10 times faster than the traditional solutions. The new algorithms can be applied to scanning of computer viruses or searching of genomic patterns. In addition we have developed new algorithms for compressed matching, parameterized matching, transposition invariant music retrieval, and bit-parallel searching.

Software-technology-based evaluation of energy-aware designs

Researcher: Vesa Hirvisalo

The objective of the research is to understand the implications of modern software technology on the design of energy-aware mobile devices. Such devices operate on battery, solar cells, or other limited source of energy. Typical examples are mobile phones, wrist watches, wrist computers, personal digital assistants, hand-held games, and telemetry systems. In general, low-energy consumption concerns a wide range of measurement, control, signal processing, and telecommunication systems. Traditionally, the design of such systems has been based on simple conservative architectures. However, satisfying future requirements for low-energy consumption and high computation power is impossible with contemporary design and implementation technologies. Because of the novel market demands, the hardware and software in such systems are evolving and becoming increasingly complex. In the near future, there seems to be competing approaches to overcome the demand for high-performance energy-aware systems.

Methods and tools for collaborative cognitive tasks

Researchers: Esko Nuutila, Seppo Törmä, Markku Syrjänen

The goal of this research is to develop conversational methods and tools that support the cognitive processes of groups of people working on collaborative tasks. Typically, such tasks include brainstorming, problem solving, information seeking, collaborative planning, writing and other document production, analysing requirements, and designing information systems. In spite of the advances in information technology, the methods and tools applied in these tasks are weak. For instance, spreadsheet and presentation programs are used for requirement analysis, strategic planning, and process specification. In many tasks, no systematic methods and applicable tools are used. The formalisms we are studying include dialogue maps, concept maps, and mind maps. We have developed an advanced concept mapping formalism called text graphs and a tool for editing them. We are studying how these formalisms can be applied in face-to-face meetings using video projectors, in distributed meetings, and for asynchronous collaboration. Different formalisms lead to different type of cognitive processing. However, the diagrams produced with different formalisms may partly overlap. Thus, we are developing tools that integrate these formalisms using interactive distributed web application technologies (e.g., Ajax, Comet, and other Web2.0 technologies). We are going to carry out empirical studies of the effects of using these formalisms and tools especially in meeting room technology, in information seeking and knowledge building, and in teaching and learning software systems. This research is based on previous research on formal knowledge representation in our laboratory.

Software visualization and computer science education research

Researchers: Lauri Malmi, Ari Korhonen, Petri Ihantola, Ville Karavirta, Päivi Kinnunen, Mikko-Jussi Laakso, Jan Lönnberg, Jussi Nikander, Otto Seppälä, Juha Sorva and Mu Zhou

The research work carried out in Computer Science Education Research group (COMPSER, directed by prof. Lauri Malmi) and Software Visualization Group (SVG, directed by Dr. Ari Korhonen) originates from the very high teaching load that Unit has as it gives programming education to all degree programmes at TKK. There are several 150-750 students on each course yearly. It has been necessary to design and implement novel tools for automatic assessment of student submissions to enable giving adequate feedback for them. Moreover, we have developed various visualization methods and tools to support learning programming, especially data structures and algorithms on a conceptual level.

The two research groups overlap heavily, but they provide two different perspectives on this topic. The SVG group concentrates on technical research, i.e., developing technical solutions, methods and software tools that can be applied in computer science education, but also in other contexts, like professional software development. The COMPSER group, on the other hand, focuses on evaluating the impact of such tools on learning. Moreover, an important research topic is gathering understanding on how students use the tools and what factors are relevant for future development of educational software and instructional methods in computer science context.

The technical research has the following key areas:

1. We develop tools for visualization of data structures, algorithms, programs and their execution. The most important concept developed here is visual algorithm simulation. In this activity, the user is able to build and modify real data structures through GUI operations. He can simulate the changes that a real algorithm would do by using context sensitive drag & drop operations on the screen. The system maintains the actual underlying data structures as well as their visual representations, and interprets the meaning of the operations between these two layers. The method thus allows interaction on a conceptual level with the topic at hand, instead of working only on implementation (code) level. This is an important contribution in algorithm animation research, as it supports novel interaction methods during the animation and giving feedback on conceptual level for the user. The Matrix framework developed in this research provides algorithm animation and simulation facilities for a wide set of ready-made data structures and algorithms.
2. We develop techniques for automatic evaluation, assessment and feedback of student submissions on algorithmic and programming exercises. The most important application is the TRAKLA2 learning environment of data structures and algorithms, which provides a large set of automatically assessed exercises covering basic data structures, sorting algorithms, dictionaries, graph algorithms and spatial data structures and algorithms. The tool has been in production use since 2003 and it is currently used in seven higher education institutes with over 1000 enrolled students yearly. The current foci of research are on automatic recognition of students' misconceptions, on recovery from erroneous states of data structures, and on giving dedicated visual and verbal feedback on the submissions (AAFAS project, funded by Academy of Finland).
3. We develop automatic analysis methods to enable giving feedback on program code and related documents, such as program comments, documents and specifications (TAPAS project, funded by Academy of Finland).
4. We develop methods for automatic generation of test data out of student programs, in terms of model checking, and for giving visual feedback on the test cases. Another branch of this research concentrates on developing visualization methods to support identifying and correcting errors in concurrent programs.
5. We develop visualization methods for terrain analysis algorithms in collaboration with Institute of Cartography and Geoinformatics, and visualization of traffic simulation data in collaboration with Laboratory of Transportation Engineering.

The evaluation research has been carried out in collaboration with University of Helsinki, Faculty of Education. Here we have carried out experiments with randomized student groups on what is the impact of TRAKLA2 exercises to student learning. The main result here has shown that we get the same learning results when students use TRAKLA2 assignments in the web on their own and when they solve similar exercises on paper in closed labs with tutoring assistants. This gives us a solid basis for developing web-based exercises further, and for concentrating the human resources to more advanced guidance and assessment, such that we cannot automate. Another line of our research concentrates on identifying patterns how students actually use the tool, by analyzing the extensive logging data we get from the tool. A third line of research works on qualitative analysis of how students understand programming work and program execution as well as what factors affect student drop out in introductory programming courses. All these lines of research apply methods and theories from Educational and Social Sciences.

COMPSER and SVG groups together currently include two senior researchers (Malmi, Korhonen), 9 doctoral students and 3 MSc students. Since the beginning, in 2000 the groups have published (including accepted papers) over 20 international journal papers, and over 40 international conference papers, and many research papers in Finnish journals and conferences. Most publication forums have been in the fields of computing education, computing education research and educational technology. Most of the research in COMPSER/SVG groups can be characterized as applied research, and the results have been extensively applied to improving programming education at TKK. However, there are basic research problems, as well, such as developing novel algorithms for identifying different forms of student's misconceptions from their submissions.

PM&RG

PM&RG research group develops a methodology for designing mobile and ubiquitous services. Methodology comprises experimentation, balanced brokering, and design data modeling. PM&RG WWW pages contain more information on research, education, seminars and events, and other activities of the group. Please, do not hesitate to contact .

• Planning Systems Group