# Spatiotemporal Data Mining: A Survey

Arun Sharma<EMAIL_ADDRESS>0002-6908-6960 University of Minnesota, Twin
CitiesMinneapolisMinnesotaUSA ,  Zhe Jiang<EMAIL_ADDRESS>University of
FloridaGainesvilleFloridaUSA and  Shashi Shekhar<EMAIL_ADDRESS>University
of Minnesota, Twin CitiesMinneapolisMinnesotaUSA

(2018)

###### Abstract.

Spatiotemporal data mining aims to discover interesting, useful but non-
trivial patterns in big spatial and spatiotemporal data. They are used in
various application domains such as public safety, ecology, epidemiology,
earth science etc. This problem is challenging because of the high societal
cost of spurious patterns and exorbitant computational cost. Recent surveys of
spatiotemporal data mining need update due to rapid growth. In addition, they
did not adequately survey parallel techniques for spatiotemporal data mining.
This paper provides a more up-to-date survey of spatiotemporal data mining
methods. Furthermore, it has a detailed survey of parallel formulations of
spatiotemporal data mining.

Spatial Data Mining, Trajectory Mining, Time Geography

††copyright: acmcopyright††journalyear: 2018††doi:
10.1145/1122445.1122456††journal: JACM††journalvolume: 37††journalnumber:
4††article: 1††publicationmonth: 8††ccs: Information Systems Spatiotemporal
Data Mining, Spatial Data Mining††ccs: Computing Methodologies Parallel
Computing

##  1\. Introduction

Spatiotemporal data mining is the process of discovering novel, non-trivial
but potentially useful patterns in large scale spatiotemporal data.
Spatiotemporal (ST) data include georeferenced climate variables, epidemic
outbreaks, crime events, social media, traffic, transportation dynamics, etc.
Analyzing and mining such data is of great importance for advancing the state-
of-the-art in many scientific problems and real-world applications due to its
interdisciplinary nature. Hence, ST data are used prominently in various
domains such as public safety, ecology, epidemiology, etc.

Figure 1. The Process of Spatiotemporal Data Mining (Best in color)

Figure 1 shows the overall process of spatiotemporal data mining. After
preprocessing to remove noise, errors, etc., the input data undergo space-time
analysis to understand their spatiotemporal distribution. Appropriate
spatiotemporal data mining algorithms are applied to produce output patterns
that are then studied and validated by domain experts to discover novel
insights, and the data mining algorithms are refined accordingly.

Figure 2. Illustrative ST Crime Dataset and Cascading ST Pattern. (Best in
color)

An example of a spatiotemporal (ST) pattern is shown in Figure 2. The figure
depicts a cascading spatiotemporal pattern (Mohan et al., 2010) that was
output on an urban crime dataset involving several event types (bar closings,
drunk driving, assaults). Figures 2(a) -2 (c) show the instances of each event
type with their times and locations, and Figure 2 (e) shows the same event
instances altogether. The detected ST pattern suggests the interesting
hypothesis that bars at closing time are potential generators of drunk driving
and assault crimes in nearby areas. Such information can help law enforcement
agencies, public safety groups, and policymakers determine appropriate crime
mitigation action.

Mining spatiotemporal data via algorithms pose unique computing challenges.
For instance, due to large data volume, users may experience unacceptable
runtime or expending great efforts in pre-processing the data due to great
variety. Besides volume and variety, high data velocity relative to ingest
capacity is another computing challenge where user experiences frequent data
loss. For instance, the real-time processing of millions of tweets involves
real-time pre-processing and mining of certain information. COVID 19 Safegraph
data (saf, 2020) records human mobility movements every minute via nearby
information (e.g., POIs, Business Categories) across the country. This
involves real-time updates on information such as the number of visits to
different POIs resulting in massive data volume (Terabytes), which is
impossible to store and process in a local machine. In addition, the US Census
(USC, 2020) including millions of records saved in different tables and schema
spanning terabytes of data space.

Querying such data may be time-consuming, and further applying algorithms
often perform poorly in terms of computation time at a large scale on
scientific or geographic computing platforms. Such computations require a
scalable and reliable software ecosystem to solve broad research problems and
efficiently help society’s decision-makers. Hence, it is important that a
broad community of scientists and users be informed about the high
performance, scalable, and open-source software tools available today that can
facilitate spatiotemporal data analytics with parallel computation to
significantly advance domain research.

However, most of these efforts have received little attention in recent
surveys of spatial and spatiotemporal data mining research. Here we provide a
comprehensive survey of spatiotemporal data mining techniques along with a
brief description of their statistical foundations and major output pattern
families (e.g., outliers, predictions, hotspots, etc.). We also provide
current literature on recent approaches that are being widely studied in both
sequential and parallel processing environments.

Similar to Shekhar et al. (Shekhar et al., 2015), this survey starts with a
review of previous surveys, followed by a statement of our contribution
towards this survey (Section 2). Section 3 provides key terms related to
spatial and spatiotemporal data and describes their statistics foundation
along with a brief statement about the societal importance of parallel
processing in spatiotemporal data mining. Section 4 describes six main output
pattern families (i.e., spatiotemporal outliers, telecouplings, prediction,
partitioning and summarization, hotspots, and change detection) along with
their respective detection approaches in both sequential and parallel
frameworks. Some current research tools are discussed in Section 5, including
state of the art parallel tools, frameworks, and libraries, which are being
used in many applications. Section 6 concludes the chapter with a look at the
current research trends and future directions.

##  2\. Related Work and Contribution

###  2.1. Framework

A large number of literature surveys can be found on spatial and
spatiotemporal data mining. Older surveys focused on methodologies without
statistical significance tests, whereas recent works have focused on pattern
families with limited attention to parallel spatiotemporal data mining
techniques. Hence, we categorized it into two groups, one without a
statistical foundation and the other with statistical foundations, as shown in
Figure 3. The earliest of these date to the 1990s (Ester et al., 1997;
Koperski et al., 1996; Roddick and Spiliopoulou, 1999). Miller et al. (Roddick
and Spiliopoulou, 1999) later reviewed trends in spatial and spatiotemporal
data mining; like earlier surveys, none of the works covered considered
statistical significance.

Figure 3. Categorizing Spatial and Spatiotemporal Data Mining Surveys

Shekhar et al. (Shekhar et al., 2003) focused on the unique characteristics of
spatial data and offered the first in-depth review of its statistical
foundation. Zhou et al. (Zhou et al., 2014) described various techniques
involved in change detection from an interdisciplinary perspective; Aggarwal
et al. (Aggarwal, 2017) reviewed spatial and spatiotemporal outlier
techniques, and Cheng et al. (Cheng et al., 2014) talked about spatiotemporal
autocorrelation, space-time forecasting, space-time clustering and its
visualization. More comprehensive reviews by Shekhar et al. (Shekhar et al.,
2011) covered most of the pattern families but did not include any research
done in the parallel computing domain. Among recent works, Atluri et al.
(Atluri et al., 2018) give a good overview of spatiotemporal data mining that
addresses pattern families and describes the methods used in a parallel
framework to some extent. Overall, however, there is no current survey on
spatiotemporal data mining that covers prominent pattern families from both a
sequential and parallel perspective.

Contributions: This chapter makes the following contributions: (i) It surveys
major pattern families with current literature in spatiotemporal data mining
from both sequential and parallel computing perspective; (ii) It informs
researchers about the current tools, platforms, and libraries that are
available for spatiotemporal data analysis in parallel computing environments
and (iii) It summarizes recent trends and suggests future work for the
advancement of high-performance spatiotemporal data mining.

##  3\. Definitions and Societal Importance

This section provides key terms and a taxonomy of spatial and spatiotemporal
data and its attributes and relationships. It also explains why parallel
computing in ST data mining is essential for society.

Spatial and Spatiotemporal Data: Spatial data provides information related to
different instances in coordinate space and can be represented as object
models (points, lines, and polygons), field models, and spatial networks
(e.g., graphs) (Shekhar, 2007). Spatiotemporal data includes additional
temporal information and can be represented by temporal snapshot models,
temporal change models, and event or process models. In temporal snapshot
models, snapshots can be considered trajectories of lines and polygons,
including spatial layers (i.e., points or multi-points). Temporal change
models represent spatiotemporal data with incremental changes from a given
start time on a spatial layer (e.g., Brownian motion, random walk). Event
models represent events as entities that remain consistent over time, while
process models represent processes as entities that are subject to change over
time.

Spatiotemporal Data Attributes: Attributes of spatiotemporal data include
spatial and non-spatial characteristics and temporal attributes that include
snapshots of spatial objects, raster layers, spatial networks, and process
durations. Since materializing spatiotemporal relationships may result in the
loss of spatial information, spatiotemporal statistics and techniques are
preferred over traditional methods. Spatiotemporal statistics integrate
spatial and temporal statistics based on first and second-order moments (mean,
variance, co-variance) and can be further classified into descriptive and
dynamic models (Cressie and Wikle, 2015).

Societal Importance: Geo-spatial algorithms use spatial and spatiotemporal
data in polygonal or raster form. However, these algorithms are hard to
execute due to the irregular structure of the statistics’ data and complexity,
making it important to optimize computations for time-critical operations. In
turn, runtime optimization supports timely decision-making by city planners,
policymakers, federal governments, etc. For instance, real-time emergency
response is required in a pandemic (COVID-19) or a natural disaster (e.g.,
hurricane, tornado) where every second lost in the decision-making process
(e.g., rescue operation) may lead to property damage, injuries, or loss of
life (Prasad et al., 2017).

Figure 4. Most Frequently Visited Business Categories in Minnesota (Sharma et
al., 2022)

Our recent work (Sharma et al., 2021), we visually monitored human mobility
patterns every week for every Point of Interest (POI) and Business Category in
Minnesota during an early phase of the COVID-19 pandemic. Figure 4 shows the
change in weekly mobility patterns for the most frequently visited business
categories, positively correlated to several cases. This information helped
Minnesota policymakers plan how to safely reopen the state economy while
reducing the virus’s spread. In another example, Chang et al. (Chang et al.,
2021) used US Census data to study the effects of mobility among disadvantaged
racial and socioeconomic groups for more-effective and equitable policy
responses to COVID-19. However, computing such intricate mobility patterns
involves large data volumes with millions of records updated periodically in
real-time. Hence, big data processing platforms (Zaharia et al., 2012) and
hardware (e.g., graphical processing units) tools are used are needed to
perform accelerated computing and provide output in real-time for time-
critical decision making.

##  4\. Output Pattern Families

This section provides a brief description of major pattern families with
current literature surveys in non-parallel and parallel frameworks. This
section describes six major pattern families in spatiotemporal data mining and
briefly surveys the current related literature in non-parallel and parallel
environments.

###  4.1. Spatiotemporal Outliers and Anomalies

Outliers are sets of observations that appear to deviate from expected
behavior as compared to other observations, resulting in abnormal patterns
that may arouse suspicion in some cases (e.g., illegal fishing (Sharma et al.,
2020)). A spatial outlier is a spatially referenced object whose non-spatial
attribute value significantly varies from other spatially referenced objects
in the spatial neighborhood. Figure 5b shows a variogram cloud of the example
dataset shown in Figure 5a, where the locations which are near one another but
with large attribute differences might indicate a spatial outlier. For
instance, pairs (P, S) and (Q, S) in Figure 5b may be potential spatial
outlier candidates since they lie above the main group of pairs. Point S might
also be considered a spatial outlier since it is present in both the (P, S)
and (Q, S) groups. A spatiotemporal outlier that differs significantly both
spatially and temporally from its spatiotemporal neighborhood results in
instability or inconsistency of the actual data. Statistics include bi-partite
multidimensional tests (e.g., Moran scatterplot) and quantitative tests (e.g.,
scatterplots), which can also be applied to spatiotemporal data.

((a)) An Example Dataset

((b)) Variogram Cloud Scatterplot

Figure 5. Example Dataset and Variogram Cloud Scatterplot (Shekhar et al.,
2003) (Best in color).

####  4.1.1. Common Approaches

Outliers in spatial time series: Detection of spatial time series outliers is
based on visualization approaches (e.g., variograms, Moran scatterplots) and
the spatiotemporal neighborhood, which can be identified with distance
measures such as K nearest neighbors or graph connectivity (Banerjee et al.,
2003). The methods can also be extended to include non-spatial, weighted,
categorical, or local spatial outliers, etc. In the parallel computing domain,
a tile-map interface is proposed for detecting anomalous events (Shin et al.,
2017) by simultaneously processing multiple tiles using multi-threading,
providing substantial computational speedup. Another spatiotemporal outlier
detection method (Barua and Alhajj, 2007) uses a parallel wavelet transform to
process massive meteorological data on high-performance architecture.

Anomalies in Spatiotemporal Data: Outliers in spatiotemporal data such as
trajectories can be defined as anomalous patterns or anomalies. Many
sequential approaches are used in finding outliers while monitoring
trajectories (Zheng, 2015; Lee et al., 2008). Recently, Lam et al. (Lam, 2016)
proposed a neighbor search approach to detect abnormal driving patterns that
efficiently summarize and analyze their spatial and temporal patterns. A
trajectory partitioning strategy was recently proposed (Lu et al., 2017) in
the parallel domain using similarity measures and taking into account the
multi-motion characteristics of a vehicle (e.g., speed, acceleration, etc.)

