SOFSEM - Day 4

Now we have snow....finally :) ...even a lot of it. It was snowing all day long, roads in Czech Republic and also in southern Germany were closed. Also Prague Airport was closed until the afternoon. But, I guess as far as I remember that are the more typical weather conditions for SOFSEM.
Anyway, the day started with a keynote of Tom Henziger about 'Games, Time, and Probability: Graph Models for System Design and Analysis'. He addressed three major sources of system complexity: concurrency, real time, and uncertainty. Concurrency can be modelled as a multi-player game representing a reactive system with potential collaborators and adversaries. Real time requires the system to combine discrete state changes as well as continous state evolution, while state changes - for uncertainty - also have to be modelled in a probabilistic way.
Unfortunately some of the presenters of the following contributed papers did not show up. Thus, the conference program was subject to several changes. In the afternoon the posters of the student research forum each had a short 5 minute presentation, followed by a poster exhibition and a lot of discussions. In the end, the participants should give a vote for the best poster presentation. My choice - which of course is completely subjective - was the poster of of Henning Fernau and Daniel Raible on 'Alliances in Graphs: a Complexity-Theoretic Study'.
In the late evening I was trying to look for my car, which was buried under the snow at the parking lot. Due to the wind the snow around the parking lot (and my car) was piled up almost half a meter...which made me think about the road conditions and the plan of driving home the next day....

SOFSEM 2007 - Day 3

Today started with a keynote given by Ricardo Baeza-Yates from Yahoo! Research on 'Mining Web Queries'. In particular he showed how to identify categories of user queries and how to use this information to create an appropriate ranking of the search results. Besides the already identified 'coarse' categories, such as, e.g., queries being 'informational', 'navigational', or 'transactional' (which means that the user wants to have (a) information about a specified topic, (b) a starting point for further research, or (c) a homepage related to the resource for transactional purposes (e.g. shopping)...), he addressed several graphs that can be compiled out of the search engine logfile, as e. g., URL cover graph, URL link graph, session graph...These graphs can be used for identifying polysemic expressions, similar or related queries, clusterings of queries, or even a (pseudo)taxonomy of queries.
Besides web query mining, he mentioned some interesting numbers concerning Yahoo, as e.g. that Yahoo administrates about 20 PetaBytes of Data with more than 10 TeraBytes of data traffic per day. But, on the other hand, he gave an estimation of the actual world knowledge and related it to the ammount of data managed by Yahoo today: given that a person creates about 10 pages of data concerning a distinct event, and if we estimate the number of events of about 5000 in a lifetime, and if we multiply that number by the world's population....we will end up with about 0,0057% of the 'world knowledge' currently being represented in Yahoo...

SOFSEM 2007 - Day 2

The second day of SOFSEM started with a keynote of Bertrand Meyer (maybe you remember Eiffel...) from ETH Zürich on 'Automatic Testing of Object-Oriented Software'. To enable automated testing, he referred the concept of 'contracts' being directly embedded in the classes of the Eiffel programming language. With a contract you are able to specify the software's expected behaviour (preconditions, postconditions, and invariants). which can be monitored during execution. In automated software testing, contracts may serve as test oracles that decide, whether a test case has passed or failed. He presented 'Auto Test' unit testing framework, which is using Eiffel contracts as test oracles. Auto Test is able to exercise all classes by generating objects and routine arguments. Also manual testing can be embedded as well as regression testing for failed test cases, which is implemented in a 'minimized' form by retaining only the relevant instructions.

For the rest of the second day contributed (refereed) paper presentations are scheduled. I will have to chair the first session of the 'emerging web technologies' track, which will be on XML technology. If there (or in any other session I attend) will be anything of interest, you will read it right here ... :)
So...Joe Tekli from the Université de Bourgogne presented a 'Hybrid Approach on XML-Similarity', which combined structural similarity of XML-Documents with 'semantic' arguments, i.e. tag names of different XML-documents are compared with the help of WordNet to compute some similarity measure. Quite an interesting application that can be build on, esp. regarding the semantic similarity aspect. But nevertheless, maybe we can use it for our MPEG-7 based video search system (OSOTIS).

