# A new type of cyclotron resonance from charge-impurity scattering in the
bulk-insulating Bi2Se3 thin films

Xingyue Han  Department of Physics and Astronomy, University of Pennsylvania,
Philadelphia, PA 19104 USA.  Maryam Salehi  Department of Material Science and
Engineering, Rutgers the State University of New Jersey, Piscataway, NJ 08854
USA.  Seongshik Oh  Department of Physics and Astronomy, Rutgers the State
University of New Jersey, Piscataway, NJ 08854 USA.  Liang Wu
<EMAIL_ADDRESS>Department of Physics and Astronomy, University of
Pennsylvania, Philadelphia, PA 19104 USA.

###### Abstract

This work focuses on the low frequency Drude response of bulk-insulating
topological insulator Bi2Se3 films. The frequency and field dependence of the
mobility and carrier density are measured simultaneously via time-domain
terahertz spectroscopy. These films are grown on buffer layers, capped by Se,
and have been exposed in air for months. Under a magnetic field up to 7 Tesla,
we observe prominent cyclotron resonances (CRs). We attribute the sharp CR to
two different topological surface states (TSSs) from both surfaces of the
films. The CR sharpens at high fields due to an electron-impurity scattering.
By using magneto-terahertz spectroscopy, we confirm that these films are bulk-
insulating, which paves the way to use intrinsic topological insulators
without bulk carriers for applications including topological spintronics and
quantum computing.

Introduction

Ordered states of matter are usually characterized by Landau’s spontaneous
symmetry breaking theory. For example, ferromagnets break continuous rotation
symmetry and superconductors break gauge symmetry. The newly discovered
topological materials are classified by the topological properties of their
bulk wavefunction. For example,the three-dimensional topological insulators
(TIs) possess insulating bulk states and conducting surface states. Hasan and
Kane (2010); Qi and Zhang (2011) . Intrinsic bulk-insulating TIs are the ideal
platforms for low-dissipation spintronics and quantum computing due to the
spin-momentum locking on the topological surface states (TSSs) Hasan and Kane
(2010); Qi and Zhang (2011). However, most TI materials are slightly doped and
thus have a conducting bulk, which is the major obstacle to reach the ideal TI
state. To solve the problem, many attempts are made to tune the chemical
potential towards the Dirac point. It was a success in graphene to probe many-
body interactions with plasmons and phonons Basov et al. (2014), and in Cu
doped Bi2Se3 with dominating electron-phonon couplingWu et al. (2015). More
advancements in TIs are still lacking .

Bi2Se3 is a typical 3D TI with a single Dirac cone on the surface. However,
native grown Bi2Se3 is known with a conducting bulk from defects. One way to
suppress the bulk carrier density is the chemical doping method Ren et al.
(2010); Xiong et al. (2012). However, the bulk carrier densities in these
samples are still not negligible and the impurity states are pinned close to
the chemical potential. The other way to suppress the bulk carriers is to grow
Bi2Se3 on a buffer layer Koirala et al. (2015); Wu et al. (2016). An open
question remains on how to keep the sample bulk-insulating after exposure in
air. In this work, we investigate Bi2Se3 thin films grown on a buffer layer
with Se capping. The TSSs are decoupled via time-domain terahertz spectroscopy
with a magnetic field up to 7 tesla.

Cyclotron resonance (CR) measurements have been shown very useful to study the
Dirac fermions and many-body interactions Crassee et al. (2010); Jiang et al.
(2007a); Jenkins et al. (2013). It is also one of the most precise method to
determine the carrier effective mass Kono and Miura (2006). In previous work,
Bi2Se3 films with conducting bulk showed a large Kerr rotation without obvious
resonance Valdés Aguilar et al. (2012). In a later report, CR emerges in
In2Se3 capped Bi2Se3 films Jenkins et al. (2013) due to the destroyed non-
TI/TI interface from Indium diffusionLee et al. (2014). This is because a
phase transition from topological to trivial insulator occurs at a low Indium
concentration ($\sim 6\%$) Wu et al. (2013). Besides, Cu doped Bi2Se3 films
also presents CR, where the bulk-insulating state is reached and the electron-
phonon coupling was revealed Wu et al. (2015).

Figure 1: (Color online) (a) Real and (b) Imaginary conductance of 32QL and
16QL Bi2Se3 grown on BIS-BL at 5K.  Figure 2: (a)Real part and (b) Imaginary
part of complex Faraday rotation for 32QL Bi2Se3 grown on BIS-BL layer.
(c)Real part and (d) Imaginary part of complex Faraday rotation for 32QL
Bi2Se3.

Results and Discussion

Here we report time-domain THz spectroscopy measurement on Bi2Se3 thin films
with 100 nm Se capping layer and (Bi1-xInx)2Se3 buffer layer (BIS-BL) Koirala
et al. (2015). These films have been exposed in air for 6 months. By using
cyclotron resonance measurement, we confirm that these films are still bulk-
insulating. We attribute the conducting channels to two different topological
surface states (TSSs) on the top and bottom of the films. By using magneto-
terahertz spectroscopy, we observe that the cyclotron resonance sharpens at
higher magnetic field, which reveal with long-range electron impurity
scattering on the surfaces.

Figure 3: (a) A representative fit quality for 1 Drude fit (dashed line) and 2
Drude fit (solid line) and a calculation by using zero-field scattering rate
(0TSC) of 32QL sample. (b) Cyclotron frequency VS field from 1 Drude fit.
Solid line is linear fit. Drude scattering rate VS field from (c)1 Drude fit
(d) 2 Drude fit

.

