The detection of groups of moving objects on a sliding window of a spatio-temporal data stream has attracted research attention over the last two decades. Until recently, existing methods required a group to be only a subset of a connected component in a sequence of contiguous snapshots, with non-group members allowed to establish connectivity. In our recent work, we have introduced continuous connectedness as a new concept to ensure the intrinsic connectivity of group members within a sliding window. While continuous connectedness has led to more meaningful groups, it has also caused a substantial cost increase because of the higher maintenance cost for the sliding window and the higher number of graph traversals. This paper provides novel performance improvements over our previous methods. First, we propose the I-Trie, a trie for efficiently updating the sliding window and using it as an effective filter for matching continuously connected groups. Second, connected components are derived from an aggregated spatial grid rather than an object graph. Our experimental results confirm that our proposed techniques substantially improve the runtime of continuously connected group detection on spatio-temporal data streams, particularly in densely populated areas.

The computation of the distance of two time series is time- consuming for any elastic distance function that accounts for misalignments. Among those functions, DTW is the most prominent. However, a recent extensive evaluation has shown that the move-split merge (MSM) metric is superior to DTW regarding the analytical accuracy of the 1-NN classifier. Unfortunately, the running time of the standard dynamic programming algorithm for MSM distance computation is Ω(n2), where n is the length of the longest time series. In this paper, we provide approaches to reducing the cost of MSM distance computations by using lower and upper bounds for early pruning paths in the underlying dynamic programming table. For the case of one time series being a constant, we present a linear-time algorithm. In addition, we propose new linear-time heuristics and adapt heuristics known from DTW to computing the MSM distance. One heuristic employs the metric property of MSM and the previously introduced linear-time algorithm. Our experimental studies demonstrate substantial speed-ups in our approaches compared to previous MSM algorithms. In particular, the running time for MSM is faster than a state- of-the-art DTW distance computation for a majority of the popular UCR data sets.

Abstract Computing an accurate mean of a set of time series is a critical task in applications like nearest-neighbor classification and clustering of time series. While there are many distance functions for time series, the most popular distance function used for the computation of time series means is the non-metric dynamic time warping (DTW) distance. A recent algorithm for the exact computation of a DTW-Mean has a running time of $${\mathcal {O}}(n^{2k+1}2^kk)$$ O ( n 2 k + 1 2 k k ) , where k denotes the number of time series and n their maximum length. In this paper, we study the mean problem for the move-split-merge (MSM) metric that not only offers high practical accuracy for time series classification but also carries of the advantages of the metric properties that enable further diverse applications. The main contribution of this paper is an exact and efficient algorithm for the MSM-Mean problem of time series. The running time of our algorithm is $${\mathcal {O}}(n^{k+3}2^k k^3 )$$ O ( n k + 3 2 k k 3 ) , and thus better than the previous DTW-based algorithm. The results of an experimental comparison confirm the running time superiority of our algorithm in comparison to the DTW-Mean competitor. Moreover, we introduce a heuristic to improve the running time significantly without sacrificing much accuracy.

Pattern matching, also known as Match-Recognize in SQL, is an expensive operator of particular relevance in many event stream applications. However, because of its sequential nature and challenging latency requirements, current stream processing engines do not provide any parallel processing support for pattern matching. In addition, hardware accelerators based on dedicated GPUs also offer limited support due to the overhead of transferring data between their local and main memory. In contrast, however, integrated GPUs (iGPUs), with their ability to access main memory directly, offer great potential to accelerate pattern matching. This paper presents the first full-fledged implementation of pattern matching cooperatively using iGPUs and CPUs. Our results obtained from a preliminary experimental performance comparison confirm the potential of our iGPU-based approaches for accelerating pattern matching.

IoT applications require a new type of database systems termed event stores for ingesting fast arriving event streams and efficiently supporting analytical ad-hoc queries over time. One of the most important operations in this regard is sequential pattern matching also known as Match\_Recognize, which matches user defined predicates to subsequences of events. While Match\_Recognize is well known in the field of event processing, it has only recently become part of the SQL standard. Despite of that, Match\_Recognize has received little attention in the database area so far. We present a novel approach to speed up an important class of Match\_Recognize queries on event stores by utilizing off-the-shelf secondary indexes on non-temporal attributes (e.g., B$^+$-trees, LSM-trees) and a cost model for selecting the most appropriate indexes. Our approach keeps temporal and sequential information in secondary indexes to prune large parts of the stream from further processing. However, simply using as many secondary indexes as available is not the right choice because the access cost for the index scans can exceed the processing time of the naï ve approach that scans the entire stream and replays it into an event processing system. In order to address this problem, we present a first cost model to estimate the total execution cost of a Match\_Recognize query for a set of available indexes. Based on this cost model, we devise an efficient index selection strategy that avoids a full enumeration of index configurations. Prototypical implementations of our approach are available in our open-source research prototype, a commercial database system, and Apache Flink. In experiments with synthetic and real-world data sets, all our index-based implementations clearly outperform the naï ve replay strategy that is currently offered in commercial database systems and Flink.

