A fast algorithm for finding frequent episodes in event streams

Frequent episode discovery is a popular framework for mining data available as a long sequence of events. An episode is essentially a short ordered sequence of event types and the frequency of an episode is some suitable measure of how often the episode occurs in the data sequence. Recently,we proposed a new frequency measure for episodes based on the notion of non-overlapped occurrences of episodes in the event sequence, and showed that, such a definition, in addition to yielding computationally efficient algorithms, has some important theoretical properties in connecting frequent episode discovery with HMM learning. This paper presents some new algorithms for frequent episode discovery under this non-overlapped occurrences-based frequency definition. The algorithms presented here are better (by a factor of N, where N denotes the size of episodes being discovered) in terms of both time and space complexities when compared to existing methods for frequent episode discovery. We show through some simulation experiments, that our algorithms are very efficient. The new algorithms presented here have arguably the least possible orders of spaceand time complexities for the task of frequent episode discovery.

Crustal Deformation and Seismic History Associated with the 2004 Indian Ocean Earthquake: A Perspective from the Andaman–Nicobar Islands

The Indian Ocean earthquake of 26 December 2004 led to significant ground deformation in the Andaman and Nicobar region, accounting for ~800 km of the rupture. Part of this article deals with coseismic changes along these islands, observable from coastal morphology, biological indicators, and Global Positioning System (GPS) data. Our studies indicate that the islands south of 10° N latitude coseismically subsided by 1–1.5 m, both on their eastern and western margins, whereas those to the north showed a mixed response. The western margin of the Middle Andaman emerged by >1 m, and the eastern margin submerged by the same amount. In the North Andaman, both western and eastern margins emerged by >1 m. We also assess the pattern of long-term deformation (uplift/subsidence) and attempt to reconstruct earthquake/tsunami history, with the available data. Geological evidence for past submergence includes dead mangrove vegetation dating to 740 ± 100 yr B.P., near Port Blair and peat layers at 2–4 m and 10–15 m depths observed in core samples from nearby locations. Preliminary paleoseismological/tsunami evidence from the Andaman and Nicobar region and from the east coast of India, suggest at least one predecessor for the 2004 earthquake 900–1000 years ago. The history of earthquakes, although incomplete at this stage, seems to imply that the 2004-type earthquakes are infrequent and follow variable intervals

Characterization of Clean and Fouled Rail Track Ballast Subsurface Using Seismic Surface Survey Method: Model and Field Studies

The efficiency of track foundation material gradually decreases due to insufficient lateral confinement, ballast fouling, and loss of shear strength of the subsurface soil under cyclic loading. This paper presents characterization of rail track subsurface to identify ballast fouling and subsurface layers shear wave velocity using seismic survey. Seismic surface wave method of multi-channel analysis of surface wave (MASW) has been carried out in the model track and field track for finding out shear wave velocity of the clean and fouled ballast and track subsurface. The shear wave velocity (SWV) of fouled ballast increases with increase in fouling percentage, and reaches a maximum value and then decreases. This character is similar to typical compaction curve of soil, which is used to define optimum and critical fouling percentage (OFP and CFP). Critical fouling percentage of 15 % is noticed for Coal fouled ballast and 25 % is noticed for clayey sand fouled ballast. Coal fouled ballast reaches the OFP and CFP before clayey sand fouled ballast. Fouling of ballast reduces voids in ballast and there by decreases the drainage. Combined plot of permeability and SWV with percentage of fouling shows that after critical fouling point drainage condition of fouled ballast goes below acceptable limit. Shear wave velocities are measured in the selected location in the Wollongong field track by carrying out similar seismic survey. In-situ samples were collected and degrees of fouling were measured. Field SWV values are more than that of the model track SWV values for the same degree of fouling, which might be due to sleeper's confinement. This article also highlights the ballast gradation widely followed in different countries and presents the comparison of Indian ballast gradation with international gradation standards. Indian ballast contains a coarser particle size when compared to other countries. The upper limit of Indian gradation curve matches with lower limit of ballast gradation curves of America and Australia. The ballast gradation followed by Indian railways is poorly graded and more favorable for the drainage conditions. Indian ballast engineering needs extensive research to improve presents track conditions.

Seismic reliability assessment of internal stability of reinforced soil walls using the pseudo-dynamic method