###  4.2. Spatiotemporal Couplings and Tele-couplings

Spatiotemporal coupling patterns are based on instances that occur in close
spatial and temporal proximity. These patterns can be unordered (co-
occurrences), partially ordered (cascading patterns), or ordered (sequential
patterns). The finding that bar closings lead to drunk driving and assault,
shown in Figure 2, is an example of a partially ordered cascading pattern. In
addition, there is the spatiotemporal tele-coupling pattern, which identifies
a significant positive or negative correlation in a spatial time series.
Statistics include the spatiotemporal cross K function, an extension of
Ripley’s K function with multiple variables.

Discovering various spatiotemporal coupling patterns and tele-coupling is
important in applications related to ecology, environmental science, public
safety, and climate science. Recent work proposed a data-driven approach for
inferring traffic cascading patterns over a real-world dataset (Liang et al.,
2017).

####  4.2.1. Common Approaches

o-Occurrence Patterns: Spatiotemporal co-occurrence patterns are simultaneous
occurrences of two or more subsets of events in both spatial and temporal
proximity. Mixed drove co-occurrence pattern detection (Celik et al., 2006) is
one such approach used in various fields such as transportation planning,
battlefield strategy, and gaming but these patterns are computationally
expensive. Other work includes a monotonic composite interest measure (Pillai
et al., 2013). In parallel computing, asynchronous co-occurrence patterns (Yu
et al., 2015a) have been studied for flood prediction by relating
precipitation with actual precipitable water through association mining. The
framework uses a MapReduce paradigm for parallelization and scalability and
identifies spatial associations on climate data between one target location
and its corresponding asynchronous locations.

Sequence Patterns: Sequence patterns are spatiotemporal events in the form of
a “chain reaction” of subsequent ordered events. Some application domains
include epidemiology to follow disease transmission patterns between several
species. Methods proposed in (Huang et al., 2008) use a spatial sequence index
as a significance measure that interprets the K-function. Other approaches
(Zheng et al., 2011) mine uncertain sequences via probabilistic methods.
Parallel implementation of sequential pattern mining (Qiao et al., 2008) was
proposed for trajectory data by first reducing candidate trajectories,
performing data parallelism for counting support, and finally using a
MapReduce model for distributing jobs for scalability. A similar MapReduce
implementation (Liang and Wu, 2015) proposed constructing a lexicographical
sequence tree for efficiently finding frequent itemsets and then implementing
a breadth-wide support pruning strategy for scalability over trajectories.

Spatial time series and teleconnections: Teleconnections are used to identify
pairs of spatial time-series at different locations and are important in
climate science and other domains for understanding oscillations (e.g.,
pairwise correlations, spatial autocorrelation on spatial time-series).
Finding these patterns is computationally expensive due to the length of the
time-series and the need for frequent enumeration of many candidates. Other
techniques (Zhang et al., 2003; Kawale et al., 2012) use spatial
autocorrelation and statistical significance testing to reduce recurrent
computations. DStep framework (Kendall et al., 2011) was proposed for
efficient domain traversal over data-intensive analysis tasks such as
teleconnection analysis on atmospheric CO2 and climate data.

###  4.3. Spatiotemporal Prediction

Spatiotemporal predictions (Zheng, 2015) aim to learn a model that can
forecast a target variable from the given explanatory feature’s forecast-
dependent variables. This includes predicting continuous values via
spatiotemporal regression or classifying outcomes via spatiotemporal
classification. Spatiotemporal prediction allows spatiotemporal dependency
over variables (e.g., neighborhood relationship, strength between elements
etc.) at different locations.

Applications vary from remote sensing, where features include spectral bands
and dependent variables such as forest, urban, water, etc. Other applications
include regression analysis to predict global or regional climate variables,
real estate pricing, etc.

####  4.3.1. Common Approaches

Spatiotemporal Regression: More recently, deep learning has been shown to
solve complex non-linear problems. Deep learning techniques have been applied
in traffic flow prediction (Chen et al., 2018; Moosavi et al., 2019) and
duration of traffic incidents (Fu et al., 2019) by utilizing data attributes
such as traffic events, weather data, points of interest, etc. In the parallel
computing domain, a novel spatiotemporal recurrent convolutional neural
network (RCNN) is proposed (Yu et al., 2017) in transportation science where
the spatial dependencies are captured in deep CNN layers while the temporal
dynamics are learned by Long Short Term Memory units and further applied in
GPUs for accelerating the model learning procedure. A similar technique,
DeepTC, uses a ConvLSTM network (Kim et al., 2018) for forecasting accurate
tropical cyclone trajectories using a Weather Research and Forecasting Model.

Spatiotemporal Kriging: Kriging is used for interpolating unknown observations
based on prior knowledge of known trajectories. Semantic Kriging (SemK)
(Bhattacharjee et al., 2016) fetches land-use/land-cover distribution of
terrain and incorporates the existing interpolation process of climatological
pattern analysis. A parallel spatiotemporal Kriging algorithm (Zhang et al.,
2018) predicts points with increasing observations, varying acceleration
proportional to prediction points, comparing the original point, and cross-
validating with real-world temperature data with the traditional model.

###  4.4. Spatiotemporal Partitioning and Summarization:

Spatiotemporal partitioning is a method of dividing underlying space and time
and clustering a set of similar observations by partitioning the. In contrast,
a spatiotemporal summarization is a brief representation of the spatiotemporal
data associated with a spatiotemporal partition where aggregated statistics
represent each partition. An example of clustering a common sub-trajectory
from a set of trajectories T1, T2, T3, T4 (as described in (Lee et al., 2007))
is shown in Figure 6. Scan statistics include spatiotemporal point density
estimation and temporal correlation.

Figure 6. Trajectory Clustering

Spatiotemporal partitioning and summarization are important in application
domains such as public health, public safety, environmental science, and law
enforcement. For instance, partitioning vehicle accident data, which is
spatial and temporal, helps law enforcement agencies find trends and
effectively deploy their resources.

####  4.4.1. Common Approaches

Spatiotemporal Event Partitioning: Methods for partitioning spatiotemporal
events can be classified as global density-based (e.g., DBSCAN, ST-DBSCAN);
hierarchical (e.g., BIRCH (Zhang et al., 1996)), which partitions
spatiotemporal data at different hierarchical levels; and graph-based (e.g.,
CHAMELEON (Karypis et al., 1999)), which proposes a sparse k nearest neighbor
that partitions the graph into segments and later merges its fragments based
on a similarity measure. A recent work (Xie and Shekhar, 2019b) added a
statistical significance test to DBSCAN that detects statistically significant
clusters of various shapes and densities.

In parallel computing, balanced K-means (von Looz et al., 2018) applies a new
geometric based optimal partitioning algorithm, resulting in faster
convergence. A parallel implementation of k-medoids clustering (Song et al.,
2017) uses a two-phase seeding and refinement approach that provides high
accuracy and efficiency. DBSCAN and other density-based clustering methods
(Welton et al., 2013; He et al., 2011; Cordova and Moh, 2015) have been
implemented across various frameworks and hardware. Spatiotemporal graph and
hypergraph partitioning models have also been proposed on multicore
architectures over sparse matrix data (Abubaker et al., 2018).

Spatial Time-Series Partitioning: Spatial time-series partitioning divides the
space into identical regions where correlations between time-series within a
region are maximum. A filter and refine approach (Zhang et al., 2003) reduce
computationally expensive and redundant computations. In medical imaging,
Fast-GPU-PCC has been proposed on functional MRI images (Eslami and Saeed,
2018).

Trajectory Data Partitioning: A recent survey (Huang et al., 2008) categorized
trajectory partitioning methods based on time interval, the trajectory’s
shape, and semantic meaning. Another recent work (Jiang et al., 2017)
partitions trajectories based on features such as density, speed, and
direction flow. In the parallel domain, recent work (Bao et al., 2016) based
on temporal partitioning using distributed and parallel RP-DBSCAN (Song and
Lee, 2018) on Apache Spark uses a random and simultaneous partition scheme and
find density reachable relationships and finally merges into a global cluster.

###  4.5. Spatiotemporal Hotspots

Given a set of geolocated objects, spatial hotspots are areas or regions where
concentration of objects inside the region is significantly greater than
outside. The log-likelihood ratio (Log LR) provides an interest measure for
estimating the concentration of activities inside the given arbitrary shape
(e.g., circle, ring) concerning the number of activities outside the shape in
a given study area. Hence, the ratio is directly proportional to the
concentration inside the given shape or region. It is complimented by a
statistical significance test (e.g., p-value) that removes patterns that are
highly unlikely to occur and is inversely proportional to the concentration of
activities inside the region.

((a)) Legionnaire’s in New York

((b)) Circular Hotspots Output

((c)) Ring Shape Hotspot Output

Figure 7. Circular and Ring-Shape Hotspot on New York Bronx Legionnaire
Outbreak (Best in color)

Figure 7 shows a case study of a New York Bronx Legionnaire’s disease outbreak
(Eftelioglu et al., 2014) where the locations of 78 infected individuals
(circular blue) and five potential outbreak sources (rectangular red) were
hand digitized on a map (Figure 7a). Figure 7b shows a circular hotspot (in
red) output by SatScan around the Opera House Hotel with a high concentration
of geo-located infected individuals inside the circle along with their
associated Log LR values and p-values. Figure 7c shows a ring-shaped hotspot
output by a different method around the same location with a higher
concentration (Log LR 34.55) of individuals inside the ring area (green) and
better statistical significance (i.e., p-value 0.001).

Spatiotemporal hotspots are high density-based cluster patterns where the
number of objects is unexpectedly more elevated than other observations within
a specific time interval. Spatial hotspots (e.g., circular (Eftelioglu et al.,
2014), ellipsoidal (Kulldorff, 1997), linear (Tang et al., 2017)) can be
extended to spatiotemporal hotspots by adding the dimension of time. Such
hotspots are useful in application domains such as public health and
criminology.

####  4.5.1. Common Approaches

Spatiotemporal Scan Statistics: Spatiotemporal hotspots can persist or emerge
(e.g., disease outbreak) over time. Recently, Spatio-Temporal Network Kernel
Density Estimation (STNKDE) (Romano and Jiang, 2017) provides visualization
for capturing the temporal dynamics of hotspots on network space and can be
used for detecting traffic accidents. Other visualization techniques
(Lukasczyk et al., 2015) are based on the topological notion of temporal
hotspots evolution over epidemiological and crime data. Lagrangian
representation of linear hotspots is discussed over traffic data (Li et al.,
2020). Parallel spatiotemporal hotspot detection was recently implemented
using Getis-Ord G* as the scan statistic on a Spark framework (Mehta et al.,
2016) using a MapReduce paradigm. A novel normalization-based scan statistic
was recently proposed (Xie and Shekhar, 2019a) for robust spatial hotspot
detection, which can also be extended to spatiotemporal hotspots by adding the
time dimension.

###  4.6. Spatiotemporal Change

Spatiotemporal change accounts the change in footprint patterns depending on
input data representations. A change is defined as a change in statistical
distribution where the data is assumed to be a part of a certain distribution.
A spatiotemporal footprint comprises both spatial and temporal direction where
a temporal footprint can be classified as a single or set of snapshots and a
point or an interval in a long series. A set of snapshots can represent a
change in a spatial field whereas a single snapshot represents a purely
spatial change.

Other spatial footprints are raster based (local, focal, zonal) and vector
based (point(s), polygon(s), line(s), network). A focal change occurs between
a location and its spatial neighborhood while a zonal change occurs inside a
spatial zone where a transition of data attributes occurs [10]. Figure 8.
shows an example of spatial zonal change footprint of vegetation cover in
Africa and its spatial zonal change patterns with longitudinal changes
throughout the years.

((a)) Vegetation Cover, August, 1981

((b)) Spatial Zonal Change Patterns in Vegetation Cover of Africa with
Longitudinal Changes

Figure 8. Spatial Zonal Change Footprint in Africa (best in color)

####  4.6.1. Common Approaches

Spatiotemporal Change Patterns with Raster-Based Spatial Footprints: A change
in footprint can be a change in human activities, a natural disaster, climate
change, etc., that is seen while comparing a collection of pixels between two
raster snapshots. A change can also be zonal if we consider objects rather
than pixels between snapshots (Zheng, 2015). Scalable probabilistic change
detection was proposed (Hong and Vatsavai, 2016) for satellite imagery using a
parallel multicore architecture by parallelizing Gaussian and KL-Divergence
computations. Another parallel implementation uses recurrent convolutional
neural network (RNN) architecture (Mou et al., 2018) for extracting both
spectral and spatiotemporal features.

##  5\. Tools for Parallel Spatiotemporal Analysis

The following provides an overview of the tools and libraries that are
available for parallel spatiotemporal analysis, using both CPU and GPU
resources as well as big data platforms such as Apache Spark.

GIS Software: ArcGIS and QGIS are widely used GIS software packages that
provide in-depth spatial and spatiotemporal analysis with the help of Parallel
Processing Factor, which divides the input for performing operations on
multiple processors. ArcGIS provides parallel extensions on various tools such
as 3D Analyst tools, spatial analysis, space-time pattern mining etc. The
popular QGIS analysis tool also provides OpenCL and CUDA support for parallel
processing.

