# Detecting Scams Using Large Language Models

Liming Jiang  Harbin University of Science and TechnologyHarbinHeilongjiang
China

###### Abstract.

Large Language Models (LLMs) have gained prominence in various applications,
including security. This paper explores the utility of LLMs in scam detection,
a critical aspect of cybersecurity. Unlike traditional applications, we
propose a novel use case for LLMs to identify scams, such as phishing, advance
fee fraud, and romance scams. We present notable security applications of LLMs
and discuss the unique challenges posed by scams. Specifically, we outline the
key steps involved in building an effective scam detector using LLMs,
emphasizing data collection, preprocessing, model selection, training, and
integration into target systems. Additionally, we conduct a preliminary
evaluation using GPT-3.5 and GPT-4 on a duplicated email, highlighting their
proficiency in identifying common signs of phishing or scam emails. The
results demonstrate the models’ effectiveness in recognizing suspicious
elements, but we emphasize the need for a comprehensive assessment across
various language tasks. The paper concludes by underlining the importance of
ongoing refinement and collaboration with cybersecurity experts to adapt to
evolving threats.

##  1\. INTRODUCTION

A large language model, often referred to as a "large language model" or
"LLM," is a type of artificial intelligence (AI) model that is trained on vast
amounts of text data to understand and generate human-like text. These models
are designed to process and generate natural language text, making them
capable of tasks like text generation, text classification, language
translation, question answering, and more. They have become increasingly
popular in recent years due to their impressive capabilities.

Key characteristics of large language models include: (1) Large language
models are characterized by their immense size, often having hundreds of
millions to billions of parameters. These parameters are the model’s learned
weights, which determine its ability to understand and generate text. (2)
Large language models are versatile and can be adapted to perform various
natural language processing tasks with minimal task-specific training data.
This adaptability has made them popular in a wide range of applications. (3)
These models are known for their ability to generate text that is coherent and
human-like, often blurring the line between machine-generated and human-
generated content.

Recently, LLMs have found various security applications due to their ability
to analyze and generate text, which can be instrumental in identifying and
addressing security threats. Some notable security applications of LLMs
include:

  * •

Phishing Detection: LLMs can assist in the detection of phishing emails and
websites by analyzing the content and language used in these fraudulent
communications. They can flag suspicious messages or URLs based on known
phishing patterns and emerging threats.

  * •

Sentiment Analysis: LLMs can be employed to monitor social media and online
forums for discussions related to security incidents or vulnerabilities.
Analyzing sentiment can help identify potential threats or vulnerabilities
early, allowing for proactive response.

  * •

Threat Intelligence: Large language models can process vast amounts of
unstructured data to extract information about potential threats and
vulnerabilities. They can help security analysts by summarizing security
reports, identifying emerging threats, and providing context to aid decision-
making.

  * •

Malware Analysis: LLMs can assist in analyzing malware reports, code samples,
and security documentation. They can help security professionals understand
the behavior of new malware strains and generate signatures or heuristics for
detection.

  * •

Vulnerability Assessment: LLMs can analyze security vulnerability reports,
software documentation, and code repositories to assist in identifying and
prioritizing software vulnerabilities, which is crucial for timely patching
and risk mitigation.

Different from those applications, we propose to use LLM for scam detection.
Scams are deceptive practices designed to exploit individuals, organizations,
or businesses, often by tricking them into giving away money or personal
information. Common scams include phishing, where fraudulent emails and
websites impersonate legitimate sources; advance fee fraud, which promises
rewards in exchange for upfront payments; romance scams that use fake online
dating profiles to solicit money; and investment schemes promising high
returns. Tech support scams, online shopping scams, lottery and prize fraud,
IRS impersonation, and charity scams are also prevalent. Vigilance and
skepticism when encountering unsolicited offers or requests for personal
information are crucial to avoid falling victim to these fraudulent schemes.
Figure 1 shows an example of a scam.

Figure 1. An example of a scam.

Building an effective scam detector using LLM involves several key steps.
Firstly, it requires comprehensive data collection encompassing various scam
types and legitimate content to create a diverse dataset. Data preprocessing
is then conducted to clean, standardize, and format the text for training.
Labeling is essential, with annotators or crowdsourcing platforms labeling
each text as "scam" or "legitimate." The right LLM architecture, like GPT-3 or
BERT, is chosen, and fine-tuning on a task-specific dataset is often
necessary. Supervised learning is employed for training, followed by rigorous
evaluation using metrics like precision, recall, and accuracy. Hyperparameter
tuning refines the model, and false positives are analyzed to improve
precision. Setting an appropriate confidence threshold for classification is
crucial, and finally, integration into the target system ensures real-time
scam detection. Collaboration with domain experts and cybersecurity
professionals is vital for ongoing refinement and adaptation to emerging
threats.

However, the goal of this paper is to introduce and explain a foundational
concept while also conducting preliminary evaluations. To achieve this, we
duplicated an email and analyzed it using two advanced language models:
GPT-3.5 and GPT-4. The results shown that the email in question is flagged as
suspicious due to various red flags, such as an unusual sender address, poor
grammar and spelling, suspicious links, an unusual request, lack of
personalization, an unusual sender name, and a generic sign-off. Two separate
analyses, one by GPT-3.5 and another by GPT-4, are presented. Both models
identify similar issues in the email, indicating their proficiency in
recognizing common signs of phishing or scam emails. However, the paragraph
emphasizes that evaluating language models goes beyond a single task, and
their effectiveness can vary depending on the complexity of the text.

Figure 2. Workflow of the method

The conclusion is that while both GPT-3.5 and GPT-4 perform well in this
specific analysis, a more comprehensive assessment is needed to determine
their relative strengths and weaknesses across various natural language
understanding and generation tasks.

##  2\. LITERATURE REVIEW

Numerous surveys and studies have already been conducted to explore the
multifaceted landscape of Large Language Models (LLMs), each with a unique
focus and perspective. These comprehensive surveys have touched upon various
aspects of LLMs, including their evolution, taxonomy, and applications across
different domains such as software engineering and medicine (chang2023survey,
; zhao2023survey, ; wu2023survey, ; hadi2023survey, ; wu2023unveiling, ;
bowman2023eight, ; zhao2023knnicl, ; fan2023large, ; hou2023large, ;
thirunavukarasu2023large, ; clusmann2023future, ).

However, this paper takes a distinctive approach by primarily emphasizing the
security and privacy facets of LLMs. As we delve into an examination of the
existing literature related to this specific focus, we uncover valuable
insights into how LLMs, particularly ChatGPT, have the potential to reshape
the current cybersecurity landscape. These insights stem from a blend of
technical and social considerations, with a particular inclination towards
understanding the social dynamics that LLMs introduce in the context of
cybersecurity (caven2023more, ).

Moreover, several studies have probed the implications of ChatGPT in
cybersecurity, emphasizing its practical applications such as code security
and malware detection (al2023chatgpt, ; marshall2023effects, ). These studies
acknowledge the transformative potential of LLMs in enhancing security
measures. However, it is worth noting that while they discuss the positive
aspects of LLMs, they may not extensively address the potential cybersecurity
threats that these models themselves might introduce. Yifan et al.
(yao2023survey, ) shed light on how LLMs can both enhance and jeopardize
cybersecurity. It underscores the need for continued research in this area to
harness the positive aspects of LLMs while mitigating their potential risks
and vulnerabilities.

In this landscape, Dhoni et al. (dhoni2023synergizing, ) have made notable
contributions by showcasing how LLMs can significantly aid security analysts
in developing effective solutions against cyber threats. Nevertheless, their
work does not delve deeply into the potential vulnerabilities or risks that
may arise from the integration of LLMs into cybersecurity practices.

##  3\. METHODOLOGY

Building an effective scam detector using LLMs is an ongoing process that
requires constant refinement and adaptation to counter new scamming techniques
and emerging threats. Collaboration with domain experts and cybersecurity
professionals is essential for a successful scam detection system. As shown in
Figure, we list the steps:

  1. (1)

Data Collection: The first crucial step in creating a scam detector with LLMs
is data collection. To build a reliable and robust model, it’s essential to
gather a diverse and extensive dataset that includes various types of known
scams and legitimate content. This dataset should encompass a wide range of
scam tactics, languages, and contexts, ensuring that the model can effectively
recognize and differentiate between scams and legitimate communications.

  2. (2)

Data Preprocessing: Once you’ve amassed your dataset, the next step is data
preprocessing. This involves cleaning and transforming the data to make it
suitable for training. Common preprocessing tasks include removing irrelevant
information, formatting the text consistently, and addressing issues like
spelling errors or inconsistent formatting. Tokenization and stemming may also
be applied to standardize the text for analysis.

  3. (3)

Labeling: The labeling process is vital for supervised learning. Annotators or
crowdsourcing platforms should be employed to label each piece of text in your
dataset as either "scam" or "legitimate." It’s crucial to ensure that the
labeling process maintains a high level of accuracy and consistency. Inter-
annotator agreement should be considered to gauge the reliability of the
labels.

  4. (4)

Model Selection: Choosing the right LLM architecture is a pivotal decision in
the development of your scam detection system. There are several LLM options
available, including GPT-3, BERT, and custom-built models. The choice depends
on your specific requirements and the complexity of the task. Additionally,
fine-tuning the selected model on a task-specific dataset is often necessary
to optimize its performance for scam detection.

  5. (5)

Training: With a labeled dataset and a selected model, it’s time to train the
LLM for scam detection. Supervised learning techniques are applied, allowing
the model to learn from the labeled examples in your dataset. The goal here is
for the model to become proficient at classifying text as either a scam or
legitimate based on the provided labels.

  6. (6)

Evaluation: After training, the model’s performance must be rigorously
evaluated. Several evaluation metrics, such as precision, recall, F1 score,
accuracy, or area under the ROC curve (AUC), can be used to assess its
effectiveness. Cross-validation or hold-out validation sets can help ensure
that the model performs well across different datasets and scenarios.

  7. (7)

Hyperparameter Tuning: To enhance the model’s accuracy and robustness,
hyperparameter tuning is conducted. Parameters like learning rate, batch size,
and model architecture are adjusted and fine-tuned to optimize the model’s
performance. This iterative process helps in achieving better results.

  8. (8)

False Positive Analysis: An essential step in the development of a scam
detector is the analysis of false positives generated by the model. By
carefully examining and addressing these false alarms, the model can be
refined to reduce the number of legitimate communications mistakenly
classified as scams. This iterative process is vital for improving the
detector’s precision.

  9. (9)