Fig.1(a)(b) shows the real and imaginary conductance for 32QL and 16QL Bi2Se3
grown on BIS-BL at 5 K. The spectral weight is lower compared with the normal
Bi2Se3 directly grown on sapphire or Si Valdés Aguilar et al. (2012), even
lower than the bulk-insulating Cu0.02Bi2Se3 Wu et al. (2015). This indicates
the bulk insulating behavior of the samples. The spectra can be fitted by the
sum of (i) two Drude terms describing free electron-like motions from top and
bottom surfaces respectively, (ii) a Drude-Lorentz term describing phonon
oscillations, and (iii) a constant term counting for the background above the
measured spectral range, as shown below.

$G(\omega)=\epsilon_{0}d\left(\sum_{i=1}^{2}-\frac{\omega^{2}_{pDi}}{i\omega-\Gamma_{Di}}-\frac{i\omega\omega^{2}_{pDL}}{\omega^{2}_{DL}-\omega^{2}-i\omega\Gamma_{DL}}-i\left(\epsilon_{\infty}-1\right)\omega\right)$
(1)

Here $\Gamma_{Di}$ and $\omega_{pDi}$ are the scattering rates and plasma
frequencies of the $i$-th Drude term. $\Gamma_{DL}$ and $\omega_{pDL}$ are the
scattering rate and plasma frequency of the Drude-Lorentz term. $d$ is the
film thickness. $\epsilon_{\infty}$ is a constant named lattice
polarizability. In the real part of the conductance $G_{D1}$, the total
spectral weight ($\omega_{pD}^{2}d$) can be extracted from the integral of
each feature with a coefficient $\frac{\pi\epsilon_{0}}{2}$. This gives the
ratio of the carrier density and the effective transport mass.

$\frac{2}{\pi\epsilon_{0}}\int
G_{D1}d\omega=\sum_{i=1}^{2}\omega_{pDi}^{2}d=\sum_{i=1}^{2}\frac{n_{2Di}e^{2}}{m_{i}^{*}\epsilon_{0}}$
(2)

In the second equality, $n_{2Di}$ and $m^{*}_{i}$ are the carrier densities
and the effective transport masses of the massless Dirac fermion. $m^{*}$ is
defined as $m^{*}=\hbar k_{F}/v_{F}.$ Consider a quadratic dispersion model
for the TSS, $E=Ak_{F}+Bk_{F}^{2}$, the coefficients $A$ and $B$ can be
obtained from photo-emission Wu et al. (2015). Then the last term in Eq.2 can
be expressed by $k_{F}$ only. For one surface state, the relation between
spectral weight and $k_{F}$ is as following. Note that the right side of
following expression is half of the value in the Bi2Se3 when we assume two
nominally same TSSs were observed in Bi2Se3.

$\omega_{pDi}^{2}d=\frac{k_{F}(A+2Bk_{F})e^{2}}{4\pi\hbar^{2}\epsilon_{0}}$
(3)

At first, a single conduction channel originated from two identical TSSs is
assumed. Using Eq.2 and 3, the $n_{2D}$ and m∗ can be determined. The fitting
results of the 32QL sample gives a total sheet carrier density $n_{2D}$ $\sim$
4.8 $\times$1012/cm2, effective transport mass $m^{*}\sim$ 0.135 ($\pm$0.005)
$m_{e}$, Fermi energy E${}_{F}\sim$ 140 ($\pm$10) meV, and phonon frequency
$\omega_{ph}\sim 1.92$ THz. 16QL sample has lower spectral weight than 32QL
sample. The same analysis gives a total sheet carrier density $n_{2D}$ $\sim$
3.8 $\times$1012/cm2, $m^{*}\sim$ 0.12 ($\pm$0.005) $m_{e}$, E${}_{F}\sim$ 120
($\pm$8) meV and phonon frequency $\omega_{ph}\sim 1.95$ THz. The estimation
of the chemical potential is consistent with an insulating bulk even after
exposure in air for 6 months Koirala et al. (2015).

We performed Faraday rotation measurements on these samples to measure the
cyclotron resonance mass and spectral weight. Data are shown in
Fig.2(a)(b)(c)(d). Similar to Cu0.02Bi2Se3, cyclotron resonates are observed
in both 32QL and 16QL samples. We use the following model to fit the
conductance spectra under an external magnetic field. Here we assume two equal
contribution from top and bottom surface states:

$G_{\pm}=-i\epsilon_{0}\omega
d\left(\sum_{i=1}^{2}\frac{\omega^{2}_{pDi}}{-\omega^{2}-i\Gamma_{Di}\omega\mp\omega_{c}\omega}+\frac{\omega^{2}_{pDL}}{\omega^{2}_{DL}-\omega^{2}-i\omega\Gamma_{DL}}+\left(\epsilon_{\infty}-1\right)\right)$
(4)

Here the $\pm$ sign corresponds to the right/left-hand circularly polarized
light, respectively. $\omega_{c}$ is the CR frequency. The Faraday rotation
can be expressed by $\mathrm{tan}(\theta_{F})=-i(t_{+}-t_{-})/(t_{+}+t_{-})$.
Here we let $\omega_{c}$ and $\Gamma_{D}$ vary with field. We find that the
fit result is not good as shown in Fig. 3(a). Let us further address the 1
Drude model analysis. As we can see in Fig.3(a), the fit quality of 1 Drude
term is not as good as Cu0.02Bi2Se3 case. Bi2Se3 is grown (Bi1-xInx)2Se3 and
$\leq$ 0.2$\%$ In is diffused into the bottom Bi2Se3 few layers. Even though
0.2$\%$ is far below the topological phase transition thresholdWu et al.
(2013), it is natural to treat top surface states (tSS) and bottom surface
states (bSS) differently. We remove the equal contribution from both surface
states and treat them separately as equation 4. The fit quality improve
significantly as shown in Fig.3(a). We can also see two Drude terms fit zero-
field conductance better in Fig.1. Then we can extract carrier density of each
surface state by the relation
$\omega_{pDi}^{2}d=\frac{n_{2Di}e^{2}}{m_{i}^{*}\epsilon_{0}}$. The parameters
for 2 Drude fits are showed in table1. Indium causes more scattering and
therefore the channel with larger scattering rate is identified as bottom
surface state. As shown in previous works, the bottom surface has more
defects, which lead to higher carrier density Valdés Aguilar et al. (2012);
Koirala et al. (2015). Therefore, the large scattering rate and the large
carrier density are consistent with each other for the bottom surface. We also
performed Faraday rotation measurements on bare buffer layer and no rotation
angle is observed. So the cyclotron resonance feature comes from the Bi2Se3
sample only.