Spatiotemporal Statistics Tools: Many statistical packages (e.g., gstat, geoR)
for spatial and spatiotemporal analysis can be run in the free R software
environment but are limited to parallel implementation. The pbdNCDF4 (Patel et
al., 2013) package provides parallel read and write capabilities for NetCDF
datasets. Python’s deep learning Tensorflow library provides various functions
for analyzing spatial and 3D spatiotemporal data.

Spatiotemporal Big Data Platforms: Big data systems are widely used for
handling large complex data and exploiting parallelism on modern hardware.
SpatialHadoop (Eldawy and Mokbel, 2015) and GeoSpark (Yu et al., 2015b)
provide support for spatial big data analytics. STARK (Hagedorn et al., 2017),
Geomesa (Hughes et al., 2015), and webGlobe (Sharma et al., 2018), all based
on the Apache Spark framework, integrate support for both spatial and temporal
data operations.

##  6\. Research Trends and Future Needs

This chapter covered state-of-the-art approaches for detecting six important
spatiotemporal pattern families in both sequential and parallel computing
environments. Our survey reveals that detection methods for some complex
pattern families such as telecouplings (e.g., cascading patterns),
summarization, change detection (e.g., vector-based footprints), etc., have
not received much attention in parallel computing environments and can be a
potential direction for future research.

Big data tools that can leverage the resources of modern architectures for
parallel processing also offer promising research opportunities. Current big
data platforms such as HadoopGIS, Spatial Hadoop etc. provide distributed
frameworks for parallel processing and some recent efforts towards processing
spatiotemporal data such as trajectory data from open-source communities
(Shang et al., 2018; Ding et al., 2018) have a great potential to be extended
toward finding non-trivial pattern families described in this chapter.

Besides parallel computing, other research directions might be interesting in
spatiotemporal data mining. For instance, a space-time prism has been proposed
(Miller, 1991) for finding regions of uncertainty within trajectory gaps given
the maximum speed of the object. Further exploration of the space-time prism
(Kuijpers et al., 2017) considers multi-attributes such as acceleration and
cases such as a sudden change in direction, providing more realistic path
scenarios(Sharma et al., 2020; Sharma and Shekhar, 2022).

###### Acknowledgements.

We would like to thank Kim Koffolt and the members of the University of
Minnesota Spatial Computing Research Group for their comments.