Threshold Setting: Determining an appropriate confidence threshold for
classification is a critical decision. Text with a confidence score above this
threshold is classified as a scam, while those below it are considered
legitimate. The threshold should strike a balance between minimizing false
positives and false negatives, aligning with your desired detection strategy.

  10. (10)

Integration: Once the model is trained and fine-tuned, it needs to be
integrated into your application, platform, or system. This integration should
enable the model to efficiently process incoming text data, make predictions
in real-time, and take appropriate actions when scams are detected.

##  4\. PRELIMINARY ASSESSMENT

In the context of this paper, our primary objective is to introduce and
elucidate a foundational concept while also performing preliminary
evaluations. To accomplish this, we have taken the step of duplicating the
email mentioned earlier and have subsequently fed this duplicated content into
two advanced language models, namely GPT-3.5 and GPT-4. The ensuing feedback
received from these models provides valuable insights and assessments, which
we shall explore and expound upon in greater detail within the subsequent
sections of this paper. The email for test is the email displayed in Figure 1.

GPT3.5. This email is very likely to be a scam. There are several red flags
indicating that it’s not legitimate:

  * •

Email Address:  The email is sent from an unusual email address,
"217376@inha.ac.kr," which does not appear to be related to Rackspace, a
reputable hosting and cloud computing company.

  * •

Poor Grammar and Spelling: The email contains several grammatical errors and
awkward phrasing, such as "we have suspend your login access" and "Some or all
of your emails may have been deleted." Legitimate companies typically have
professional communication.

  * •

Suspicious Links: The email contains a link to a website called
"wwwthefitdollar.com/gabbyr," which is not related to Rackspace or any
legitimate financial institution. Scammers often use deceptive links to
phishing websites to steal your personal information.

  * •

Unusual Request: The email asks you to click on a link to remove restrictions
on your account, which is a common tactic used by scammers to trick recipients
into providing sensitive information.

  * •

Lack of Personalization: The email does not address you by name, which is
unusual for legitimate businesses that often personalize their communications.

  * •

Unusual Sender Name: The sender’s name appears as "Rackspace Support," but the
email address does not match this name, further indicating that it may be a
scam.

  * •

Generic Sign-off: The email closes with a generic sign-off, "Sincerely, Online
Email Team," without providing any specific contact information or phone
number.

In summary, this email displays numerous signs of a phishing attempt or scam.
It’s crucial not to click on any links or provide any personal information in
response to such emails. Instead, if you have concerns about your account,
always contact the company directly through their official website or customer
support phone number to verify the information.

GPT4. The email you received contains several signs that suggest it could be a
scam:

  * •

Suspicious Sender Address: The email is from a sender with an address ending
in<EMAIL_ADDRESS>which is not a domain typically associated with Rackspace.
Legitimate emails from companies usually come from their own domain (e.g.,
@rackspace.com).

  * •

Unusual Links: The links provided in the email (like "wwwthefitdollar.com" and
a strangely formatted Rackspace link) do not seem to be legitimate Rackspace
domains. Scammers often use misleading URLs that resemble legitimate ones to
trick recipients into clicking them.

  * •

Grammar and Spelling Errors: The email contains several grammatical and
spelling errors ("suspend" instead of "suspended", "your login access.Some",
etc.), which are not expected in official communication from a reputable
company like Rackspace.

  * •

Sense of Urgency and Fear: The email creates a sense of urgency by stating
that your login access has been suspended and that your emails may have been
deleted. Scammers often use these tactics to prompt a quick, emotional
response.

  * •

Request Not to Reply: The instruction not to reply to the email is suspicious.
Legitimate companies usually provide a way for you to contact them for
verification.

Generic Salutation: The email addresses you as "Dear Customer" instead of
using your name. Legitimate emails from your service providers usually address
you by name.

Considering these factors, it is highly advisable not to click on any links or
provide any personal information. You should directly contact Rackspace
through their official website or customer support channels to verify the
authenticity of the email

Result Analysis: While both GPT-3.5 and GPT-4 appear to perform similarly in
their assessment of the email, it’s important to note that the evaluation of
language models goes beyond just a single task or context. The effectiveness
of these models can vary depending on the complexity and nuances of the text
being analyzed. In this particular instance, where the email is relatively
straightforward and its red flags are apparent, both GPT-3.5 and GPT-4 are
able to identify the key issues with the email, such as the suspicious sender
address, unusual links, grammar and spelling errors, the sense of urgency, and
the generic salutation. Their assessments align closely, demonstrating that
both models are proficient in recognizing common signs of phishing or scam
emails. However, when assessing the overall performance of language models
like GPT-3.5 and GPT-4, it’s essential to consider their capabilities across a
wide range of tasks and domains. These models are often evaluated on their
ability to understand and generate human-like text, provide contextually
relevant responses, and handle more intricate language tasks. Furthermore, the
quality of results can also depend on the training data, fine-tuning methods,
and the specific versions of these models. It’s advisable to conduct
comprehensive evaluations and comparisons on various tasks and datasets to
determine their relative strengths and weaknesses accurately. In conclusion,
while both GPT-3.5 and GPT-4 demonstrate comparable proficiency in analyzing
this particular email for signs of phishing, a more in-depth and comprehensive
assessment would be needed to definitively determine which model excels in a
broader spectrum of natural language understanding and generation tasks.

## CONCLUSION

In conclusion, this paper has explored the potential application of large
language models (LLMs) in the critical domain of scam detection within the
cybersecurity landscape. LLMs, with their remarkable adaptability and natural
language understanding abilities, offer a promising avenue for enhancing the
identification and mitigation of fraudulent schemes that pose a significant
threat to individuals and organizations alike. Through an analysis of various
security applications of LLMs and a detailed description of the steps involved
in building an effective scam detector, this paper has laid the groundwork for
harnessing the power of LLMs in combating online scams.

Furthermore, the preliminary evaluation conducted using advanced language
models, GPT-3.5 and GPT-4, has demonstrated their proficiency in recognizing
common red flags associated with scam emails. However, it is crucial to
acknowledge that evaluating LLMs extends beyond a single task, and their
effectiveness may vary across different linguistic complexities and contexts.
Moving forward, additional research is necessary to comprehensively assess the
strengths and weaknesses of LLMs in various scam detection scenarios.
Collaboration with domain experts and continuous adaptation to emerging
threats are vital aspects of this endeavor. By further refining and optimizing
LLMs for scam detection, we can bolster online security measures, thereby
safeguarding individuals and organizations from financial and personal harm
caused by deceptive practices. Ultimately, the integration of LLMs into
cybersecurity protocols holds the potential to significantly enhance our
ability to combat online scams in an ever-evolving digital landscape.

## References

  * (1) Y. Chang, X. Wang, J. Wang, Y. Wu, K. Zhu, H. Chen, L. Yang, X. Yi, C. Wang, Y. Wang _et al._ , “A survey on evaluation of large language models,” _arXiv preprint arXiv:2307.03109_ , 2023.
  * (2) W. X. Zhao, K. Zhou, J. Li, T. Tang, X. Wang, Y. Hou, Y. Min, B. Zhang, J. Zhang, Z. Dong _et al._ , “A survey of large language models,” _arXiv preprint arXiv:2303.18223_ , 2023.
  * (3) J. Wu, S. Yang, R. Zhan, Y. Yuan, D. F. Wong, and L. S. Chao, “A survey on llm-gernerated text detection: Necessity, methods, and future directions,” _arXiv preprint arXiv:2310.14724_ , 2023.
  * (4) M. U. Hadi, R. Qureshi, A. Shah, M. Irfan, A. Zafar, M. Shaikh, N. Akhtar, J. Wu, and S. Mirjalili, “A survey on large language models: Applications, challenges, limitations, and practical usage,” _TechRxiv_ , 2023.
  * (5) X. Wu, R. Duan, and J. Ni, “Unveiling security, privacy, and ethical concerns of chatgpt,” 2023.
  * (6) S. R. Bowman, “Eight things to know about large language models,” _arXiv preprint arXiv:2304.00612_ , 2023.
  * (7) W. Zhao, Y. Liu, Y. Wan, Y. Wang, Q. Wu, Z. Deng, J. Du, S. Liu, Y. Xu, and P. S. Yu, “knn-icl: Compositional task-oriented parsing generalization with nearest neighbor in-context learning,” 2023.
  * (8) A. Fan, B. Gokkaya, M. Harman, M. Lyubarskiy, S. Sengupta, S. Yoo, and J. M. Zhang, “Large language models for software engineering: Survey and open problems,” 2023.
  * (9) X. Hou, Y. Zhao, Y. Liu, Z. Yang, K. Wang, L. Li, X. Luo, D. Lo, J. Grundy, and H. Wang, “Large language models for software engineering: A systematic literature review,” _arXiv preprint arXiv:2308.10620_ , 2023.
  * (10) A. J. Thirunavukarasu, D. S. J. Ting, K. Elangovan, L. Gutierrez, T. F. Tan, and D. S. W. Ting, “Large language models in medicine,” _Nature medicine_ , vol. 29, no. 8, pp. 1930–1940, 2023.
  * (11) J. Clusmann, F. R. Kolbinger, H. S. Muti, Z. I. Carrero, J.-N. Eckardt, N. G. Laleh, C. M. L. Löffler, S.-C. Schwarzkopf, M. Unger, G. P. Veldhuizen _et al._ , “The future landscape of large language models in medicine,” _Communications Medicine_ , vol. 3, no. 1, p. 141, 2023.
  * (12) P. Caven, “A more insecure ecosystem? chatgpt’s influence on cybersecurity,” _ChatGPT’s Influence on Cybersecurity (April 30, 2023)_ , 2023.
  * (13) M. Al-Hawawreh, A. Aljuhani, and Y. Jararweh, “Chatgpt for cybersecurity: practical applications, challenges, and future directions,” _Cluster Computing_ , vol. 26, no. 6, pp. 3421–3436, 2023.
  * (14) J. Marshall, “What effects do large language models have on cybersecurity,” 2023.
  * (15) Y. Yao, J. Duan, K. Xu, Y. Cai, E. Sun, and Y. Zhang, “A survey on large language model (llm) security and privacy: The good, the bad, and the ugly,” _arXiv preprint arXiv:2312.02003_ , 2023.
  * (16) P. Dhoni and R. Kumar, “Synergizing generative ai and cybersecurity: Roles of generative ai entities, companies, agencies, and government in enhancing cybersecurity,” 2023.


# Kraken: A Direct Event/Frame-Based Multi-sensor Fusion SoC for Ultra-
Efficient Visual Processing in Nano-UAVs