|  n2D (1012/cm2) |  m∗ (me) |  $\Gamma$(7T) (THz) |  $\mu$(7T) (cm2/Vs)
---|---|---|---|---
tSS 32QL |  2.2 |  0.13 |  0.24 |  8980
bSS 32QL |  2.7 |  0.14 |  0.55 |  3640
tSS 16QL |  1.3 |  0.11 |  0.29 |  8780
bSS 16QL |  2.0 |  0.12 |  0.43 |  5420
Table 1: Fit parameters for two-Drude fit

Now let us address the decreasing scattering rate VS field as shown in Fig.
3(c-d). Short-range charge impurity scattering rate leads to $\sqrt{B}$
increasing scattering rate, as predicted and observed in grapheneShon and Ando
(1998); Orlita et al. (2008); Jiang et al. (2007b). Electron-phonon scattering
rate causes broadening of cyclotron resonance and saturation of scattering
rate above phonon energyWu et al. (2015). Long-range charge impurity
scattering rate leads to decreasing scattering rate VS fieldYang et al.
(2010). It was not the dominant mechanism in graphene and therefore was never
observed. Similar trend were reported in InSe quantum well and was interpreted
as scattering over Gaussian potential larger or equal to the cyclotron
orbitKress-Rogers et al. (1983). The saturation of scattering rate above 4T in
Fig. 3(c-d) is due to electron-phonon scattering as cyclotron frequency
reaches $\sim$ 0.7 THz at 4 T in both samples which corresponds to either Kohn
anomaly of surface $\beta$ phonon or highest acoustic phonon frequencyWu et
al. (2015). In the two-Drude fit, one channel has stronger field dependence
and is identified as bottom surface state. The reason is charge impurities
most likely are created on the bottom surface state due to charge
imhomogenity. Top surface state has less effect due to screening. This kind of
long-range charge impurity scattering was further corroborated by the fact no
Shubnikov de-Has (SdH) oscillation was observed on these sample while CR is
very robustKoirala et al. (2015). SdH is limited by quantum life-time which is
sensitive to both small-angle and large-angle scatting while CR is sensitive
to transport life-time which is limited by back scattering. The low quantum
life-time in these samples indicates significant small-angle scattering rate
coming from long-range coulomb potential. Similar trend was observed in 2DEG
systemGaska et al. (1998) and theoretically investigated in literatureAdam et
al. (2012).

To conclude, we observe sharp cyclotron resonance in bulk-insulating Bi2Se3
thin films. The field dependence reveals a decreasing of the scattering rate
with increasing magnetic fields. We attribute the origin to impurity
scattering due to the buffer layer. This work shows that cyclotron resonance
is a powerful tool to study many-body interactions in topological materials.
On the practical side, this work establishes that a 100 nm thick Se capping
layer is simple, but very useful for keeping the topological insulator thin
films bulk-insulating. The evidence for the long-range impurity scattering at
the bottom interface due to buffer layers shreds light on film growth to
further decreases the carrier concentration and enhances mobility for future
low-dissipation spintronic devices.

Acknowledgement

This project is supported from the ARO under the Grant W911NF2020166. The
development of the THz polarity is supported by the ARO YIP award under the
Grant W911NF1910342. The acquisition of the laser for the THz system is
support from a seed grant at National Science Foundation supported University
of Pennsylvania Materials Research Science and Engineering Center
(MRSEC)(DMR-1720530). X.H. is also partially supported by the Gordon and Betty
Moore Foundation’s EPiQS Initiative, Grant GBMF9212 to L.W . L.W. also
acknowledges partial summer support from the NSF EArly-concept Grants for
Exploratory Research (EAGER) grant (Grant No. DMR2132591).

Data Availability Statement

The data that support the findings of this study are all present in this
paper. Further data are available from the corresponding author upon
reasonable request.