## References

  * (1)
  * saf (2020) 2020\.  safegraph.  https://www.safegraph.com/.
  * USC (2020) 2020\.  US Census.  https://www.safegraph.com/.
  * Abubaker et al. (2018) Nabil Abubaker, Kadir Akbudak, and Cevdet Aykanat. 2018\.  Spatiotemporal graph and hypergraph partitioning models for sparse matrix-vector multiplication on many-core architectures.  _IEEE Transactions on Parallel and Distributed Systems_ 30, 2 (2018), 445–458.
  * Aggarwal (2017) Charu C Aggarwal. 2017\.  An introduction to outlier analysis.  In _Outlier analysis_. Springer, 1–34.
  * Atluri et al. (2018) Gowtham Atluri, Anuj Karpatne, and Vipin Kumar. 2018\.  Spatio-temporal data mining: A survey of problems and methods.  _ACM Computing Surveys (CSUR)_ 51, 4 (2018), 1–41.
  * Banerjee et al. (2003) Sudipto Banerjee, Bradley P Carlin, and Alan E Gelfand. 2003\.  _Hierarchical modeling and analysis for spatial data_.  Chapman and Hall/CRC.
  * Bao et al. (2016) Jie Bao, Ruiyuan Li, Xiuwen Yi, and Yu Zheng. 2016\.  Managing massive trajectories on the cloud. In _Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems_. 1–10.
  * Barua and Alhajj (2007) Sajib Barua and Reda Alhajj. 2007.  Parallel wavelet transform for spatio-temporal outlier detection in large meteorological data. In _International Conference on Intelligent Data Engineering and Automated Learning_. Springer, 684–694.
  * Bhattacharjee et al. (2016) Shrutilipi Bhattacharjee, Monidipa Das, Soumya K Ghosh, and Shashi Shekhar. 2016.  Prediction of meteorological parameters: an a-posteriori probabilistic semantic kriging approach. In _Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems_. 1–10.
  * Celik et al. (2006) Mete Celik, Shashi Shekhar, James P Rogers, James A Shine, and Jin Soung Yoo. 2006.  Mixed-drove spatio-temporal co-occurence pattern mining: A summary of results. In _Sixth International Conference on Data Mining (ICDM’06)_. IEEE, 119–128.
  * Chang et al. (2021) Serina Chang, Emma Pierson, Pang Wei Koh, Jaline Gerardin, Beth Redbird, David Grusky, and Jure Leskovec. 2021.  Mobility network models of COVID-19 explain inequities and inform reopening.  _Nature_ 589, 7840 (2021), 82–87.
  * Chen et al. (2018) Cen Chen, Kenli Li, Sin G Teo, Guizi Chen, Xiaofeng Zou, Xulei Yang, Ramaseshan C Vijay, Jiashi Feng, and Zeng Zeng. 2018.  Exploiting spatio-temporal correlations with multiple 3d convolutional neural networks for citywide vehicle flow prediction. In _2018 IEEE international conference on data mining (ICDM)_. IEEE, 893–898.
  * Cheng et al. (2014) Tao Cheng, James Haworth, Berk Anbaroglu, Garavig Tanaksaranond, and Jiaqiu Wang. 2014.  Spatiotemporal data mining.  _Handbook of regional science_ (2014), 1173–1193.
  * Cordova and Moh (2015) Irving Cordova and Teng-Sheng Moh. 2015.  DBSCAN on resilient distributed datasets. In _2015 International Conference on High Performance Computing & Simulation (HPCS)_. IEEE, 531–540.
  * Cressie and Wikle (2015) Noel Cressie and Christopher K Wikle. 2015.  _Statistics for spatio-temporal data_.  John Wiley & Sons.
  * Ding et al. (2018) Xin Ding, Lu Chen, Yunjun Gao, Christian S Jensen, and Hujun Bao. 2018.  UlTraMan: A unified platform for big trajectory data management and analytics.  _Proceedings of the VLDB Endowment_ 11, 7 (2018), 787–799.
  * Eftelioglu et al. (2014) Emre Eftelioglu, Shashi Shekhar, Dev Oliver, Xun Zhou, Michael R Evans, Yiqun Xie, James M Kang, Renee Laubscher, and Christopher Farah. 2014.  Ring-shaped hotspot detection: A summary of results. In _2014 IEEE International Conference on Data Mining_. IEEE, 815–820.
  * Eldawy and Mokbel (2015) Ahmed Eldawy and Mohamed F Mokbel. 2015.  Spatialhadoop: A mapreduce framework for spatial data. In _2015 IEEE 31st international conference on Data Engineering_. IEEE, 1352–1363.
  * Eslami and Saeed (2018) Taban Eslami and Fahad Saeed. 2018.  Fast-GPU-PCC: a GPU-based technique to compute pairwise Pearson’s correlation coefficients for time series data—fMRI study.  _High-throughput_ 7, 2 (2018), 11.
  * Ester et al. (1997) Martin Ester, Hans-Peter Kriegel, and Jörg Sander. 1997\.  Spatial data mining: A database approach. In _International symposium on spatial databases_. Springer, 47–66.
  * Fu et al. (2019) Kaiqun Fu, Taoran Ji, Liang Zhao, and Chang-Tien Lu. 2019\.  Titan: A spatiotemporal feature learning framework for traffic incident duration prediction. In _Proceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems_. 329–338.
  * Hagedorn et al. (2017) Stefan Hagedorn, Philipp Gotze, and Kai-Uwe Sattler. 2017\.  The STARK framework for spatio-temporal data analytics on spark.  _Datenbanksysteme für Business, Technologie und Web (BTW 2017)_ (2017).
  * He et al. (2011) Yaobin He, Haoyu Tan, Wuman Luo, Huajian Mao, Di Ma, Shengzhong Feng, and Jianping Fan. 2011.  Mr-dbscan: an efficient parallel density-based clustering algorithm using mapreduce. In _2011 IEEE 17th international conference on parallel and distributed systems_. IEEE, 473–480.
  * Hong and Vatsavai (2016) Seokyong Hong and Ranga Raju Vatsavai. 2016.  A Scalable Probabilistic Change Detection Algorithm for Very High Resolution (VHR) Satellite Imagery. In _2016 IEEE International Congress on Big Data (BigData Congress)_. IEEE, 275–282.
  * Huang et al. (2008) Yan Huang, Liqin Zhang, and Pusheng Zhang. 2008.  A framework for mining sequential patterns from spatio-temporal event data sets.  _IEEE Transactions on Knowledge and data engineering_ 20, 4 (2008), 433–448.
  * Hughes et al. (2015) James N Hughes, Andrew Annex, Christopher N Eichelberger, Anthony Fox, Andrew Hulbert, and Michael Ronquest. 2015.  Geomesa: a distributed architecture for spatio-temporal fusion. In _Geospatial informatics, fusion, and motion video analytics V_ , Vol. 9473. SPIE, 128–140.
  * Jiang et al. (2017) Wei Jiang, Jie Zhu, Jiajie Xu, Zhixu Li, Pengpeng Zhao, and Lei Zhao. 2017\.  A feature based method for trajectory dataset segmentation and profiling.  _World Wide Web_ 20, 1 (2017), 5–22.
  * Karypis et al. (1999) George Karypis, Eui-Hong Han, and Vipin Kumar. 1999.  Chameleon: Hierarchical clustering using dynamic modeling.  _Computer_ 32, 8 (1999), 68–75.
  * Kawale et al. (2012) Jaya Kawale, Snigdhansu Chatterjee, Dominick Ormsby, Karsten Steinhaeuser, Stefan Liess, and Vipin Kumar. 2012.  Testing the significance of spatio-temporal teleconnection patterns. In _Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining_. 642–650.
  * Kendall et al. (2011) Wesley Kendall, Jingyuan Wang, Melissa Allen, Tom Peterka, Jian Huang, and David Erickson. 2011\.  Simplified parallel domain traversal. In _Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis_. 1–11.
  * Kim et al. (2018) Seongchan Kim, Ji-Sun Kang, Minho Lee, and Sa-kwang Song. 2018\.  DeepTC: ConvLSTM network for trajectory prediction of tropical cyclone using spatiotemporal atmospheric simulation data.  (2018).
  * Koperski et al. (1996) Krzysztof Koperski, Junas Adhikary, and Jiawei Han. 1996\.  Spatial data mining: progress and challenges survey paper. In _Proc. ACM SIGMOD Workshop on Research Issues on Data Mining and Knowledge Discovery, Montreal, Canada_. Citeseer, 1–10.
  * Kuijpers et al. (2017) Bart Kuijpers, Harvey J Miller, and Walied Othman. 2017\.  Kinetic prisms: incorporating acceleration limits into space–time prisms.  _International Journal of Geographical Information Science_ 31, 11 (2017), 2164–2194.
  * Kulldorff (1997) Martin Kulldorff. 1997\.  A spatial scan statistic.  _Communications in Statistics-Theory and methods_ 26, 6 (1997), 1481–1496.
  * Lam (2016) Hoang Thanh Lam. 2016\.  A concise summary of spatial anomalies and its application in efficient real-time driving behaviour monitoring. In _Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems_. 1–9.
  * Lee et al. (2008) Jae-Gil Lee, Jiawei Han, and Xiaolei Li. 2008.  Trajectory outlier detection: A partition-and-detect framework. In _2008 IEEE 24th International Conference on Data Engineering_. IEEE, 140–149.
  * Lee et al. (2007) Jae-Gil Lee, Jiawei Han, and Kyu-Young Whang. 2007.  Trajectory clustering: a partition-and-group framework. In _Proceedings of the 2007 ACM SIGMOD international conference on Management of data_. 593–604.
  * Li et al. (2020) Yan Li, Yiqun Xie, Pengyue Wang, Shashi Shekhar, and William Northrop. 2020.  Significant lagrangian linear hotspot discovery. In _Proceedings of the 13th ACM SIGSPATIAL International Workshop on Computational Transportation Science_. 1–10.
  * Liang et al. (2017) Yuxuan Liang, Zhongyuan Jiang, and Yu Zheng. 2017.  Inferring traffic cascading patterns. In _Proceedings of the 25th acm sigspatial international conference on advances in geographic information systems_. 1–10.
  * Liang and Wu (2015) Yen-hui Liang and Shiow-yang Wu. 2015.  Sequence-growth: A scalable and effective frequent itemset mining algorithm for big data based on MapReduce framework. In _2015 IEEE International Congress on Big Data_. IEEE, 393–400.
  * Lu et al. (2017) Liping Lu, Hao Cheng, Shengwu Xiong, Pengfei Duan, and Yuan Xiao. 2017.  Distributed anomaly detection algorithm for spatio-temporal trajectories of vehicles. In _2017 IEEE International Symposium on Parallel and Distributed Processing with Applications and 2017 IEEE International Conference on Ubiquitous Computing and Communications (ISPA/IUCC)_. IEEE, 590–598.
  * Lukasczyk et al. (2015) Jonas Lukasczyk, Ross Maciejewski, Christoph Garth, and Hans Hagen. 2015.  Understanding hotspots: A topological visual analytics approach. In _Proceedings of the 23rd SIGSPATIAL international conference on advances in geographic information systems_. 1–10.
  * Mehta et al. (2016) Paras Mehta, Christian Windolf, and Agnès Voisard. 2016\.  Spatio-temporal hotspot computation on apache spark (gis cup). In _24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems_.
  * Miller (1991) Harvey J Miller. 1991\.  Modelling accessibility using space-time prism concepts within geographical information systems.  _International Journal of Geographical Information System_ 5, 3 (1991), 287–301.
  * Mohan et al. (2010) Pradeep Mohan, Shashi Shekhar, James A Shine, and James P Rogers. 2010.  Cascading spatio-temporal pattern discovery: A summary of results. In _Proceedings of the 2010 SIAM International Conference on Data Mining_. SIAM, 327–338.
  * Moosavi et al. (2019) Sobhan Moosavi, Mohammad Hossein Samavatian, Srinivasan Parthasarathy, Radu Teodorescu, and Rajiv Ramnath. 2019.  Accident risk prediction based on heterogeneous sparse data: New dataset and insights. In _Proceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems_. 33–42.
  * Mou et al. (2018) Lichao Mou, Lorenzo Bruzzone, and Xiao Xiang Zhu. 2018\.  Learning spectral-spatial-temporal features via a recurrent convolutional neural network for change detection in multispectral imagery.  _IEEE Transactions on Geoscience and Remote Sensing_ 57, 2 (2018), 924–935.
  * Patel et al. (2013) Pragneshkumar Patel, George Ostrouchov, Wei-Chen Chen, Drew Schmidt, and David Pierce. 2013\.  A Quick Guide for the pbdNCDF4 package.  _R Vignette, URL http://cran. r-project. org/package= pbdNCDF4_ (2013).
  * Pillai et al. (2013) Karthik Ganesan Pillai, Rafal A Angryk, and Berkay Aydin. 2013\.  A filter-and-refine approach to mine spatiotemporal co-occurrences. In _Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems_. 104–113.
  * Prasad et al. (2017) Sushil K Prasad, Danial Aghajarian, Michael McDermott, Dhara Shah, Mohamed Mokbel, Satish Puri, Sergio J Rey, Shashi Shekhar, Yiqun Xe, Ranga Raju Vatsavai, et al. 2017\.  Parallel processing over spatial-temporal datasets from geo, bio, climate and social science communities: A research roadmap. In _2017 IEEE International Congress on Big Data (BigData Congress)_. IEEE, 232–250.
  * Qiao et al. (2008) Shaojie Qiao, Changjie Tang, Shucheng Dai, Mingfang Zhu, Jing Peng, Hongjun Li, and Yungchang Ku. 2008.  Partspan: Parallel sequence mining of trajectory patterns. In _2008 Fifth International Conference on Fuzzy Systems and Knowledge Discovery_ , Vol. 5. IEEE, 363–367.
  * Roddick and Spiliopoulou (1999) John F Roddick and Myra Spiliopoulou. 1999.  A bibliography of temporal, spatial and spatio-temporal data mining research.  _ACM SIGKDD Explorations Newsletter_ 1, 1 (1999), 34–38.
  * Romano and Jiang (2017) Benjamin Romano and Zhe Jiang. 2017.  Visualizing traffic accident hotspots based on spatial-temporal network kernel density estimation. In _Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems_. 1–4.
  * Shang et al. (2018) Zeyuan Shang, Guoliang Li, and Zhifeng Bao. 2018.  DITA: distributed in-memory trajectory analytics. In _Proceedings of the 2018 International Conference on Management of Data_. 725–740.
  * Sharma et al. (2022) Arun Sharma, Majid Farhadloo, Yan Li, Jayant Gupta, Aditya Kulkarni, and Shashi Shekhar. 2022\.  Understanding COVID-19 Effects on Mobility: A Community-Engaged Approach.  _AGILE: GIScience Series_ 3 (2022), 1–15.
  * Sharma et al. (2021) Arun Sharma, Yan Li, and Shashi Shekhar. May 21, 2021\.  SafeGraph Data Analysis to Assess COVID-19 Effects on MN Mobility.  _Impacts of the COVID-19 Pandemic on Minnesota’s Traffic and Transit Networks, Center for Transportation Studies, University of Minnesota_ (May 21, 2021).  http://www.spatial.cs.umn.edu/Project/covid_19/Appendix_Weekly_Mobility_Patterns_05212021.pdf
  * Sharma and Shekhar (2022) Arun Sharma and Shashi Shekhar. 2022.  Analyzing Trajectory Gaps to Find Possible Rendezvous Region.  _ACM Transactions on Intelligent Systems and Technology (TIST)_ 13, 3 (2022), 1–23.
  * Sharma et al. (2020) Arun Sharma, Xun Tang, Jayant Gupta, Majid Farhadloo, and Shashi Shekhar. 2020.  Analyzing trajectory gaps for possible rendezvous: A summary of results. In _11th International Conference on Geographic Information Science (GIScience 2021)-Part I_. Schloss Dagstuhl-Leibniz-Zentrum für Informatik.
  * Sharma et al. (2018) Arun Sharma, Syed Mohammed Arshad Zaidi, Varun Chandola, Melissa R Allen, and Budhendra L Bhaduri. 2018.  WebGIobe-A cloud-based geospatial analysis framework for interacting with climate data. In _Proceedings of the 7th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data_. 42–46.
  * Shekhar (2007) Shashi Shekhar. 2007\.  _Spatial databases_.  Pearson Education India.
  * Shekhar et al. (2011) Shashi Shekhar, Michael R Evans, James M Kang, and Pradeep Mohan. 2011.  Identifying patterns in spatial information: A survey of methods.  _Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery_ 1, 3 (2011), 193–214.
  * Shekhar et al. (2015) Shashi Shekhar, Zhe Jiang, Reem Y Ali, Emre Eftelioglu, Xun Tang, Venkata Gunturi, and Xun Zhou. 2015.  Spatiotemporal data mining: A computational perspective.  _ISPRS International Journal of Geo-Information_ 4, 4 (2015), 2306–2338.
  * Shekhar et al. (2003) Shashi Shekhar, Pusheng Zhang, Yan Huang, and Ranga Raju Vatsavai. 2003.  Trends in spatial data mining.  _Data mining: Next generation challenges and future directions_ (2003), 357–380.
  * Shin et al. (2017) Sungbok Shin, Minsuk Choi, Jinho Choi, Scott Langevin, Christopher Bethune, Philippe Horne, Nathan Kronenfeld, Ramakrishnan Kannan, Barry Drake, Haesun Park, et al. 2017\.  Stexnmf: Spatio-temporally exclusive topic discovery for anomalous event detection. In _2017 IEEE International conference on data mining (ICDM)_. IEEE, 435–444.
  * Song and Lee (2018) Hwanjun Song and Jae-Gil Lee. 2018.  RP-DBSCAN: A superfast parallel DBSCAN algorithm based on random partitioning. In _Proceedings of the 2018 International Conference on Management of Data_. 1173–1187.
  * Song et al. (2017) Hwanjun Song, Jae-Gil Lee, and Wook-Shin Han. 2017\.  PAMAE: parallel k-medoids clustering with high accuracy and efficiency. In _Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_. 1087–1096.
  * Tang et al. (2017) Xun Tang, Emre Eftelioglu, Dev Oliver, and Shashi Shekhar. 2017.  Significant linear hotspot discovery.  _IEEE Transactions on Big Data_ 3, 2 (2017), 140–153.
  * von Looz et al. (2018) Moritz von Looz, Charilaos Tzovas, and Henning Meyerhenke. 2018\.  Balanced k-means for parallel geometric partitioning. In _Proceedings of the 47th International Conference on Parallel Processing_. 1–10.
  * Welton et al. (2013) Benjamin Welton, Evan Samanas, and Barton P Miller. 2013\.  Mr. scan: Extreme scale density-based clustering using a tree-based network of gpgpu nodes. In _SC’13: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis_. IEEE, 1–11.
  * Xie and Shekhar (2019a) Yiqun Xie and Shashi Shekhar. 2019a.  A nondeterministic normalization based scan statistic (NN-scan) towards robust hotspot detection: A summary of results. In _Proceedings of the 2019 SIAM International Conference on Data Mining_. SIAM, 82–90.
  * Xie and Shekhar (2019b) Yiqun Xie and Shashi Shekhar. 2019b.  Significant DBSCAN towards statistically robust clustering. In _Proceedings of the 16th International Symposium on Spatial and Temporal Databases_. 31–40.
  * Yu et al. (2015a) Chung-Hsien Yu, Dong Luo, Wei Ding, Joseph Cohen, David Small, and Shafiqul Islam. 2015a.  Spatio-temporal asynchronous co-occurrence pattern for big climate data towards long-lead flood prediction. In _2015 IEEE International Conference on Big Data (Big Data)_. IEEE, 865–870.
  * Yu et al. (2017) Haiyang Yu, Zhihai Wu, Shuqin Wang, Yunpeng Wang, and Xiaolei Ma. 2017.  Spatiotemporal recurrent convolutional networks for traffic prediction in transportation networks.  _Sensors_ 17, 7 (2017), 1501.
  * Yu et al. (2015b) Jia Yu, Jinxuan Wu, and Mohamed Sarwat. 2015b.  Geospark: A cluster computing framework for processing large-scale spatial data. In _Proceedings of the 23rd SIGSPATIAL international conference on advances in geographic information systems_. 1–4.
  * Zaharia et al. (2012) Matei Zaharia, Mosharaf Chowdhury, Tathagata Das, Ankur Dave, Justin Ma, Murphy McCauly, Michael J Franklin, Scott Shenker, and Ion Stoica. 2012.  Resilient distributed datasets: A $\\{$Fault-Tolerant$\\}$ abstraction for $\\{$In-Memory$\\}$ cluster computing. In _9th USENIX Symposium on Networked Systems Design and Implementation (NSDI 12)_. 15–28.
  * Zhang et al. (2003) Pusheng Zhang, Yan Huang, Shashi Shekhar, and Vipin Kumar. 2003\.  Correlation analysis of spatial time series datasets: A filter-and-refine approach. In _Pacific-Asia Conference on Knowledge Discovery and Data Mining_. Springer, 532–544.
  * Zhang et al. (1996) Tian Zhang, Raghu Ramakrishnan, and Miron Livny. 1996\.  BIRCH: an efficient data clustering method for very large databases.  _ACM sigmod record_ 25, 2 (1996), 103–114.
  * Zhang et al. (2018) Yueheng Zhang, Xinqi Zheng, Zhenhua Wang, Gang Ai, and Qing Huang. 2018.  Implementation of a parallel GPU-based space-time kriging framework.  _ISPRS International Journal of Geo-Information_ 7, 5 (2018), 193.
  * Zheng et al. (2011) Kai Zheng, Goce Trajcevski, Xiaofang Zhou, and Peter Scheuermann. 2011.  Probabilistic range queries for uncertain trajectories on road networks. In _Proceedings of the 14th International Conference on Extending Database Technology_. 283–294.
  * Zheng (2015) Yu Zheng. 2015.  Trajectory data mining: an overview.  _ACM Transactions on Intelligent Systems and Technology (TIST)_ 6, 3 (2015), 1–41.
  * Zhou et al. (2014) Xun Zhou, Shashi Shekhar, and Reem Y Ali. 2014.  Spatiotemporal change footprint pattern discovery: an inter-disciplinary survey.  _Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery_ 4, 1 (2014), 1–23.


main

# Supplemental Material for
“Optical Telecommunications-Band Clock based on Neutral Titanium Atoms”

Scott Eustice  Department of Physics, University of California, Berkeley, CA
94720  Challenge Institute for Quantum Computation, University of California,
Berkeley, CA 94720  Dmytro Filin  Department of Physics and Astronomy,
University of Delaware, Newark, DE 19716  Jackson Schrott  Department of
Physics, University of California, Berkeley, CA 94720  Challenge Institute for
Quantum Computation, University of California, Berkeley, CA 94720  Sergey
Porsev  Department of Physics and Astronomy, University of Delaware, Newark,
DE 19716  Charles Cheung  Department of Physics and Astronomy, University of
Delaware, Newark, DE 19716  Diego Novoa  Department of Physics, University of
California, Berkeley, CA 94720  Challenge Institute for Quantum Computation,
University of California, Berkeley, CA 94720  Dan M. Stamper-Kurn  Department
of Physics, University of California, Berkeley, CA 94720  Challenge Institute
for Quantum Computation, University of California, Berkeley, CA 94720
Materials Science Division, Lawrence Berkeley National Laboratory, Berkeley,
CA 94720  Marianna S. Safronova  Department of Physics and Astronomy,
University of Delaware, Newark, DE 19716  Joint Quantum Institute, National
Institute of Standards and Technology and the University of Maryland, College
Park, Maryland 20742

††preprint: APS/123-QED

##  S1 Calculation of E1, M1, and E2 Transition Rates in Ti I