Due to the widespread availability of general purpose GPUs, an integration of their processing capabilities into an event stream pipeline presents an exciting opportunity riddled with challenging requirements: Even though the single instruction multiple data (SIMD) model is a natural fit to answer long running event queries on high volume streams, those queries are usually associated with latency requirements that make transferring data to GPUs unfeasible. Traditionally, this challenge is solved through software by scheduling some tasks to the GPU and some to the CPU. However, the assumptions about transfer do not hold for widely adopted integrated GPUs (iGPUs), which directly share memory with the CPU. We develop a prototypical event processing framework based on the Heterogeneous System Architecture (HSA) and show that a variety of new HSA features enable iGPUs to be an affordable accelerator for a wide variety of event processing queries.

Reactive security monitoring, self-driving cars, the Internet of Things (IoT), and many other novel applications require systems for both writing events arriving at very high and fluctuating rates to persistent storage as well as supporting analytical ad hoc queries. As standard database systems are not capable of delivering the required write performance, log-based systems, key-value stores, and other write-optimized data stores have emerged recently. However, the drawbacks of these systems are a fair query performance and the lack of suitable instant recovery mechanisms in case of system failures. In this article, we present ChronicleDB, a novel database system with a storage layout tailored for high write performance under fluctuating data rates and powerful indexing capabilities to support a variety of queries. In addition, ChronicleDB offers low-cost fault tolerance and instant recovery within milliseconds. Unlike previous work, ChronicleDB is designed either as a serverless library to be tightly integrated in an application or as a standalone database server. Our results of an experimental evaluation with real and synthetic data reveal that ChronicleDB clearly outperforms competing systems with respect to both write and query performance.

The visualization of spatial data becomes increasingly important in science, business and many other domains. In geography, data often corresponds to a large number of point observations that should be displayed on a constrained screen with limited resolution. This causes, however, a loss of information due to an overloaded and occluded visualization. In this paper we present a new visualization algorithm that avoids this problem by aggregating point data into a set of non-overlapping circles that capture all important information. Our algorithm based on a quadtree computes the circles in linear time with respect to the number of points.

During the last decade, complex event processing (CEP) has emerged as a technological foundation for many time-critical monitoring applications. CEP is powerful, effective, easy to use and low in costs at the same time. Common CEP applications are for example stock-market analysis, detection of fraudulent credit card use, traffic monitoring and consumption forecasting in power grids. Many application domains are still hard to target by CEP, because state of the art CEP technology is characterized by a static behavior and by a signature-based detection paradigm. In this paper, we motivate substantial improvements of CEP technology by making the behavior of the infrastructure dynamic and by switching the detection paradigm from signatures to anomalies. This leads to multiple changes in the infrastructure that raise interesting and challenging research questions. The resulting dynamic CEP infrastructure not only makes existing applications more powerful and easier to maintain but also enables novel application domains.

Partial persistent index structures support efficient access to current and past versions of objects, while updates are allowed on the current version. The Multiversion B-Tree (MVBT) represents a partially persistent index-structure with both, asymptotic worst-case performance and excellent performance in real life applications. Updates are performed tuple-by-tuple with the same asymptotic performance as for standard B+trees. To the best of our knowledge, there is no efficient algorithm for bulk loading and bulk update of MVBT and other partially persistent index structures. In this paper, we propose the first loading algorithm for MVBT that meets the lower-bound of external sorting. In addition, our approach is also applicable to bulk updates. This is achieved by combining two basic technologies, weight balancing and buffer tree. Our extensive set of experiments confirm the theoretical findings: Our loading algorithm runs considerably faster than performing updates tuple-by-tuple.

Bulk-loading of R-trees has been an important problem in academia and industry for more than twenty years. Current algorithms create R-trees without any information about the expected query profile. However, query profiles are extremely useful for the design of efficient indexes. In this paper, we address this deficiency and present query-adaptive algorithms for building R-trees optimally designed for a given query profile. Since optimal R-tree loading is NP-hard (even without tuning the structure to a query profile), we provide efficient, easy to implement heuristics. Our sort-based algorithms for query-adaptive loading consist of two steps: First, sorting orders are identified resulting in better R-trees than those obtained from standard space-filling curves. Second, for a given sorting order, we propose a dynamic programming algorithm for generating R-trees in linear runtime. Our experimental results confirm that our algorithms generally create significantly better R-trees than the ones obtained from standard sort-based loading algorithms, even when the query profile is unknown.