## References

  * Hasan and Kane (2010) M. Z. Hasan and C. L. Kane, Rev. Mod. Phys. 82, 3045 (2010).
  * Qi and Zhang (2011) X.-L. Qi and S.-C. Zhang, Rev. Mod. Phys. 83, 1057 (2011).
  * Basov et al. (2014) D. Basov, M. Fogler, A. Lanzara, F. Wang, and Y. Zhang, Reviews of Modern Physics 86, 959 (2014).
  * Wu et al. (2015) L. Wu, W.-K. Tse, M. Brahlek, C. M. Morris, R. V. Aguilar, N. Koirala, S. Oh, and N. P. Armitage, Physical Review Letters 115, 217602 (2015).
  * Ren et al. (2010) Z. Ren, A. A. Taskin, S. Sasaki, K. Segawa, and Y. Ando, Phys. Rev. B 82, 241306 (2010).
  * Xiong et al. (2012) J. Xiong, A. Petersen, D. Qu, Y. Hor, R. Cava, and N. Ong, Physica E 44, 917 (2012).
  * Koirala et al. (2015) N. Koirala, M. Brahlek, M. Salehi, L. Wu, J. Dai, J. Waugh, T. Nummy, M.-G. Han, J. Moon, Y. Zhu, et al., Nano Letters 15, 8245 (2015).
  * Wu et al. (2016) L. Wu, M. Salehi, N. Koirala, J. Moon, S. Oh, and N. Armitage, Science 354, 1124 (2016).
  * Crassee et al. (2010) I. Crassee, J. Levallois, A. Walter, M. Ostler, A. Bostwick, E. Rotenberg, T. Seyller, D. Van Der Marel, and A. Kuzmenko, Nature Physics 7, 48 (2010).
  * Jiang et al. (2007a) Z. Jiang, E. Henriksen, L. Tung, Y.-J. Wang, M. Schwartz, M. Han, P. Kim, and H. Stormer, Phys. Rev. Lett. 98, 197403 (2007a).
  * Jenkins et al. (2013) G. S. Jenkins, D. C. Schmadel, A. B. Sushkov, H. D. Drew, M. Bichler, G. Koblmueller, M. Brahlek, N. Bansal, and S. Oh, Phys. Rev. B 87, 155126 (2013).
  * Kono and Miura (2006) J. Kono and N. Miura, High Magnetic Fields: Science and Technology, Volume III, World Scientific, Singapore (2006).
  * Valdés Aguilar et al. (2012) R. Valdés Aguilar, A. V. Stier, W. Liu, L. S. Bilbro, D. K. George, N. Bansal, L. Wu, J. Cerne, A. G. Markelz, S. Oh, et al., Phys. Rev. Lett. 108, 087403 (2012).
  * Lee et al. (2014) H. Lee, C. Xu, S. Shubeita, M. Brahlek, N. Koirala, S. Oh, and T. Gustafsson, Thin Solid Films 556, 322 (2014).
  * Wu et al. (2013) L. Wu, M. Brahlek, R. V. Aguilar, A. V. Stier, C. M. Morris, Y. Lubashevsky, L. S. Bilbro, N. Bansal, S. Oh, and N. P. Armitage, Nature Physics 9, 410 (2013).
  * Shon and Ando (1998) N. H. Shon and T. Ando, Journal of the Physical Society of Japan 67, 2421 (1998).
  * Orlita et al. (2008) M. Orlita, C. Faugeras, P. Plochocka, P. Neugebauer, G. Martinez, D. K. Maude, A.-L. Barra, M. Sprinkle, C. Berger, W. A. De Heer, et al., Physical review letters 101, 267601 (2008).
  * Jiang et al. (2007b) Z. Jiang, E. Henriksen, L. Tung, Y.-J. Wang, M. Schwartz, M. Han, P. Kim, and H. Stormer, Physical review letters 98, 197403 (2007b).
  * Yang et al. (2010) C. Yang, F. Peeters, and W. Xu, Physical Review B 82, 075401 (2010).
  * Kress-Rogers et al. (1983) E. Kress-Rogers, R. Nicholas, and A. Chevy, Journal of Physics C: Solid State Physics 16, 2439 (1983).
  * Gaska et al. (1998) R. Gaska, J. Yang, A. Osinsky, Q. Chen, M. A. Khan, A. Orlov, G. Snider, and M. Shur, applied physics letters 72, 707 (1998).
  * Adam et al. (2012) S. Adam, E. Hwang, and S. D. Sarma, Physical Review B 85, 235413 (2012).


11institutetext: Foundation for Research and Technology, Institute of Computer
Science, Greece 22institutetext: University of Crete, Department of Computer
Science, Greece
22email<EMAIL_ADDRESS>
# Parallel and Distributed Data Series Processing on Modern and Emerging
Hardware††thanks: Supported by the Hellenic Foundation for Research and
Innovation (HFRI) under the “Second Call for HFRI Research Projects to support
Faculty Members and Researchers” (project number: 3684).

Panagiota Fatourou 1122

###### Abstract

This paper summarizes state-of-the-art results on data series processing with
the empahsis on parallel and distributed data series indexes that exploit the
computational power of modern computing platforms. The paper comprises a
summary of the tutorial the author delivered at the 15th International
Conference on Management of Digital EcoSystems (MEDES’23).

##  1 Introduction

Ordered sequences of data points, known as data series, are one of the most
common types of data. They are heavily produced by several applications in
many different domains, including finance, astrophysics, telecommunications,
environmental sciences, engineering, multimedia, neuroscience, and many others
[26, 40]). Similarity search is a fundamental building block in data series
processing, as many types of complex analytics, such as, clustering,
classification, motif and outlier detection, etc., are heavily dependent on
it. A similarity search query is also useful in itself. It searches for the
data seires in the collection that has the smallest distance to the query
series, given some distance metric (which can be e.g., Euclidean distance [2]
or Dynamic-Time Warping [35]).

As data series collections grow larger, sequential data series indexing
technologies turn out to be inadequate. For example, the state-of-the-art such
index, ADS$+$ [38], requires more than 4min to answer a single query on a
moderately sized 250GB sequence collection. Thus, ADS is inefficient in
processing the enormous sequence collections that are produced in many
domains.

We briefly present a sequence of state-of-the-art indexes that take advantage
of multiple nodes and modern hardware parallelization in each node, in order
to accelerate processing times and achieve scalability.