###  A Theoretical framework: CI+all-order method

We use the CI+all-order method [1] that combines linearized coupled cluster
and configuration interaction (CI) approaches. In this method, the electrons
are separated into the $1s^{2}2s^{2}2p^{6}3s^{2}3p^{6}$ core and four
remaining valence electrons. First, the coupled cluster method is used to
construct the effective Hamiltonian $H_{\rm{eff}}$ that accounts for core and
core-valence correlations and can be constructed using second-order many-body
perturbation theory in the CI + MBPT method or the coupled cluster approach
(CI + all-order method). The CI method is used to correlate the remaining four
valence electrons using this effective Hamiltonian rather than the usual bare
Hamiltonian. This procedure effectively includes all types of correlation
effects in the core and valence spaces.

The CI wave function is constructed as a linear combination of all distinct
states of a specified angular momentum $J$ and parity,

$\psi_{J}=\sum_{i}c_{i}\Phi_{i},$ (S1)

where $\\{\Phi_{i}\\}$ is the set of Slater determinants generated by exciting
electrons from the reference configuration to higher orbitals. The many-
electron Schrödinger equation can be written as

$H_{\rm{eff}}\Psi=E\Psi,$ (S2)

where the effective Hamiltonian has the form

$H_{\rm{eff}}=H_{\rm{CI}}+\Sigma.$ (S3)

Here, $H_{\rm{CI}}$ is the CI Hamiltonian described by the equation

$H_{\rm{CI}}=E_{core}+\sum_{i>N_{core}}h_{i,CI}+\sum_{j>i>M_{core}}V_{ij},$
(S4)

where $E_{core}$ is the energy of the frozen core, $N_{core}$ is the number of
core electrons, $h_{i,CI}$ represents the kinetic energy of the valence
electrons and their interaction with the central field and $V_{ij}$ accounts
for the valence–valence correlations.

The core-valence correlation potential,

$\Sigma=\Sigma_{1}+\Sigma_{2},$

is obtained from the all-order method. Here, $\Sigma_{1}$ and $\Sigma_{2}$ are
the one- and two-electron parts of the core–valence correlation potential,
respectively. After Eq. (S2) is solved using the CI technique and the wave
functions are obtained, they are used to calculate matrix elements of the
electric-dipole, magnetic-dipole, electric-quadrupole, and other one-electron
operators.

###  B Energy level calculation

When applying the CI+all-order method to atomic Ti, we used a a $V^{N-4}$
potential of the $1s^{2}2s^{2}2p^{6}3s^{2}3p^{6}$ frozen core. We solve Dirac-
Hartree-Fock equations in this potential to generate $3d$, $4s$, $4p$, $5s$,
$4d$, $5p$, and $4f$ orbitals. All other orbitals are constructed in a
spherical cavity of 40 a.u. using B-splines.

The set of CI configurations has to be constructed separately for even and odd
states. We carry out several calculations with increasing number of
configurations to ensure convergence of the CI with the number of included
configurations. For even states, we find it sufficient to make all possible
single and double excitations to a $20spd18f16g$ basis starting from
$4s^{2}3d^{2}$, $4s3d^{2}5s$, $4s^{2}3d4d$, $3d^{2}4p^{2}$, $3d^{2}5s^{2}$,
$4s3d^{3}$, $4s3d^{2}4d$, $3d^{3}5s$, and $3d^{2}5s4d$ configurations. We
verified that a subset of triple excitations give a negligible contribution.
For odd states, the CI configuration space is sufficiently saturated by the
single and double excitations to the same large basis from the $4s3d^{2}4p$,
$3d^{3}4p$, $4s3d^{2}5p$, $3d^{2}4p5s$, $4s3d4p4d$, $3d^{2}5s5p$, and
$3d^{2}4p4d$ configurations.

We have carried out calculation of energies for 85 levels and compared them
with experiment. Most of the theoretical energies differ from experimental
values by only 0.1-2.5%. We present results only for the lines and levels that
can be used to pump titanium optically into the metastable state to perform
laser cooling and to drive the relevant clock transitions. The selected energy
levels in cm-1 are listed in Tables S1 and S2.

Table S1: Comparison of theoretical even energy levels (in cm-1) with experiment [2]. Configuration | Term | Expt | Theory | Diff | Diff %
---|---|---|---|---|---
$3d^{2}4s^{2}$ | $a\tensor{*}[^{3}]{F}{{}_{2}}$ | 0 | 0 | 0 |
| $a\tensor{*}[^{3}]{F}{{}_{3}}$ | 170 | 177 | 7 | 4.1%
| $a\tensor{*}[^{3}]{F}{{}_{4}}$ | 387 | 396 | 9 | 2.3%
$3d^{3}(^{4}F)4s$ | $a\tensor{*}[^{5}]{F}{{}_{1}}$ | 6557 | 6374 | -183 | -2.8%
| $a\tensor{*}[^{5}]{F}{{}_{2}}$ | 6599 | 6416 | -183 | -2.8%
| $a\tensor{*}[^{5}]{F}{{}_{3}}$ | 6661 | 6477 | -184 | -2.8%
| $a\tensor{*}[^{5}]{F}{{}_{4}}$ | 6743 | 6557 | -186 | -2.8%
| $a\tensor{*}[^{5}]{F}{{}_{5}}$ | 6843 | 6652 | -191 | -2.8%
$3d^{3}(^{2}G)4s$ | $a\tensor{*}[^{3}]{G}{{}_{5}}$ | 15220 | 15497 | 276 | 1.8%
$3d^{3}(^{2}H)4s$ | $a\tensor{*}[^{3}]{H}{{}_{5}}$ | 18141 | 18450 | 308 | 1.7%
| $a\tensor{*}[^{3}]{H}{{}_{6}}$ | 18193 | 18498 | 306 | 1.7%
$3d^{3}(^{2}H)4s$ | $a\tensor{*}[^{1}]{H}{{}_{5}}$ | 20796 | 21171 | 375 | 1.8%
Table S2:  Comparison of theoretical odd energy levels (in cm-1) with experiment [2]. Configuration | Term | Expt | Theory | Diff | Diff %
---|---|---|---|---|---
$3d^{2}(^{3}F)4s4p(^{3}P^{o})$ | $z\tensor{*}[^{5}]{G}{{}^{o}_{6}}$ | 16459 | 16454 | -5 | 0.0%
$3d^{2}(^{3}F)4s4p(^{3}P^{o})$ | $z\tensor{*}[^{1}]{S}{{}^{o}_{0}}$ |  | 24174 |  |
$3d^{2}(^{3}P)4s4p(^{3}P^{o})$ | $\tensor{*}[^{5}]{D}{{}^{o}_{4}}$ | 25927 | 26081 | 154 | 0.6%
$3d^{3}(^{4}F)4p$ | $y\tensor{*}[^{5}]{G}{{}^{o}_{6}}$ | 26911 | 26982 | 71 | 0.3%

We compute the expectation values $\langle L^{2}\rangle$ and $\langle
S^{2}\rangle$, where $L$ and $S$ are the total electron orbital and spin
angular momentum operators, to obtain approximate quantum numbers $L$ and $S$,
where $\langle L^{2}\rangle=L(L+1)$ and $\langle S^{2}\rangle=S(S+1)$, which
allowed us to unambiguously identify all terms in Tables S1 and S2. As a
result, we identify a level, 3d24s4p 1S${}^{o}_{0}$, not listed in the NIST
database. This level is included in Table S2.

###  C Optical clock transitions

Table S3: Results of calculations for the $a\tensor{*}[^{3}]{F}{{}_{4}}\to a\tensor{*}[^{5}]{F}{{}_{5}}$ clock transitions of Ti. Wavelength, $\lambda$, (in units of nm), E2 and M1 reduced matrix elements (ME) (in a.u. for E2 transitions, in $\mu_{B}$ for M1 transitions), transition rates (in $\times 10^{-7}$s-1), and branch ratio. Upper | Term | Level | Lower | Term | Level | $\lambda$ |  | ME | Tr. rate | Branching ratio
---|---|---|---|---|---|---|---|---|---|---
$3d^{3}(^{4}F)4s$ | $a\tensor{*}[^{5}]{F}{{}_{5}}$ | 6843 | $3d^{2}4s^{2}$ | $a\tensor{*}[^{3}]{F}{{}_{3}}$ | 170 | 1498.6 | E2 | 0.0472(7) | 3.00(9) | 0.00838(25)
|  |  |  | $a\tensor{*}[^{3}]{F}{{}_{4}}$ | 387 | 1548.9 | M1 | 0.0010(5) | 7(6) | 0.020(17)
|  |  |  |  |  |  | E2 | 0.140(4) | 22.4(1.3) | 0.063(4)
|  |  | $3d^{3}(4F)4s$ | $a\tensor{*}[^{5}]{F}{{}_{4}}$ | 6743 | 99794.4 | M1 | 3.632(10) | 325.43(18) | 0.909(16)
|  |  |  |  |  |  | E2 | 1.748(18) | $3.14(8)\times 10^{-6}$ | $8.78(22)\times 10^{-9}$
$3d^{2}4s^{2}$ | $a\tensor{*}[^{3}]{F}{{}_{4}}$ | 387 | $3d^{2}4s^{2}$ | $a\tensor{*}[^{3}]{F}{{}_{3}}$ | 170 | 46138. | M1 | 2.597(0.026) | 2059(53) | 1
Table S4: Wavelengths (in nm), electric-dipole reduced matrix elements Dtot (in a.u.), transition rates (in s-1), and branching ratios for cooling transitions of Ti I. The Dtot values (in a.u.) are calculated with CI+all-order method and include the random-phase approximation (RPA), the core-Brueckner ($\sigma$), structural radiation (SR), two-particle (2P), and normalization (Norm) corrections. For approximate values (indicated by a $\sim$ symbol), the precise value of the matrix element is highly uncertain, and the reported value should be interpreted as correct only within an order of magnitude. Upper | Term | Level | Lower | Term | Level | $\lambda$ |  | Dtot | Tr. rate | Branch ratio
---|---|---|---|---|---|---|---|---|---|---
$3d^{3}(^{4}F)4p$ | $y\tensor{*}[^{5}]{G}{{}^{o}_{6}}$ | 26911 | $3d^{3}(^{4}F)4s$ | $a\tensor{*}[^{5}]{F}{{}_{5}}$ | 6843 | 498 | E1 | 7.337(12) | 6.780(23)$\times 10^{7}$ | 0.9999989(5)
|  |  | $3d^{3}(^{2}G)4s$ | $a\tensor{*}[^{3}]{G}{{}_{5}}$ | 15220 | 855 | E1 | $\sim 0.007$ | $\sim 11$ | $\sim 2\times 10^{-7}$
|  |  | $3d^{3}(^{2}H)4s$ | $a\tensor{*}[^{3}]{H}{{}_{5}}$ | 18141 | 1140 | E1 | 0.0055(14) | 3.2(1.4) | 4.7(2.0)$\times 10^{-8}$
|  |  | $3d^{3}(^{2}H)4s$ | $a\tensor{*}[^{3}]{H}{{}_{6}}$ | 18193 | 1147 | E1 | 0.025(4) | 62(19) | 9(3)$\times 10^{-7}$
|  |  | $3d^{3}(^{2}H)4s$ | $a\tensor{*}[^{1}]{H}{{}_{5}}$ | 20796 | 1635 | E1 | $\sim 0.0004$ | $\sim 0.005$ | $\sim 7\times 10^{-11}$
$3d^{2}(^{3}F)4s4p(^{3}P^{o})$ | $z\tensor{*}[^{5}]{G}{{}^{o}_{6}}$ | 16459 | $3d^{3}(^{4}F)4s$ | $a\tensor{*}[^{5}]{F}{{}_{5}}$ | 6843 | 1040 | E1 | 0.86(3) | 1.03(8)$\times 10^{5}$ | 0.99999969(2)
|  |  | $3d^{3}(^{2}G)4s$ | $a\tensor{*}[^{3}]{G}{{}_{5}}$ | 15220 | 8076 | E1 | 0.01040(10) | 0.0318(25) | 3.1(2)$\times 10^{-7}$
Table S5: Wavelengths (in nm), calculated and observed transition rates (in s${}^{-1\times 10^{6}}$), and branching ratios for optical pumping of Ti. The upper state for all transitions is the $3d^{2}(^{3}P)4s4p(^{3}P^{o})$ $\tensor{*}[^{5}]{D}{{}^{o}_{4}}$ level, at 25967 cm-1. Lower | Term | Level | $\lambda$ | Tr. rate, theory | Tr. rate, lit | Branch ratio
---|---|---|---|---|---|---
$3d^{2}4s^{2}$ | $a\tensor{*}[^{3}]{F}{{}_{3}}$ | 170 | 388.2 | 0.13(6) | 0.28(6) | 0.049
| $a\tensor{*}[^{3}]{F}{{}_{4}}$ | 387 | 391.5 | 1.8(8) | 2.11(28) | 0.68
$3d^{3}(^{4}F)4s$ | $a\tensor{*}[^{5}]{F}{{}_{3}}$ | 6661 | 519.1 | 0.00036(12) |  | 0.00014
| $a\tensor{*}[^{5}]{F}{{}_{4}}$ | 6743 | 521.3 | 0.08(8) | 0.31(16) | 0.030
| $a\tensor{*}[^{5}]{F}{{}_{5}}$ | 6843 | 524.0 | 0.4(4) |  | 0.17
| $b\tensor{*}[^{3}]{F}{{}_{4}}$ | 11777 | 706.7 | 0.06(3) |  | 0.02
$3d^{3}(^{4}P)4s$ | $a\tensor{*}[^{5}]{P}{{}_{3}}$ | 14106 | 845.9 | 0.129(4) |  | 0.049