Spatial histograms are extremely useful for approximate query processing in large spatial databases. The problem of generating optimal spatial histograms is NP-hard; therefore, many heuristic-based methods have emerged over the last 15 years. Shortcomings of these methods are their complex algorithmic design and their sensitivity to parameter setting, preventing them to be easily integrated into real systems. In this paper, we present a class of spatial histograms derived from the popular family of R-tree indexes. We propose a cost-optimized approach that combines bulk-loading of R-trees and the construction of spatial histograms. This results in a robust histogram method with high accuracy for selectivity estimation of spatial queries. Our method does not require the setting of intuitive parameters at all. In addition, the estimation error continuously decreases with increasing number of histogram buckets, and therefore, our histogram methods can take benefit from large main memories. In an experimental evaluation, we compare the performance of our histograms with state-of-the-art spatial histograms. Our results confirm that our histograms provide low estimation errors and short build-times.

Since navigation systems and tracking devices are becoming ubiquitous in our daily life, the development of efficient methods for processing massive sets of mobile objects are of utmost importance. Although future routes of mobile objects are often known in advance in many applications, this information is not fully utilized in most methods so far. In this paper, we reveal the beneficial effects of exploiting future routes for the early generation of the expected results of spatio-temporal queries. This kind of probable results is important for operative analytics in many applications like smart fleet management or intelligent logistics. For efficiently computing the high number of future trajectory points, a new index structure is presented which allows for a fast maintenance of query results under continuous changes of mobile objects. Our methods make use of specific update patterns, which require substantially less maintenance costs than the most general case of an update. A set of experiments based on a commonly used simulation environment shows the efficiency of our approach.

Since navigation systems and tracking devices are becoming ubiquitous in our daily life, the development of efficient methods for processing massive sets of mobile objects are of utmost importance. Although future routes of mobile objects are often known in advance in many applications, this information is not fully utilized in most methods so far. In this paper, we reveal the beneficial effects of exploiting future routes for the early generation of the expected results of spatio-temporal queries. This kind of probable results is important for operative analytics in many applications like smart fleet management. In order to maintain the results of spatio-temporal queries under continuous changes of mobile objects, we present efficient methods for the maintenance of the results. Our methods make use of specific update patterns, which require substantially less maintenance costs than the most general case of an update.

The multiversion B+-tree (MVBT) by Becker et al. assumes a single-data-item update model in which each new version created for a data item is given a timestamp that is unique across the entire MVBT. In this paper, we extend the MVBT model with multi-action transactions such that all (final) data-item versions created by a transaction are given the same timestamp. We show that the MVBT algorithms can be modified to work in a setting in which multiple readonly transactions and a single updating transaction operate concurrently in snapshot isolation on the MVBT, without compromising the asymptotically optimal time complexity of key inserts, key deletes, and key-range scans on any version. The structural consistency and balance of the MVBT is guaranteed by short-duration latching of pages, redo-only logging of structure modifications (version splits, key splits and page merges), and redo-undo logging of key insertions and deletions. The redo pass of our ARIES-based restart-recovery algorithm always produces a structurally consistent and balanced MVBT on which any undo action by a backward-rolling updating transaction can be performed logically if a physical undo is not possible. The standard steal-and-no-force buffering policy is assumed.

In this paper we present an improved redesign of the R*-tree that is entirely suitable for running within a DBMS. Most importantly, an insertion is guaranteed to be restricted to a single path because re-insertion could be abandoned. We re-engineered both, subtree choice and split algorithm, to be more robust against specific data distributions and insertion orders, as well as peculiarities often found in real multidimensional data sets. This comes along with a substantial reduction in CPU-time.

In recent years the processing of continuous queries over potentially infinite data streams has attracted a lot of research attention. We observed that the majority of work addresses individual stream operations and system-related issues rather than the development of a general-purpose basis for stream processing systems. Furthermore, example continuous queries are often formulated in some declarative query language without specifying the underlying semantics precisely enough. To overcome these deficiencies, this article presents a consistent and powerful operator algebra for data streams which ensures that continuous queries have well-defined, deterministic results. In analogy to traditional database systems, we distinguish between a logical and a physical operator algebra. While the logical algebra specifies the semantics of the individual operators in a descriptive but concrete way over temporal multisets, the physical algebra provides efficient implementations in the form of stream-to-stream operators. By adapting and enhancing research from temporal databases to meet the challenging requirements in streaming applications, we are able to carry over the conventional transformation rules from relational databases to stream processing. For this reason, our approach not only makes it possible to express continuous queries with a sound semantics, but also provides a solid foundation for query optimization, one of the major research topics in the stream community. Since this article seamlessly explains the steps from query formulation to query execution, it outlines the innovative features and operational functionality implemented in our state-of-the-art stream processing infrastructure.