We focus on a specific family of indexes, namely the iSAX indexes [39, 32, 34,
33, 29, 30]. An iSAX index first computes the iSAX summary [36] of each data
series in the collection (summarization phase). Then, it builds a tree storing
all summaries (tree construction phase), and uses it to answer similarity
search queries. Given a query $q$, the similarity search algorithm first
traverses a path of the tree to find a first approximate answer to $q$. This
approximate answer is called Best-So-Far (BSF). Then, it traverses the
collection of data series to prune those whose summaries have higher distance
to $q$’s summary than the value stored in BSF. The distance between the
summaries of two data series is called lower bound distance. It has been
proved that if the lower bound distance of a series DS from q is higher than
BSF, the real distance of DS from q is also higher than BSF. Then, DS can be
pruned. Finally, the actual (real) distances between each data series that
cannot be pruned and $q$ is calculated. Whenever a real distance computation
results in a lower value than that of BSF, then BSF is updated. Eventually,
the answer to $q$ is the value stored in BSF. If the pruning degree is high, a
vast amount of expensive real distance computations are avoided. This results
in good performance.

We first discuss ParIS+ [32, 34], a disk-based concurrent index, capable to
manipulate big data series collections stored in secondary storage. We then
continue to present MESSI [28, 29], the state-of-the-art in-memory concurrent
index. Next, we discuss the challenges originating from the utilization of
Graphics Processing Units (GPUs) [30] for further improving performance during
query answering. We also discuss SING [30], an index that utilizes GPUs for
query answering to perform better than MESSI. These indexes improve
performance drastically in comparison to ADS$+$, the state-of-the-art
sequential index [38]: to answer a similarity search query on a 100GB (in
memory) data series collection, SING requires 35 msec whereas ADS$+$ requires
several tens of seconds.

Finally, we discuss Odyssey [7], a distributed data-series (DS) indexing and
processing framework, that efficiently addresses the challenges for efficient
and highly-scalable multi-node data series processing.

All the indexes that we discuss in the next sections, exploit the Single
Instruction Multiple Data (SIMD) capabilities of modern CPUs to further
parallelize the execution of individual instructions inside each core.

##  2 ParIS+

ParIS+ [32, 34] is a disk-based index that takes advantage of the
computational power of multi-core architectures in order to execute in
parallel the computations needed for both index creation and query answering.
ParIS+ makes careful design choices in the coordination of the computational
and I/O tasks, thus managing to completely hide the CPU cost during index
creation under I/O.

ParIS+ is 2.6x faster than ADS$+$ [38] in index creation, and up to 1 order of
magnitude faster in query answering. This makes ParIS+ a very efficient
solution for disk-resident data. However, its answering time to a search query
on a 100GB dataset is 15sec. This performance not only does not support
interactive analysis (i.e., 100msec) [21], but also it is above the limit for
keeping the user’s attention.

To move data from disk to main memory, ParIS+ uses a double buffering scheme.
While a coordinator thread moves data to one part of the buffer, a number of
worker threads compute the iSAX summaries for the data series stored into the
other part, and store them in a set of iSAX buffers. The use of the double
buffering scheme enables ParIS+ to hide CPU computation under I/O.

The worker threads traverse the iSAX buffers storing pairs of iSAX summaries
and the pointers to the corresponding data series, into the leaves of the
index tree. The iSAX buffers are needed to ensure some form of data locality.
All data series found in an iSAX buffer are stored in the same subtree of the
index tree. ParIS+ uses a dedicated thread to build each subtree. This
eliminates the need for costly synchronization and communication between the
threads.

During query answering, ParIS+ first calculates BSF using the index tree (and
never uses the tree again). Then, a number of threads concurrently traverse
different parts of an array, called SAX, which contains the iSAX summaries of
all data series of the collection, in order to create a list (candidate list)
of those series that are good candidates to be the query’s answer (i.e., those
whose lower bound distance is smaller than BSF and cannot be pruned). Finally,
a number of threads perform in parallel, using SIMD, the real-distance
computations needed to find the closest data series to the query, among the
candidate series.

##  3 MESSI

The second index, called MESSI [28, 29], provides an efficient indexing and
query answering scheme for _in-memory_ data series processing. Fast in-memory
data series computations often appear in real scenaria [27, 9]. For instance,
Airbus stores petabytes of data series, reasoning about the behavior of
aircraft components or pilots [23], but requires experts to run analytics only
on subsets of the data (e.g., on those relevant to landings from Air France
pilots) that fit in memory. MESSI features a novel solution for answering
similarity search queries which is 6-11x faster than an in-memory version of
ParIS+, achieving for the first time interactive exact query answering times,
at $\sim$60msec. It also provides redesigned algorithms that lead to a further
$\sim$4x speedup in index construction time, in comparison to (in-memory)
ParIS+.

The design decisions in ParIS+ were heavily influenced by the fact that its
performance cost was mostly I/O bounded. Since MESSI copes with in-memory data
series, no CPU cost can be hidden under I/O. Therefore, MESSI required more
careful design choices and coordination of the parallel workers. This led to
the development of a more subtle design for the index construction and new
algorithms for answering similarity search queries on this index.

For query answering, in particular, the MESSI paper shows that an in memory
version of ParIS+ is far from being optimal. Thus, MESSI proposes new
solutions to achieve a good balance between the amount of communication among
the parallel worker threads, and the effectiveness of each individual worker.

MESSI uses concurrent priority queues for storing the data series that cannot
be pruned, and for processing them in order, starting from those that have the
smallest lower bound distance to the query series. In this way, the worker
threads achieve a better degree of pruning. Moreover, MESSI assigns an iSAX
summary to each node of the index tree. Then, it traverses the tree to decide
which data series cannot be pruned based on these iSAX summaries. If the lower
bound distance of a node from the query series is lower than BSF, the entire
subtree rooted at the node can be pruned. In this way, the number of lower
bound distance calculations performed is significantly reduced. To achieve
load balancing, MESSI ensures that all priority queues have about the same
number of elements, and workers use randomization to choose the priority
queues they will work on.

