Query Workloads for Data Series Indexes

Kostas Zoumpatianos, Yin Lou, Themis Palpanas, Johannes Gehrke

Abstract

Data series are a prevalent data type that has attracted lots of interest in recent years. Most of the research has focused on how to efficiently support similarity, or nearest neighbor queries over large data series collections, which is an important data mining task, and several data series summarization and indexing methods have been proposed in order to solve this problem. Nevertheless, up to this point very little attention has been paid to properly evaluating such index structures, with most previous work relying solely on randomly selected data series to use as queries (with/without adding noise). In this work, we show that random workloads are inherently not suitable for the task at hand and we argue that there is a need for carefully generating a query workload. We define measures that capture the characteristics of queries, and we propose a method for generating workloads with the desired properties, that is, effectively evaluating and comparing data series summarizations and indexes. In our experimental evaluation, with carefully controlled query workloads, we shed light on key factors affecting the performance of nearest neighbor search in large data series collections.


Code and data are freely available for research purposes as long as you cite:
Journal Version Plain
Kostas Zoumpatianos, Yin Lou, Ioana Ileana, Themis Palpanas, Johannes Gehrke, "Generating Data Series Query Workloads",
International Journal on Very Large Data Bases (VLDBJ), 2018
Journal Version BibTeX
@inproceedings {zlipg2018,
    author    = "Zoumpatianos, Kostas and Lou, Yin and Ileana, Ioana and Palpanas, Themis and Gehrke, Johannes",
    title     = "Generating Data Series Query Workloads",
    booktitle = "International Journal on Very Large Data Bases (VLDBJ)",
    year      = "2018"
}
Conference Version Plain
Kostas Zoumpatianos, Yin Lou, Themis Palpanas, Johannes Gehrke, "Query Workloads for Data Series Indexes",
ACM International Conference on Knowledge Discovery and Data Mining (KDD), Sydney, Australia, 2015
Conference Version BibTeX
@inproceedings {zlpg2015,
    author    = "Zoumpatianos, Kostas and Lou, Yin and Palpanas, Themis and Gehrke, Johannes",
    title     = "Query Workloads for Data Series Indexes",
    booktitle = "ACM International Conference on Knowledge Discovery and Data Mining (KDD), Sydney, Australia",
    year      = "2015"
}
Journal Paper Conference Paper