We study forbidden transitions between the $a\tensor{*}[^{3}]{F}{}$ and
$a\tensor{*}[^{5}]{F}{}$ terms to identify the most suitable clock transition.
The main text summarizes the properties of the clock transitions. The total
clock transition linewidth accounts not only for spontaneous decay on the
clock transition itself, but also for decay of the upper and lower levels of
the clock transition to other states, leading to an overall clock transition
linewidth that is larger than the spontaneous decay rate on the clock
transition alone. In Table S3, we list the contributions that determine the
linewidth of the $a^{3}F_{4}\to a^{5}F_{5}$ clock transition. We note that the
clock transition linewidth is dominated by M1 decays of both the lower and
upper states to other fine structure states within their respective manifolds.
The same calculation was performed to calculate the linewidth of all other
clock transitions. The random-phase approximation (RPA) corrections are
included to the effective electric quadupole and magnetic dipole operators,
see, for example Ref. [3]. Such effective operators account for the core-
valence correlations in analogy with the effective Hamiltonian $H_{\rm{eff}}$
discussed above. The uncertainties in the values of matrix elements were
estimated as difference between values obtained using CI+all-order and CI+MBPT
methods.

###  D Laser cooling transitions

Ref. [4] identified two candidate transitions on which Ti may be laser cooled.
To support ongoing experimental efforts to realize laser cooling of Ti, we
characterized these two transitions theoretically using our atomic-structure
calculations described herein. Specifically, we calculated the strengths of
the two electric-dipole laser cooling transitions, and also, critically to
experimental efforts, determined the small leakage rate (branching ratio) out
of the laser cooling transitions. Results for two of the cooling transitions,
$3d^{3}(\tensor{*}[^{4}]{F}{})4p$ $y\tensor{*}[^{5}]{G}{{}^{{}^{\circ}}_{6}}$
\- $3d^{3}(\tensor{*}[^{4}]{F}{})4s$ $a\tensor{*}[^{5}]{F}{{}_{5}}$ at
$\lambda=498$ nm and
$3d^{3}(\tensor{*}[^{3}]{F}{})4s4p(\tensor{*}[^{3}]{P}{{}^{o}})$
$z\tensor{*}[^{5}]{G}{{}^{o}_{6}}$ \- $3d^{3}(\tensor{*}[^{4}]{F}{})4s$
$a\tensor{*}[^{5}]{F}{{}_{5}}$ at $\lambda=1040$ nm are listed in Table S4).

In Ref. [4] it was noted that while there do exist other even parity states to
which a Ti atom in the excited state of the laser cooling transition can
decay, such scattering would be strongly suppressed because the transitions
are spin forbidden. Our calculations confirm this expectation. Indeed, we find
the branching to those states is exceptionally low, at the $10^{-6}$ level for
the 498 nm transition and at the $3\cdot 10^{-7}$ level for the 1040 nm
transition. These are low enough branching ratios to enable the typical tools
of modern ultracold atomic physics, including both Doppler and sub-Doppler
cooling techniques and single-atom fluorescenence detection in quantum-gas
microscopes or optical tweezers, without the need for additional repumping
lasers.

To obtain transition rates and branching ratios for the cooling transitions
(see Table S4) we use the electric-dipole reduced matrix elements calculated
with the effective electric-dipole operator in the random-phase approximation.
We also considered other correction to the E1 operator beyond RPA: the core-
Brueckner ($\sigma$), structural radiation (SR), two-particle (2P), and
normalization (Norm) corrections [5, 6, 7]. As has been noted for the case of
Sr [3], these corrections cannot be omitted at the 1% level of accuracy.

In Table S4 we include transition matrix elements, $D_{tot}$, obtained taking
into account all the corrections mentioned above. The uncertainties were
estimated by taking the difference between the values obtained using CI+all-
order and CI+MBPT methods. For very small matrix elements (marked by the tilde
symbol), we provide approximate values without explicit evaluation of errors.
For these, the error should be assumed to be at the same order of magnitude as
the quantity itself.

###  E Optical pumping transitions

Gas phase Ti atoms may be produced with a thermal source that operates between
1200°C to 1800°C. At these temperatures, a low population of the Ti atoms
produced would be in the $a\tensor{*}[^{5}]{F}{{}_{5}}$ laser-coolable state.
It would therefore be necessary to transfer atoms to this state from the
$a\tensor{*}[^{3}]{F}{}$ ground state manifold via optical pumping. Through
our calculations, we examined multiple potential excited states that could be
used to transfer population efficiently to the $a\tensor{*}[^{5}]{F}{{}_{5}}$
state. We found the
$3d^{2}(\tensor{*}[^{3}]{P}{})4s4p(\tensor{*}[^{3}]{P}{{}^{o}})$
$y\tensor{*}[^{5}]{D}{{}^{o}_{4}}$ state has a significant branching ratio to
both the $a\tensor{*}[^{5}]{F}{{}_{5}}$ state and $a\tensor{*}[^{3}]{F}{}$
states, allowing for optical pumping of atoms from the ground states to the
laser cooling state. The transition wavelengths are also amenable to current
laser technology.

##  S2 Optical Clock Rabi Frequencies

The optical clock transitions of Ti can be driven by either the M1 or E2
multipoles of the electromagnetic field, both of which must be accounted for
when calculating the overall Rabi frequency. In each of the transitions we
highlighted in the main text ($m_{J}=0\to m^{\prime}_{J}=0$, $J=4\to
J^{\prime}=4,5$) only one of the two multipoles is allowed.

Given a reduced M1 matrix element, $D_{M1}$, for a transitions between lower
and upper levels $J$ and $J^{\prime}$, and a magnetic field $\mathbf{B}$ of
the clock laser, the M1 Rabi frequency between a lower and upper sublevel
$m_{J}$ and $m^{\prime}_{J}$ is given by

$\Omega_{M1}=-\frac{D_{M1}}{\hbar}(-1)^{J^{\prime}-m^{\prime}_{J}}\hat{\mathbf{e}}^{*}_{m^{\prime}_{J}-m_{J}}\cdot\mathbf{B}\\\
\times\begin{pmatrix}J&1&J^{\prime}\\\
m_{J}&m^{\prime}_{J}-m_{J}&-m^{\prime}_{J}\end{pmatrix}.$ (S5)

For an electric quadrupole transition with reduced matrix element $D_{E2}$
driven by a plane-wave clock laser field $\mathbf{E}$ with polarization
$\bm{\varepsilon}$ and propagation wavevector $\mathbf{k}$, the Rabi frequency
is

$\Omega_{E2}=\frac{iD_{E2}}{2\hbar}(-1)^{J^{\prime}-m^{\prime}_{J}}\begin{pmatrix}J&2&J^{\prime}\\\
m_{J}&m^{\prime}_{J}-m_{J}&-m^{\prime}_{J}\end{pmatrix}\\\
\times\sum_{i,j}M_{ij}(m^{\prime}_{J}-m_{J})k_{i}\varepsilon_{j}.$ (S6)

Here, $M_{ij}(q)$ is a geometric factor given by

$M_{ij}(q)=(-1)^{q}\sqrt{5}\sum_{q_{1},q_{2}}(\mathbf{\hat{e}}_{i}\cdot\mathbf{\hat{e}}^{*}_{q_{1}})(\mathbf{\hat{e}}_{j}\cdot\mathbf{\hat{e}}^{*}_{q_{1}})\begin{pmatrix}1&1&2\\\
q_{1}&q_{2}&-q\end{pmatrix},$ (S7)

where $\mathbf{\hat{e}}_{i}$ and $\mathbf{\hat{e}}_{q}$ are the cartesian and
spherical basis vectors respectively.

##  S3 Dynamical Polarizability of Ti I

Table S6: Contributions to the static electric-dipole polarizability $\alpha_{0}$ with the appropriate reduced matrix elements $D$ (in a.u.) of the $3d^{2}4s^{2}$ $a\tensor{*}[^{5}]{F}{{}_{5}}$ level. For comparison, the experimental and theoretical energy levels (in cm-1) are shown. Configuration | Term | Exp. Level | Theor. Level | Diff % | D | Contrib. to $\alpha_{0}$
---|---|---|---|---|---|---
$3d^{2}(^{3}F)4s4p(^{3}P^{o})$ | $z\tensor{*}[^{5}]{G}{{}^{o}_{6}}$ | 16459 | 16454 | 0.0% | 0.86(3) | 1.00(8)
| $z\tensor{*}[^{5}]{F}{{}^{o}_{5}}$ | 17215 | 17185 | -0.2% | 2.48(6) | 7.7(4)
| $z\tensor{*}[^{5}]{D}{{}^{o}_{4}}$ | 18695 | 18769 | 0.4% | 2.08(3) | 4.77(16)
$3d^{3}(^{4}F)4p$ | $y\tensor{*}[^{5}]{G}{{}^{o}_{5}}$ | 26773 | 26850 | 0.3% | 2.299(5) | 3.48(2)
| $y\tensor{*}[^{5}]{G}{{}^{o}_{6}}$ | 26911 | 26982 | 0.3% | 7.837(12) | 40.16(12)
| $y\tensor{*}[^{5}]{F}{{}^{o}_{4}}$ | 28788 | 29061 | 1.0% | 2.410(7) | 3.45(2)
| $y\tensor{*}[^{5}]{F}{{}^{o}_{5}}$ | 28896 | 29164 | 0.9% | 7.251(6) | 31.07(5)
| $x\tensor{*}[^{5}]{D}{{}^{o}_{4}}$ | 30060 | 30474 | 1.4% | 6.723(12) | 25.24(12)
Other |  |  |  |  |  | 11.7
Total |  |  |  |  |  | 128.5(2.0)
Table S7: Contributions to the static electric-dipole polarizability $\alpha_{0}$ with the appropriate reduced matrix elements $D$ (in a.u.) of the $3d^{2}4s^{2}$ $a\tensor{*}[^{3}]{F}{{}_{4}}$ level. For comparison, the experimental and theoretical energy levels (in cm-1) are shown. Configuration | Term | Exp. Level | Theor. Level | Diff % | D | Contrib. to $\alpha_{0}$
---|---|---|---|---|---|---
$3d^{2}(^{3}F)4s4p(^{3}P^{o})$ | $z\tensor{*}[^{3}]{F}{{}^{o}_{4}}$ | 19574 | 19632 | 0.3% | 1.682(13) | 2.39(4)
| $z\tensor{*}[^{3}]{D}{{}^{o}_{3}}$ | 20126 | 20115 | -0.1% | 1.467(9) | 1.774(22)
| $z\tensor{*}[^{3}]{G}{{}^{o}_{5}}$ | 21740 | 22025 | 1.3% | 1.297(4) | 1.263(8)
| $z\tensor{*}[^{1}]{G}{{}^{o}_{4}}$ | 24695 | 25163 | 1.9% | 1.1(4) | 0.8(6)
$3d^{2}(^{3}F)4s4p(^{1}P^{o})$ | $y\tensor{*}[^{3}]{F}{{}^{o}_{3}}$ | 25227 | 25351 | 0.5% | 1.479(13) | 1.423(25)
| $y\tensor{*}[^{3}]{F}{{}^{o}_{4}}$ | 25388 | 25531 | 0.6% | 3.9(3) | 9.8(1.8)
$3d^{3}(^{4}F)4p$ | $y\tensor{*}[^{3}]{D}{{}^{o}_{3}}$ | 25644 | 25591 | -0.2% | 3.12(17) | 6.3(7)
$3d^{2}(^{1}D)4s4p(^{3}P^{o})$ | $x\tensor{*}[^{3}]{F}{{}^{o}_{4}}$ | 27026 | 27325 | 1.1% | 3.36(11) | 6.8(5)
$3d^{2}(^{3}F)4s4p(^{1}P^{o})$ | $y\tensor{*}[^{3}]{G}{{}^{o}_{5}}$ | 27750 | 27846 | 0.35% | 4.65(25) | 12.7(1.4)
| $w\tensor{*}[^{3}]{D}{{}^{o}_{3}}$ | 29912 | 30145 | 0.8% | 2.983(17) | 4.86(5)
$3d^{2}(^{1}G)4s4p(^{3}P^{o})$ | $x\tensor{*}[^{3}]{G}{{}^{o}_{5}}$ | 30039 | 30349 | 1.0% | 4.416(10) | 10.53(5)
$3d^{3}(^{4}F)4p$ | $w\tensor{*}[^{3}]{G}{{}^{o}_{5}}$ | 31629 | 32053 | 1.3% | 4.61(20) | 10.9(1.0)
$3d^{2}(^{1}G)4s4p(^{3}P^{o})$ | $v\tensor{*}[^{3}]{F}{{}^{o}_{4}}$ | 34205 | 34742 | 1.6% | 3.60(14) | 6.1(5)
$3d^{3}(^{2}D_{2})4p$ | $u\tensor{*}[^{3}]{F}{{}^{o}_{3}}$ | 37744 | 38871 | 3.0% | 2.74(13) | 3.2(3)
$3d^{2}(^{3}P)4s4p(^{1}P^{o})$ | $u\tensor{*}[^{3}]{D}{{}^{o}_{3}}$ | 38159 | 38909 | 2.0% | 1.74(5) | 1.28(7)
$3d^{3}(^{2}G)4p$ | $t\tensor{*}[^{3}]{F}{{}^{o}_{4}}$ | 38671 | 39560 | 2.3% | 2.6(4) | 2.9(8)
$3d^{3}(^{2}D_{2})4p$ | $s\tensor{*}[^{3}]{D}{{}^{o}_{3}}$ | 39715 | 40515 | 2.0% | 1.5(4) | 0.9(5)
$3d^{2}4s(^{4}F)5p$ | $o\tensor{*}[^{3}]{D}{{}^{o}_{3}}$ | 44234 | 45270 | 2.3% | 2.11(8) | 1.61(12)
Other |  |  |  |  |  | 14.9
Total |  |  |  |  |  | 100.4(1.8)