Our demonstration introduces a novel system architecture which massively facilitates optimization in data stream management systems (DSMS). The basic idea is to decouple optimization from the operative system by means of a secondary optimization system, which bears the burden of determining new query plans. Within the secondary system, which typically runs on a separate machine, we utilize suitable statistical models of the original data streams to simulate them. As the simulation can run at much faster rates, we are able to examine and assess new query plans in a shorter period of time without running the risk of deteriorating the original plan; we only migrate practically approved plans into the operative system. In our demonstration, we will present our prototypical implementation of this optimization architecture. We will demonstrate the interaction between primary and secondary system as well as the key features of the whole optimization process.

Data stream management systems need to control their resources adaptively since stream characteristics as well as query workload vary over time. In this paper we investigate an approach to adaptive resource management for continuous sliding window queries that adjusts window sizes and time granularities to keep resource usage within bounds. These two novel techniques differ from standard load shedding approaches based on sampling as they ensure exact query answers for given user-defined Quality of Service specifications, even under query re-optimization. In order to quantify the effects of both techniques on the various operations in a query plan, we develop an appropriate cost model for estimating operator resource allocation in terms of memory usage and processing costs. A thorough experimental study not only validates the accuracy of our cost model but also demonstrates the efficacy and scalability of the proposed techniques.

A variety of real-world applications heavily relies on an adequate analysis of transient data streams. Due to the rigid processing requirements of data streams, common analysis techniques as known from data mining are not directly applicable. A fundamental building block of many data mining and analysis approaches is density estimation. It provides a well-defined estimation of a continuous data distribution, a fact, which makes its adaptation to data streams desirable. A convenient method for density estimation utilizes kernels. The computational complexity of kernel density estimation, however, renders its application to data streams impossible. In this paper, we tackle this problem and propose our Cluster Kernel approach which provides continuously computed kernel density estimators over streaming data. Not only do Cluster Kernels meet the rigid processing requirements of data streams, they also allocate only a constant amount of memory, even with the opportunity to adapt it dynamically to changing system resources. For this purpose, we develop an intelligent merge scheme for Cluster Kernels and utilize continuously collected local statistics to resample already processed data. We focus on Cluster Kernels for one-dimensional data streams, but also address the multi-dimensional case. We validate the efficacy of Cluster Kernels for a variety of real-world data streams in an extensive experimental study.

Computing temporal aggregates is an important but costly operation for applications that maintain time-evolving data (data warehouses, temporal databases, etc.) Due to the large volume of such data, performance improvements for temporal aggregate queries are critical. Previous approaches have aggregate predicates that involve only the time dimension. In this article we examine techniques to compute temporal aggregates that include key-range predicates as well ( range-temporal aggregates ). In particular we concentrate on the SUM aggregate, while COUNT is a special case. To handle arbitrary key ranges, previous methods would need to keep a separate index for every possible key range. We propose an approach based on a new index structure called the Multiversion SB-Tree , which incorporates features from both the SB-Tree and the Multiversion B+--tree, to handle arbitrary key-range temporal aggregate queries. We analyze the performance of our approach and present experimental results that show its efficiency. Furthermore, we address a novel and practical variation called functional range-temporal aggregates. Here, the value of any record is a function over time. The meaning of aggregates is altered such that the contribution of a record to the aggregate result is proportional to the size of the intersection between the record's time interval and the query time interval. Both analytical and experimental results show the efficiency of our result.

A variety of scientific and commercial applications requires an immediate analysis of transient data streams. Many approaches for analyzing data share the property that an estimation of the underlying data distribution is used as a fundamental building block. To estimate the density of a continuous data distribution, wavelet density estimation, a technique from the area of nonparametric statistics, is very appealing as it is theoretically well-founded and practically approved. For that reason, its application to data streams is highly promising; it provides a convenient way to analyze the characteristics of a stream. However, the heavy computational cost of wavelet density estimators renders their direct application to the streaming scenario impossible. In this work, we tackle this problem and present a novel approach to adaptive wavelet density estimators over data streams. Not only do our estimators meet the rigid processing requirements for data streams, they also adapt to changing system resources in a well-defined manner. A thorough experimental evaluation demonstrates the efficacy of our wavelet density estimators and shows their superiority to competing kernel- and histogram-based estimators.