##  4 SING

Although ParIS+ [32, 34] and MESSI [33, 29] exhibit advanced performance by
exploiting the parallelism opportunities offered by the multi-core and SIMD
architectures, they ignore the computational power of Graphics Processing
Units (GPUs). SING [31] is the first (in-memory) data series indexing scheme
that combines the GPU’s parallelization opportunities with those of multi-core
architectures (and SIMD), to further accelerate exact similarity search. SING
outperforms MESSI in a variety of settings, reducing the MESSI cost for query
answering to (almost) half.

Data series processing with GPUs is challenging for several reasons. First,
the GPU memory is rather limited, so storing the entire raw data set in it is
impossible. Moreover, the slow interconnect speeds disallows processing raw
data in the GPU memory, as moving even small subsets of such data (i.e., those
data series that are not pruned) in the GPU memory incurs a prohibitively high
cost. Last, GPUs employ non-sophisticated cores, which are not readily suited
to processing tree indexes and algorithms on top of them that frequently
involve branching. These considerations imply that it is just (parts of) the
query answering computation that can be performed efficiently in the GPU.
Furthermore, the SING paper provides experimental evidence that simple GPU
adaptations of the techniques employed by previously-presented tree-based
indices for implementing those parts cannot outperform state-of-the-art
solutions, such as MESSI.

To address these challenges, SING provides a new similarity search algorithm
that runs on top of the tree structure created by MESSI. The algorithm ensures
the efficient collaboration of both the CPU and GPU cores to answer queries.
The main ideas on which it is based are the following. SING stores in the GPU
memory, an array of (just) the iSAX summaries of the data series in the
collection. This array is sorted in the order the data series appear in the
leaves of the index tree. SING performs an inital pruning phase to prune
entire root subtrees, thus reducing the number of lower bound distance
computations that the GPU executes. Moreover, it employs a simple polynomial
function to compute lower bound distances. This enables the computation of
lower bound distances in their entirety within the GPU. SING employs streaming
to effectively synchronize the parallel execution of CPU and GPU threads.

##  5 Odyssey

The data series indexes discussed in the previous sections, operate on a
single node. Thus, they do not take advantage of the full computational power
of modern distributed systems comprised of multiple multi-core nodes. Odyssey
[7] is a state-of-the-art distributed data-series processing framework, which
ensures good speedup and high scalability, thus addressing two major
challenges of distributed data series indexing. An ideal distributed data
series index should achieve linear speedup or be able to process data
collections whose size is proportional to the number of nodes in the system.
Experiments show [7] that Odyssey does not notably depart from this ideal
behavior.

Odyssey provides a collection of scheduling schemes for query batches, which
result in good performance under several different workloads. These schemes
are based on predicting the execution time of each query. Odyssey provides a
query analysis that shows correlation between the total execution time of a
query and its initial best-so-far value. This analysis enables the calculation
of the predictions.

Odyssey achieves a good degree of load-balancing among the nodes even in
settings where the execution time predictions are not accurate. Odyssey’s load
balancing algorithm illustrates how to efficiently implement the work-stealing
approach [1, 3, 5, 6, 14, 19, 20] in distributed data series indexing
settings. In the work-stealing approach, nodes sitting idle may steal work
from busy nodes. The difficulty here is how to achieve this without ever
moving any data around, as moving data between nodes would be prohibitively
expensive. In Odyssey, this is esured by employing a (partial) replication
scheme, which is flexible enough to allow Odyssey to navigate through a
fundamental trade-off between data scalability, and good performance during
query answering. Specifically, no data replication would minimize space
overhead, but it would dissallow a cheap load-balancing solution, thus
resulting in higher execution times for answering queries. In Odyssey, a user
may choose the replication degree that is the most relevant to its application
based on its scalability and performance needs.

Odyssey is the first data series index that supports parallelization outside
the boundaries of a single node, without sacrificing the good performance of
state-of-the-art indexes [33, 29, 30] within a node. This was not a trivial
task, as experiments show that simple solutions of using as many instances of
a state-of-the-art data series index as the number of nodes would not result
in good performance, mainly due to severe load balancing problems. Supporting
work-stealing on top of a state-of-the-art index would require moving data
around. Odyssey single-node indexing algorithm borrows techniques from MESSI
[33, 29], but it also provides new mechanisms to allow a node $v$ to rebuild
parts of the index tree of another node $v^{\prime}$ needed for executing the
load that $v$ steals from $v^{\prime}$. This requires the utilization of a
different pattern of parallelism in traversing the index tree to produce the
set of data series that cannot be pruned, and new implementations for
populating and processing the data structures needed for efficient query
answering.

Experiments show that Odyssey’s index creation exhibits perfect scalability as
both the dataset size and the number of nodes increase. Moreover, Odyssey
exhibits up to 6.6x times faster exact query answering times than other state
of the art parallel or distributed data series indexes.

##  6 Discussion

We discussed state-of-the-art parallel and distributed indexes for answering
similarity search queries on big collections of data series in a fast and
scalable way. We started with concurrency techniques for disk-based indexes.
We continued with efficient parallelization techniques for indexes built to
work on in-memory data. We also focused on techniques for data series
processing that utilize GPUs to further speed up computation. Finally, we
touched upon the main challenges that are introduced when moving from a single
multi-core node to a distributed system with many multi-core nodes, and
summarized state-of-the-art techniques for addressing these challenges.