Alfio Di Mauro24, Moritz Scherer24, Davide Rossi3, Luca Benini23  2 ETH
Zürich, Switzerland, 3 University of Bologna, Italy 4 equal contribution

##  I Introduction

Small-size unmanned aerial vehicles (UAV) have the potential to dramatically
increase safety and reduce cost in applications like critical infrastructure
maintenance and post-disaster search and rescue[1]. Many scenarios require
UAVs to shrink toward nano and pico-size form factors [2]. The key open
challenge to achieve true autonomy on Nano-UAVs is to run complex visual tasks
like object detection, tracking, navigation and obstacle avoidance fully on
board, at high speed and robustness, under tight payload and power
constraints. With the Kraken System-on-Chip (SoC), fabricated in
$22\text{\,}\mathrm{nm}$ FDX technology (Fig. 7,7), we demonstrate a multi-
visual-sensor capability exploiting both event-based and BW/RGB imagers,
combining their output for multi-functional visual tasks previously impossible
on a single low-power chip for Nano-UAVs[1]. Kraken is an ultra-low-power,
heterogeneous SoC architecture integrating three acceleration engines and a
vast set of peripherals to enable efficient interfacing with standard frame-
based sensors and novel event-based Dynamic Vision Sensors (DVSs) [3]. Kraken
enables highly sparse event-driven sub-$\text{\,}\mathrm{\SIUnitSymbolMicro
J}$/inf Spiking Neural Network (SNN) inference on a dedicated neuromorphic
energy-proportional accelerator. Moreover, it can perform frame-based
inference by combining a
$1.8\text{\,}\mathrm{T}\mathrm{O}\mathrm{p}\mathrm{/}\mathrm{s}\mathrm{/}\mathrm{W}$
8-cores RISC-V processor cluster with mixed-precision Deep Neural Network
(DNN) extensions with a
$1036\text{\,}\mathrm{T}\mathrm{O}\mathrm{p}\mathrm{/}\mathrm{s}\mathrm{/}\mathrm{W}$
Ternary Neural Network (TNN) accelerator.

##  II Architecture

The Kraken SoC (Fig. 7) is built around a 32bit fabric controller (FC) RISC-V
core, it hosts 1MiB of scratchpad SRAM memory (L2) and standard peripherals: 4
QSPI, 4 I2C, 2 UART and 48 GPIOs. The FC can offload compute intensive kernels
to three programmable, power-gateable accelerators.

###  II-1 Sparse Neural Engine (SNE)

It targets spiking convolutional neural network (SCNN) inference with 4bit 3x3
kernels and 8bit leaky-integrate and fire (LIF) neuron states. SNE exploits an
explicit coordinate list (COO) data representation to efficiently transform
unstructured spatio/temporal sparse event computation, which is difficult to
perform efficiently, into SNE “dense” computational bursts. SNE hosts eight
8KiB LIF neuron state memories and a dedicated 9.2KB weight buffer.

###  II-2 Completely Unrolled Ternary Inference Engine (CUTIE)

It is a TNN accelerator designed to maximize energy efficiency by minimizing
data movement during inference. This is achieved by keeping all ternary
weights on-chip (in 1.6 bits/weight compressed format), fully spatially
unrolling the ternary multiplications, and the multi-bit accumulation required
to compute an output channel activation followed by per-channel normalization,
non-linearity, and thresholding. CUTIE achieves one output activation element
per cycle per output channel throughput. The CUTIE instance in Kraken supports
96 parallel output channels, 158kB, and 117kB memories for feature map and
weight storage, respectively.

###  II-3 Parallel ultra-low power cluster (PULP)

It hosts 8 RISC-V cores sharing a single-cycle 128kiB L1 scratchpad memory.
The cores feature dedicated extensions for energy-efficient digital signal
processing such as hardware loops, multiply-accumulate with concurrent load
(MAC-LD) and multi-precision (fp32/fp16/fp16-brain) floating point. The
Cluster also supports SIMD (int8/int4/int2) widening dot-product operations,
as well as all their mixed-precision combinations, thanks to a status-based
RISC-V ISA extension.

##  III Applications and results