In data stream environments, the initial plan of a long-running query may gradually become inefficient due to changes of the data characteristics. In this case, the query optimizer generates a more efficient plan based on the current statistics. The online transition from the old to the new plan is called dynamic plan migration. In addition to correctness, an effective technique for dynamic plan migration should achieve the following objectives: 1) minimize the memory and CPU overhead of the migration, 2) reduce the duration of the transition, and 3) maintain a steady output rate. The only known solutions for this problem are the moving states (MS) and parallel track (PT) strategies, which have some serious shortcomings related to the above objectives. Motivated by these shortcomings, we first propose HybMig, which combines the merits of MS and PT and outperforms both in every aspect. As a second step, we extend PT, MS, and HybMig to the general problem of migration, where both the new and the old plans are treated as black boxes

In this paper we introduce the problem of Constrained Subspace Skyline Queries. This class of queries can be thought of as a generalization of subspace skyline queries using range constraints. Although both constrained skyline queries and subspace skyline queries have been addressed previously, the implications of constrained subspace skyline queries has not been examined so far. Constrained skyline queries are usually more expensive than regular skylines. In case of constrained subspace skyline queries additional performance degradation is caused through the projection. In order to support constrained skylines for arbitrary subspaces, we present approaches exploiting multiple low-dimensional indexes instead of relying on a single high-dimensional index. Effective pruning strategies are applied to discard points from dominated regions. An important ingredient of our approach is the workload-adaptive strategy for determining the number of indexes and the assignment of dimensions to the indexes. Extensive performance evaluation shows the superiority of our proposed technique compared to its most related competitors.

A fundamental building block of many data mining and analysis approaches is density estimation as it provides a comprehensive statistical model of a data distribution. For that reason, its application to transient data streams is highly desirable. A convenient, nonparametric method for density estimation utilizes kernels. However, its computational complexity collides with the rigid processing requirements of data streams. In this work, we present a new approach to this problem that combines linear processing cost with a constant amount of allocated memory. Our approach also supports a dynamic memory adaptation to changing system resources.

In order to support continuous queries over data streams, a plethora of suitable techniques as well as prototypes have been developed and evaluated in recent years. In particular, it is of utmost importance to confirm their necessity and feasibility in real-world applications. For that reason, we have successfully coupled our infrastructure for data stream processing (PIPES) with an industrial Production-to-Business software (i-Plant) dedicated to highly automated manufacturing processes.

Adaptivity is a challenging open issue in data stream management. In this paper, we tackle the problem of memory adaptivity inside a system executing temporal sliding window queries over continuous data streams. Two different techniques to control the memory usage at runtime are proposed which refer to changes in window sizes and time granularities. Both techniques differ from standard load shedding approaches based on sampling as they ensure precise query answers for user-defined Quality of Service (QoS) specifications, even under query re-optimization.

A variety of real-world applications requires a meaningful online analysis of transient data streams. An important building block of many analysis tasks is the characterization of the underlying data distribution. Sophisticated techniques from the area of nonparametric statistics provide a well-defined estimation of continuous data distributions. The analysis of data streams may gain advantage of these techniques, however, the rigid processing requirements of streams render a direct application impossible. In our work, we tackle the adaptation of nonparametric techniques to streaming data. We concentrate on density estimation as it provides a convenient basis for the exploration of an unknown continuous data distribution. Specifically, we have developed kerneland wavelet-based density estimators for data streams in compliance with their processing requirements. Both techniques are incorporated into PIPES, our Java library for advanced data stream processing and analysis. In the demonstration, we present our nonparametric density estimators over data streams and show their performance for a variety of heterogeneous data streams from different real-world application scenarios. We also present the implementation of further analysis tasks on top of our estimators by means of illustrative use cases

The skyline of a d -dimensional dataset contains the points that are not dominated by any other point on all dimensions. Skyline computation has recently received considerable attention in the database community, especially for progressive methods that can quickly return the initial results without reading the entire database. All the existing algorithms, however, have some serious shortcomings which limit their applicability in practice. In this article we develop branch-and-bound skyline (BBS), an algorithm based on nearest-neighbor search, which is I/O optimal, that is, it performs a single access only to those nodes that may contain skyline points. BBS is simple to implement and supports all types of progressive processing (e.g., user preferences, arbitrary dimensionality, etc). Furthermore, we propose several interesting variations of skyline computation, and show how BBS can be applied for their efficient processing.

PIPES is a flexible and extensible infrastructure providing fundamental building blocks to implement a data stream management system (DSMS). It is seamlessly integrated into the Java library XXL [1, 2, 3] for advanced query processing and extends XXL's scope towards continuous data-driven query processing over autonomous data sources.

Support for exploratory interaction with databases in applications such as data mining requires that the first few results of an operation be available as quickly as possible. We study the algorithmic side of what can and what cannot be achieved for processing join operations. We develop strategies that modify the strict two-phase processing of the sort-merge paradigm, intermingling join steps with selected merge phases of the sort. We propose an algorithm that produces early join results for a broad class of join problems, including many not addressed well by hash-based algorithms. Our algorithm has no significant increase in the number of I/O operations needed to complete the join compared to standard sort-merge algorithms.