We focused on solving the problem of exact similarity search on big
collections of fixed-length data series. Exact similarity search is a core
operation needed in many critical data analytics tasks (including outlier
detection, frequent pattern mining, clustering, classification, and others)
[27]. An interesting open problem is whether the discussed techniques can be
easily extended to efficiently support other types of similarity search
queries, such as approximate search, without or with (deterministic or
probabilistic) guarantees [11]. Also, it is interesting to study how these
parallelization techniques can be extended to indexes that handle data series
of variable length [25].

Concurrent iSAX indexes are locality-aware. They maintain some form of data
locality, and achieve high parallelism with low synchronization cost by having
threads working, independently, on different parts of the data as much as
possible, to avoid the need of frequent communication between threads.
However, they all employ locks, thus, they are blocking. If a thread holding a
lock becomes slow (or crashes), the entire index blocks without being able to
make any further progress. Lock-freedom [24] is a widely-studied property when
designing concurrent trees [4, 12, 13, 18] and other data structures [16, 22,
24]. It avoids the use of locks, ensuring that the system, as a whole, makes
progress, independently of delays (or failures) of threads. A recent study
[17] presented the first lock-free iSAX index, FreSh, together with Refresh, a
generic approach that can be applied on top of any iSAX index to provide lock-
freedom without adding any performance cost. An interesting open problem is to
study the fundamental performance properties that govern other families of
data series indexes, and come up with generic schemes for achieving locality-
aware, lock-free synchronization on top of them.

The tree employed by an iSAX index has big root fan-out and its root subtrees
are leaf-oriented binary trees. This type of trees support locality-aware
parallelization, using locks, in a relatively easy way. Experimental work [10]
has shown that no single indexing method is an overall winner in exact query
answering. For this reason, recent indexing schemes [8] incorporate key ideas
from more than one data series indexing families with the goal of exhibiting
the combined performance power of the different incorporated approaches. It
would be interesting to see what kind of parallelization techniques would be
suitable to types of indexes that are not in the iSAX family [37], or for
indexes that follow combined approaches [8].

Next generation computer systems will utilize emerging memory technologies,
such as Non-Volatile Memory (NVM), to address the high computation demands of
modern applications and provide persistence [4, 15]. The availability of non-
volatile memory has increased the interest in the crash-recovery model, in
which failed threads may be resurrected after the system crashes. Developing a
recoverable data series index that will exploit the NVM performance benefits
and offer recoverability, distilling the best from both approaches, disk-based
[34] and in-memory [28] data series indices, is an interesting open problem.

###  6.0.1 Acknowledgements

This work has been supported by the Hellenic Foundation for Research and
Innovation (HFRI) under the “Second Call for HFRI Research Projects to support
Faculty Members and Researchers” (project number: 3684).

