Association Rules Discovery in Multivariate Time Series♣ © Elena Lutsiv University of St.-Petersburg, Faculty of Mathematics and Mechanics eluciv@math.spbu.ru Abstract chaotic nature. On the other hand, when someone thinks of the system behavior, he rather keeps in mind some A problem of association rules discovery in a dependencies between typical local development pieces multivariate time series is considered in this or scenarios. When an expert inspects system behavior paper. A method for finding interpretable over time, usually he tries to find some relatively short association rules between frequent qualitative and simple pieces of history that occur frequently patterns is proposed. A pattern is defined as a enough and are easy to interpret. The next natural step sequence of mixed states. The multivariate is to find out some cause-effect, coincidence or some time series is transformed into a set of labeled other dependencies between frequent episodes. For intervals and mined for frequently occurring example, he may find that “IF pressure falls and it is patterns. Then these patterns are analyzed to summer THEN rain will start in 24 hours with high find out which of them occur close to each confidence”. In this paper we propose a method for other frequently. Some modifications and such association rules discovery from a multivariate improvements of the method are proposed and temporal sequence. discussed. Automation of this process requires a definition of time series similarity. Frequent episodes obtained with 1 Introduction different measures traditionally used for estimating similarity (e.g. Euclidian distance) provide a little Many classes of data that we deal with in our everyday information about system behavior that can be life are temporal in their nature: medical information interpreted by a human ([1], [5]). In this paper we use a about patients and their diseases, goods selling data, different way to discover frequent time series episodes financial data from stock markets, etc. In most cases (or patterns). Similar approaches are used, for example, they describe development of some variables or objects in [10] and [14]. This kind of process is believed to be over time. All these data provide relatively small much closer to a process used by a human (see [10]). amount of knowledge by themselves, but much more The main idea is to divide up the time series into a set information can be obtained from objects behavior of labeled intervals. Each interval is a time interval analysis. Such analysis that aimed at extracting during which some condition is true in the original previously unknown rules from temporal data is called series (for example, “a series decreases” or “a patient Temporal Data Mining or Knowledge Discovery. A has flu”). This can be done in different ways: intervals comprehensive and detailed overview of temporal data and their labels can be identified empirically or as a mining techniques can be found, for example, in [3] and result of some automatic process, e.g. short [12]. subsequences clustering [6]. Once we have the initial Discovered knowledge can be used both to improve set of intervals, we build all intersections of all subsets understanding of underlying processes and for time of intervals and add them to our set. Finally we know series prediction given some observations in the past. In all segments of time series where one or more simple both cases it is important for all found regularities, conditions hold simultaneously. patterns and rules to be understandable and interpretable This paper proposes the method of frequent patterns by a domain expert. It seems that the best way for this is discovery from the described interval set. A pattern is to create a model of time series behavior (e.g., ARMA defined as a sequence of state labels (simple or mixed). or ARIMA models [4]), but in many cases these models More formally it will be defined later. An algorithm of are difficult to understand for a human. Furthermore, finding such pattern’s occurrences has been developed for many series, such as stock market data, it is and is described in the paper. impossible to develop a global model due to their The paper is organized as follows: Section 2 ♣ contains a brief overview of similar works; Section 3 This work was partially supported by RFBR (grant defines a notion of a pattern and describes frequent 07-07-00268a). patterns discovery procedure; in Section 4 a process of Proceedings of the Spring Young Researcher's association rules generation is briefly outlined; Section Colloquium On Database and Information Systems 5 is devoted to discussions of the method and some SYRCoDIS, Moscow, Russia, 2007 modifications are proposed there. Section 6 contains matching even if some conditions except ones defined conclusions and outlines further work directions. by the pattern are held on it. 2 Related Work 3 Frequent Patterns Discovery There are a number of approaches dealing with symbol The frequent patterns discovery procedure includes sequences. In [6] a set of symbols is obtained from a three general steps: time series by clustering short subsequences extracted 1. Extract a basic set of simple intervals from the time with a sliding window. Then the sequence is mined for series (i.e. intervals labeled with simple states); associations between symbols that are close enough to 2. Convert an initial time series into a sequence of non- each other. In [13] an a priori style algorithm is used to overlapping intervals labeled with mixed states; discover frequent Episodes in a symbol sequence. In [8] 3. Mine the sequence for frequent patterns. authors apply genetic programming for pattern mining This section gives a definition of a pattern and describes and use special hardware for efficient sequence all these stages in details. matching. The following approaches work with interval 3.1 Basic Interval Set sequences produced from the time series, for example, As was mentioned above, to be able to discover time using feature extraction. In [11] a sequence of intervals series behavior qualitative patterns, we need to extract a is searched for containment relations. In [7] a time set of labeled intervals from the series. Let’s denote as series is divided into a set of labeled intervals. Then the S0 a set of all simple states or conditions based on which interval set is mined for patterns described in terms of we divide our series into intervals (for example, “a Allen’s [2] interval logic. Interesting patterns are patient has a high temperature” or “humidity goes up”). restricted to A1 patterns, where operators can be States in S0 are not required to be mutually exclusive, so appended only on the right hand side. Another method intervals of the resulting set may overlap. This fact that uses Allen’s operators for pattern definition is allows us not to restrict ourselves with only single proposed in [10]. A set of labeled intervals is obtained univariate time series, but freely work with multivariate from a multivariate time series and mined for patterns time series or even with several ones as well. Thus we with a sliding window to restrict pattern length. Then obtain a set I0 from our time series – a set of intervals patterns are filtered by their interestingness using J- labeled with simple states: measure [15]. The last mentioned method is close to the proposed I0 = {(s1, b1, e1), (s2, b2, e2), … , (sn, bn, en)} (1) approach, but its has two main disadvantages. The first Here (si, bi, ei) denotes an interval labeled with a is that pattern’s frequency strongly depends on the state si ∈ S0, beginning at bi and ending at ei. All these width of the sliding window. If an occurrence of a intervals are required to be maximal intervals. This pattern is a little longer than the window, it’s not taken means that in I0 there are no adjacent intervals or into account at all. The second disadvantage is that intervals with non-empty intersection labeled with the patterns in [10] are expressed in terms of interval logic, same state. I.e.: that makes them difficult to understand. The approach proposed in this paper solves both of ∀ i=1..n, j=1..n: si = sj => ej < bi ∨ ei < bj (2) these problems. It uses “windows” of all widths, that For the next step we need to order states of S0 in significantly smooths the difference between some way. A choice of ordering procedure is not very frequencies of patterns with instances of close lengths. important. For example, states may be ordered Patterns are expressed in terms of simultaneous states – lexicographically according to names of their labels or in the way that is closer to the human reasoning. The somehow else. This is needed only to enable ordering of author believes that a description like “pressure all intervals of I0 according to the rules below: increases and temperature decreases for 1 hour, and then (may be after some time) pressure slightly ∀ (si, bi, ei), (sj, bj, ej) ∈ I0: decreases” is more natural then “an interval where • If bi < bj then (si, bi, ei) < (sj, bj, ej); pressure increases is overlapped by an interval where • If bi > bj then (si, bi, ei) > (sj, bj, ej); temperature decreases, and the latter one is met by an • If bi = bj then: interval where pressure slightly decreases”. Moreover, − If si < sj then (si, bi, ei) < (sj, bj, ej); since the first statement involves only important − If si > s j then (si, bi, ei) > (sj, bj, ej); sequence pieces, it matches more segments of the time − Note that si = sj is impossible due to the series than the second one. maximality requirement. Ther is another work ([14]) that uses an idea of I0 – is a set of maximal simple intervals – that is simultaneous states, but in rather simplified form: it’s ordered as described above, we call it a basic interval authors state that a labelled interval matches an “Event” set. An example is shown on the Fig. 1. Here S0 = {A, (a set of simultaneously holding states) if a set of states B, C, D} and I0 = {(A, 1, 4), (B, 2, 3), (C, 2, 6), (D, 3, holding on this interval exactly coincides with the 5)}. Event. The method proposed in the current paper uses more flexible approach that allows to treat an interval as A or psu+1 ⊆ psu)) B associate (sv,bv,ev) with psu; C v := v + 1; D end while 1 2 3 4 5 6 u := u + 1; end while. Fig. 1. An example of interval set There are some facts that should be noted: 1. If an interval (sk, bk, ek) belongs to a group associated 3.2 Patterns with psu, then psu ⊆ sk. 2. If ek < bk+1, then (sk, bk, ek) and (sk+1, bk+1, ek+!) As was mentioned above, the main goal of this method cannot be associated with the same element of P. I. e. is to find association rules for patterns expressed in non-adjacent intervals cannot be associated with the terms of simultaneous or mixed states. A mixed state is same element of P. any subset of S0. An interval i is labeled with a mixed 3. If psu+1 ⊆ psu, (sk-1, bk-1, ek-1) is associated with psu state s = {s1 , …, sn} if: and psu+1 ⊆ sk, then (sk, bk, ek) will be associated with i = i1 ∩ i2 ∩ … ∩ in: ik ∈ I0 and ik is labeled with (3) psu+1 only if psu { sk. This is due to semantics of sk, k = 1..n such patterns. A pattern <{A, B}, {A}> means that at In other words, if two or more simple intervals first conditions A and B must hold for some time overlap, then their intersection is labeled with a mixed simultaneously and then there must be some time state, composed of all simple state labels of these when A is true and B is false. If an existence of one intervals. Since I0 consists of maximal intervals, all of these intervals is not important, then the pattern is simple states in a mixed state are different. to be reduced to <{A}> or <{A, B}>. For further description of patterns and matching Fig. 2 (b, c) shows how a sequence ({A}, {A, B, C}, procedure we need to define a sequence I that will be {A, C, D}, {C, D}, {D}) matches patterns <{A}, {A, B}, searched for pattern occurrences. Let D = {d1, d2, …, {C, D}, {D}> and <{A}, {B}, {C}, {D}>. dm} be an ordered sequence of all different beginning and ending points of I0 intervals. I consists of all A ABC ACD CD D a) intervals (s, dk, dk+1), where s is a mixed state that includes all simple states holding during this time A AB CD D b) interval. For example, Fig. 2 (a) illustrates I for A B C D intervals shown on Fig. 1: c) D = {1, 2, 3, 4, 5, 6}; Fig. 2. Pattern matching I = (({A}, 1, 2), ({A, B, C}, 2, 3), ({A, C, D}, 3, 4), ({C, D}, 4, 5), ({C}, 5, 6)) To find all subsequences of I that match P – Note that I consists of maximal intervals due to occurrences of P – the following procedure is used: maximality of all intervals of I0. 1. Let u = 1. A pattern is defined as a sequence of mixed states. 2. Find and add to the resulting subsequence the earliest For example, <{A}, {A, B}, {C}> denotes a pattern interval (sk(u), bk(u), ek(u)) so that psu ⊆ sk(u). that consists of mixed states {A}, {A, B} and {C}, 3. If psu+1 ⊆ psu, then find the maximum d(u) so that where A, B and C are simple states. (sk(u), bk(u), ek(u)), (sk(u)+1, bk(u)+1, ek(u)+1), …, (sk(u)+d(u), Consider: bk(u)+d(u), ek(u)+d(u)) are adjacent intervals and psu ⊆ − a pattern P = sk(u), psu ⊆ sk(u)+1, …, psu ⊆ sk(u)+d(u). Add these − a subsequence Q of I: Q = ((s1, b1, e1), (s2, b2, intervals to the resulting subsequence. e2), … , (sm, bm, em)), where (sk, bk, ek) ∈ I and ek ≤ bk+1. 4. If psu+1 { psu, then find the maximum d(u) so that An algorithm that matches P and Q is outlined (sk(u), bk(u), ek(u)), (sk(u)+1, bk(u)+1, ek(u)+1), …, (sk(u)+d(u), below. After successful matching the sequence Q is bk(u)+d(u), ek(u)+d(u)) are adjacent intervals and psu ⊆ broken into n groups of consecutive intervals so that k- sk(u), psu(u) ⊆ sk(u)+1, …, psu ⊆ sk(u)+d(u) and psu+1 { th group is associated with psk. Q matches P only if u > n, v > m and all intervals of Q are associated with states sk(u), psu+1 { sk(u)+1, …, psu+1 { sk(u)+d(u). Add these of P when this process finishes. intervals to the resulting subsequence. u := 1; v := 1; 5. Repeat steps 2 – 4 with the next u and all intervals while (u ≤ n and v ≤ m and psu ⊆ sv) beginning later than ek(u)+d(u) until u > n or the end of while ((v = 1 or ev-1 = bv I is reached. If all elements of P are processed, then or (sv-1,bv-1,ev-1) is the resulting sequence matches P. associated with psu-1) 6. Repeat steps 1 – 5 with all intervals beginning later and v ≤ m and psu ⊆ sv than ek(1)+d(1) until the end of I is reached. and (u = n or psu+1 { sv 3.3 Frequent Patterns Discovery Step k+1: For each P= ∈ Fk find all In this section the procedure of frequent patterns patterns Q= ∈ Fk so that qs1 = ps2, …, discovery is described. qsk-1 = psk, and generate patterns Let a time series under consideration be of length L. from P and each described Q. Test all generated Consider a time “window” of width w ≤ L that overlaps patterns and add all frequent ones to Fk+1. [0, L]. There are (L + w) different windows of width w. Consider a set of all different windows of length ≤ L. 4 Association Rules Discovery This set is of size 3L2/2. Once all frequent patterns are discovered, we can try to Consider a pattern P of cardinality n and a set of all intervals {[pb1, pe1], [pb2, pe2], …, [pbr, per]} so that find association rules. Let’s denote a rule as A B. But for each 1 ≤ i ≤ r: first of all we need to define which patterns will be − pbi < pbi+1 (if i < r); considered as associated. This must be some condition − there is a subsequence ((s1, b1, e1), (s2, b2, e2), …, (sm, (cond) describing how antecedent pattern (A) and bm, em)) of I matching P so that: succedent pattern (B) are disposed. For example, this • if n ≥ 2, then: can be “B starts during A and ends within 2 hours after − ex = pbi and by = pei (where (sx, bx, ex) is the last A ends” or “B starts within 5 minutes after A ends”. interval associated with ps1, and (sy, by, ey) is This condition is to be chosen by a domain expert so the first interval associated with psn during that discovered rules would be easy to interpret. matching); Consider all occurrences of A and B that satisfy − there are no shorter (i.e. with less |by – ex|) condition cond. Let suppA B(A) and suppA B(B) be a subsequences of I matching P within [pbi, pei]. supports of A and B respectively, that are built basing • if n = 1, then pbi = b1 and pei = e1. only on such occurrences. Support of A B is defined in (5). n ≥ 2: (5) supp(A B) = suppA B(A) ∩ suppA B(B) r ⎛ ( pbk − pbk −1 ) 2 ⎞ supp ( P ) = ∑ ⎜⎜ ( pbk − pbk −1 )( L − pl k ) − ⎟⎟ k =1 ⎝ 2 ⎠ The simplest way to generate association rules is to (4) n = 1: evaluate a confidence: r ⎛ ( pek − pek −1 ) 2 plk ⎞ supp(A 6 B) 2 supp( P) = ∑ ⎜⎜ ( pek − pek −1 )( L + plk ) − − ⎟ conf(A 6 B) = k =1 ⎝ 2 2 ⎟⎠ supp(A) supp(P) – a support of P – is a set of all windows of for each pair of frequent patterns and select the rule length ≤ L that contain at least one of [pbi, pei] (if n ≥ 2) only if conf(A B) ≥ confmin. But this will result in a or overlap with at least one of [pbi, pei] (if n = 1), 1 ≤ i large set of relatively useless rules. For example, if ≤ r. occurrences of B cover almost all time series, then all This definition is similar to a support definition rules with B as a succedent will be selected, but most of given in [10], but considers “sliding windows” of any them will be of small interest. length between 0 and L, that allows not to limit a length of a pattern occurrence. In common words it can be ⎛ ⎛ p( B | A) ⎞ ⎛ 1 − p( B | A) ⎞ ⎞ J ( B; A) = p( A)⎜⎜ p( B | A) log⎜ ⎟ + (1 − p( B | A) ) log⎜ ⎟ ⎟⎟ (6) expressed like this: if we take any window of length ≤ ⎝ ⎝ p ( B ) ⎠ ⎝ 1 − p ( B) ⎠ ⎠ L, and consider it as a time series, and try to find occurrences of P in it, and succeed, then this window is [9] gives a survey of the most successful an element of supp(P). interestingness measures used in knowledge discovery. |supp(P)| is a cardinality of supp(P). A pattern is One of the most popular measures for association rules called frequent if |supp(P)| ≥ suppmin. Assuming pb0 = - evaluation is a J-measure [15] (see (6)). It is a special L + pe1 and pe0 = -L + pb1, (4) is a formula for case of Shannon’s mutual information and takes into |supp(P)| evaluation. account both rule frequency and rule “surprisingness”. An important property of these definitions is that If J-measure of a rule is less than some threshold value, any subpattern of a frequent pattern is also frequent. then it is not interesting enough and should be excluded This enables the following procedure of frequent pattern from consideration. discovery: find all frequent patterns of length 1, then In our context p(B) is a probability of pattern B construct patterns of length k+1 by appending one occurring in randomly selected window of length ≤ L, mixed state to frequent patterns of length k and get a set and p(A B) is a probability of the fact that B occurs Fk+1 – a set of all frequent patterns of length k+1. The in a randomly selected window of length ≤ L that process finishes when no new frequent patterns can be contains an occurrence of A and cond is true for these found. In more details the procedure is described below: occurrences. The probabilities are evaluated as: Step 1: Scan I and find all patterns of length 1 so that there exists an interval (s, b, e) ∈ I with ps ⊆ s. supp(B) supp( A 6 B) Add all frequent patterns to F1. p(B) = 2 ; p(B | A) = (7) 3L / 2 supp( A) 5 Discussion and Evaluation Fig. 3. Too short intervals There are a number of issues that should be discussed 35000 about the proposed method. One of them is a number of 30000 mixed states. In general case, having N simple states, we obtain 2N possible mixed states. But in practice 25000 some of them cannot take place simultaneously (or can 20000 hold only simultaneously) due to some reason. For 15000 example, consider 3 time series: pressure, temperature 10000 and humidity data, and 6 simple states for each of them: 5000 “increase”, “slow increase”, “fast increase”, “decrease”, 0 “slow decrease”, “fast decrease”. There are 23*6 possible % % % % % % % % % % % 10 12 14 16 18 20 22 24 26 28 30 mixed states, but it is obvious that slowly increasing and fast increasing segments of the same time series Fig. 4. Dependency of frequent patterns number from cannot overlap, or decreasing and fast decreasing suppmin segments of the series always overlap, and so on. Thus the number of possible mixed states is reduced to 73 (or 5000 even 53 if any decreasing/increasing segment is either 4500 fast or slowly decreasing/increasing). Moreover, 4000 possibly not all of them have support exceeding suppmin, 3500 3000 so they will be removed from consideration after the 2500 first step of frequent patterns discovery procedure. 2000 Another problem is very short mixed-state intervals 1500 appearing due to inaccurate initial time series division 1000 500 (especially if it was performed by a human). On Fig. 3 0 (a) the bounds of intervals labeled with simple states A 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 and B were defined roughly, and this resulted in a small interval labeled with a mixed state {A, B}. A simple Fig. 5. Dependency of frequent patterns number from ε solution is to ignore intervals shorter than some threshold ε when searching for pattern occurrences. For Fig. 4 and Fig. 5 present dependencies of discovered example, if l < ε, then a sequence from the Fig. 3 (a) frequent patterns number from suppmin and ε does not match a pattern <{A}, {A, B}, {B}>. The respectively. Data were obtained by applying of a same idea can be applied to situation when there is a pattern discovery algorithm to a simulated interval set. small gap between intervals labeled with the same state To simulate it the following parameters were used: (see Fig. 3 (b)). Such gaps may appear, for example, − number of variables: 3; due to smoothing faults. In this case it may be ignored − number of labels: 9; during patterns discovery and both intervals may be − random interval length from 1 to 100; considered as one continuous interval. − total series length: 30000. But what if the user wants to have patterns that Fig. 4 shows that the number of patterns is inversely exactly define which intervals must be adjacent and proportional to suppmin, and it seems that this number which may have a gap between them in a matching decreases close to linearly if ε grows (Fig. 5). sequence? For example, he wants to extend pattern <{A}, {B}, {C}> with some information like “in a 6 Conclusion and Future Work matching sequence {A}-interval must be met by {B}- interval, but there may be a gap between {B}-interval This paper proposes a method and an algorithm for and {C}-interval”. Such patterns can be enabled by frequent patterns and rules discovery in labeled interval introducing of a special symbol “gap” ( ). A pattern sequence. The interval sequence can be obtained, for example, from multivariate time series by dividing each described above can be expressed like <{A}, {B}, , variable’s behavior into labeled intervals. Since pattern {C}>. “Gap” is not a mixed state, so pattern cardinality is a sequence of mixed states, a domain expert can does not change, but a space of all candidate patterns easily interpret all found frequent patterns and rules. increases. Inaccuracy of series division and data smoothing A defects can be compensated by filtering intervals with B A A minimum interval length. The method was tested over A AB B simulated interval set and dependency of a frequent l patterns number from minimum support and minimum l interval length were investigated. (a) (b) The problem of the proposed method is a large number of generated frequent patterns and rules. A J- measure can help to reduce it, but there still remains a problem of ranking patterns by their interpretability and “importance”. Also an effective algorithm for frequent [15] Smyth, P., Goodman, R. M. Rule Induction Using patterns discovery needs to be developed. Although an Information Theory. In: Knowledge Discovery in initial interval set is converted to a simple sequence of Databases, chapter 9. MIT Press (1991) 159 – 176 mixed state intervals and a pattern is either a mixed states sequence, classical methods of finding subsequence in a sequence are not suitable for pattern matching, since this process is rather complicated. References [1] Agrawal, R., Lin, K.-L., Sawhney, H.S., Shim, K.: Fast Similarity Search in The Presence of Noise, Scaling and Translation in Time-Series Databases. In: Proc. of the 21st Int. Conf. on Very Large Databases, Zurich, Switzerland (1995) [2] Allen, J.F.: Maintaining knowledge about temporal intervals. Communications of the ACM, 26(11) (1983) 832 – 843 [3] Antunes, C., Oliveira, A.: Temporal Data Mining: an Overview. In: KDD Workshop on Temporal Data Mining, San Francisco (2001) 1–13 [4] Box, G.E.P., Jenkins, G.M.: Time Series Analysis: Forecasting and Control. San-Francisco, Holden-Day (1976) [5] Brendt, D.J., Clifford, J.: Finding Patterns in Time Series: A Dynamic Programming Approach. In: Advances in Knowledge Discovery And Data Mining, chapter 9. MIT Press (1996) 229 – 248 [6] Das, G., Lin, K.-I., Mannila, H., Renganathan, G., Smyth, P.: Rule Discovery from Time Series. In: Proc. of the 4th Int. Conf. on Knowledge Discovery and Data Mining, AAAI Press (1998) 16 – 22 [7] Fu, A.W.C., Kam, P.S.: Discovering Temporal Patterns for Interval-Based Events. In: Kambayashi, Y., Mohania, M.K., Tjoa, A.M., eds.: Second International Conference on Data Warehousing and Knowledge Discovery (DaWaK 2000). Volume 1874., London, UK, Springer (2000) 317 – 326 [8] Hetland, M.L., Saetrom, P.: Temporal Rule Discovery Using Genetic Programming and Specialized Hardware. In: Proc. of 4th Int. Conf. on Recent Advances in Soft Computing (2002) 182 – 188 [9] Hilderman, R.J., Hamilton, H.J.: Knowledge discovery and interestingness measures: A survey. Technical Report CS 99-04, Department of Computer Science, University of Regina (1999) [10] Höppner, F.: Discovery of Temporal Patterns – Learning Rules about the Qualitative Behavior of Time Series. In: Proc. of the 5th European Conference on Principles and Practice of Knowledge Discovery in Databases, Lecture Notes in Artificial Intelligence 2168, Springer (2001) [11] Hua, K.A., Maulik, B., Tran, D., Villafane, R.: Mining Interval Time Series. In: Data Warehousing and Knowledge Discovery. (1999) 318 – 330 [12] Lin, W., Orgun, M.A., Williams, G.J.: An Overview of Temporal Data Mining. In: Proceedings of the 1st Australian Data Mining Workshop, Canberra, Australia (2002) [13] Mannila, H., Toivonen, H., Verkamo, A.I.: Discovery of Frequent Episodes in Event Sequences. Data Mining and Knowledge Discovery 1 (1997) 259 – 289 [14] Moerchen, F., Ultsch, A.: Mining Hierarchical Temporal Patterns in Multivariate Time Series. In: Proc. of the 27th German Conference on Artificial Intelligence (KI). Ulm, Germany (2004)