The skyline of a set of d-dimensional points contains the points that are not dominated by any other point on all dimensions. Skyline computation has recently received considerable attention in the database community, especially for progressive (or online) algorithms that can quickly return the first skyline points without having to read the entire data file. Currently, the most efficient algorithm is NN (nearest neighbors), which applies the divide -and-conquer framework on datasets indexed by R-trees. Although NN has some desirable features (such as high speed for returning the initial skyline points, applicability to arbitrary data distributions and dimensions), it also presents several inherent disadvantages (need for duplicate elimination if d>2, multiple accesses of the same node, large space overhead). In this paper we develop BBS (branch-and-bound skyline), a progressive algorithm also based on nearest neighbor search, which is IO optimal, i.e., it performs a single access only to those R-tree nodes that may contain skyline points. Furthermore, it does not retrieve duplicates and its space overhead is significantly smaller than that of NN. Finally, BBS is simple to implement and can be efficiently applied to a variety of alternative skyline queries. An analytical and experimental comparison shows that BBS outperforms NN (usually by orders of magnitude) under all problem instances.

We examine the problem of processing temporal joins in the presence of indexing schemes. Previous work on temporal joins has concentrated on non-indexed relations which were fully scanned. Given the large data volumes created by the ever increasing time dimension, sequential scanning is prohibitive. This is especially true when the temporal join involves only parts of the joining relations (e.g., a given time interval instead of the whole timeline). Utilizing an index becomes then beneficial as it directs the join to the data of interest. We consider temporal join algorithms for three representative indexing schemes, namely a B+-tree, an R*-tree and a temporal index, the Multiversion B+-tree (MVBT). Both the B+-tree and R*-tree result in simple but not efficient join algorithms because neither index achieves good temporal data clustering. Better clustering is maintained by the MVBT through record copying. Nevertheless, copies can greatly affect the correctness and effectiveness of the join algorithms. We identify these problems and propose efficient solutions and optimizations. An extensive comparison of all index based temporal joins, using a variety of datasets and query characteristics shows that the MVBT based join algorithms are consistently faster. In particular the link-based algorithm has the most robust behavior. In our experiments it showed a ten fold improvement over the R*-tree joins while it was between six and thirty times faster than the B+-tree joins.

Many recent database applications need to deal with similarity queries. For such applications, it is important to measure the similarity between two objects using the distance between them. Focusing on this problem, this paper proposes the slim-tree, a new dynamic tree for organizing metric data sets in pages of fixed size. The slim-tree uses the triangle inequality to prune the distance calculations that are needed to answer similarity queries over objects in metric spaces. The proposed insertion algorithm uses new policies to select the nodes where incoming objects are stored. When a node overflows, the slim-tree uses a minimal spanning tree to help with the splitting. The new insertion algorithm leads to a tree with high storage utilization and improved query performance. The slim-tree is a metric access method that tackles the problem of overlaps between nodes in metric spaces and that allows one to minimize the overlap. The proposed "fat-factor" is a way to quantify whether a given tree can be improved and also to compare two trees. We show how to use the fat-factor to achieve accurate estimates of the search performance and also how to improve the performance of a metric tree through the proposed "slim-down" algorithm. This paper also presents a new tool in the slim-tree's arsenal of resources, aimed at visualizing it. Visualization is a powerful tool for interactive data mining and for the visual tracking of the behavior of a tree under updates. Finally, we present a formula to estimate the number of disk accesses in range queries. Results from experiments with real and synthetic data sets show that the new slim-tree algorithms lead to performance improvements. These results show that the slim-tree outperforms the M-tree by up to 200% for range queries. For insertion and splitting, the minimal-spanning-tree-based algorithm achieves up to 40 times faster insertions. We observed improvements of up to 40% in range queries after applying the slim-down algorithm.

The similarity join is an important operation for mining high-dimensional feature spaces. Given two data sets, the similarity join computes all tuples (x, y) that are within a distance ε.One of the most efficient algorithms for processing similarity-joins is the Multidimensional-Spatial Join (MSJ) by Koudas and Sevcik. In our previous work --- pursued for the two-dimensional case --- we found however that MSJ has several performance shortcomings in terms of CPU and I/O cost as well as memory-requirements. Therefore, MSJ is not generally applicable to high-dimensional data.In this paper, we propose a new algorithm named Generic External Space Sweep (GESS). GESS introduces a modest rate of data replication to reduce the number of expensive distance computations. We present a new cost-model for replication, an I/O model, and an inexpensive method for duplicate removal. The principal component of our algorithm is a highly flexible replication engine.Our analytical model predicts a tremendous reduction of the number of expensive distance computations by several orders of magnitude in comparison to MSJ (factor 107). In addition, the memory requirements of GESS are shown to be lower by several orders of magnitude. Furthermore, the I/O cost of our algorithm is by factor 2 better (independent from the fact whether replication occurs or not). Our analytical results are confirmed by a large series of simulations and experiments with synthetic and real high-dimensional data sets.