In order to find the magic wavelengths of the clock transitions, it is
necessary to calculate the polarizability of Ti in both the
$a\tensor{*}[^{3}]{F}{{}_{4}}$ and $a\tensor{*}[^{5}]{F}{{}_{5}}$ states over
a wide range of frequencies. Performing this calculation directly remains a
computational challenge for complex atoms like Ti. Direct calculation requires
the inversion of huge matrices — 350,000 $\times$ 350,000 in our case — which
is computationally intractable. Instead, we use an iterative approach included
in the pCI Code Package [8] implementing the CI+all-order technique to
calculate the polarizability of the considered states of Ti. This approach
allows us to get accurate results using the inversion of smaller matrices
(15,000 $\times$ 15,000), making the task feasible. Unfortunately, this method
does not work at all frequencies, owing to the potential divergence of the
iterative process. We successfully obtained static polarizabilities for both
$3d^{2}4s^{2}$ $a\tensor{*}[^{3}]{F}{{}_{4}}$ and $3d^{3}(^{4}F)4s$
$a\tensor{*}[^{5}]{F}{{}_{5}}$ levels, but for dynamic polarizabilities the
calculation diverged for wavelengths shorter than 750 nm (900 nm) for the
$a\tensor{*}[^{3}]{F}{{}_{4}}$ ($a\tensor{*}[^{5}]{F}{{}_{5}}$) level. To
overcome this, we used a combination of the CI+all-order technique and the
sum-over-states method to calculate the scalar, vector and tensor
polarizability from 1100 nm to 400 nm.

The sum-over-states method involves using only bound states of an atom, and
there is always some inaccuracy due to missing contributions from continuum
states and bound states not included in the calculation. For the best
accuracy, it is advisable to use as many states as possible in the sum.
However, there are always limits on the accuracy of calculations of highly
excited states. To balance these trade-offs, we use in the sum-over-state
method for the lower lying states that contribute the majority of the dc
polarizability but still can be properly calculated. For this purpose, we used
73 states to obtain the polarizability of the $3d^{2}4s^{2}$
$a\tensor{*}[^{3}]{F}{{}_{4}}$ level and 49 states for the polarizability of
the $3d^{3}(^{4}F)4s$ $a\tensor{*}[^{5}]{F}{{}_{5}}$ level. The most important
contributions to both polarizabilities are shown in Tables S6, S7. The
polarizability is generally divided into three terms: $\alpha^{S}$ \- scalar,
$\alpha^{V}$-vector, and $\alpha^{T}$ \- tensor polarizabilities. They are
represented for an arbitrary state $i$ as follows [9, 10]:

$\alpha^{S}_{i}(\omega)=\frac{2}{3(2J_{i}+1)}\sum_{n}\frac{(E_{n}-E_{i})|\langle
n||D||i\rangle|^{2}}{(E_{n}-E_{i})^{2}-\omega^{2}}$ (S8)
$\begin{split}\alpha^{V}_{i}(\omega)=C_{1}\sum_{n}(-1)^{J_{n}+J_{i}}\begin{Bmatrix}1&1&1\\\
J_{i}&J_{i}&J_{n}\end{Bmatrix}\\\ \frac{\omega|\langle
n||D||i\rangle|^{2}}{(E_{n}-E_{i})^{2}-\omega^{2}}\end{split}$ (S9)
$\begin{split}\alpha^{T}_{i}(\omega)=C_{2}\sum_{n}(-1)^{J_{n}+J_{i}}\begin{Bmatrix}1&1&2\\\
J_{i}&J_{i}&J_{n}\end{Bmatrix}\\\ \frac{(E_{n}-E_{i})|\langle
n||D||i\rangle|^{2}}{(E_{n}-E_{i})^{2}-\omega^{2}},\end{split}$ (S10)

where

$C_{1}=-2\sqrt{\frac{6J_{i}}{(J_{i}+1)(2J_{i}+1)}}$

and

$C_{2}=4\sqrt{\frac{5J_{i}(2J_{i}-1)}{6(J_{i}+1)(2J_{i}+1)(2J_{i}+3)}}.$

The index $n$ refers to the states in the sum-over-states that contribute to
the polarizability of the state $i$; $E_{n,i}$ is the energy and $J_{n,i}$ is
the total angular momentum of the state; $\langle n||D||i\rangle$ is the
reduced matrix element between the two states, and $\omega$ is the frequency
of the external electric field. The total dynamic polarizability can be
expressed as follows:

$\begin{split}\alpha_{i}(\omega)&=\alpha^{S}_{i}(\omega)+\varepsilon\cos(\theta_{k})\frac{m_{J_{i}}}{2J_{i}}\alpha^{V}_{i}(\omega)+\\\
&+\left(\frac{3\cos^{2}\theta_{p}-1}{2}\right)\frac{3m^{2}_{J_{i}}-J_{i}(J_{i}+1)}{J_{i}(2J_{i}-1)}\alpha^{T}_{i}(\omega),\end{split}$
(S11)

where $\varepsilon$ is the ellipticity of the polarization, $\theta_{k}$ is
the angle between the direction of propagation of the light and the
quantization axis, $\theta_{p}$ is the angle between the polarization of the
light and the quantization axis, and $m_{J_{i}}$ is a magnetic quantum number.

To obtain an accurate value of dynamic polarizability with the sum-over-states
method, one has to estimate the residual contribution to the polarizability
from states that are not included in summation. We made this estimate using
the fact that $|\omega/(E_{n}-E_{i})|\ll 1$ for all such residual states in
the range of wavelengths that we are considering. Indeed, using this ratio as
a small parameter and expanding to the lowest non-zero order in, Eq. S8 can be
simplified to

$\alpha^{S}_{i}(\omega)=\alpha^{S_{N}}_{i}(\omega)+\alpha^{S_{res}}_{i}(\omega)$
(S12)

where

$\alpha^{S_{N}}_{i}(\omega)=\frac{2}{3(2J_{i}+1)}\sum^{N}_{n=1}\frac{(E_{n}-E_{i})|\langle
n|D|i\rangle|^{2}}{(E_{n}-E_{i})^{2}-\omega^{2}}$ (S13)

and where $N$ is the number of states used in direct summation. Moreover, we
can write

$\alpha^{S_{res}}_{i}(\omega)=A_{0}+B_{0}\,\omega^{2}$ (S14)

where $A_{0}$ and $B_{0}$ are expansion constants for the long wavelength
scalar polarizability. The same simplification works for
$\alpha^{V}_{i}(\omega)$ and $\alpha^{T}_{i}(\omega)$, by writing
$\alpha^{V_{N}}_{i}(\omega)$ and $\alpha^{T_{N}}_{i}(\omega)$ as a summation
as in S13. This yields the expansion of the long wavelength residuals:

$\begin{split}\alpha^{V_{res}}_{i}(\omega)&=B_{1}\omega\\\
\alpha^{T_{res}}_{i}(\omega)&=A_{2}+B_{2}\,\omega^{2}\end{split}$ (S15)

where $B_{1}$, $A_{2}$, and $B_{2}$ are additional expansion constants.

Using the results of the sum-over-states method, we identified the four
candidate magic wavelengths discussed in the main text. The atoms were assumed
to have magnetic quantum numbers $m_{J}=0$ and the optical field parameters
were $\varepsilon=0$ and $\theta_{p}=\theta_{k}=90\degree$. However, the more
accurate iterative approach used by the pCI code package was found to not
converge at all of the candidate wavelengths. Using the fact that convergence
in the iterative polarizability can be achieved at $\omega=0.043989$ a.u.
($\lambda=1035.8$ nm) and for all smaller values of $\omega$ down to
$\omega=0$, we subtracted the values of $\alpha_{i}(0.043989)$ and
$\alpha_{i}(0)$ obtained from the sum-over-states method from the
corresponding results computed with the pCI code. In this way, we found the
residuals $\alpha^{S_{res}}_{i}(0)$, $\alpha^{V_{res}}_{i}(0)$,
$\alpha^{T_{res}}_{i}(0)$ and $\alpha^{S_{res}}_{i}(0.043989\,\mathrm{a.u.})$,
$\alpha^{V_{res}}_{i}(0.043989\,\mathrm{a.u.})$,
$\alpha^{T_{res}}_{i}(0.043989\,\mathrm{a.u.})$. This allowed us to determine
the parameters $A_{0,2}$ and $B_{0,1,2}$ in Eqs. S14, S15 and thus extend the
accuracy of the direct iterative polarizability calculation to frequencies
where the iterative calculation fails to converge.

The uncertainty on the polarizabilities were obtained by comparing the
calculations of the more accurate CI+all-order technique with CI+MBPT at the
points where the direct calculation converged. The difference between the
values of the appropriate reduced matrix elements $|\langle
n||D||i\rangle|_{CI+all-order}$ and $|\langle n||D||i\rangle|_{CI+MBPT}$ is an
additional possible inaccuracy of the method and thus is used to estimate the
uncertainties of the polarizabilities. Furthermore, possible errors in the
parameters $A_{0,2}$ and $B_{0,1,2}$ were included in the final uncertainties
as the difference between the correspondent parameters calculated with the
CI+all-order and CI+MBPT methods.

##  S4 Dipole-Dipole Interactions

As discussed in the main text, dipole-dipole interactions underlie several
effects that impact the operation of a Ti atomic clock. One can distinguish
between interactions that are inelastic or elastic in the motional degrees of
freedom. Inelastic interactions can be described as spin relaxation, a dipole-
mediated conversion of internal Zeeman energy into external motional energy.
For example, in an optical lattice spin relaxation may couple atoms from lower
to higher bands of the lattice. As discussed in the main text, inelastic
motional interactions can be suppressed by trapping atoms in a lattice with a
sufficiently large band gap [11].

One may then focus on elastic motional interactions. We describe these
interactions purely in the spin sector using the secular Hamiltonian, which
accounts for cycle-averaging over the Larmor precession of the atomic spins
[12]. This secular Hamiltonian, whose form is presented also in the main text,
is given for two atoms as

$H_{dd}=\frac{\mu_{0}\mu_{B}^{2}}{4\pi}\frac{g_{J_{1}}g_{J_{2}}}{r_{12}^{3}}\left(1-3\cos^{2}\theta_{12}\right)\\\
\times\left(J^{z}_{1}J^{z}_{2}-\frac{1}{4}\left(J^{+}_{1}J^{-}_{2}+J^{-}_{1}J^{+}_{2}\right)\right)$
(S16)

with $1$ and $2$ labelling the two atoms, and $r_{12}$ and $\theta_{12}$
describing their position difference vector and the angle it makes with the
quantization axis.

One can consider separately two effects of this secular Hamiltonian. The first
is a spin-elastic interaction, which is diagonal in the separable basis of
magnetic sublevel states. This shift is zero on the $m_{J}=0$ magnetic
sublevels and therefore does not affect a clock based on an
$m_{J}=m^{\prime}_{J}=0$ transition.

The second effect is the spin mixing interaction, which is off-diagonal in the
separable magnetic sublevel basis. This interaction conserves the total
magnetic quantum number of the two atoms,
$m_{J}^{(\mathrm{tot})}=m_{J}^{(1)}+m_{J}^{(2)}$, but changes the magnetic
quantum numbers of the individual atoms. In the absence of dipolar
interactions, the entire manifold of two-atom states with identical
$m_{J}^{(\mathrm{tot})}$ is degenerate for atoms with equal Zeeman splittings.
Dipolar interactions can then generate significant mixing and energy shifts
within this manifold, leading to imprecise measurement of the clock
transition.

While several methods have been developed in NMR to control dipolar spin
mixing, e.g. multiple pulse sequences [13] and magic angle spinning [14],
these techniques are not needed to suppress spin mixing in a Ti clock system.
As described in the main text, spin mixing within the clock states is
mitigated by the tensor light shift imposed by the optical lattice beams. From
Eq. S11, the tensor light shift includes a part proportional to $m^{2}_{J}$,
which splits the degeneracy of the aforementioned states and energetically
suppresses the spin mixing process.