SOFSEM 2007 - Day 1

This year, after about 7 or 8 years, I am attending again the SOFSEM conference on 'Current Trends in Theory and Practice of Computer Science' (for the 2nd time). Maybe SOFSEM is not the most important of all the computer science conferences around, but it is rather original and has quite some history (i.e. it's tradition dates back more than 30 years...). SOFSEM means SOFtware SEMinar, and this already gives some hint about its originality. Starting from a winter lecture with only limited international attendance it has developed to an interesting mixture of lectures (given by invited speakers of significant reputation), presentations of reviewed research papers, and student paper presentations. By tradition, it's location always switches between somewhere in Slowakia and the Czech Republique and always in winter. Unfortunately, this year winter did not really show up and thus, we are sitting here in Harrachow (a well known winter resort) without any snow. On the other hand, nice thing about this situation is that travelling this year has become much easier (because there is no snow even in the mountain areas).
This year, I am co-chairing the track 'emerging web technologies' as being one of the four SOFSEM tracks. By tradition, there is always a track 'foundations of computer science' besides of three changable tracks concering breaking topics of current interest , i.e. (in this year) 'multi-agent systems', 'emerging web technologies', and 'dependable software and systems'.
The first day on SOFSEM, after the opening note given by Jan van Leeuwen, in which he referred to the long tradition of SOFSEM and to Czech computer science history, starts with a full day of invited lectures covering all four topics.

• Manfred Broy from TU Munich started with a presentation on 'Interaction and Realizability'. In interactive computation - in difference to sequential, atomic computation - input as well as output is not provided as a whole, but step by step while the computation continues. He pointed out that interactive behaviour can be modeled with Moore machines and introduced the term of 'realizability', which is a fundamental issue when asking whether a behaviour corresponds to a computation. 'Realizable functions' are defined as being abstractions of state machines (in a similar way as partial functions are abstractions of Turing machines) and can be used to extend the idea of computability to interactive computations.


• Andrew Goldberg followed with a talk on 'Point-to-Point Shortest Path Algorithms with Preprocessing'. To run on even small devices while at the same time covering graphs with tens of millions of nodes (as, e.g., in roadmaps for navigation devices), off course efficient algorithms are required. The traditional way is to search a ball around the starting point (as e.g. in Dijkstra's algorithm) that can be speed up by biasing the search towards to intendet target point (as e.g. in A* search, if additional information is available that provides a lower-bound on the distance to the target) or by pruning the search graph (as e.g. in ALT algorithms that precompute distances to preselected landmarks, or using 'reaches').


• Jerome Lang from IRIT (France) continued the afternoon session with a survey on 'Computational Issues in Group Decision Making', which combines 'social choice' (from economics) and AI (applications) into 'computational social choice' theory. In this new and very active discipline concepts as e.g. voting procedures, coalition formation, and fair division (from social choice), which is also important for multi-agent systems, are examined under the consideration of complexity analyses and algorithm design.
  


• I realized that I will be the chairman of today's last session. Thus, the summary of Remco Veltkamp's (University of Utrecht, The Netherlands) talk on 'Multimedia Retrieval Algorithms' will come with a little delay....
  The presentation started with citing Marshal McLuhan's famous quote 'The medium is the message' smartly being connected to the basic definitions of multimedia retrieval. Difficult thing in multimedia retrieval is the proper understanding of the mechanisms of human perception and in connection to that the question of how to take care of it's peculiarity in information retrieval. E. g., the human visual system is famous for 'generic interpretations', i.e. sometimes we see things that are not really there, as already has been described by Wertheimer's Gestalttheorie back in 1923. Interesting fact, that some of these visual illusions do also exist for audio perception. For multimedia retrieval metrics have to be defined for computing similarities (as well as differences of multimedia objects) in an efficient way, while the algorithms dealing with multimedia retrieval have to be carefully designed according to the type of problem that is addressed (e.g., computing problem, optimization problem, decision problem, etc.). The presentation closed with a short demonstration of the music search engine Muugle that realizes the concept of 'query-by-humming'.