A temporal aggregation query is an important but costly operation for applications that maintain time-evolving data (data warehouses, temporal databases, etc.). Due to the large volume of such data, performance improvements for temporal aggregation queries are critical. In this paper we examine techniques to compute temporal aggregates that include key-range predicates (range temporal aggregates). In particular we concentrate on SUM, COUNT and AVG aggregates. This problem is novel; to handle arbitrary key ranges, previous methods would need to keep a separate index for every possible key range. We propose an approach based on a new index structure called the Multiversion SB-Tree, which incorporates features from both the SB-Tree and the Multiversion B-Tree, to handle arbitrary key-range temporal SUM, COUNT and AVG queries. We analyze the performance of our approach and present experimental results that show its efficiency.

The partition-based spatial-merge join (PBSM) of J.M. Patel and D.J. DeWitt (1996) and the size separation spatial join (S/sup 3/J) of N. Koudas and K.C. Sevcik (1997) are considered to be among the most efficient methods for processing spatial (intersection) joins on two or more spatial relations. Neither method assumes the presence of pre-existing spatial indices on the relations. In this paper, we propose several improvements to these join algorithms. In particular, we deal with the impact of data redundancy and duplicate detection on the performance of these methods. For PBSM, we present a simple and inexpensive online method to detect duplicates in the response set. There is no longer any need to eliminate duplicates in a final sorting phase, as was originally suggested. We also investigate the impact of different internal algorithms on the total run-time of PBSM. For S/sup 3/J, we break with the original design goal and introduce controlled redundancy of data objects. Results of a large set of experiments with real data sets reveal that our suggested modifications to PBSM and S/sup 3/J result in substantial performance improvements, where PBSM is generally superior to S/sup 3/J.

We discovered a surprising law governing the spatial join selectivity across two sets of points. An example of such a spatial join is “find the libraries that are within 10 miles of schools”. Our law dictates that the number of such qualifying pairs follows a power law, whose exponent we call “pair-count exponent” (PC). We show that this law also holds for self-spatial-joins (“find schools within 5 miles of other schools”) in addition to the general case that the two point-sets are distinct. Our law holds for many real datasets, including diverse environments (geographic datasets, feature vectors from biology data, galaxy data from astronomy).

Presents a new algorithm called the 'bulk index join' that can be applied to a broad class of non-equijoins. Similar to the well-known index nested-loops join algorithm, the bulk index join probes the records of the outer relation against the inner relation by using a pre-existing index structure. Like the index nested-loops join, our algorithm is generic in that any tree-based index structure supporting the join predicate can be used. Moreover, the designer of a new index structure might use our generic code to extend the functionality of the index structure without any additional effort. Our experience indicates that the bulk index join is a generic algorithm that performs very fast, and that its implementation is simple enough to be of immediate practical value.

In this paper, we present a comparison of nonparametric estimation methods for computing approximations of the selectivities of queries, in particular range queries. In contrast to previous studies, the focus of our comparison is on metric attributes with large domains which occur for example in spatial and temporal databases. We also assume that only small sample sets of the required relations are available for estimating the selectivity. In addition to the popular histogram estimators, our comparison includes so-called kernel estimation methods. Although these methods have been proven to be among the most accurate estimators known in statistics, they have not been considered for selectivity estimation of database queries, so far. We first show how to generate kernel estimators that deliver accurate approximate selectivities of queries. Thereafter, we reveal that two parameters, the number of samples and the so-called smoothing parameter, are important for the accuracy of both kernel estimators and histogram estimators. For histogram estimators, the smoothing parameter determines the number of bins (histogram classes). We first present the optimal smoothing parameter as a function of the number of samples and show how to compute approximations of the optimal parameter. Moreover, we propose a new selectivity estimator that can be viewed as an hybrid of histogram and kernel estimators. Experimental results show the performance of different estimators in practice. We found in our experiments that kernel estimators are most efficient for continuously distributed data sets, whereas for our real data sets the hybrid technique is most promising.

We show that spatial joins are very suitable to be processed on a parallel hardware platform. The parallel system is equipped with a so called shared virtual memory which is well suited for the design and implementation of parallel spatial join algorithms. We start with an algorithm that consists of three phases: task creation, task assignment and parallel task execution. In order to reduce CPU and I/O cost, the three phases are processed in a fashion that preserves spatial locality. Dynamic load balancing is achieved by splitting tasks into smaller ones and reassigning some of the smaller tasks to idle processors. In an experimental performance comparison, we identify the advantages and disadvantages of several variants of our algorithm. The most efficient one shows an almost optimal speed up under the assumption that the number of disks is sufficiently large.