The study focuses on probabilistic assessment of the internal seismic stability of reinforced soil structures (RSS) subjected to earthquake loading in the framework of the pseudo-dynamic method. In the literature, the pseudo-static approach has been used to compute reliability indices against the tension and pullout failure modes, and the real dynamic nature of earthquake accelerations cannot be considered. The work presented in this paper makes use of the horizontal and vertical sinusoidal accelerations, amplification of vibrations, shear wave and primary wave velocities and time period. This approach is applied to quantify the influence of the backfill properties, geosynthetic reinforcement and characteristics of earthquake ground motions on reliability indices in relation to the tension and pullout failure modes. Seismic reliability indices at different levels of geosynthetic layers are determined for different magnitudes of seismic acceleration, soil amplification, shear wave and primary wave velocities. The results are compared with the pseudo-static method, and the significance of the present methodology for designing reinforced soil structures is discussed.

Seismic hazard map of Coimbatore using subsurface fault rupture

This study presents the future seismic hazard map of Coimbatore city, India, by considering rupture phenomenon. Seismotectonic map for Coimbatore has been generated using past earthquakes and seismic sources within 300 km radius around the city. The region experienced a largest earthquake of moment magnitude 6.3 in 1900. Available earthquakes are divided into two categories: one includes events having moment magnitude of 5.0 and above, i.e., damaging earthquakes in the region and the other includes the remaining, i.e., minor earthquakes. Subsurface rupture character of the region has been established by considering the damaging earthquakes and total length of seismic source. Magnitudes of each source are estimated by assuming the subsurface rupture length in terms of percentage of total length of sources and matched with reported earthquake. Estimated magnitudes match well with the reported earthquakes for a RLD of 5.2% of the total length of source. Zone of influence circles is also marked in the seismotectonic map by considering subsurface rupture length of fault associated with these earthquakes. As earthquakes relive strain energy that builds up on faults, it is assumed that all the earthquakes close to damaging earthquake have released the entire strain energy and it would take some time for the rebuilding of strain energy to cause a similar earthquake in the same location/fault. Area free from influence circles has potential for future earthquake, if there is seismogenic source and minor earthquake in the last 20 years. Based on this rupture phenomenon, eight probable locations have been identified and these locations might have the potential for the future earthquakes. Characteristic earthquake moment magnitude (M-w) of 6.4 is estimated for the seismic study area considering seismic sources close to probable zones and 15% increased regional rupture character. The city is divided into several grid points at spacing of 0.01 degrees and the peak ground acceleration (PGA) due to each probable earthquake is calculated at every grid point in city by using the regional attenuation model. The maximum of all these eight PGAs is taken for each grid point and the final PGA map is arrived. This map is compared to the PGA map developed based on the conventional deterministic seismic hazard analysis (DSHA) approach. The probable future rupture earthquakes gave less PGA than that of DSHA approach. The occurrence of any earthquake may be expected in near future in these eight zones, as these eight places have been experiencing minor earthquakes and are located in well-defined seismogenic sources.

Fast algorithms for frequent episode discovery in event sequences

In this paper we consider the process of discovering frequent episodes in event sequences. The most computationally intensive part of this process is that of counting the frequencies of a set of candidate episodes. We present two new frequency counting algorithms for speeding up this part. These, referred to as non-overlapping and non-inteleaved frequency counts, are based on directly counting suitable subsets of the occurrences of an episode. Hence they are different from the frequency counts of Mannila et al [1], where they count the number of windows in which the episode occurs. Our new frequency counts offer a speed-up factor of 7 or more on real and synthetic datasets. We also show how the new frequency counts can be used when the events in episodes have time-durations as well.

Generalized frequent episodes in Event Sequences

Discovering patterns in temporal data is an important task in Data Mining. A successful method for this was proposed by Mannila et al. [1] in 1997. In their framework, mining for temporal patterns in a database of sequences of events is done by discovering the so called frequent episodes. These episodes characterize interesting collections of events occurring relatively close to each other in some partial order. However, in this framework(and in many others for finding patterns in event sequences), the ordering of events in an event sequence is the only allowed temporal information. But there are many applications where the events are not instantaneous; they have time durations. Interesting episodesthat we want to discover may need to contain information regarding event durations etc. In this paper we extend Mannila et al.’s framework to tackle such issues. In our generalized formulation, episodes are defined so that much more temporal information about events can be incorporated into the structure of an episode. This significantly enhances the expressive capability of the rules that can be discovered in the frequent episode framework. We also present algorithms for discovering such generalized frequent episodes.