Figure S1: The secular dipole-dipole interaction of two atoms in the
$a^{3}F_{4}$ (g) and $a^{5}F_{5}$ (e) clock states. The $g$ and $e$ states
have angular momentum quantum numbers $J=4$ and $J=5$, giving rise to $2J+1$
magnetic sublevels each. For brevity, the figure shows only three of these
$m_{J}$ sublevels in each state, split by Zeeman shifts. The clock drive
$\Omega_{M1}$ couples the $|g_{m_{J}=0}\rangle$ and $|e_{m_{J}=0}\rangle$
states, and $H_{dd}$ couples the subspaces of the two atoms. Figure S2: (left)
Ramsey contrast of the clock transition as a function of the free evolution
time $T$. The contrast, shown in violet (green), dies quickly (slowly) when
the ac Stark shift, $H_{ac}$, is excluded (included) from the simulation. Note
the split in the $T$ axis and change in scale at 0.25 s. (right) The resulting
Ramsey fringes for $T=0.2$ s (indicated by circles in the left plot). We plot
the probability an atom is found in state $|e_{0}\rangle$ as a function of the
detuning $\delta$ from the clock transition.. Figure S3: (left) The 2-atom
level structure with and without the ac Stark shifts applied ($H_{ac}$). Only
states that are symmetric under particle exchange are shown, as these are the
only states involved in the dynamics. The states $S(|g^{(1)}_{m_{J}\neq
0};e^{(2)}_{-m_{J}}\rangle)$ are omitted because they are split from the
$S(|g^{(1)}_{0};e^{(2)}_{0}\rangle)$ state by the differential Zeeman shift.
The dotted lines show that the degeneracy of the $m^{tot}_{J}=0$ sublevels is
lifted when $H_{ac}$ is turned on. The five boxed levels include the clock
states and the states most strongly coupled to them by $H_{dd}$. (right) The
simplified picture, including only the levels boxed in the left panel.
$H_{dd}$ couples the states $|\xi^{(1)}_{0};\xi^{(2)}_{0}\rangle$ and
$S(|\xi^{(1)}_{m_{J}};\xi^{(2)}_{-m_{J}}\rangle)$ with rate
$\Omega^{\xi}_{SM}$.

To study the suppression of spin mixing, we simulate the secular dipole-dipole
interaction of two nearest neighbor atoms in an optical lattice with and
without accounting for the lattice-induced ac Stark shift. Figure S1 shows a
schematic of the system under consideration. We notate the single atom states
by $|\xi^{(i)}_{m_{J}}\rangle$ where $\xi\in\\{g,e\\}$ refers to the upper or
lower clock states, the superscript denotes the $i^{th}$atom, and the $m_{J}$
subscript is the magnetic sublevel. We use $g$ to refer to the lower
$a^{3}F_{4}$ clock state, and $e$ to refer to the upper $a^{5}F_{5}$ state.
The two atom system consists of $[(2J_{g}+1)+(2J_{e}+1)]^{2}=400$ states.

We simulate a simple Ramsey interferometry sequence which includes the
dynamics of $H_{dd}$, the Zeeman Hamiltonian $H_{Z}$, and, optionally, the ac
Stark Hamiltonian $H_{ac}$. We initialize two atoms in the
$|g^{(1)}_{0};g^{(2)}_{0}\rangle$ state, apply a $\pi/2$ pulse to each atom on
the $g_{0}\rightarrow e_{0}$ clock transition, allow the two-atom state to
evolve for a time $T$ under $H_{Z}$, $H_{dd}$, and (optionally) $H_{ac}$;
apply a second $\pi/2$ pulse to each atom; and then determine the probability
of an atom being in the $e_{0}$ state. We vary the detuning of the clock drive
frequency, $\delta$, to generate a Ramsey interferometry fringe. From this
fringe, we obtain the contrast $C(T)=(\max P_{e}(T,\delta)-\min
P_{e}(T,\delta))$.

Figure S2 shows the results of the simulation. The left panel demonstrates the
decay of the Ramsey contrast with and without $H_{ac}$ included. We break the
axis at 0.25 s to illustrate that the tensor ac Stark shift extends the decay
time of the contrast significantly. Because we only simulate unitary dynamics
of two neighboring atoms, revivals of the contrast are observed in the
simulation beyond the times plotted in Figure S2, but these would not occur in
a true many-body situation as the coherence would spread between many
particles and be lost. The right panel shows the resulting Ramsey fringes
taken at the time highlighted on the left side of the figure. When no optical
lattice is applied, the coherence on the clock transition quickly vanishes,
leading to a loss of the Ramsey signal. The fringe survives for $\sim 85$ s
when the lattice beams are on.

Figure S3 gives a simplified picture of the level structure at play.
$S(|\psi\rangle)$ is defined as the function that symmetrizes a multiparticle
state by adding states with swapped $m_{J}$ and, if necessary, states in which
the excited atom is switched. The initial state of the Ramsey sequence
($|g^{(1)}_{0};g^{(2)}_{0}\rangle$) is symmetric under particle exchange and
the Hamiltonian commutes with the exchange operator, so all states involved in
the dynamics must remain symmetric. The left panel of Figure S3 illustrates
that in the absence of a tensor light field or dipole-dipole shifts, the
$|\xi^{(1)}_{0};\xi^{(2)}_{0}\rangle$ states are degenerate with all the
symmetrized states
$S(|\xi^{(1)}_{m_{J}};\xi^{(2)}_{-m_{J}}\rangle)=1/\sqrt{2}(|\xi^{(1)}_{m_{J}};\xi^{(2)}_{-m_{J}}\rangle+|\xi^{(1)}_{-m_{J}};\xi^{(2)}_{m_{J}}\rangle)$.
On the other hand, the figure shows the singly excited state
$S(|g^{(1)}_{0};e^{(2)}_{0}\rangle)=1/\sqrt{2}(|g^{(1)}_{0};e^{(2)}_{0}\rangle+|e^{(1)}_{0};g^{(2)}_{0}\rangle)$
is not degenerate with states of mixed angular momentum (e.g.
$S(|g^{(1)}_{1};e^{(2)}_{-1}\rangle)$) because the $g$ and $e$ states have
different Zeeman splittings.

The dotted lines show the lifting of the degeneracy of the spin-mixed states
by the ac Stark shift ($H_{ac}$). The splitting leads to the simplified level
structure shown in the right panel of Figure S3. After the splitting, only the
$S(|\xi^{(1)}_{1};\xi^{(2)}_{-1}\rangle)$ states remain energetically nearby
the $|\xi^{(1)}_{0};\xi^{(2)}_{0}\rangle$ clock states. The splitting between
the $|\xi^{(1)}_{0};\xi^{(2)}_{0}\rangle$ and
$S(|\xi^{(1)}_{1};\xi^{(2)}_{-1}\rangle)$ states by the tensor ac light shift
is denoted $\Delta E_{tens}^{\xi}$. With the parameters previously used to
describe the optical lattice, this splitting is $h\times 4(2)$ kHz for $gg$
atoms, $h\times 4.8(6)$ kHz for $ee$ atoms. The spin mixing term in $H_{dd}$
couples the nearby states with rates $\Omega^{\xi}_{SM}$ ($h\times 2.4$ Hz for
$gg$ atoms, $h\times 4.6$ Hz for $ee$ atoms). The coupling produces first-
order level mixing at the $\Omega^{\xi}_{SM}/\Delta E^{\xi}_{tens}\sim
10^{-3}$ level between these states — small enough to not directly impact the
coherence of the clock.

However at second-order, both of the clock states will experience an energy
shift of $\Delta E_{\xi\xi}\sim-(\Omega^{\xi}_{SM})^{2}/\Delta
E^{\xi}_{tens}$. It is clear that the difference between these two shifts
leads to a shift of the clock frequency, which from the simplified treatment
is $\sim 3$ mHz for two atoms. The sum of the shifts to the clock states also
leads to decoherence through entanglement generation. To understand this
effect, we consider the state of the two atom system after it has evolved for
a time $t$ during the Ramsey sequence:

$\displaystyle|\psi(t)\rangle=\frac{1}{2}\big{[}e^{-i\Delta E_{gg}t/\hbar}$
$\displaystyle|g_{0}^{(1)};g_{0}^{(2)}\rangle+e^{-i\Delta
E_{ee}t/\hbar}|e_{0}^{(1)};e_{0}^{(2)}\rangle$
$\displaystyle+|g_{0}^{(1)};e_{0}^{(2)}\rangle+|e_{0}^{(1)};g_{0}^{(2)}\rangle\big{]}$
(S17)

where we’ve included only the non-trivial phases accumulated from the second-
order dipole-dipole interaction. If we trace over the second atom state space,
we find the single atom reduced density matrix is:

$\displaystyle\rho^{(1)}(t)=$ $\displaystyle|g^{(1)}_{0}\rangle\langle
g^{(1)}_{0}|+|e^{(1)}_{0}\rangle\langle e^{(1)}_{0}|$
$\displaystyle+\big{[}(1+e^{-i(\Delta E_{gg}+\Delta
E_{ee})t/\hbar})|g^{(1)}_{0}\rangle\langle e^{(1)}_{0}|+h.c.\big{]}$ (S18)

From this, we can see the coherence is fully lost when $(\Delta E_{gg}+\Delta
E_{ee})t/\hbar=\pm\pi$. Given the second-order dipole-dipole shifts calculated
above, this corresponds to a full loss of coherence at $t\sim 86$ s. This is
in agreement with the lifetime seen in the simulation from Figure S2.

## References

  * Safronova  _et al._ [2009] M. S. Safronova, M. G. Kozlov, W. R. Johnson, and D. Jiang, Development of a configuration-interaction plus all-order method for atomic calculations, Physical Review A 80, 012516 (2009).
  * Kramida and Ralchenko [1999] A. Kramida and Y. Ralchenko, NIST Atomic Spectra Database, NIST Standard Reference Database 78 (1999), type: dataset.
  * Safronova  _et al._ [2013] M. S. Safronova, S. G. Porsev, U. I. Safronova, M. G. Kozlov, and C. W. Clark, Blackbody-radiation shift in the Sr optical atomic clock, Physical Review A 87, 012509 (2013).
  * Eustice  _et al._ [2020] S. Eustice, K. Cassella, and D. Stamper-Kurn, Laser cooling of transition-metal atoms, Physical Review A 102, 053327 (2020).
  * Dzuba  _et al._ [1998] V. A. Dzuba, V. V. Flambaum, M. G. Kozlov, and S. G. Porsev, Using effective operators in calculating the hyperfine structure of atoms, Journal of Experimental and Theoretical Physics 87, 885 (1998).
  * Porsev  _et al._ [1999a] S. G. Porsev, Y. G. Rakhlina, and M. G. Kozlov, Electric-dipole amplitudes, lifetimes, and polarizabilities of the low-lying levels of atomic ytterbium, Physical Review A 60, 2781 (1999a).
  * Porsev  _et al._ [1999b] S. G. Porsev, Y. G. Rakhlina, and M. G. Kozlov, Calculation of hyperfine structure constants for ytterbium, Journal of Physics B: Atomic, Molecular and Optical Physics 32, 1113 (1999b).
  * Cheung  _et al._ [2021] C. Cheung, M. Safronova, and S. Porsev, Scalable Codes for Precision Calculations of Properties of Complex Atomic Systems, Symmetry 13, 621 (2021).
  * Le Kien  _et al._ [2013] F. Le Kien, P. Schneeweiss, and A. Rauschenbeutel, Dynamical polarizability of atoms in arbitrary light fields: general theory and application to cesium, The European Physical Journal D 67, 10.1140/epjd/e2013-30729-x (2013).
  * Bai  _et al._ [2022] J. Bai, X. Wang, X. Hou, W. Liu, and J. Wang, Angle-Dependent Magic Optical Trap for the 6S1/2-nP3/2 Rydberg Transition of Cesium Atoms, Photonics 9, 303 (2022).
  * de Paz  _et al._ [2013] A. de Paz, A. Chotia, E. Maréchal, P. Pedri, L. Vernac, O. Gorceix, and B. Laburthe-Tolra, Resonant demagnetization of a dipolar Bose-Einstein condensate in a three-dimensional optical lattice, Physical Review A 87, 051609 (2013).
  * Chomaz  _et al._ [2022] L. Chomaz, I. Ferrier-Barbut, F. Ferlaino, B. Laburthe-Tolra, B. L. Lev, and T. Pfau, Dipolar physics: A review of experiments with magnetic quantum gases (2022), number: arXiv:2201.02672 arXiv:2201.02672 [cond-mat, physics:physics, physics:quant-ph].
  * Choi  _et al._ [2020] J. Choi, H. Zhou, H. S. Knowles, R. Landig, S. Choi, and M. D. Lukin, Robust Dynamic Hamiltonian Engineering of Many-Body Spin Systems, Physical Review X 10, 031002 (2020).
  * Polenova  _et al._ [2015] T. Polenova, R. Gupta, and A. Goldbourt, Magic Angle Spinning NMR Spectroscopy: A Versatile Technique for Structural and Dynamic Analysis of Solid-Phase Systems, Analytical Chemistry 87, 5458 (2015).