We focus on a nano-UAV workload composed of three key visual tasks (Fig. 7).
The SNE subsystem assists navigation by providing optical flow reconstruction
from DVS events (produced by a DVS132s 128x132 by
IniVation111https://inivation.com), while PULP and CUTIE execute obstacle
avoidance and target object detection, respectively, on BW images (produced by
the HM01B0 320X240 imager from HIMAX222https://www.himax.com.tw). We present
post-silicon measurements to assess the energy consumption of the
aforementioned tasks. SNE can compute per pixel optical flow with a 4bit
quantized, 4-layer, Convolutional Spiking Neural Network (CSNN), low-memory
footprint, LIF-FireNet proposed in [4]. During inference, the SNE consumes
98mW at 222MHz, 0.8V. At this frequency, SNE can perform 20800 inf/s at low
(1%) network activity, and 1019 inf/s at the 20% average activity (Fig. 7). In
parallel, CUTIE can perform object classification at more than 10000 inf/s on
a ternary CIFAR10 network derived from[5], in a power envelope of 110mW, at
0.8V, when clocked at 330MHz. The PULP cluster performs a navigation and
obstacle avoidance task based on an 8bit quantized DroNet network presented
in[2]. The network can be executed at a rate of 28inf/s when PULP is running
at 330MHz, 0.8V, in an 80mW power envelope.

SNE energy efficiency has been benchmarked against SoA on a 6-layer CSNN
network presenting similar complexity and memory footprint as the LIF-FireNet
one. On the standard event-based IBM-DVSGesture, our design can achieve SoA
92% accuracy while showing an energy efficiency that outperforms the state-of-
the-art by 1.7$\times$ [6]. CUTIE has been benchmarked on a ternarized version
of the binary network reported in [5], performing object detection on the
CIFAR10 data set. It achieves 2% better accuracy than [5] and energy
efficiency of
$1036\text{\,}\mathrm{T}\mathrm{O}\mathrm{p}\mathrm{/}\mathrm{s}\mathrm{/}\mathrm{W}$,
outperforming the state-of-the-art by 2$\times$[5]. To benchmark the PULP
cluster energy efficiency against a similar SoA RISC-V cluster[7], we executed
standalone convolutional layer patches that are representative of multi-
precision DNN inference. Compared to Vega[7], on the same workload, Kraken
show 1.66$\times$ higher throughput at the same frequency, thanks to the MAC-
LD instruction, allowing to achieve a peak throughput of 0.98 mac/cycle/core.
In terms of energy efficiency, the SIMD operations for highly quantized
inference enable Kraken to achieve more than 2.6$\times$ better energy
efficiency on 4-b and 2-b convolutions (Fig. 7). Kraken engines’ energy
efficiency is summarized in Fig. 7 and compared against each SoA counterpart.
By combining SNE, CUTIE, and PULP with the microcontroller FC subsystem,
Kraken’s heterogeneous SoC architecture can concurrently execute all visual
tasks required for autonomous navigation on Nano-UAVs.

## References

  * [1] A. Bachrach, “Skydio autonomy engine: Enabling the next generation of autonomous flight,” in _2021 IEEE Hot Chips 33 Symposium (HCS)_ , 2021.
  * [2] D. Palossi _et al._ , “A 64-mw dnn-based visual navigation engine for autonomous nano-drones,” _IEEE Internet of Things Journal_ , vol. 6, no. 5, pp. 8357–8371, 2019.
  * [3] C. Li _et al._ , “A 132 by 104 $10\mu m$-pixel $250\mu w$ 1kefps dynamic vision sensor with pixel-parallel noise and spatial redundancy suppression,” in _2019 Symposium on VLSI Circuits_ , 2019, pp. C216–C217.
  * [4] J. Hagenaars _et al._ , “Self-supervised learning of event-based optical flow with spiking neural networks,” in _Advances in Neural Information Processing Systems_ , M. Ranzato _et al._ , Eds., vol. 34. Curran Associates, Inc., 2021, pp. 7167–7179.
  * [5] B. Moons _et al._ , “Binareye: An always-on energy-accuracy-scalable binary cnn processor with all memory on chip in 28nm cmos,” in _Proc. IEEE CICC_ , 2018.
  * [6] L. Deng _et al._ , “Tianjic: A unified and scalable chip bridging spike-based and continuous neural computation,” _IEEE Journal of Solid-State Circuits_ , vol. 55, no. 8, pp. 2228–2246, 2020.
  * [7] D. Rossi _et al._ , “Vega: A ten-core soc for iot endnodes with dnn acceleration and cognitive wake-up from mram-based state-retentive sleep mode,” _IEEE Journal of Solid-State Circuits_ , vol. 57, no. 1, pp. 127–139, 2022.

Figure 1: System level overview showing the three main computation engines and
their integration into the SoC.

Figure 2: Description of the application scenario. The two computation
subsystems are shown in red and blue respectively.

Figure 3: Die micrograph of the Kraken SoC showing the different power
domains.

Figure 4: Energy efficiency of the PULP cluster for different bit precision.
unless “fp” specified, integer arithmetic is indented. SIMD instructions are
used below 32bit precision.

Technology | GF $22\text{\,}\mathrm{nm}$ FDX
---|---
Chip area | $9\text{\,}{\mathrm{mm}}^{2}$
L2 memory (SRAM) | 1MiB
L1 Memory (SRAM) | 128kiB
VDD Range | $0.5\text{\,}\mathrm{V}0.8\text{\,}\mathrm{V}$
Cluster Max. Frequency | $330\text{\,}\mathrm{MHz}$
EHWPE Max. Frequency | $330\text{\,}\mathrm{MHz}$
FC Max. Frequency | $330\text{\,}\mathrm{MHz}$
Power Range | $2\text{\,}\mathrm{mW}300\text{\,}\mathrm{mW}$

Figure 5: Physical implementation details for the kraken chip. Maximum
frequency has been measured on 32bit floating point matrix-to-matrix
multiplication benchmarks for both FC and cluster. For CUTIE and SNE, CNN
workloads have been used.

Figure 6: Comparison of the energy efficiency of the cluster, SNN accelerator
and TNN accelerator with state-of-the-art designs. In the case of PULP, 2
N-bit OP = 1 N-bit MAC. For CUTIE, 2 ternary OP = 1 ternary MAC. In the case
of SNE, 1 SOP = 1 4b-ADD + 1 8b-MUL + 1 8b-COMPARE

Figure 7: SNE inference per second versus the DVS network activity (Top). SNE
inference energy versus DVS network activity (Bottom).


# Local Similarity Search on Geolocated Time Series Using Hybrid Indexing

Georgios Chatzigeorgakidis  IMSI, Athena R.C., Greece, email:
<EMAIL_ADDRESS>Dimitrios Skoutas  IMSI, Athena R.C., Greece, email:
<EMAIL_ADDRESS>Kostas Patroumpas  IMSI, Athena R.C., Greece, email:
<EMAIL_ADDRESS>Themis Palpanas  LIPADE, Paris Descartes University,
France, French University Institute (IUF) email<EMAIL_ADDRESS>Spiros Athanasiou  IMSI, Athena R.C., Greece, email<EMAIL_ADDRESS>Spiros Skiadopoulos  Dept. of Inf. & Telecommunications University of
Peloponnese, Greece email<EMAIL_ADDRESS>
###### Abstract

Geolocated time series, i.e., time series associated with certain locations,
abound in many modern applications. In this paper, we consider hybrid queries
for retrieving geolocated time series based on filters that combine spatial
distance and time series similarity. For the latter, unlike existing work, we
allow filtering based on local similarity, which is computed based on
subsequences rather than the entire length of each series, thus allowing the
discovery of more fine-grained trends and patterns. To efficiently support
such queries, we first leverage the state-of-the-art BTSR-tree index, which
utilizes bounds over both the locations and the shapes of time series to prune
the search space. Moreover, we propose optimizations that check at specific
timestamps to identify candidate time series that may exceed the required
local similarity threshold. To further increase pruning power, we introduce
the $\mathcal{S}$BTSR-tree index, an extension to BTSR-tree, which
additionally segments the time series temporally, allowing the construction of
tighter bounds. Our experimental results on several real-world datasets
demonstrate that $\mathcal{S}$BTSR-tree can provide answers much faster for
all examined query types. This paper has been published in the 27th
International Conference on Advances in Geographic Information Systems (ACM
SIGSPATIAL 2019).

##  1 Introduction

A time series is a time-ordered sequence of data points. Time series are
ubiquitous in many application domains. They can represent various types of
measurements, such as user check-ins at various Points of Interest, energy
consumption in smart buildings, PM2.5 particle concentration measured by air
pollution sensors, etc. Analyzing and mining time series data is highly
important for discovering trends and patterns in such phenomena, and has
attracted extensive research interest over the last years [8, 13, 20].

However, what is usually overlooked is that the phenomena represented by time
series are often also associated with geographic locations, e.g., time series
generated by sensors installed at fixed positions. In such cases, spatial
distance also plays an important role in the analysis, since discovery of
trends and patterns may depend not only on time series similarity but also on
geographic proximity. Motivated by this observation, in previous work [6, 5]
we introduced the concept of geolocated time series and we proposed hybrid
indexing techniques that efficiently support the retrieval of time series
based on both spatial distance and time series similarity.

In particular, we introduced the BTSR-tree [6], a hybrid index that first
builds an R-tree over the locations of the time series data. It then enhances
each node with appropriate upper- and lower-bounding time series (MBTS) that
enclose the subset of time series represented by it. Combining MBTSs and MBRs,
the query evaluation algorithm can simultaneously prune the search space based
on time series similarity and spatial distance while traversing the index. To
further increase its pruning power, the BTSR-tree groups together similar time
series within each node to derive tighter bounds.

This existing approach for hybrid search over geolocated time series using the
BTSR-tree supports only global time series similarity, i.e., similarity
measured across the entire length of time series. Specifically, as in other
works in this area [8, 11, 2, 3], the distance between two time series is
measured by aggregating the pairwise Euclidean distance of their respective
values across the entire sequences. However, in many cases, more fine-grained
trends and patterns may exist, which are missed under this global similarity
measure. For example, consider two time series representing the hourly energy
consumption of two nearby buildings over a week, and assume that the two
buildings exhibit a similar consumption pattern during working days but a
different one in weekends. A query imposing a similarity threshold over the
entire week would fail to identify these two geolocated time series as
similar. However, it may be useful to discover that there is a period of up to
5 days during which these two time series are actually similar.

Motivated by this observation, in this work we extend our previous approach on
hybrid queries over geolocated time series to support local similarity of time
series, thus allowing more flexible and fine-grained queries and analyses. The
local similarity score between two time series $T_{i}$ and $T_{j}$ is defined
as the maximum number of consecutive timestamps during which the respective
values of $T_{i}$ and $T_{j}$ do not differ by more than a user-specified
threshold $\epsilon$. Notice that, compared to global similarity, this
condition is more relaxed, in the sense that it is applied to subsequences of
length lower than $T_{i}$ and $T_{j}$, but at the same time stricter, in the
sense that the threshold $\epsilon$ is required to be satisfied at each
individual timestamp during the selected period rather than on the aggregate
distance over all timestamps.

Combining this local similarity constraint with a filter on spatial distance
leads to a novel set of hybrid queries. Figure 1 shows an example with a query
time series $T_{q}$ searching over a set of time series $T_{1},\dots,T_{9}$
for those within radius $\rho$ from its location and also locally similar to
$T_{q}$. In particular, with respect to a given $\epsilon$, results should
also be locally similar to $T_{q}$ for at least 5 consecutive timestamps.
Qualifying results include $T_{2}$ with local similarity score $\sigma_{2}=5$
(bottom chart), and $T_{7}$ with $\sigma_{7}=7$ (top chart).

Figure 1: Retrieving geolocated time series based on spatial distance and
local similarity.

It turns out that such hybrid queries involving local similarity can still be
evaluated using the BTSR-tree index. We first present a baseline method
employing a sweep-line algorithm to check for local similarity, and then
describe how this can be optimized by using appropriately placed checkpoints,
based on the local similarity score threshold specified by the query, in order
to skip unnecessary comparisons. Despite the fact that this saves some
computations, the resulting time savings are relatively small, since the
number of index nodes that need to be probed is not essentially reduced. To
overcome this problem, we introduce an improvement to the BTSR-tree index,
which is based on temporally segmenting the time series bounds within each
node and deriving tighter bounds per segment. Once the time series bounds in
each node become more fine-grained, pruning the search space for local
similarity queries proves much more effective.

Summarizing, our main contributions are as follows:

  * •

We extend our previous work on hybrid queries for geolocated time series to
support local time series similarity. We consider both range and top-$k$
queries, including combined criteria for spatial distance and local time
series distance.

  * •

We present how such queries can be answered efficiently exploiting the
previously introduced BTSR-tree index.

  * •

To achieve greater savings in execution time by further reducing node
accesses, we propose an enhanced variant of BTSR-tree, called
$\mathcal{S}$BTSR-tree, which additionally employs temporal segmentation in
each node to derive tighter, more fine-grained time series bounds.

  * •

We experimentally evaluate our methods using real-world datasets from
different application domains, showing that BTSR-tree can efficiently handle
hybrid queries under local similarity search, while $\mathcal{S}$BTSR-tree
achieves even higher performance due to the additional temporal segmentation.

The remainder of the paper is structured as follows. Section 2 reviews related
work. Section 3 formally defines the problem. Section 4 presents how query
evaluation under local time series similarity can be executed using the BTSR-
tree, while Section 5 presents the enhanced $\mathcal{S}$BTSR-tree. Section 6
reports our experimental results, and Section 7 concludes the paper.

##  2 Related Work

Similarity search over time series has provided a wide range of algorithmic
approaches; a detailed survey with experimental evaluation is available in
[8]. Initially, the focus was mostly on wavelet-based methods [4] to reduce
the dimensionality of time series and generate an index based on the
transformed sequences. In contrast, state-of-the-art approaches for time
series indexing are based on the Symbolic Aggregate Approximation (SAX)
representation [11]. The first index in this family was $i$SAX[17], offering
multi-resolution representations for time series. Further extensions like
$i$SAX 2.0 [2], $i$SAX2+ [3], ADS+ [21], Coconut [10], DPiSAX [18], and ParIS
[14] provided a wide range of advanced capabilities. These indices support
global similarity search, i.e., the similarity score is computed over the
entire length of the compared time series, as opposed to local similarity,
which allows to consider similar subsequences. The most recent addition to
this $SAX$-based family is ULISSE [12], which can answer similarity search
queries of varying length. However, this still differs from our setting, since
in ULISSE the goal is to build an index that supports similarity search for
queries of any length within a given range $[\ell_{min},\ell_{max}]$.
Furthermore, none of the aforementioned approaches supports geolocated time
series, and thus cannot efficiently process hybrid queries combining
conditions on spatial distance and time series similarity.

The problem of subsequence matching over time series is to identify matches of
a (relatively short) query subsequence across one or more (relatively long)
time series. The UCR suite [15] offers a framework comprising various
optimizations regarding subsequence similarity search. Matrix Profile [19]
includes methods for detecting, for each subsequence of a time series, its
nearest neighbor subsequence, by keeping track of Euclidean distances among
candidate pairs. Applying such approaches in our setting is not
straightforward. First, they involve Euclidean or DTW distances, which are
different from our definition of local similarity score, hence the pruning
heuristics do not hold in our case. Second, they do not consider geolocated
time series, thus spatial filtering has to be carried out independently, which
reduces pruning opportunities.

To the best of our knowledge, the only index that supports searching over
geolocated time series is the BTSR-tree [6, 5]. This hybrid index follows a
similar rationale set by spatio-textual indices [7] that can facilitate
evaluation of queries combining location-based predicates with keyword search.
In a similar spirit, BTSR-tree is a spatial-first index based on the R-tree
that can additionally compute bounds on similarity of time series instead of a
textual similarity between documents. Apart from an MBR, each node also stores
bounds over the time series indexed in its subtree. Thus, it offers increased
pruning capabilities for range and top-$k$ queries involving both time series
similarity and spatial proximity. In the current work, we show how BTSR-tree
can be used for another family of hybrid queries involving local similarity of
time series. Furthermore, we introduce a variant structure, called
$\mathcal{S}$BTSR-tree, which constructs tighter bounds over temporally
segmented time series to offer stronger pruning power.

##  3 Local Similarity Search on Geolocated Time Series

Next, we briefly present some background on geolocated time series and the
BTSR-tree index, and then formally define the problem.

###  3.1 Preliminaries

_Geolocated Time Series_. A time series is a time-ordered sequence of values
$T=\\{T^{1},T^{2}\ldots,T^{n}\\}$, where $T^{i}$ is the value at the $i$-th
timestamp and $n$ is the length of the series. A geolocated time series is
additionally characterized by a _location_ , denoted by $T.loc$. The spatial
distance $d$ between two geolocated time series is the Euclidean distance of
their respective locations.

_The BTSR-tree Index_. In [6], we have introduced the BTSR-tree index, which
is based on the notion of Minimum Bounding Time Series (MBTS). In a similar
manner that an MBR encloses a set of geometries, an MBTS encloses a set of
time series $\mathcal{T}$ using a pair of bounds that fully contain all of
them. Figure 2 depicts an example of two MBTSs for two disjoint sets of time
series. Formally, given a set of time series $\mathcal{T}$, its MBTS consists
of an _upper bounding time series_ $B^{\sqcap}$ and a _lower bounding time
series_ $B^{\sqcup}$, constructed by respectively selecting the maximum and
minimum of values at each timestamp $i\in\\{1,\dots,n\\}$ among all time
series in set $\mathcal{T}$ as follows:

$\displaystyle\begin{split}&B^{\sqcap}=\\{\max_{T\in\mathcal{T}}T^{1},\ldots,\max_{T\in\mathcal{T}}T^{n}\\}\\\
&B^{\sqcup}=\\{\min_{T\in\mathcal{T}}T^{1},\ldots,\min_{T\in\mathcal{T}}T^{n}\\}\end{split}$
(1)

Figure 2: MBTS constructed for two sets of time series.

A BTSR-tree index is initialized as an R-tree [9] built on the spatial
attributes of the given geolocated time series dataset, as depicted in the
example of Figure 3. Besides MBRs, each node is enhanced to also store MBTSs,
shown as colored strips per node in Figure 3c. This enables efficient pruning
of the search space when evaluating hybrid queries combining time series
similarity with spatial proximity. For each child, a node stores a pre-
specified number of MBTSs. Each MBTS is calculated according to Eq. 1.
Construction and maintenance of the BTSR-tree follow the procedures of the
R-tree for data insertion, deletion and node splitting. Objects (i.e.,
geolocated time series) are inserted into leaf nodes and any resulting changes
are propagated upwards. Once the nodes have been populated, the MBTS of each
node are calculated bottom-up, relying on $k$-means clustering according to
their Euclidean distance in the time series domain. The example in Figure 2
depicts the $k=2$ MBTSs (as two bands with a thick outline) obtained for a set
of time series (shown as thin polylines). In a BTSR-tree, each parent node
receives all the MBTSs of its children and computes its own $k$ MBTSs. The
process continues upwards, until reaching the root.

(a) Sample dataset with MBRs over locations

(b) Spatial-only R-tree index

(c) Hybrid BTSR-tree index

Figure 3: The BTSR-tree index.

###  3.2 Problem Definition

We first define the local similarity between time series, and then present the
query variants we consider in this paper.

######  Definition 1 (Local Time Series Similarity)

The local similarity score $\sigma$ between two time series $T$ and
$T^{\prime}$ is the maximum count of consecutive timestamps during which the
respective values of $T$ and $T^{\prime}$ do not differ by more than a given
margin $\epsilon$, i.e., $\sigma(T,T^{\prime},\epsilon)=|I_{max}|$, where
$I_{max}$ is the longest consecutive time interval $I$ such that $\forall i\in
I,|T^{i}-T^{\prime i}|\leq\epsilon$.

In this work, our goal is to efficiently support hybrid queries on geolocated
time series that retrieve the results based both on spatial proximity and
local similarity. Specifically, we focus on the following types of queries
(hereafter referred to as LS-queries):

  * •

$Q_{rr}(T_{q},\rho,\epsilon,\delta)$: Given a geolocated time series $T_{q}$,
retrieve every geolocated time series $T$ such that $T$ is located within
range $\rho$ from $T_{q}$, i.e., $d(T_{q},T)\leq\rho$ and has local similarity
to $T_{q}$ at least $\delta$, i.e., $\sigma(T_{q},T)\geq\delta$.

  * •

$Q_{kr}(T_{q},k,\epsilon,\delta)$: Given a geolocated time series $T_{q}$,
retrieve the spatial $k$-nearest neighbors to $T_{q}$ that also have local
similarity to $T_{q}$ at least $\delta$.

  * •

$Q_{rk}(T_{q},\rho,\epsilon,k)$: Given a geolocated time series $T_{q}$,
retrieve the top-$k$ geolocated time series that have the highest local
similarity to $T_{q}$ with respect to $\epsilon$ and are located within range
$\rho$ from $T_{q}$.

###### Example 1

Figure 1 depicts an example of the $Q_{rr}(T_{q},\rho,\epsilon,\delta)$ query.
Given the geolocated time series $T_{q}$ as query, we seek the spatially close
ones (i.e., within a circle of radius $\rho$) that are also locally similar
within margin $\epsilon$ for at least $\delta$ timestamps. In this example,
despite five geolocated time series being within range, only $T_{2}$ and
$T_{7}$ qualify for the final result, since these are the ones that are also
locally similar for at least one time interval of length at least $\delta$.

##  4 LS-Queries Using the BTSR-tree

A straightforward approach for answering LS-queries would be to use a spatial
index to first filter by spatial distance and then perform a sequential scan
across each result to filter out those having local similarity score below the
given threshold. This suffers from generating an unnecessarily large number of
intermediate results which are then discarded. Instead, we propose to process
LS-queries by leveraging the BTSR-tree index [6], which can prune the search
space simultaneously according to both criteria.

While traversing the BTSR-tree, spatial filtering is performed at each node
$N$ by computing the bounding distance $mindist_{sp}$ between the location of
$T_{q}$ and the MBR of $N$, as in R-Trees [16].

For time series similarity, we exploit the MBTS stored within each node.
Considering an MBTS at a node $N$, we calculate its distance
$mindist_{ts}^{i}$ from $T_{q}$ at each timestamp $i$ as:

$\begin{split}mindist_{ts}^{i}(T_{q},{MBTS}_{N})=\begin{cases}T_{q}^{i}-B_{N}^{\sqcap_{i}},&\text{if}\;\;T_{q}^{i}>B_{N}^{\sqcap_{i}}\\\
B_{N}^{\sqcup_{i}}-T_{q}^{i},&\text{if}\;\;T_{q}^{i}<B_{N}^{\sqcup_{i}}\\\
0,&\text{if}\;\;B_{N}^{\sqcap_{i}}\leq T_{q}^{i}\leq
B_{N}^{\sqcup_{i}}\end{cases}\end{split}$ (2)

where $B_{N}^{\sqcap_{i}}$ and $B_{N}^{\sqcup_{i}}$ are the upper and lower
values of the MBTS at timestamp $i$. By definition of MBTS, no time series
indexed under $N$ can differ from $T_{q}$ by less than $mindist_{ts}^{i}$ at
timestamp $i$. Hence, only at those timestamps that
$mindist_{ts}^{i}\leq\epsilon$, it is possible that a time series indexed
under $N$ is locally similar to $T_{q}$. Subsequently, we can compute a local
similarity bound $\sigma_{B}$:

$\sigma_{B}(T_{q},MBTS_{N},\epsilon)=max\\{|I|;\forall i\in
I,mindist^{i}_{ts}(T_{q},MBTS_{N})\leq\epsilon\\}.$ (3)

that reflects the maximum interval $I$ of consecutive timestamps where the
distance computed by Eq. 2 does not exceed margin $\epsilon$. This value is an
upper bound of the local similarity scores of $T_{q}$ with any time series
enclosed in this MBTS. Figure 4 shows that $T_{q}$ deviates from the given
MBTS by no more than $\epsilon$ during two intervals: one consisting of
$|I_{1}|=5$ consecutive timestamps and a smaller one with only $|I_{2}|=2$
timestamps (shown as square points). So, the local similarity bound for this
MBTS is $\sigma_{B}=5$.

Figure 4: Local similarity check against an MBTS.

By construction, the MBTSs of a child node $N^{\prime}$ get tighter bounds
compared to those of its parent $N$ as we descend the BTSR-tree. It is easy to
verify that

$\begin{split}\sigma_{B}(T_{q},MBTS_{N},\epsilon)\geq\sigma_{B}(T_{q},MBTS_{N^{\prime}},\epsilon)\end{split}$
(4)

hence local similarity bounds can only diminish when descending the index.
This bound provides a useful pruning condition during search with a cutoff
threshold $\delta$. Any node where all its MBTSs have local similarity bound
$\sigma_{B}$ below $\delta$ can be safely pruned.

Next, we describe a baseline approach that employs a sequential scan over
MBTSs, and then we present an optimization that prioritizes selected
checkpoints to avoid many point-wise comparisons.

###  4.1 Sweep Line Approach

We explain how the BTSR-tree can be used, in conjunction with a simple sweep-
line algorithm, to answer each of the three LS-queries, taking advantage of
the two types of bounds, $mindist_{sp}$ and $mindist_{ts}$, described above.

$\mathbold{Q_{rr}(T_{q},\rho,\epsilon,\delta)}$: We traverse the BTSR-tree
starting from its root. At each inner node $N$, we first check whether
$mindist_{sp}(T_{q},MBR_{N})$ $\leq$ $\rho$. If so, we employ a sweep line
across the time axis to compute the local similarity bound
$\sigma_{B}(T_{q},MBTS_{N},\epsilon)$ for every MBTS included in $N$. If all
resulting bounds $\sigma_{B}$ are below $\delta$, the subtree under $N$ is
pruned. Otherwise, the search continues at the children. Upon reaching a leaf
node, we fetch the geolocated time series contained therein, and verify the
query constraints against each one. Each $T$ such that
$d(T_{q}.loc,T.loc)\leq\rho$ and $\sigma(T_{q},T,\epsilon)\geq\delta$ is added
to the results.

$\mathbold{Q_{kr}(T_{q},k,\epsilon,\delta)}$: We maintain a priority queue $P$
containing both inner nodes (sorted by ascending $mindist_{sp}$) and
geolocated time series (sorted by ascending spatial distance to $T_{q}$). We
start by adding to $P$ the root of BTSR-tree. In each iteration, we retrieve
the top element from $P$. If it is an inner node, we visit its children to
calculate local similarity bounds $\sigma_{B}$ according to Eq. 3. For any
child $N$ that $\sigma_{B}$ of one of its MBTSs satisfies threshold $\delta$,
we search the subtree of $N$. Then, we calculate the corresponding spatial
distance ($mindist_{sp}$ for a node $N$ or Euclidean distance for a geolocated
time series $T$) and insert it back to $P$. Once we encounter a geolocated
time series $T$ at the top of $P$, we add it to the results. The process
terminates once $k$ geolocated time series have been obtained.

$\mathbold{Q_{rk}(T_{q},\rho,\epsilon,k)}$: This query is evaluated similarly
to the previous one, with two differences. The first difference is that the
priority queue $P$ is now sorted based on local similarity bounds in
descending order, instead of spatial distance bounds in ascending order. The
second is that before inserting an item (node or time series) to $P$, its
spatial distance ($mindist_{sp}$ or exact) is calculated, and if it is higher
than $\rho$ the item is skipped. The traversal starts again from the root, and
terminates once $k$ time series have been retrieved from the top of $P$. These
are the top-$k$ results with respect to local similarity (if another time
series $T$ had higher local similarity, it would have been retrieved from $P$
first), and they are located within range $\rho$ from $T_{q}$ (otherwise, they
would not have been admitted to $P$).

###  4.2 Checkpoint Approach

The drawback of the sweep-line approach is that it needs to perform a
comparison for each individual timestamp to eventually determine the exact or
maximum local similarity of a given time series or node, respectively. In the
following, we explain how we can use checkpoints along the time axis to avoid
this exhaustive search. These checkpoints prioritize specific timestamps when
checking for candidate matches to eagerly filter out non-qualifying items.

Assume a query with local similarity threshold $\delta$. We can place
checkpoints at every $\delta$ timestamps, and only apply the local similarity
filter (i.e., $|T_{q}^{i}-T^{i}|\leq\epsilon$) at those. If no checkpoint
satisfies the condition, this item can be safely pruned since it cannot have
local similarity to $T_{q}$ at least $\delta$ (as this would require the
condition to be true for at least $\delta$ consecutive timestamps, thus
crossing at least one checkpoint).

(a) Checkpoints placed every $\delta$ timestamps.

(b) Local similarity starting before checkpoint at $t^{\prime}$.

(c) Local similarity ending after checkpoint at $t^{\prime}$.

Figure 5: Local time series similarity via checkpoints.

Figure 5a shows an example with checkpoints placed along the time axis every
$\delta=5$ timestamps. For clarity, we consider a single time series $T$.
Assume a checkpoint at timestamp $t^{\prime}$ and a minimal duration $\delta$
starting at timestamp $t^{\prime}-\delta+1$ for asserting local similarity
with query $T_{q}$, as shown with the grey strip in Figure 5b. This interval
cannot have smaller duration, as it would not satisfy the $\delta$ constraint.
Thus, the local similarity condition will evaluate to true at checkpoint
$t^{\prime}$. Similarly, if such an interval ends at timestamp
$t^{\prime}+\delta-1$ (Figure 5c), it will be detected at the checkpoint at
$t^{\prime}$. This observation entails that it suffices to check for local
similarity only at checkpoints, i.e., every $\delta$ timestamps. We denote the
set of checkpoints as $C$, determined at query time. If a checkpoint satisfies
the condition, then we need to scan both forward and backward from it to
determine the actual local similarity score, i.e., to find the exact extent of
the time interval for which the condition holds.

Figure 6 exemplifies the use of checkpoints for comparing $T_{q}$ to an MBTS
of a node for $\delta=5$ timestamps. Instead of sequentially performing 11
comparisons until verifying that local similarity score $\sigma$ is at least
$\delta$ (i.e., we stop the verification at $t=11$, once $\sigma=5$), we check
only around the checkpoints. At the leftmost checkpoint $c_{1}$, no local
similarity is found ($T_{q}$ is farther than $\epsilon$ from the MBTS), so we
skip directly to checkpoint $c_{2}$. Since $T_{q}$ differs by less than
$\epsilon$ at $c_{2}$, we need to compare values backward and forward, up to
the previous and next checkpoint, respectively. This requires only 6
comparisons instead of 11 to decide that this node may contain candidates.
Next, we describe how probing with checkpoints is applied during evaluation of
LS-queries.

Figure 6: Local similarity with a MBTS using checkpoints.

$\mathbold{Q_{rr}(T_{q},\rho,\epsilon,\delta)}$: Algorithm 1 outlines the
procedure. Initially, we obtain the children of the root node in a list and
place the checkpoints every $\delta$ timestamps (Lines 1-3). We iterate over
each item $N$ in this list. If $N$ is an inner node, we have to examine
whether both constraints with respect to $\rho$ and $\delta$ are met for each
of its children. Verification of MBTS against query $T_{q}$ will be discussed
shortly. If this is the case, we traverse the sub-tree of each child in the
same manner, by adding it to the list (Lines 7-11), thus descending the tree.
If the examined node is a leaf (Line 12), we iterate over each contained time
series $T$ to check the constraints $\rho$ and $\delta$. If $T$ qualifies, it
is added to the results (Lines 13-15). Note that now the calculation of local
similarity scores for geolocated time series is based on checkpoints (Line
14), as discussed above.

Verification of MBTS against the local similarity constraints
$\epsilon,\delta$ is applied using checkpoints (Lines 17-38). This
verification concerns each MBTS in a given node $N^{\prime}$. At each
checkpoint $c$, we first verify whether its $mindist_{ts}^{c}$ to query
$T_{q}$ is at most $\epsilon$ (Line 20). If so, we first scan backward to
inspect whether there are at least $\delta$ consecutive timestamps where
$T_{q}$ deviates by at most $\epsilon$ from this MBTS (Lines 22-29).
Similarly, we probe forward from checkpoint $c$ (Lines 30-37). In either case,
once local similarity no longer holds at a timestamp, probing skips to the
next checkpoint. If the check fails for all checkpoints of all MBTSs, then
this node cannot contain any results (Line 38).

1 $R\leftarrow\emptyset$

2 $List\leftarrow Root.entries$

3 $C\leftarrow determineCheckpoints(\delta)$

4 while  _$List\neq\emptyset$_ do

5 $N\leftarrow List.getNext()$

6 if  _$N$ is not leaf_ then

7 foreach  _$N^{\prime}\in N.getChildren()$_ do

8 if  _$mindist_{sp}(T_{q},MBR_{N^{\prime}})\leq\rho$_ then

9 $count\leftarrow\emptyset$

10 if  _$VerifyMBTS(T_{q},N^{\prime},C,\epsilon,\delta)$_ then

11 $List\leftarrow List\cup\\{N^{\prime}.getChildren()\\}$

12

13

14

15

16 else

17 foreach  _$T\in N.getObjects()$_ do

18 if  _$d(T_{q},T)\leq\rho\land\sigma^{C}(T_{q},T,\epsilon)\geq\delta$_ then

19 $R\leftarrow R\cup\\{T\\}$

20

21

22 return R

23

24

25 Procedure  _$VerifyMBTS(T_{q},N^{\prime},C,\epsilon,\delta)$_

26 foreach  _$MBTS\in N^{\prime}$_ do

27 foreach  _$c\in C$_ do

28 if  _$mindist_{ts}^{c}(T_{q},MBTS)\leq\epsilon$_ then

29 $count++,c^{\prime}\leftarrow c$

30 while  _True_ do

31 $c^{\prime}--$

32 if  _$mindist_{ts}^{c^{\prime}}(T_{q},MBTS)\leq\epsilon$_ then

33 $count++$

34 if  _$count\geq\delta$_ then

35 return True

36

37 else

38 $break$

39

40 while  _True_ do

41 $c++$

42 if  _$mindist_{ts}^{c}(T_{q},MBTS)\leq\epsilon$_ then

43 $count++$

44 if  _$count\geq\delta$_ then

45 return True

46

47 else

48 $break$

49

50

51

52

53 return $False$

54

Algorithm 1 $Q_{rr}(T_{q},\rho,\epsilon,\delta)$

$\mathbold{Q_{kr}(T_{q},k,\epsilon,\delta)}$: We follow a similar procedure to
the one in Section 4.1 for query $Q_{kr}$, employing the same verification
process over MBTSs and time series as in Algorithm 1. Algorithm 2 describes
the procedure. We start by adding the root node to a priority queue $P$ based
on spatial distance (Line 2). After determining the checkpoints using the
given $\delta$ (Line 3), we iteratively retrieve elements from $P$ (Line 5).
Then, three cases may occur:

  1. (i)

If this element is a time series (Lines 6-9), it is guarranteed to be a
result, given that $P$ is sorted based on spatial distance from $T_{q}$.
Indeed, any subsequent element must be located farther than the current. When
list $R$ obtains the required number $k$ of results, the search terminates.

  2. (ii)

The element is a leaf node (Lines 10-14): In this case, we obtain each time
series $T$ contained in this leaf, and verify the local similarity score of
$T$ against $\delta$. If the condition is met, we calculate the spatial
distance of candidate $T$ from query $T_{q}$ and push $T$ into the priority
list along with its spatial distance (Lines 10-14).

  3. (iii)

If the element is an inner node, we iterate over its children and only push
back to the queue the ones whose MBTSs are verified against $\epsilon$ and
$\delta$ using checkpoints (Lines 15-19).

1 $R\leftarrow\emptyset$

2 $P.push(Root)$

3 $C\leftarrow determineCheckpoints(\delta)$

4 while  _$P$ is not empty_ do

5 $N\leftarrow P.poll()$

6 if  _$N$ is raw_ then

7 $R\leftarrow R\cup\\{N\\}$

8 if  _$|R|=k$_ then

9 $break$

10

11

12 else if  _$N$ is leaf_ then

13 foreach  _$T\in N.getObjects()$_ do

14 if  _$\sigma^{C}(T_{q},T,\epsilon)\geq\delta$_ then

15 $T.dist\leftarrow d(T_{q},T)$

16 $P.push(T,T.dist)$

17

18

19

20 else

21 foreach  _$N^{\prime}\in N.getChildren()$_ do

22 if  _$VerifyMBTS(T_{q},N^{\prime},C,\epsilon,\delta)$_ then

23 $N^{\prime}.dist\leftarrow mindist_{sp}(T_{q},MBR_{N^{\prime}})$

24 $P.push(N^{\prime},N^{\prime}.dist)$

25

26

27

28

return R

Algorithm 2 $Q_{kr}(T_{q},k,\epsilon,\delta)$

$\mathbold{Q_{rk}(T_{q},\rho,\epsilon,k)}$: The procedure for this query is
listed in Algorithm 3. Notice that for employing checkpoints, we need a local
similarity threshold $\delta$, so as to determine their placement, but this
query does not specify a fixed $\delta$. To be able to obtain one during
search, we now maintain two priority queues: $P$ holds inner nodes sorted by
local similarity bounds (Eq. 3), while $R$ keeps up to $k$ geolocated time
series sorted by local similarity scores (as in Def. 1). We initially set
$\delta=1$, so checkpoints are trivially placed at every timestamp. This
implies that computation of local similarity scores with $\delta=1$ is
equivalent to the sweep line approach. However, $\delta$ increases with the
detection of qualifying results, hence checkpoints will progressively get
placed more sparsely. The search starts by adding the BTSR-tree root in $P$
(Line 2). We iteratively poll the top element from $P$, and there are two
possible cases:

  1. (i)

The top element is a leaf node. Then, we iterate over the contained time
series and add the ones that satisfy the spatial condition ($\rho$) to $R$,
along with their corresponding local similarity score $\sigma$ if it exceeds
the current value of $\delta$ (Lines 8-12). Once $R$ exceeds capacity $k$, its
last element is evicted to make room for the newly inserted one and $\delta$
is updated according to the local similarity score $\sigma_{k}$ of the $k$-th
element in $R$. In this case, the placement of checkpoints is re-adjusted
according to the increased $\delta$ value (Lines 13-16).

  2. (ii)

The top element is an inner node. In this case, we iterate over each child
$N^{\prime}$ and check if $mindist_{sp}(T_{q},{MBR_{N}^{\prime}})\leq\rho$. If
$N^{\prime}$ qualifies, we calculate the local similarity bound $\sigma_{B}$
of all its MBTSs using checkpoints. If the maximum among these bounds
$max(\sigma_{B})\geq\delta$, then $N^{\prime}$ is inserted to $P$ with this
maximum score (Lines 17-25).

The process terminates once the top element in $P$ has local similarity less
than $\delta$ (Lines 6-7). The result is the contents of $R$.

1 $R\leftarrow\emptyset$

2 $P.push(Root)$

3 $\delta\leftarrow 1$

4 $C\leftarrow determineCheckpoints(\delta)$

5 while  _$P$ is not empty_ do

6 if  _$P.peekFirst.\sigma_{B} <\delta$_ then

7 $break$

8

9 if  _$N$ is leaf_ then

10 foreach  _$T\in N.getObjects()$_ do

11 if  _$d(T_{q},T)\leq\rho$_ then

12 if  _$\sigma^{C}(T_{q},T,\epsilon)\geq\delta$_ then

13 $R.push(T,\sigma^{C}(T_{q},T,\epsilon))$

14

15

16 if  _$R.size >k$_ then

17 $R.pollLast$

18 $\delta\leftarrow R.peekLast.\sigma$

19 $C\leftarrow determineCheckpoints(\delta)$

20

21

22

23 else

24 foreach  _$N^{\prime}\in N.getChildren()$_ do

25 if  _$mindist_{sp}(T_{q},MBR_{N^{\prime}})\leq\rho$_ then

26 $\sigma_{B}\leftarrow 0$

27 foreach  _$MBTS\in N^{\prime}$_ do

28 if  _$\sigma_{B}^{C}(T_{q},MBTS,\epsilon)\geq\sigma_{B}$_ then

29 $\sigma_{B}\leftarrow\sigma_{B}^{C}(T_{q},MBTS,\epsilon)$

30

31 if  _$\sigma_{B}\geq\delta$_ then

32 $P.push(N^{\prime},\sigma_{B})$

33

34

35

36

37

return R

Algorithm 3 $Q_{rk}(T_{q},k,\rho)$

##  5 The $\mathcal{S}$BTSR-tree Index

###  5.1 Index Structure

The BTSR-tree index uses $k$-means clustering to cluster the time series under
each node and then stores the MBTSs of those clusters. However, clustering
entire time series typically generates many overlapping MBTSs, incurring much
dead space. This has a negative impact on the pruning power of the index,
especially when considering local similarities. Figure 7a depicts such a case
of six time series indexed in a node. A $k$-means clustering with $k=3$ will
form the depicted MBTSs denoted with shaded colors. As a result, the dark area
$A$ represents the overlap between $mbts.1$ and $mbts.2$ and actually makes
those bounds less tight. Hence, such MBTSs inflate estimates for local
similarity bounds, and thus lead to unnecessarily descending further down the
index.

To reduce the amount of overlap within the MBTSs of nodes, we introduce an
extended version of the BTSR-tree, named $\mathcal{S}$BTSR-tree.
$\mathcal{S}$BTSR-tree attempts to eliminate as much overlap as possible,
through segmentation of time series. Figure 7b depicts the intuition. If we
segment the time series before applying $k$-means, the resulting MBTSs for
each segment tend to be tighter, eliminating the excessive overlap $A$ from
Figure 7a. The $\mathcal{S}$BTSR-tree is built similarly to BTSR-tree. The
only difference is that the MBTSs of each node are calculated per segment. In
this method, we assume a pre-defined number $s$ of segments, but segmentation
is orthogonal to our problem and can be carried out by applying existing
methods like [1]. Ultimately, $\mathcal{S}$BTSR-tree allows for more
aggressive pruning when traversing the index.

(a) Example of a node’s MBTS.

(b) Segmenting can eliminate whitespace.

Figure 7: Segmenting time series yields more tight MBTS.

###  5.2 Cross-Segment Continuity Via Bit-Vectors

A downside of the segmentation approach is the loss of the MBTS continuity
across time, which results in MBTSs enclosing different time series in
neighboring segments. For example, in Figure 7b, there are no MBTSs in the
right segment containing the same time series as $mbts1.1$ and $mbts1.2$, a
fact which hinders the calculation of local similarity on the segment
boundaries (the vertical line). To overcome this, we introduce a bit-vector
$V$ along each MBTS of a segment, having one bit for each MBTS created. If in
the current segment a bit in vector $V$ of a given MBTS is set, this indicates
that this MBTS encloses at least one common time series with another MBTS′ in
the next segment. In the example shown in Figure 7b, $V=110$ for $mbts1.1$
indicates common time series with $mbts2.1$ and $mbts2.2$ in the next segment,
while $V=001$ for $mbts1.3$ signifies common time series with only $mbts2.3$.
This way, to calculate local similarity, we can easily identify all the MBTSs
that share common time series among two successive segments.

To evaluate LS-queries, traversal of the $\mathcal{S}$BTSR-tree index follows
a similar rationale to the procedure in Section 4.2. For each checkpoint $c$,
we first obtain the segment where it falls in, and we scan each MBTS leftward
and rightward from $c$, as discussed in Section 4.2. If we cross the border to
another segment, the available bit-vectors directly identify the MBTS that
need be examined in this neighboring segment. This propagates until the local
similarity constraints ($\epsilon$ and $\delta$) are satisfied. Figure 8
illustrates an example of a node verification. Let us consider a predetermined
number of three segments and the corresponding MBTS of each segment for that
node. Suppose that there exists a checkpoint $c$ on the second segment. To
verify whether this node satisfies the local similarity constraints, we start
from checkpoint $c$ and we check leftwards whether
$mindist_{ts}^{i}\leq\epsilon$ for each timestamp. If the currently examined
timestamp falls in the first segment, we fetch the corresponding MBTS and bit-
vectors and continue checking whether $mindist_{ts}^{i}\leq\epsilon$ in both
MBTS (green shaded), as their bit-vectors both indicate common members with
the first one in segment 2. A similar procedure is followed rightwards, where
we only have to check the first MBTS, according to the bit-vectors.

Figure 8: Example of verifying a $\mathcal{S}$BTSR-tree node.

##  6 Experimental Evaluation

Next, we report results from a comprehensive evaluation of our methods against
real-world datasets.

###  6.1 Experimental Setup

####  6.1.1 Datasets

We use three real-world datasets (Table 1) selected from different application
domains, containing diverse types of geolocated time series, as detailed
below:

Table 1: Datasets and parameters used in the experiments. Dataset | Area | Number of | Length of | Default query parameters
---|---|---|---|---
(km2) | locations | timeseries | $\rho$ | $\epsilon$ | $\delta$ | $k$
Flickr | Earth | 414,967 | 96 | 30% | 7.5% | 20 | 30
Crime | 392,000 | 362,215 | 76 | 30% | 7.5% | 25 | 30
Taxi | 2,500 | 417,960 | 168 | 30% | 10% | 20 | 30

_UK historical crime data (Crime)_. Contains time series representing the
temporal variation in the number of crime incidents reported across England
and Wales over 76 months (December 2010– March 2017). We generated time series
over a grid with cell size 200 meters applied on the original
data111https://data.police.uk/data/. For each month, we counted incidents
having their location within each cell.

_Flickr geotagged photos (Flickr)_. Contains time series data extracted from
geolocated Flickr images between 2006 and 2013 over the entire
planet222https://code.flickr.net/category/geo/. To get meaningful geolocated
time series, we partitioned the space by a uniform grid of of $7200\times
3600$ cells (each one spanning $0.05$ decimal degrees in each dimension) and
counted the number of photos contained in every cell each month. We excluded
empty cells (e.g., in the oceans). Each time series conveys the visits pattern
(in terms of number of photos taken per month) of that region over this
period.

_NYC taxi dropoffs (Taxi)_. Contains time series extracted from yellow taxi
rides in New York City during 2015. The original
data333http://www.nyc.gov/html/tlc/html/about/trip_record_data.shtml provide
pick-up and drop-off locations, as well as corresponding timestamps for each
ride. For each month, we generated time series by applying a uniform spatial
grid over the entire city (cell side was 200 meters) and counting all drop-
offs therein for each day of the week at the time granularity of one hour.
Thus, we obtained the number of drop-offs for $24\times 7$ time intervals in
every cell, which essentially captures the weekly fluctuation of taxi
destinations there. Without loss of generality, the centroid of each cell is
used as the geolocation of the corresponding time series.

_Synthetic_. To test scalability, we augmented the Flickr dataset by slightly
moving each location in a random manner and altering each time series value by
a random number between $1$ and $10$. We produced three additional synthetic
datasets each containing $\times 2$, $\times 3$, $\times 4$ the number of time
series from the original dataset.

####  6.1.2 Index and Query Parameters

To evaluate the performance benefits observed in the experiments only based on
pruning, we tuned the index parameters to fixed values. The minimum ($m$) and
maximum ($M$) number of entries stored in each node are set to $40$ and $100$,
respectively. For both BTSR-tree and $\mathcal{S}$BTSR-tree, the number of
MBTS to 10 and for $\mathcal{S}$BTSR-tree, the number of segments $s$ is also
set to 10. The query parameters involve the spatial distance and local
similarity thresholds, i.e., $\rho$, $\epsilon$, $\delta$ and $k$. The values
of these parameters are set differently for each dataset, based on their
characteristics; default values are shown in Table 1. The value of $\rho$ is
set relatively, by setting the covered area as a percentage of the total area.
Similarly, $\epsilon$ is set as a percentage of the maximum difference between
the observed values.

####  6.1.3 Evaluation Setting

Each experiment is performed using a randomly selected workload of 100 queries
for each dataset and we report the average response time. All indices are held
in memory, while the leafs contain pointers to files with geolocated time
series stored on disk. All methods were developed in Java. Tests were executed
on a server with 4 CPUs, each containing 8 cores clocked at 2.13GHz, and 256
GB RAM running Debian Linux.

###  6.2 Query Performance

We compare the average per query execution time for all three queries using
sweep line and checkpoint methods on BTSR-tree and the checkpoint method on
$\mathcal{S}$BTSR-tree.

(a)

(b) Crime

(c) Crime

(d) Flickr

(e) Flickr

(f) Taxi

(g) Taxi

Figure 9: Query $Q_{rr}(T_{q},\rho,\epsilon,\delta)$ for varying $\rho$ and
$\epsilon$.

(a)

(b) Crime ($Q_{rr}$)

(c) Crime ($Q_{kr}$)

(d) Crime ($Q_{rk}$)

(e) $Q_{rr}$

(f) Flickr ($Q_{rr}$)

(g) Flickr ($Q_{kr}$)

(h) Flickr ($Q_{rk}$)

(i) $Q_{kr}$

(j) Taxi ($Q_{rr}$)

(k) Taxi ($Q_{kr}$)

(l) Taxi ($Q_{rk}$)

(m) $Q_{rk}$

Figure 10: Per column: $Q_{rr}(T_{q},\rho,\epsilon,\delta)$ for varying
$\delta$ – $Q_{kr}(T_{q},k,\epsilon,\delta)$ for varying $k$ –
$Q_{rk}(T_{q},k,\rho)$ for varying $k$ – Scalability.

####  6.2.1 $Q_{rr}(T_{q},\rho,\epsilon,\delta)$

Figure 9 illustrates the query performance for varying thresholds $\rho$ and
$\epsilon$ and the first column of Figure 10 for varying $\delta$, on all
three datasets. It is apparent that the $\mathcal{S}$BTSR-tree with the
checkpoint approach outperforms the rest in all cases. Its superior pruning
power is attributed to the segmentation, which yields tighter bounds within
the nodes and consequently less disk accesses. The sweep line and checkpoint
methods over BTSR-tree perform similarly in all cases. Both methods access the
same nodes, but the checkpoint approach needs to examine significantly less
values across time in order to determine local similarities. However, since
all local similarity calculations take place in-memory, computation cost does
not make a big difference, compared to the lesser node accesses required with
the $\mathcal{S}$BTSR-tree.

More specifically, for the crime dataset, relaxing $\rho$ (Figure 9b) has a
negative impact on all three methods as more nodes have to be accessed and
pruning depends mostly on the $\epsilon$ value. $\mathcal{S}$BTSR-tree
increasingly outperforms the rest as $\rho$ increases, due to its more
aggressive pruning on local similarity. For the case of increasing $\epsilon$
(Figure 9c), the result is the opposite, as this way the parameter is relaxed
and more nodes get accessed. For very large $\epsilon$ values, pruning is
solely based on spatial distance and all approaches perform similarly.
Finally, increasing $\delta$ (Figure 10b) also increases the difference in
performance among the three approaches, while it also reduces the average
query response time. This is due to large numbers of subsequences qualifying
for small $\delta$ values, resulting in more node accesses. As $\delta$
increases, pruning is more rapidly improved in the case of $\mathcal{S}$BTSR-
tree due to its tighter bounds.

The results are similar but with larger differences for the Flickr dataset
(Figures 9d, 9e and 10f). Intuitively, the less periodicity in a dataset, the
more the benefit from segmentation; if the time series in the dataset exhibit
periodicity, the bounds that will occur from applying $k$-means clustering on
the whole sequences will be relatively tighter than otherwise. The Flickr
dataset, due to its nature, is more random than the crime dataset, which
justifies the larger differences. This explanation is also supported by the
results for the taxi dataset, illustrated in Figures 9b, 9c and 10b. Despite a
similar behavior in varying all thresholds, the differences in average query
response time among the different approaches are smaller than in the crime and
Flickr datasets, due to the high daily periodicity of taxi drop-offs.

####  6.2.2 $Q_{kr}(T_{q},k,\epsilon,\delta)$

Figures 10c, 10g and 10k depict the results for the
$Q_{kr}(T_{q},k,\epsilon,\delta)$ query for the three datasets. As $k$
increases, more nodes have to be traversed in order to fetch the additional
results, and the execution time increases for all methods. Nevertheless,
$\mathcal{S}$BTSR-tree still clearly outperforms the other two algorithms.

####  6.2.3 $Q_{rk}(T_{q},k,\rho)$

Finally, Figures 10d, 10h and 10l depict the results for the
$Q_{rk}(T_{q},k,\rho)$ query. In this case, the performance deterioration as
$k$ increases is less abrupt, especially for the crime dataset, as usually the
top-$k$ results are spatially closely located and are retrieved quickly.
Again, the largest and smallest differences are spotted on the Flickr and taxi
datasets, respectively.

###  6.3 Scalability

We performed a scalability evaluation for all three queries using the Flickr-
based synthetic datasets, again measuring the average query response time for
the same query workload. The results for increasing dataset size (up to four
times) are depicted in Figure 10. In all cases, the $\mathcal{S}$BTSR-tree-
based approach scales better, especially in the top-$k$ queries (Figures 10i
and 10m), where the larger difference observed in Figures 10g and 10h is
further augmented.

##  7 Conclusions

We have studied three variants of hybrid queries on geolocated time series,
involving both range and top-$k$ search, and combining spatial distance with
local time series similarity. The latter allows to measure similarity of time
series over subsequences instead of their entire length, and thus enables the
identification of more fine-grained trends and patterns. The queries are
evaluated by hybrid index structures, in order to allow for simultaneous
pruning by both criteria. We first discuss query evaluation using the
previously proposed BTSR-tree, and then we further extend it to derive the
$\mathcal{S}$BTSR-tree which exhibits even better performance, by using
temporal segmentation of time series to derive tighter bounds. Our evaluation
against several real-world datasets has shown that $\mathcal{S}$BTSR-tree can
compute results much faster for all query variants.

## References

  * [1] E. Bingham, A. Gionis, N. Haiminen, H. Hiisilä, H. Mannila, and E. Terzi.  Segmentation and dimensionality reduction.  In SIAM, pages 372–383, 2006.
  * [2] A. Camerra, T. Palpanas, J. Shieh, and E. J. Keogh.  iSAX 2.0: Indexing and mining one billion time series.  In ICDM, pages 58–67, 2010.
  * [3] A. Camerra, J. Shieh, T. Palpanas, T. Rakthanmanon, and E. J. Keogh.  Beyond one billion time series: indexing and mining very large time series collections with i SAX2+.  Knowl. Inf. Syst., 39(1):123–151, 2014.
  * [4] K. Chan and A. W. Fu.  Efficient time series matching by wavelets.  In ICDE, pages 126–133, 1999.
  * [5] G. Chatzigeorgakidis, K. Patroumpas, D. Skoutas, S. Athanasiou, and S. Skiadopoulos.  Scalable hybrid similarity join over geolocated time series.  In SIGSPATIAL, pages 119–128, 2018.
  * [6] G. Chatzigeorgakidis, D. Skoutas, K. Patroumpas, S. Athanasiou, and S. Skiadopoulos.  Indexing geolocated time series data.  In SIGSPATIAL, pages 19:1–19:10, 2017.
  * [7] L. Chen, G. Cong, C. S. Jensen, and D. Wu.  Spatial keyword query processing: An experimental evaluation.  PVLDB, 6(3):217–228, 2013.
  * [8] K. Echihabi, K. Zoumpatianos, T. Palpanas, and H. Benbrahim.  The lernaean hydra of data series similarity search: An experimental evaluation of the state of the art.  PVLDB, 12(2):112–127, 2018.
  * [9] A. Guttman.  R-trees: A dynamic index structure for spatial searching.  In SIGMOD, pages 47–57, 1984.
  * [10] H. Kondylakis, N. Dayan, K. Zoumpatianos, and T. Palpanas.  Coconut: A scalable bottom-up approach for building data series indexes.  PVLDB, 11(6):677–690, 2018.
  * [11] J. Lin, E. J. Keogh, L. Wei, and S. Lonardi.  Experiencing SAX: a novel symbolic representation of time series.  Data Min. Knowl. Discov., 15(2):107–144, 2007.
  * [12] M. Linardi and T. Palpanas.  Scalable, variable-length similarity search in data series: The ulisse approach.  PVLDB, 11(13):2236–2248, 2018.
  * [13] M. Linardi, Y. Zhu, T. Palpanas, and E. J. Keogh.  VALMOD: A suite for easy and exact detection of variable length motifs in data series.  In SIGMOD, pages 1757–1760, 2018.
  * [14] B. Peng, P. Fatourou, and T. Palpanas.  Paris: The next destination for fast data series indexing and query answering.  In IEEE BigData, 2018.
  * [15] T. Rakthanmanon, B. Campana, A. Mueen, G. Batista, B. Westover, Q. Zhu, J. Zakaria, and E. Keogh.  Searching and mining trillions of time series subsequences under dynamic time warping.  In SIGKDD, pages 262–270, 2012.
  * [16] N. Roussopoulos, S. Kelley, and F. Vincent.  Nearest neighbor queries.  In SIGMOD, pages 71–79, 1995.
  * [17] J. Shieh and E. J. Keogh.  _i_ SAX: indexing and mining terabyte sized time series.  In SIGKDD, pages 623–631, 2008.
  * [18] D.-E. Yagoubi, R. Akbarinia, F. Masseglia, and T. Palpanas.  Massively distributed time series indexing and querying.  TKDE (to appear), 2018.
  * [19] C.-C. M. Yeh, Y. Zhu, L. Ulanova, N. Begum, Y. Ding, H. A. Dau, D. F. Silva, A. Mueen, and E. Keogh.  Matrix profile i: all pairs similarity joins for time series: a unifying view that includes motifs, discords and shapelets.  In ICDM, 2016.
  * [20] C. M. Yeh, Y. Zhu, L. Ulanova, N. Begum, Y. Ding, H. A. Dau, Z. Zimmerman, D. F. Silva, A. Mueen, and E. J. Keogh.  Time series joins, motifs, discords and shapelets: a unifying view that exploits the matrix profile.  Data Min. Knowl. Discov., 32(1):83–123, 2018.
  * [21] K. Zoumpatianos, S. Idreos, and T. Palpanas.  Indexing for interactive exploration of big data series.  In SIGMOD, pages 1555–1566, 2014.