Pattern-based aggregate (PBA) queries constitute an important and widely used type of analytical queries in sequence OLAP (S-OLAP) systems. Unfortunately, finding accurate answers to PBA queries in the S-OLAP system is often very expensive both in terms of time and memory consumption. In this paper we propose an efficient and easily maintainable index structure called the ABBA Index, which addresses the problem of PBA query processing. Experiments conducted using the KDD Cup data and public transport passengers’ travel behavior data show that our index outperforms state-of-the art solutions while requiring much less memory. The ABBA Index can be easily extended to support pattern-based aggregate queries over hierarchy (PBA-H), a novel class of analytical queries which we introduce as the second main contribution of the paper. Sensitivity, scalability and complexity analysis of the ABBA Index is also provided.

Abstract There is a certain belief among data science researchers and enthusiasts alike that clustering can be used to improve classification quality. Insofar as this belief is fairly uncontroversial, it is also very general and therefore produces a lot of confusion around the subject. There are many ways of using clustering in classification and it obviously cannot always improve the quality of predictions, so a question arises, in which scenarios exactly does it help? Since we were unable to find a rigorous study addressing this question, in this paper, we try to shed some light on the concept of using clustering for classification. To do so, we first put forward a framework for incorporating clustering as a method of feature extraction for classification. The framework is generic w.r.t. similarity measures, clustering algorithms, classifiers, and datasets and serves as a platform to answer ten essential questions regarding the studied subject. Each answer is formulated based on a separate experiment on 16 publicly available datasets, followed by an appropriate statistical analysis. After performing the experiments and analyzing the results separately, we discuss them from a global perspective and form general conclusions regarding using clustering as feature extraction for classification.

Now that the use of XML is prevalent, methods for mining semi-structured documents have become even more important. In particular, one of the areas that could greatly benefit from in-depth analysis of XML’s semi-structured nature is cluster analysis. Most of the XML clustering approaches developed so far employ pairwise similarity measures. In this paper, we study clustering algorithms, which use patterns to cluster documents without the need for pairwise comparisons. We investigate the shortcomings of existing approaches and establish a new pattern-based clustering framework called XPattern, which tries to address these shortcomings. The proposed framework consists of four steps: choosing a pattern definition, pattern mining, pattern clustering, and document assignment. The framework’s distinguishing feature is the combination of pattern clustering and document-cluster assignment, which allows to group documents according to their characteristic features rather than their direct similarity. We experimentally evaluate the proposed approach by implementing an algorithm called PathXP, which mines maximal frequent paths and groups them into profiles. PathXP was found to match, in terms of accuracy, other XML clustering approaches, while requiring less parametrization and providing easily interpretable cluster representatives. Additionally, the results of an in-depth experimental study lead to general suggestions concerning pattern-based XML clustering.

One of the important research and technological problems in data warehousing is the optimization of star queries. So far, most of the research focused on optimizing such queries by means of join indexes and bitmap join indexes. In this paper we propose an index, called Time-HOBI, for optimizing star queries and computing aggregates along dimension hierarchies. Time-HOBI, created on a dimension hierarchy, is composed of: (1) a hierarchically organized bitmap index (HOBI), one bitmap index for one dimension level and (2) a time index (TI) that implicitly encodes time in every dimension. HOBI allows to quickly search for fact rows that fulfill selection criteria. With the support of TI joining a fact table with the Time dimension is avoided. Time-HOBI was implemented and evaluated experimentally on a real dataset, coming from the biggest East-European Internet auction platform Allegro.pl. The experiments show that Time-HOBI offers a promising star query performance.

A data warehouse (DW) is fed with data that come from external data sources that are production systems. External data sources, which are usually autonomous, often change not only their content but also their structure. The evolution of external data sources has to be reflected in a DW, that uses the sources. Traditional DW systems offer a limited support for handling dynamics in their structure and content. A promising approach to handling changes in DW structure and content is based on a multiversion data warehouse. In such a DW, each DW version describes a schema and data at certain period of time or a given business scenario, created for simulation purposes. In order to appropriately analyze multiversion data, an extension to a traditional SQL language is required. In this paper we propose an approach to querying a multiversion DW. To this end, we extended a SQL language and built a multiversion query language interface with functionality that allows: (1) expressing queries that address several DW versions and (2) presenting their results annotated with metadata information.

In this paper we present some of the results achieved while realising an international research project aiming at the design and development of an Object-Relational Data Warehousing System ORDAWA. Important goals of the project are to develop techniques for the integration and consolidation of different external data sources in an object-relational data warehouse, the construction and maintenance of materialised relational as well as object-oriented views, index structures, query transformations and optimisations, and techniques of data mining. The achievements discussed in this paper concern the application of materialised object-oriented views in the process of building an object-relational data warehouse.

The concurrency control problem for multiversion database systems (MVDBSs) with system-imposed upper bounds on the total number of data item versions stored in the database is considered. Concurrency control theory for MVDBSs is reviewed. The inadequacy of this theory for analyzing concurrency control algorithms for k-version database systems (KVDBSs) is demonstrated. A formal concurrency control theory for KVDBS is presented. It is developed in terms of KV schedules. The relationships among mono-multi, and KV schedules are summarized.>

An erroneous fact concerning the assumption of irreducibility of nonjoining attributes of the distributed query optimization algorithm called GENERAL presented in the above paper (see ibid., vol.SE-9, no.1, p.57-68, Jan. 1983) is pointed out. It is shown that it is possible to generate an efficient semijoin program with better response time than the one produced by the GENERAL algorithm. A counterexample that proves this possibility is provided.>