Spatial joins are one of the most important operations for combining spatial objects of several relations. In this paper, spatial join processing is studied in detail for extended spatial objects in two-dimensional data space. We present an approach for spatial join processing that is based on three steps. First, a spatial join is performed on the minimum bounding rectangles of the objects returning a set of candidates. Various approaches for accelerating this step of join processing have been examined at the last year's conference [BKS 93a]. In this paper, we focus on the problem how to compute the answers from the set of candidate which is handled by the following two steps. First of all, sophisticated approximations are used to identify answers as well as to filter out false hits from the set of candidates. For this purpose, we investigate various types of conservative and progressive approximations. In the last step, the exact geometry of the remaining candidates has to be tested against the join predicate. The time required for computing spatial join predicates can essentially be reduced when objects are adequately organized in main memory. In our approach, objects are first decomposed into simple components which are exclusively organized by a main-memory resident spatial data structure. Overall, we present a complete approach of spatial join processing on complex spatial objects. The performance of the individual steps of our approach is evaluated with data sets from real cartographic applications. The results show that our approach reduces the total execution time of the spatial join by factors.

Abstract: In this paper, we show that spatial joins are very suitable to be processed on a parallel hardware platform. The parallel system is equipped with a so-called shared virtual memory which is well-suited for the design and implementation of parallel spatial join algorithms. We start with an algorithm that consists of three phases: task creation, task assignment and parallel task execu-tion. In order to reduce CPU- and I/O-cost, the three phases are processed in a fashion that pre-serves spatial locality. Dynamic load balancing is achieved by splitting tasks into smaller ones and reassigning some of the smaller tasks to idle processors. In an experimental performance compar-ison, we identify the advantages and disadvantages of several variants of our algorithm. The most efficient one shows an almost optimal speed-up under the assumption that the number of disks is sufficiently large. Topics: spatial database systems, parallel database systems 1

we consider how to exploit multiple disks to improve the performance of B-tree structured files.Attention is paid both to the response time of individual operations and to the throughput of the system in a multi-user environment.We begin with a survey of three different approaches to designing multi-disk B-trees: distributing records among disks, using large multi-disk pages, and distributing pages among disks.For each approach, several alternatives are discussed and their main advantages and disadvantages are identified.We then propose a new scheme, based on page distribution, that is intended to provide a better local balancing of the request load than previous schemes.Preliminary performance results confirm that this irrproves both response time and throughput.

The R-tree, one of the most popular access methods for rectangles, is based on the heuristic optimization of the area of the enclosing rectangle in each inner node. By running numerous experiments in a standardized testbed under highly varying data, queries and operations, we were able to design the R*-tree which incorporates a combined optimization of area, margin and overlap of each enclosing rectangle in the directory. Using our standardized testbed in an exhaustive performance comparison, it turned out that the R*-tree clearly outperforms the existing R-tree variants. Guttman's linear and quadratic R-tree and Greene's variant of the R-tree. This superiority of the R*-tree holds for different types of queries and operations, such as map overlay, for both rectangles and multidimensional points in all experiments. From a practical point of view the R*-tree is very attractive because of the following two reasons 1 it efficiently supports point and spatial data at the same time and 2 its implementation cost is only slightly higher than that of other R-trees.

The authors consider the case of nonuniform weakly correlated or independent multidimensional record distributions. After demonstrating the advantages of multidimensional hashing schemes without directory, they suggest using piecewise linear expansions to distribute the load more evenly over the pages of the file. The resulting piecewise linear order preserving hashing scheme (PLOP-hashing) is then compared to the two-level grid file, which turned out to be the most popular scheme in practical applications.>

Previous multidimensional dynamic hashing schemes exhibit two obvious shortcomings. First, even for uniform record distribution, the retrieval performance of these schemes suffers from several disadvantages. In a recent paper we have suggested a multidimensional dynamic hashing scheme which exhibits better retrieval performance than its competitors for uniform distribution. The even more severe second disadvantage of all known multidimensional dynamic hashing schemes is the very poor performance for non-uniform record distributions. In this paper we present the quantile method as a scheme which exhibits for non-uniform distributions practically the same performance as for uniform distributions. This is underlined by experimental runs with an implementation of our scheme. In addition to its excellent performance, our scheme fulfills all the necessary requirements to be used in an engineering database system: it is dynamic, is suitable for secondary storage devices, supports point data and spatial data objects and supports spatial clustering (proximity queries).