## References

  * [1] Cilk: An efficient multithreaded runtime system. Journal of Parallel and Distributed Computing 37(1), 55–69 (1996)
  * [2] Agrawal, R., Faloutsos, C., Swami, A.N.: Efficient similarity search in sequence databases. In: FODO (1993)
  * [3] Arora, N.S., Blumofe, R.D., Plaxton, C.G.: Thread scheduling for multiprogrammed multiprocessors. In: Proceedings of the Tenth Annual ACM Symposium on Parallel Algorithms and Architectures. pp. 119–129. SPAA ’98, Association for Computing Machinery, New York, NY, USA (1998). https://doi.org/10.1145/277651.277678, https://doi.org/10.1145/277651.277678
  * [4] Attiya, H., Ben-Baruch, O., Fatourou, P., Hendler, D., Kosmas, E.: Detectable recovery of lock-free data structures. In: Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. pp. 262–277. PPoPP ’22 (2022)
  * [5] Blelloch, G.E., Gibbons, P.B., Matias, Y., Narlikar, G.J.: Space-efficient scheduling of parallelism with synchronization variables. In: Proceedings of the Ninth Annual ACM Symposium on Parallel Algorithms and Architectures. SPAA ’97, Association for Computing Machinery (1997)
  * [6] Blumofe, R.D., Leiserson, C.E.: Scheduling multithreaded computations by work stealing. J. ACM 46(5), 720–748 (sep 1999). https://doi.org/10.1145/324133.324234, https://doi.org/10.1145/324133.324234
  * [7] Chatzakis, M., Fatourou, P., Kosmas, E., Palpanas, T., Peng, B.: Odyssey: A journey in the land of distributed data series similarity search. Proc. VLDB Endow. 16(5), 1140–1153 (jan 2023). https://doi.org/10.14778/3579075.3579087, https://doi.org/10.14778/3579075.3579087
  * [8] Echihabi, K., Fatourou, P., Zoumpatianos, K., Palpanas, T., Benbrahim, H.: Hercules Against Data Series Similarity Search. PVLDB (2022)
  * [9] Echihabi, K., Zoumpatianos, K., Palpanas, T.: Big Sequence Management: on Scalability (tutorial). In: IEEE BigData (2020)
  * [10] Echihabi, K., Zoumpatianos, K., Palpanas, T., Benbrahim, H.: The lernaean hydra of data series similarity search: An experimental evaluation of the state of the art. Proc. VLDB Endow. 12(2), 112–127 (oct 2018). https://doi.org/10.14778/3282495.3282498, https://doi.org/10.14778/3282495.3282498
  * [11] Echihabi, K., Zoumpatianos, K., Palpanas, T., Benbrahim, H.: Return of the lernaean hydra: Experimental evaluation of data series approximate similarity search. Proc. VLDB Endow. 13(3), 403–420 (2019). https://doi.org/10.14778/3368289.3368303, http://www.vldb.org/pvldb/vol13/p403-echihabi.pdf
  * [12] Ellen, F., Fatourou, P., Helga, J., Ruppert, E.: The amortized complexity of non-blocking binary search trees. In: ACM Symposium on Principles of Distributed Computing, PODC ’14, Paris, France, July 15-18, 2014. pp. 332–340 (2014). https://doi.org/10.1145/2611462.2611486, https://doi.org/10.1145/2611462.2611486
  * [13] Ellen, F., Fatourou, P., Helga, J., Ruppert, E.: The amortized complexity of non-blocking binary search trees. In: Proc. 33rd ACM Symposium on Principles of Distributed Computing. pp. 332–340 (2014)
  * [14] Fatourou, P.: Low-contention depth-first scheduling of parallel computations with write-once synchronization variables. In: Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures. SPAA ’01, Association for Computing Machinery, New York, NY, USA (2001). https://doi.org/10.1145/378580.378639, https://doi.org/10.1145/378580.378639
  * [15] Fatourou, P., Kallimanis, N.D., Kosmas, E.: The performance power of software combining in persistence. In: Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. pp. 337–352. PPoPP ’22, Association for Computing Machinery, New York, NY, USA (2022). https://doi.org/10.1145/3503221.3508426, https://doi.org/10.1145/3503221.3508426
  * [16] Fatourou, P., Kallimanis, N.D., Ropars, T.: An efficient wait-free resizable hash table. In: Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures. pp. 111–120. SPAA ’18, Association for Computing Machinery, New York, NY, USA (2018). https://doi.org/10.1145/3210377.3210408, https://doi.org/10.1145/3210377.3210408
  * [17] Fatourou, P., Kosmas, E., Palpanas, T., Paterakis, G.: Fresh: A lock-free data series index. In: International Symposium on Reliable Distributed Systems (SRDS) (2023)
  * [18] Fatourou, P., Ruppert, E.: Persistent non-blocking binary search trees supporting wait-free range queries. CoRR abs/1805.04779 (2018), http://arxiv.org/abs/1805.04779
  * [19] Fatourou, P., Spirakis, P.: A new scheduling algorithm for general strict multithreaded computations. In: Jayanti, P. (ed.) Distributed Computing. pp. 297–311. Springer Berlin Heidelberg, Berlin, Heidelberg (1999)
  * [20] Fatourou, P., Spirakis, P.: Efficient scheduling of strict multithreaded computations. Theory of Computing Systems 33, 173–232 (2000)
  * [21] Fekete, J.D., Primet, R.: Progressive analytics: A computation paradigm for exploratory data analysis. CoRR (2016)
  * [22] Fraser, K.: Practical lock-freedom. Tech. Rep. 579, University of Cambridge Computer Laboratory (2004), https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-579.pdf
  * [23] Guillaume, A.: Head of Operational Intelligence Department Airbus. Personal communication. (2017)
  * [24] Herlihy, M., Shavit, N.: The art of multiprocessor programming. Morgan Kaufmann (2008)
  * [25] Linardi, M., Palpanas, T.: Scalable data series subsequence matching with ulisse. VLDBJ (2020)
  * [26] Palpanas, T.: Data series management: The road to big sequence analytics. SIGMOD Record (2015)
  * [27] Palpanas, T., Beckmann, V.: Report on the first and second interdisciplinary time series analysis workshop (ITISA). SIGREC (48(3), 2019)
  * [28] Peng, B., Fatourou, P., Palpanas, T.: MESSI: In-Memory Data Series Indexing. In: ICDE (2020)
  * [29] Peng, B., Fatourou, P., Palpanas, T.: Fast data series indexing for in-memory data. VLDB J. 30(6), 1041–1067 (2021)
  * [30] Peng, B., Fatourou, P., Palpanas, T.: SING: Sequence Indexing Using GPUs. In: Proceedings of the International Conference on Data Engineering (ICDE) (2021)
  * [31] Peng, B., Fatourou, P., Palpanas, T.: SING: sequence indexing using gpus. In: 37th IEEE International Conference on Data Engineering, ICDE 2021, Chania, Greece, April 19-22, 2021. pp. 1883–1888. IEEE (2021). https://doi.org/10.1109/ICDE51399.2021.00171, https://doi.org/10.1109/ICDE51399.2021.00171
  * [32] Peng, B., Palpanas, T., Fatourou, P.: Paris: The next destination for series indexing and query answering. IEEE BigData (2018)
  * [33] Peng, B., Palpanas, T., Fatourou, P.: Messi: In-memory data series indexing. In: ICDE (2020)
  * [34] Peng, B., Palpanas, T., Fatourou, P.: Paris+: Data series indexing on multi-core architectures. TKDE (2020)
  * [35] Rakthanmanon, T., Campana, B.J.L., Mueen, A., Batista, G.E.A.P.A., Westover, M.B., Zhu, Q., Zakaria, J., Keogh, E.J.: Searching and mining trillions of time series subsequences under dynamic time warping. In: SIGKDD (2012)
  * [36] Shieh, J., Keogh, E.: Isax: Indexing and mining terabyte sized time series (2008). https://doi.org/10.1145/1401890.1401966, https://doi.org/10.1145/1401890.1401966
  * [37] Wang, Y., Wang, P., Pei, J., Wang, W., Huang, S.: A data-adaptive and dynamic segmentation index for whole matching on time series. Proc. VLDB Endow. 6(10), 793–804 (aug 2013). https://doi.org/10.14778/2536206.2536208, https://doi.org/10.14778/2536206.2536208
  * [38] Zoumpatianos, K., Idreos, S., Palpanas, T.: Ads: the adaptive data series index. VLDB J. (2016)
  * [39] Zoumpatianos, K., Idreos, S., Palpanas, T.: ADS: the adaptive data series index. VLDB J. (2016)
  * [40] Zoumpatianos, K., Palpanas, T.: Data series management: Fulfilling the need for big sequence analytics. In: ICDE (2018)