Automated Performance Test Generation and Comparison for Complex Data Structures - Exemplified on High-Dimensional Spatio-Temporal Indices

Please use this identifier to cite or link to this item:
Open Access logo originally created by the Public Library of Science (PLoS)
Title: Automated Performance Test Generation and Comparison for Complex Data Structures - Exemplified on High-Dimensional Spatio-Temporal Indices
Authors: Menninghaus, Mathias
ORCID of the author:
Thesis advisor: Prof. Dr. Elke Pulvermüller
Thesis referee: Prof. Dr. Martin Breunig
Abstract: There exist numerous approaches to index either spatio-temporal or high-dimensional data. None of them is able to efficiently index hybrid data types, thus spatio-temporal and high-dimensional data. As the best high-dimensional indexing techniques are only able to index point-data and not now-relative data and the best spatio-temporal indexing techniques suffer from the curse of dimensionality, this thesis introduces the Spatio-Temporal Pyramid Adapter (STPA). The STPA maps spatio-temporal data on points, now-values on the median of the data set and indexes them with the pyramid technique. For high-dimensional and spatio-temporal index structures no generally accepted benchmark exists. Most index structures are only evaluated by custom benchmarks and compared to a tiny set of competitors. Benchmarks may be biased as a structure may be created to perform well in a certain benchmark or a benchmark does not cover a certain speciality of the investigated structures. In this thesis, the Interface Based Performance Comparison (IBPC) technique is introduced. It automatically generates test sets with a high code coverage on the system under test (SUT) on the basis of all functions defined by a certain interface which all competitors support. Every test set is performed on every SUT and the performance results are weighted by the achieved coverage and summed up. These weighted performance results are then used to compare the structures. An implementation of the IBPC, the Performance Test Automation Framework (PTAF) is compared to a classic custom benchmark, a workload generator whose parameters are optimized by a genetic algorithm and a specific PTAF alternative which incorporates the specific behavior of the systems under test. This is done for a set of two high-dimensional spatio-temporal indices and twelve variants of the R-tree. The evaluation indicates that PTAF performs at least as good as the other approaches in terms of minimal test cases with a maximized coverage. Several case studies on PTAF demonstrate its widespread abilities.
Subject Keywords: performance tests; test case generation; benchmark generation; workload generation; indexing; access methods; high-dimensional; spatio-temporal; subway-track planning; performance comparison; algorithm engineering; performance measurement; java; software engineering
Issue Date: 23-Aug-2018
License name: Namensnennung - Weitergabe unter gleichen Bedingungen 3.0 Deutschland
License url:
Type of publication: Dissertation oder Habilitation [doctoralThesis]
Appears in Collections:FB06 - E-Dissertationen

Files in This Item:
File Description SizeFormat 
thesis_menninghaus.pdfPräsentationsformat3,2 MBAdobe PDF

This item is licensed under a Creative Commons License Creative Commons