  Data series indexes are necessary for managing and analyzing the increasing
amounts of data series collections that are nowadays available. These indexes
support both exact and approximate similarity search, with approximate search
providing high-quality results within milliseconds, which makes it very
attractive for certain modern applications. Reducing the pre-processing (i.e.,
index building) time and improving the accuracy of search results are two major
challenges. DSTree and the iSAX index family are state-of-the-art solutions for
this problem. However, DSTree suffers from long index building times, while
iSAX suffers from low search accuracy. In this paper, we identify two problems
of the iSAX index family that adversely affect the overall performance. First,
we observe the presence of a proximity-compactness trade-off related to the
index structure design (i.e., the node fanout degree), significantly limiting
the efficiency and accuracy of the resulting index. Second, a skewed data
distribution will negatively affect the performance of iSAX. To overcome these
problems, we propose Dumpy, an index that employs a novel multi-ary data
structure with an adaptive node splitting algorithm and an efficient building
workflow. Furthermore, we devise Dumpy-Fuzzy as a variant of Dumpy which
further improves search accuracy by proper duplication of series. Experiments
with a variety of large, real datasets demonstrate that the Dumpy solutions
achieve considerably better efficiency, scalability and search accuracy than
its competitors. This paper was published in SIGMOD'23.
