Space efficient quantile summary for constrained sliding windows on a data stream

In many online applications, we need to maintain quantile statistics for a sliding window on a data stream. The sliding windows in natural form are defined as the most recent N data items. In this paper, we study the problem of estimating quantiles over other types of sliding windows. We present a uniform framework to process quantile queries for time constrained and filter based sliding windows. Our algorithm makes one pass on the data stream and maintains an E-approximate summary. It uses O((1)/(epsilon2) log(2) epsilonN) space where N is the number of data items in the window. We extend this framework to further process generalized constrained sliding window queries and proved that our technique is applicable for flexible window settings. Our performance study indicates that the space required in practice is much less than the given theoretical bound and the algorithm supports high speed data streams.

Towards pattern-based design recovery

A method and a corresponding tool is described which assist design recovery and program understanding by recognising instances of design patterns semi-automatically. The approach taken is specifically designed to overcome the existing scalability problems caused by many design and implementation variants of design pattern instances. Our approach is based on a new recognition algorithm which works incrementally rather than trying to analyse a possibly large software system in one pass without any human intervention. The new algorithm exploits domain and context knowledge given by a reverse engineer and by a special underlying data structure, namely a special form of an annotated abstract syntax graph. A comparative and quantitative evaluation of applying the approach to the Java AWT and JGL libraries is also given.

Palynostratigraphy of Ordovician strata, Canning Basin, Western Australia. Part One: acritarchs and prasinophytes

This paper is the initial part of a comprehensive bipartite monograph of palynomorphs (viz., acritarchs, prasinophyte phycomata, and chitinozoans) that are represented profusely in marine lower Palaeozoic strata of the Canning Basin, Western Australia. The prime aim is to establish a palynologically based zonal scheme for the Ordovician sequence as represented in five cored boreholes drilled through the Lower to Middle Ordovician strata of the central-northeastern Canning Basin. These strata embrace the Oepikodus communis through Phragmodus-Plectodina conodont zonal interval and comprise (in ascending order) the Willara, Goldwyer, and Nita formations, of inferred early Arenig to Llanvirn age. All three formations contain moderately diverse and variably preserved palynomorphs. The palynomorph taxa, detailed systematically in the current Part One of this monograph, comprise 66 species of acritarchs and six of prasinophytes. Of these, two species of prasinophytes and 11 of acritarchs are newly established: Cymatiosphaera meandrica and Pterospermella franciniae; Aremoricanium hyalinum, A. solaris, Baltisphaeridium tenuicomatum, Gorgonisphaeridium crebrum, Lophosphaeridium aequalium, L. aspersum, Micrhystridium infrequens, Pylantios hadrus, Sertulidium amplexum, Striatotheca indistincta, and Tribulidium globosum. Pylantios (typified by P. hadrus), Sertulidium (typified by S. amplexum), and Tribulidium (typified by T globosum); are defined as new acritarch genera. Three new combinations are instituted: Baltisphaeridium pugiatum (PLAYFORD & MARTIN 1984), Polygonium canningianum (COMRAZ & PENIGUEL 1972), and Sacculidium furtivum (PLAYFORD & MARTIN 1984); and Ammonidium macilentum PLAYFORD & MARTIN 1984 and Sacculidium furtivum (PLAYFORD & MARTIN 1984) are emended. An appreciable number of palynomorph species are not formally named owing to lack of sufficient or adequately preserved specimens; others are compared but not positively identified with previously instituted species. The ensuing Part Two of this study will complete the systematic-descriptive documentation, i.e., chitinozoans, and evaluate the Canning Basin palynoflora in terms of its chronological and stratigraphic-correlative significance.