# On Reporting Durable Patterns in Temporal Proximity Graphs

Pankaj K. Agarwal  Duke UniversityDurhamUSA<EMAIL_ADDRESS>,  Xiao Hu
University of WaterlooWaterlooCanada<EMAIL_ADDRESS>,  Stavros Sintos
University of Illinois at ChicagoChicagoUSA<EMAIL_ADDRESS>and  Jun Yang
Duke UniversityDurhamUSA<EMAIL_ADDRESS>
(December 2023; February 2024; March 2024)

###### Abstract.

Finding patterns in graphs is a fundamental problem in databases and data
mining. In many applications, graphs are temporal and evolve over time, so we
are interested in finding durable patterns, such as triangles and paths, which
persist over a long time. While there has been work on finding durable simple
patterns, existing algorithms do not have provable guarantees and run in
strictly super-linear time. The paper leverages the observation that many
graphs arising in practice are naturally _proximity graphs_ or can be
approximated as such, where nodes are embedded as points in some high-
dimensional space, and two nodes are connected by an edge if they are close to
each other. We work with an implicit representation of the proximity graph,
where nodes are additionally annotated by time intervals, and design near-
linear-time algorithms for finding (approximately) durable patterns above a
given durability threshold. We also consider an interactive setting where a
client experiments with different durability thresholds in a sequence of
queries; we show how to compute incremental changes to result patterns
efficiently in time near-linear to the size of the changes.

temporal graph, proximity graph, durability, durable pattern, doubling
dimension, cover tree

††copyright: acmlicensed††journal: PACMMOD††journalyear: 2024††journalvolume:
2††journalnumber: 2 (PODS)††article: 81††publicationmonth: 5††doi:
10.1145/3651144††ccs: Theory of computation Data structures and algorithms for
data management

##  1\. Introduction

Finding patterns in large graphs is a fundamental problem in databases and
data mining. In many practical applications, graphs evolve over time, and we
are often more interested in patterns that are “durable,” i.e., persisting
over a long time. Here are two examples of finding durable patterns in
temporal graphs.

###### Example 1.1.

Consider an online forum with social networking features, where users with
similar profiles are connected as friends. Each user may be active on the
forum only for a period of time during the day. We are interested in finding
cliques of connected users who are simultaneously active for a sufficiently
long time period. Such queries are useful to forum administrators who want to
understand how the social network influences user interactions and leverage
this knowledge to promote more interactions.

###### Example 1.2.

Consider a co-authorship graph where two researchers are connected if they
have written at least one paper together. Further suppose that researchers are
each associated with a time period when they remain active in research.
Besides researchers with direct co-authorship, we might be interested in pairs
who co-authored with a set of common researchers over a long period of time.
We would not be interested in researchers with a common co-author if the
respective collaborations happened at distant times.

The problem of finding (durable) patterns , such as triangles, in general
graphs is  challenging: known (conditional) lower bounds suggest that it is
unlikely to have near-linear algorithms (abboud2014popular, ; alon2008testing,
; patrascu2010towards, ). However, many graphs that arise in practice are
naturally _proximity graphs_ , or can be approximated as such. In proximity
graphs, nodes are embedded as points in some high-dimensional space, and two
nodes are connected by an edge if they are close to each other (i.e., their
distance is within some threshold). For example, social networks such as
Example 1.1 can be embedded (with small error) in the space of user profiles
with a low intrinsic dimension (verbeek2014metric, ). Similarly, in the co-
authorship graph, where two authors nodes are connected if they have written
at least $m$ papers together for some $m\geq 1$, the nodes can also be
embedded in a space with low intrinsic dimension (yang2012defining, ).
Generally, for many graphs arising in a wide range of applications (e.g.
social network, transportation network, Internet), there exist appropriate
node embeddings that preserve the structures and shortest paths in the
original graphs (verbeek2014metric, ; zhao2010orion, ; zhao2011efficient, ).
This observation enables us to leverage the properties of proximity graphs to
develop efficient algorithms for finding patterns in such graphs, which
overcome the hardness of the problem on arbitrary graphs.

This paper hence tackles the problem of finding durable patterns in temporal
_proximity_ graphs, for which we are not aware of efficient algorithms. For
simplicity, we assume in this paper that the embedding of the graph is given –
there are efficient algorithms for computing graph embeddings
(verbeek2014metric, ; chen1997algorithmic, ; kutuzov2020making, ;
cai2018comprehensive, ; zeng2019accurate, ). We work with an implicit
representation of the proximity graphs – nodes represented as points and edges
defined between pairs of points within a threshold distance in the embedding
space. We never construct the graph itself explicitly. We design efficient
algorithms whose running time depend on the number of nodes and the intrinsic
dimension (_doubling dimension_) of the data. Our approach extends naturally
to other classes of graphs including interval graphs, permutation graphs, and
grid graphs. Next, we formally define the problems we study. Our notation is
summarized in Table 1.

###  1.1. Problem Definitions

Let $(P,\phi)$ be a metric space over a set of $n$ points
$P\subset\mathbb{R}^{d}$, for some $d\geq 1$, and a metric $\phi$. For a
parameter $r>0$, let $G_{\phi}(P,r)=(P,E)$ where $E=\\{(p,q)\mid\phi(p,q)\leq
r\\}$ be a proximity graph, also called a unit disk graph. For simplicity, we
assume $r=1$ and let $G_{\phi}(P)=G_{\phi}(P,1)$. Suppose a function $I$
assigns each point $p\in P$ to a time interval called its _lifespan_ , denoted
$I_{p}=[I_{p}^{-},I_{p}^{+}]$. We can interpret the lifespan of $p$ as
inserting $p$ at time-stamp $I_{p}^{-}$ and deleting it at time-stamp
$I_{p}^{+}$. We use $(P,\phi,I)$ to refer to the _temporal_ proximity graph,
or the underlying metric space with points annotated with interval lifespans.
For simplicity, all defined problems assume that the query pattern is
triangle. As we point out in Section 1.2, all techniques are extended to more
general patterns.  For an interval $I$, we define $|I|$ as the length of $I$.
If $I$ is a set of intervals then $|I|$ is defined as the length of the union
of intervals in $I$.

Durable triangles. A triplet $(p_{1},p_{2},p_{3})\in P\times P\times P$ forms
a triangle in $G_{\phi}(P)$ if $\phi(p_{1},p_{2})$, $\phi(p_{2},p_{3})$,
$\phi(p_{1},p_{3})\leq 1$. We also introduce an approximate notion of
triangles: for a parameter $\varepsilon>0$, a triplet $(p_{1},p_{2},p_{3})$
forms an $(1+\varepsilon)$-approximate triangle, or $\varepsilon$-triangle for
brevity, if $\phi(p_{1},p_{2})$, $\phi(p_{2},p_{3})$, $\phi(p_{1},p_{3})\leq
1+\varepsilon$. The lifespan of $(p_{1},p_{2},p_{3})$ is defined as
$I(p_{1},p_{2},p_{3})=I_{p_{1}}\cap I_{p_{2}}\cap I_{p_{3}}$. For a durability
parameter $\tau>0$, $(p_{1},p_{2},p_{3})$ is _$\tau$ -durable_ if
$|I(p_{1},p_{2},p_{3})|\geq\tau$. Let $T_{\tau},T_{\tau}^{\varepsilon}$ be the
set of $\tau$-durable triangles, and $\tau$-durable $\varepsilon$-triangles
respectively. Note that $T_{\tau}\subseteq T_{\tau}^{\varepsilon}$.  Given a
$\tau$-durable triangle with three points, the point that _anchors_ the
triangle is the one whose lifespan starts the latest among the three. By
convention, we will list the anchor first in the triplet; i.e., in a
$\tau$-durable triangle $(p,q,s)$, we have
$I_{p}^{-}\geq\max\\{I_{q}^{-},I_{s}^{i}\\}$.

$P$ | point set
---|---
$n$ | $|P|$
$\phi$ | distance function
$\rho$ | doubling dimension
$\varepsilon$ | distance approximation
$\tau$ | durability parameter
$I_{p}=[I_{p}^{-},I_{p}^{+}]$ | lifespan (interval) of point $p$
$T_{\tau}$ |  $\tau$-durable triangles
$T_{\tau}^{\varepsilon}$ |  $\tau$-durable $\varepsilon$-triangles
$K_{\tau}^{\varepsilon}$ |  $\tau$-SUM durable $\varepsilon$-pairs
$K_{\tau,\kappa}^{\varepsilon}$ |  $(\tau,\kappa)$-UNION durable $\varepsilon$-pairs
OUT | Output size
Table 1. Table of Notations

###### Definition 1.3 (DurableTriangle).

Given $(P,\phi,I)$ and $\tau\geq 0$, it asks to report all $\tau$-durable
triangles (or $\varepsilon$-triangles).

Suppose we have embedded the social network in Example 1.1 as a proximity
graph where nodes represent users. The goal is to find triplets (or generally
cliques) of users who are simultaneously active on the forum.111While for
simplicity of exposition we assume that each node has a single-interval
lifespan, it is straightforward to extend our temporal model consider
multiple-interval lifespans, with the complexities of our solutions in the
following sections increased by a factor equal to the maximum number of
intervals per lifespan.

In some use cases, we do not have a clear choice of the durability parameter
$\tau$ in mind, and we may want to explore with different settings. Supporting
this mode of querying motivates the problem of incrementally reporting
$\tau$-durable triangles. Here, queries arrive in an online fashion, each
specifying a different durability parameter $\tau_{1},\tau_{2},\ldots$.
Instead of computing each query $\tau_{i+1}$ from scratch, we want to leverage
the previous query result $T_{\tau_{i}}$ and only incrementally compute what
is new. Note that every $\tau$-durable triangle must also be
$\tau^{\prime}$-durable for every $\tau^{\prime}\leq\tau$. Therefore, if
$\tau_{i+1}\geq\tau_{i}$, we have $T_{\tau_{i+1}}\subseteq T_{\tau_{i}}$ so we
simply need to filter the old results to obtain new ones (assuming we remember
results together with their lifespans). The more interesting case is when
$\tau_{i+1}<\tau_{i}$, so $T_{\tau_{i+1}}\supseteq T_{\tau_{i}}$, and we need
to incrementally report new results.

###### Definition 1.4 (IncrDurableTriangle).

Given $(P,\phi,I)$ and ${\tau_{\prec}}>\tau>0$, it asks to report all
$\tau$-durable triangles (or $\varepsilon$-triangles) that are not
${\tau_{\prec}}$-durable, along with their lifespans.

Aggregate-durable pairs. Given a pair $(p_{1},p_{2})\in P\times P$, we
consider the set $U$ of nodes incident to both $p_{1}$ and $p_{2}$ and
aggregate the lifespans of triplets $(u,p_{1},p_{2})$. We call $U$ the witness
of $(p_{1},p_{2})$. There are two natural ways of aggregating over $U$: SUM
and UNION. For SUM, we aggregate by summing up the durabilities of triplet
lifespans, i.e., $\textsf{AGG}(p_{1},p_{2},U)=\sum_{u\in
U}\left|I(u,{p_{1}},{p_{2}})\right|$. For UNION, we aggregate by first taking
the union of the triplet lifespans and then considering its length, i.e.,
$\textsf{AGG}(p_{1},p_{2},U)=\left|\bigcup_{u\in
U}I(u,{p_{1}},{p_{2}})\right|$. Intuitively, SUM gives higher weights to time
periods when multiple simultaneous connections exist, while UNION only cares
about whether a period is covered at all by any connection. Given durability
parameter $\tau>0$, a pair $(p_{1},p_{2})\in P\times P$ is $\tau$-aggregate-
durable if $\phi(p_{1},p_{2})\leq 1$ and $\textsf{AGG}(p_{1},p_{2},U)\geq\tau$
for $U=\\{u\in P\mid\phi(p_{1},u),\phi(p_{2},u)\leq 1\\}$. We also define
_$\tau$ -aggregate-durable $\varepsilon$-pairs_ by relaxing the distance
thresholds for $\phi(p_{1},p_{2})$, $\phi(p_{1},u)$, and $\phi(p_{2},u)$ from
$1$ to $1+\varepsilon$. Let $K_{\tau},K_{\tau}^{\varepsilon}$ be the set of
all $\tau$-aggregate-durable pairs, $\varepsilon$-pairs respectively. Notice
that $K_{\tau}\subseteq K_{\tau}^{\varepsilon}$.

###### Definition 1.5 (AggDurablePair).

Given $(P,\phi,I)$ and $\tau\geq 0$, it asks to report all $\tau$-aggregate-
durable pairs (or $\varepsilon$-pairs).

Suppose we have embedded the co-authorship graph in Example 1.2 as a proximity
graph where nodes represent authors. The goal is to find pairs of coauthors
$p_{i},p_{j}$ who have collaborated sufficiently with various others, either
in terms of total time over all collaborators (SUM), or over a large portion
of $p_{i}$ and $p_{j}$’s shared active lifespan (UNION).

Problem | Time complexity in $\tilde{O}(\cdot)$
---|---
DurableTriangle | $n\varepsilon^{-O(\rho)}+\textsf{OUT}$
IncrDurableTriangle | $\varepsilon^{-O(\rho)}\cdot\textsf{OUT}$
AggDurablePair–SUM | $\varepsilon^{-O(\rho)}\cdot(n+\textsf{OUT})$
AggDurablePair–UNION | $\kappa\varepsilon^{-O(\rho)}\cdot(n+\textsf{OUT})$
Table 2. Summary of our main results. Here, $n$ is the input size, i.e., the
number of points in $P$; $\rho$ is the doubling dimension of $(P,\phi)$;
$\tau$ is the durability parameter; OUT is the output size for the respective
problem (different for each problem); $\varepsilon$ is the approximation
ratio; and $k$ is the parameter used for $(\tau,\kappa)$-UNION durability. In
the complexities reported above, $\tilde{O}(\cdot)$ hides a
$\mathop{\mathrm{polylog}}n$ factor, and the hidden constants in $O(\cdot)$
and $\tilde{O}(\cdot)$ may depend on $\rho$, which is assumed to be a
constant.

###  1.2. Our Results and Approach

We present algorithms for $\varepsilon$-approximate versions of all three
problems, whose time complexity are summarized in Table 2. In all cases, we
report all durable triangles along with some durable $\varepsilon$-triangles.
The running time is always near-linear in terms of the input and output size,
which is almost the best one could hope for. Our solutions leverage the
observation that proximity graphs in practice often have bounded _spread_
$\Delta$ and _doubling dimension_ $\rho$ — Section 2 further reviews these
concepts and the associated assumptions. The complexities in Table 2 assume
spread to be $n^{O(1)}$ (hence $\Delta$ is omitted) and doubling dimension to
be constant, but our algorithms also work for more general cases.

For DurableTriangle (Section 3), our main approach is to construct a
hierarchical space decomposition consisting of a canonical set of balls, via a
_cover tree_. We use the canonical set of balls to obtain a compact, implicit
representation of points within unit distance from each point, and then use an
interval tree along with auxiliary data structures to report durable triangles
in linear time. The algorithm runs in
$\tilde{O}(n\varepsilon^{-O(\rho)}+\textsf{OUT})$ time, where
$\textsf{OUT}\in[|T_{\tau}|,|T_{\tau}^{\varepsilon}|]$ is the result size.
(The $\tilde{O}(\cdot)$ notation hides polylogarithmic factors). For the
$\ell_{\infty}$ metric, this result can be improved to
$\tilde{O}(n+|T_{\tau}|)$. Moreover, our data structures can be extended to
support delay-guaranteed enumeration as well as dynamic settings where nodes
are inserted or deleted according to their lifespan.

For IncrDurableTriangle (Section 4), to support incremental computation of
queries arriving in an online setting, we additionally maintain an activation
threshold for each point with respect to different durability parameters. In
more detail, for each durability parameter $\tau$, we design an oracle that
can efficiently find the largest value $\beta<\tau$ such that $p$ participates
in a $\beta$-durable triangle that is not $\tau$-durable, which is key to
achieve near-linear time complexity. Our algorithm constructs an
$\tilde{O}(n)$-size data structure in $\tilde{O}(n\varepsilon^{-O(\rho)})$
time, such that given the previous query parameter ${\tau_{\prec}}$ and
current query parameter $\tau<{\tau_{\prec}}$, it can report the delta results
in $\tilde{O}(\varepsilon^{-O(\rho)}\cdot\textsf{OUT})$ time, where
$\textsf{OUT}\in\left[|T_{\tau}-T_{{\tau_{\prec}}}|,|T_{\tau}^{\varepsilon}-T_{{\tau_{\prec}}}^{\varepsilon}|\right]$
is the delta result size. Specifically, for the $\ell_{\infty}$ metric,
IncrDurableTriangle can be solved exactly in
$\tilde{O}(|T_{\tau_{i+1}}\setminus T_{\tau_{i}}|)$ time.

For AggDurablePair (Section 5), recall that the problem requires aggregating
lifespans over witness set $U$. We build auxiliary data structures to compute
the sum or union of intervals intersecting any given interval. Additionally,
we identify a special ordering of $P$ such that only a bounded number of pairs
that are not aggregate-durable will be visited, so the linear-time complexity
can be guaranteed. For the SUM version of the problem, we present an
$\tilde{O}((n+\textsf{OUT})\cdot\varepsilon^{-O(\rho)})$-time algorithm, where
$\textsf{OUT}\in\left[K_{\tau},K^{\varepsilon}_{\tau}\right]$ is the output
size. The UNION version is more challenging because of the inherent hardness
of computing the union of intervals that intersect a query interval. However,
as shown in Section 5.2, we can still get an near-linear-time and output-
sensitive algorithm that reports all $\tau$-UNION-durable pairs along with
some $(1-1/e)\tau$-UNION-durable $\varepsilon$-pairs.

#### Extensions.

Our algorithms also work for every $\ell_{\alpha}$-metric222If $\phi$ is the
_$\ell_{\alpha}$ -metric_ then
$\phi(p,q)=\left(\sum_{j=1}^{d}|p_{j}-q_{j}|^{\alpha}\right)^{1/\alpha}$,
where $p_{j},q_{j}$ are the $j$-th coordinates of points $p$ and $q$,
respectively. or metric with bounded expansion constant333A metric space
$(P,\phi)$ has _expansion constant_ $D$ if $D$ is the smallest value such that
for every $p\in P$ and $r>0$ $|P\cap\mathcal{B}(p,2r)|\leq
D\cdot|P\cap\mathcal{B}(p,r)|$, where $\mathcal{B}(p,r)$ is the ball with
center $p$ and radius $r$.. Moreover, all our results for reporting triangles
can be extended to reporting cliques, paths, and star patterns of constant
size. See details in Appendix D.

Connection with triangle listing algorithms in general graphs. Consider simple
directed or undirected graphs with $n$ vertices and $m$ edges. The trivial
algorithm by listing all triples of vertices runs in $O(n^{3})$ time. This is
worst-case optimal in terms of $n$, since a dense graph may contain
$\Theta(n^{3})$ triangles. A graph with $m$ edges contains $O(m^{3/2})$
triangles. It has been shown that all triangles in a graph of $m$ edges can be
enumerated in $\tilde{O}(m^{3/2})$ time (itai1977finding, ; ngo2018worst, ;
veldhuizen2014leapfrog, ). This is also worst-case optimal, since a graph of
$m$ edges may contain $\Theta(m^{3/2})$ triangles. Later, output-sensitive
algorithms for listing triangles were developed using fast matrix
multiplication, which run in
$\tilde{O}(n^{\omega}+n^{\frac{3(\omega-1)}{5-\omega}}\cdot\textsf{OUT}^{\frac{2(3-\omega)}{5-\omega}})$
or
$\tilde{O}(m^{\frac{2\omega}{\omega+1}}+m^{\frac{3(\omega-1)}{\omega+1}}\cdot\textsf{OUT}^{\frac{3-\omega}{\omega+1}})$
time, where $O(n^{\omega})$ is the running time of $n\times n$ matrix
multiplication and OUT is the number of triangles in the graph
(bjorklund2014listing, ). In contrast, it has been shown (patrascu2010towards,
) that listing $m$ triangles in a graph of $m$ edges requires
$\Omega(m^{4/3-o(1)})$ time, assuming the 3SUM conjecture444The 3SUM
conjecture states that: Given three sets $A,B,C$ of $n$ elements, any
algorithm requires $\Omega(n^{2-o(1)})$ time to determine whether there exists
a triple $(a,b,c)\in A\times B\times C$ such that $a+b+c=0$.. A careful
inspection of this lower bound construction reveals that listing $n^{3/2}$
triangles in a graph of $n$ vertices requires $\Omega(n^{2-o(1)})$ time,
assuming the 3SUM conjecture. These lower bounds together rule out the
possibility of listing triangles in general graphs within
$O(m+n+\textsf{OUT})$ time, unless the 3SUM conjecture is refuted.

Existing techniques for listing triangles in general graphs do not yield
efficient algorithms for our setting and several new ideas are needed to
obtain the results of this paper. First, most traditional techniques for
listing triangles do not handle temporal constraints on vertices or edges.
Recently, efficient algorithms for durable–join with temporal constraints on
edges are proposed in (hu2022computing, ). However, their algorithm requires
$\Omega(m^{3/2})$ time for listing durable triangles, even if the number of
durable triangles is much smaller. Even without temporal constraints, all the
worst-case optimal join algorithms run in super-linear time, in terms of $n$
and OUT, for listing triangles in proximity graphs. Furthermore, in our
setting, the input is an implicit representation of a proximity graph
$(P,\phi)$. To feed $(P,\phi)$ as input to these algorithm, the number of
edges $m$ can be quadratic in terms of $|P|$, which already requires
$\Omega(n^{2})$ time for processing the input, not to mention the time for
identifying triangles. Our algorithms use novel geometric data structures to
identify all triangles that a point belongs to in time which is linear
(ignoring $\log n$ factors) to both input size $n$ and output size OUT.
Finally, the known algorithms do not handle the incremental or the aggregate
versions of our problem, and we need completely new techniques to further
exploit the structure of proximity graphs.

##  2\. Preliminaries

We start by reviewing some basic concepts and data structures. Building on the
basic data structures, we introduce an oracle that will be frequently used by
our algorithms in the ensuing sections.

###  2.1. Basic concepts and data structures

Spread. The _spread_ of a set $P$ under distance metric $\phi$ is the ratio of
the maximum and minimum pairwise distance in $P$. For many data sets that
arise in practice, the spread is polynomially bounded in $n$, and this
assumption is commonly made in machine learning and data analysis
(beygelzimer2006cover, ; cunningham2021k, ; kumar2008good, ;
borassi2019better, ).

#### Doubling dimension.

For $x\in\mathbb{R}^{d}$ and $r\geq 0$, let
$\mathcal{B}(x,r)=\\{y\in\mathbb{R}^{d}\mid\phi(x,y)\leq r\\}$ denote the ball
(under the metric $\phi$) centered at point $x$ with radius $r$. A metric
space $(P,\phi)$ has _doubling dimension_ $\rho$ if for every $p\in P$ and
$r>0$, $\mathcal{B}(p,r)\cap P$ can be covered by the union of at most
$2^{\rho}$ balls of radius $r/2$. For every $\alpha>0$, let $\ell_{\alpha}$ be
the $\alpha$ norm. The metric space $(P,\ell_{\alpha})$ has doubling dimension
$d$ for every $P\subset\mathbb{R}^{d}$, but for specific
$P\subset\mathbb{R}^{d}$, the doubling dimension can be much smaller—e.g.,
points in $3$d lying on a $2$-dimensional plane or sphere has doubling
dimension $2$. Doubling dimensions and their variants are popular approaches
for measuring the intrinsic dimension of a data set in high dimension; see,
e.g., (DBLP:conf/iclr/PopeZAGG21, ; facco2017estimating, ; bshouty2009using, ;
DBLP:conf/iclr/PopeZAGG21, ). It has been widely shown that graphs arising in
practice have low doubling dimension (ng2002predicting, ; tenenbaum2000global,
; feldmann2020parameterized, ; damian2006distributed, ; zhoudoubling, ;
verbeek2014metric, ).  Empirical studies in these papers and other sources
(e.g., (linkDdim, )) show that the doubling dimension of router graphs,
internet latency graphs, citation graphs, and movie database graphs are less
than $15$.

#### Interval tree.

Let $\mathcal{I}$ be a set of intervals. An interval tree
(mark2008computational, ) is a tree-based data structure that can find
intersections of a query interval $I$ with the set of intervals $\mathcal{I}$
stored in the interval tree. For example, it can report or count the number of
intervals in $\mathcal{I}$ intersected by $I$ visiting only $O(\log n)$ nodes.
It has $O(n)$ space and it can be constructed in $O(n\log n)$ time.

#### Cover tree.

A cover tree $\mathcal{T}$ is a tree-based data structure where each node $u$
of $\mathcal{T}$ is associated with a representative point
$\textsf{Rep}_{u}\in P$ and a ball $\mathcal{B}_{u}$. Each node belongs to an
integer-numbered level; if a node $u$ is at level $i$ then its children are at
level $i-1$. Let $C_{i}$ be the set of balls associated with nodes at level
$i$. The radius of each ball $\mathcal{B}_{u}$ at level $i$ is $2^{i}$ (notice
that our definition allows level numbers to be positive or negative). Each
point $p\in P$ is stored in one of the leaf nodes. The root consists of a ball
that covers the entire data set  and its representative point is any point in
$P$. A cover tree satisfies the following constraints:

  * •

(Nesting) If there is a node $u$ at level $i$ with a representative point
$\textsf{Rep}_{u}\in P$, then $\textsf{Rep}_{u}$ is also a representative
point in a node at level $i-1$.

  * •

(Covering) For every representative point $\textsf{Rep}_{u}$ at level $i-1$,
there exists at least one representative $\textsf{Rep}_{v}$ at level $i$ such
that $\phi(\textsf{Rep}_{v},\textsf{Rep}_{u})<2^{i}$. We designate $v$ as the
parent of $u$.

  * •

(Separation) For every $u,v$ at level $i$,
$\phi(\textsf{Rep}_{u},\textsf{Rep}_{v})>2^{i}$.

Traditionally, a cover tree is used mostly for approximate nearest-neighbor
queries (beygelzimer2006cover, ; har2005fast, ).  We modify the construction
of the cover tree to use it for _ball-reporting queries_ in bounded doubling
spaces. Given a point $p$, let
$\mathcal{B}(p,r)=\\{x\in\mathbb{R}^{d}\mid\phi(x,p)\leq r\\}$ be a ball with
radius $r$ centered at $p$, and let $\mathcal{B}(p):=\mathcal{B}(p,1)$. Given
a query point $p$, the goal is to report $B(p)\cap P$ efficiently. We modify
the cover tree to answer ball-reporting queries approximately.  In each node
$u$ of the cover tree, we (implicitly) store $P_{u}$, i.e., the points that
lie in the leaf nodes of the subtree rooted at $u$. Let $p$ be a query point.
We find a set of nodes in the cover tree whose associated balls entirely cover
$\mathcal{B}(p)$ and might cover some region outside $\mathcal{B}(p)$ within
distance $(1+\varepsilon)$ from the center of $\mathcal{B}$. The set of nodes
we find in the query procedure are called _canonical nodes_ , their
corresponding balls are called _canonical balls_ , and the subsets of points
stored in the canonical balls are called _canonical subsets_. In the end, we
report all points stored in the canonical nodes. More formally, in Appendix A,
we show how to construct a data structure with space $O(n)$ in $O(n\log n)$
time, while achieving the following guarantees when the spread is bounded. For
a query point $q\in\mathbb{R}^{d}$, in $O(\log n+\varepsilon^{-O(\rho)})$
time, it returns a set of $O(\varepsilon^{-O(\rho)})$ canonical balls
(corresponding to nodes in the modified cover tree) of diameter no more than
$\varepsilon$, possibly intersecting, such that each point of
$\mathcal{B}(q)\cap P$ belongs to a unique canonical ball. Each canonical ball
may contain some points of $\mathcal{B}(q,1+\varepsilon)\cap P$.

###  2.2. Durable ball query

In this subscection, we describe an extension of the ball-reporting query that
will be frequently used by our algorithms. Given $(P,\phi,I)$, $\tau>0$, and a
point $p$ with interval $I_{p}$, a _$\tau$ -durable ball query_ finds all
points $q\in P$ such that $\phi(p,q)\leq 1$, $|I_{p}\cap I_{q}|\geq\tau$, and
$I_{p}^{-}\in I_{q}$. Answering such a query exactly is inherently expensive
even in the Euclidean space, since a near-linear space data structure has
$\Omega(n^{1-1/d}+\textsf{OUT})$ query time (chan2012optimal, ), where OUT is
the output size. If we use such a data structure for our problem in metrics
with bounded doubling dimension, it would lead to a near-quadratic time
algorithm for the DurableTriangleproblem. Instead, we consider the following
relaxed version:

###### Definition 2.1 ($\varepsilon$-approximate $\tau$-durable ball query).

Given $(P,\phi,I)$, $\tau\geq 0$,  $\varepsilon\in(0,1)$, and a point $p$ with
interval $I_{p}$, find a subset $Q\subseteq P$ of points such that
$\mathcal{B}(p)\cap P\subseteq Q\subseteq\mathcal{B}(p,1+\varepsilon)\cap P$,
and for every $q\in Q$, $|I_{p}\cap I_{q}|\geq\tau$ and $I_{p}^{-}\in I_{q}$.

We note that the condition $I_{p}^{-}\in I_{q}$ is needed to avoid reporting
duplicate results, as we will see in the next sections.

#### Data structure.

Intuitively, we use a multi-level data structure $\mathcal{D}$ to handle this
query. At the first level, we construct a cover tree $\mathsf{CT}$ on $P$ to
find a small number of canonical nodes that contain the points of
$\mathcal{B}(p)\cap P$ (but may also contain some point of
$\mathcal{B}(p,1+\varepsilon)\cap P$). At each node $u$ of the cover tree, we
construct an interval tree $\mathsf{IT}_{u}$ over the temporal intervals of
$P_{u}$. Using the cover tree along with interval trees, we can find a set of
$O(\varepsilon^{-d})$ canonical nodes that contain all points $q$ within
distance $1$ from $p$ and $I_{p}^{-}\in I_{q}$, but they may also contain
points within distance $1+\varepsilon$ from $p$. $\mathcal{D}$ uses $O(n\log
n)$ space and can be constructed in $O(n\log^{2}{n})$ time.

Let $\mathsf{durableBallQ}(p,\tau,\varepsilon)$ denote the query procedure of
$\mathcal{D}$ with parameters $p,\tau,\varepsilon$. It answers the query as
follows:

  * •

(step 1) We query $\mathsf{CT}$ with point $p$ and radius $1$, and obtain a
set of canonical nodes $\mathcal{C}=\\{u_{1},u_{2},\ldots,u_{k}\\}$ for
$k=O(\varepsilon^{-O(\rho)})$. From Appendix A, each node in $\mathcal{C}$
corresponds to a ball with diameter no more than $\varepsilon$. For each
$u_{j}\in\mathcal{C}$, $\phi(p,\textsf{Rep}_{j})\leq 1+\varepsilon/2$.555 For
simplicity, we denote the representative point of a node $u_{i}$ by
$\textsf{Rep}_{i}$.

  * •

(step 2) For each canonical node $u_{j}\in\mathcal{C}$, we query
$\mathsf{IT}_{u_{j}}$ with $I^{-}_{p}$, and obtain all $q\in\mathsf{IT}_{u}$
such that $I_{q}^{-}+\tau\leq I_{p}^{-}+\tau\leq I_{q}^{+}$.

In the end, $\mathsf{durableBallQ}$ returns $O(k)$ disjoint result point sets,
whose union is the answer to the $\varepsilon$-approximate $\tau$-durable ball
query. The grouping of result points into subsets and the implicit
representation of these subsets is an important feature of
$\mathsf{durableBallQ}$ that we shall exploit in later sections. Note that
$\mathsf{durableBallQ}$ might return a point $q$ such that $\phi(p,q)>1$, but
$\phi(p,q)\leq 1+\varepsilon$ always holds. Together, we obtain:

###### Lemma 2.2.

Given a set $P$ of $n$ points, a data structure can be built in
$O(n\log^{2}n)$ time with $O(n\log n)$ space, that supports an
$\varepsilon$-approximate $\tau$-durable ball query, computing a family of
$O(\varepsilon^{-d})$ canonical subsets in $O(\varepsilon^{-d}\log n)$ time.

Extended data structure with refined result partitioning. We define the more
involved query procedure
$\mathsf{durableBallQ}^{\prime}(p,\tau,\tau^{\prime},\varepsilon)$, which will
be used by our algorithms for IncrDurableTriangle in Section 4. The goal is to
return a subset $Q\subseteq P$ such that $\mathcal{B}(q)\cap P\subseteq
Q\subseteq\mathcal{B}(q,1+\varepsilon)\cap P$, and for every $q\in Q$,
$I_{q}^{-}+\tau\leq I_{p}^{-}+\tau\leq I_{q}^{+}$ (just as for
$\mathsf{durableBallQ}$), with the additional constraint that $I_{q}^{+}\geq
I_{p}^{-}+\tau^{\prime}$. Let $\mathcal{D}^{\prime}$ be the extended version
of $\mathcal{D}$ to answer $\mathsf{durableBallQ}^{\prime}$. It consists of a
cover tree along with two levels of interval trees, one to handle the first
linear constraint, and the second to handle the additional linear constraint.
The space, construction time and query time of $\mathcal{D}^{\prime}$ are
increased only by a $\log n$ factor compared with $\mathcal{D}$.

##  3\. Reporting Durable Triangles

This section describes our near-linear time algorithm for the
$\varepsilon$-approximate DurableTriangle problem. As mentioned, our algorithm
works for every general metric with constant doubling dimension. In Appendix
B, we show how to solve the problem exactly for $\ell_{\infty}$ metric.

High-level Idea. We visit each point $p\in P$ with $|I_{p}|\geq\tau$ (a
prerequisite for $p$ to be in a $\tau$-durable triangle), and report all
$\tau$-durable triangles that $p$ anchors. To find all $\tau$-durable
triangles anchored by $p$, we run a $\tau$-durable ball query around $p$ on
$\mathcal{D}$ (Section 2.2) to get an implicit representation (as a bounded
number of canonical subsets) of all points within distance $1$ from $p$, where
$I_{p}^{-}$ is the largest left endpoint among their lifespans  ($p$ should be
the newest point among the three points of each triangle we report). Recall
that each canonical subset returned consists of points within a ball of a
small diameter, so we can approximate inter-ball distances among points by the
distances among the ball centers. For every pair of balls, if their centers
are within distance $1$ (plus some slack), we report all $\tau$-durable
triangles consisting of $p$ and the Cartesian product of points in the two
balls.

1

2$\mathcal{C}_{p}:\\{\mathcal{C}_{p,1},\mathcal{C}_{p,2},\cdots,\mathcal{C}_{p,k}\\}\leftarrow\mathsf{durableBallQ}(p,\tau,\varepsilon/2)$,
with $\textsf{Rep}_{i}$ denoting the representative point of the ball for
$\mathcal{C}_{p,i}$;

3 foreach  _$j\in[k]$_ do

4 foreach  _$q,s\in\mathcal{C}_{p,j}$ where $q$ precedes $s$_ do

5 report $(p,q,s)$;

6

7

8foreach  _$i,j\in[k]$ where $i<j$_ do

9 if  _$\phi(\textsf{Rep}_{i},\textsf{Rep}_{j})\leq 1+\frac{\varepsilon}{2}$_
then

10 foreach  _$(q,s)\in\mathcal{C}_{p,i}\times\mathcal{C}_{p,j}$_ do

11 report $(p,q,s)$;

12

13

14

Algorithm 1 ReportTriangle$(\mathcal{D},p,\tau,\varepsilon)$

#### Algorithm.

As a preprocessing step, we construct the data structure $\mathcal{D}$ as
described in Section 2.2 over $P$. Our algorithm invokes ReportTriangle
(Algorithm 1) for each point $p\in P$. ReportTriangle runs a $\tau$-durable
ball query $\mathsf{durableBallQ}(p,\tau,\varepsilon/2)$—note the use of
$\varepsilon/2$ here for technical reasons—and obtains a family of disjoint
result point sets
$\mathcal{C}_{p}=\\{\mathcal{C}_{p,1},\mathcal{C}_{p,2},\ldots,\mathcal{C}_{p,k}\\}$
for some $k=O(\varepsilon^{-\rho})$ (see also Figure 1). Each
$\mathcal{C}_{p,j}$ is covered by a cover tree ball in $\mathcal{D}$ with
diameter of no more than $\varepsilon/2$, and contains all points therein
whose intervals “sufficiently intersect” $I_{p}$, i.e., any $q$ in the ball
satisfying $I_{q}^{-}+\tau\leq I_{p}^{-}+\tau\leq I_{q}^{+}$, as explained in
Section 2.2.

Figure 1. Illustration of Algorithm 1: $p$ is visited. The small (possibly
overlapping) balls represent the canonical nodes returned from $\mathcal{D}$.
Each point within distance $1$ from $p$ lies in exactly one such ball. We
report the triangles formed by $p$ and the points in red and blue balls that
satisfy the durability constraint. We do not report triangles formed by $p$
and the points in blue and green balls because they are well separated.

Given $p$, all $\tau$-durable triangles $(p,q,s)$ anchored by $p$ can be
classified into two types: (1) $q$ and $s$ belong to the same result point set
$\mathcal{C}_{p,j}$ for some $j$; and (2) $q$ and $s$ belong to different sets
$\mathcal{C}_{p,i}$ and $\mathcal{C}_{p,j}$ (where $i\neq j$) that are
sufficiently close. To report triangles of the first type, we simply enumerate
all pairs of $q$ and $s$ within $\mathcal{C}_{p,j}$, for each $j$. We avoid
duplicate reporting of $(p,q,s)$ and $(p,s,q)$ by always picking $q$ as the
point with the smaller index in $\mathcal{C}_{p,j}$. To report triangles of
the second type, we consider $(i,j)$ pairs where $\textsf{Rep}_{i}$ and
$\textsf{Rep}_{j}$, the representative points of the balls containing
$\mathcal{C}_{p,i}$ and $\mathcal{C}_{p,j}$, are within distance
$1+\varepsilon/2$. We simply enumerate the Cartesian product of
$\mathcal{C}_{p,i}$ and $\mathcal{C}_{p,j}$. We avoid duplicate reporting of
$(p,q,s)$ and $(p,s,q)$ by imposing the order $i<j$.

Correctness. Let $(p,q,s)$ be a triangle reported by our algorithm. We show
that $(p,q,s)$ is a $\tau$-durable $\varepsilon$-triangle. From Section 2.2,
we know that $\phi(p,q)\leq 1+\varepsilon/2$ and $\phi(p,s)\leq
1+\varepsilon/2$, because $q$ and $s$ belong in one or two canonical subsets
in $\mathcal{C}_{p}$. If $q$ and $s$ belong to the same canonical subset
$\mathcal{C}_{p,i}$ then by definition $\phi(q,s)\leq\varepsilon/2$. If
$q\in\mathcal{C}_{p,i}$ and $s\in\mathcal{C}_{p,j}$ for $i\neq j$, then
$\phi(q,s)\leq\phi(q,\textsf{Rep}_{i})+\phi(s,\textsf{Rep}_{j})+\phi(\textsf{Rep}_{i},\textsf{Rep}_{j})\leq\varepsilon/4+\varepsilon/4+(1+\varepsilon/2)\leq
1+\varepsilon$. In every case, it is true that
$\phi(p,q),\phi(p,s),\phi(s,q)\leq 1+\varepsilon$. Hence, $(p,q,s)$ is an
$\varepsilon$-triangle. Next, we show that $|I_{p}\cap I_{q}\cap
I_{s}|\geq\tau$. Recall that by definition, $|I_{p}|\geq\tau$. Using the
$\tau$-durable ball query $\mathsf{durableBallQ}(p,\tau,\varepsilon/2)$, we
have that $|I_{p}\cap I_{q}|\geq\tau$, $|I_{p}\cap I_{s}|\geq\tau$,
$I_{p}^{-}\in I_{q}$, and $I_{p}^{-}\in I_{s}$ (see also Definition 2.1). We
can rewrite these inequalities as $I_{q}^{-}+\tau\leq I_{p}^{-}+\tau\leq
I_{q}^{+}$ and $I_{s}^{-}+\tau\leq I_{p}^{-}+\tau\leq I_{s}^{+}$. Hence,
$I_{p}^{-}+\tau\leq\min\\{I_{q}^{+},I_{s}^{+}\\}$, concluding that $|I_{p}\cap
I_{q}\cap I_{s}|\geq\tau$. Each triangle $(p,q,s)$ is reported only once, in a
specific vertex order: the temporal conditions ensure that $p$ anchors the
triangle, and the ordering of $q$ and $s$ is consistently enforced by
ReportTriangle. Overall, we showed that if $(p,q,s)$ is reported, then it is a
$\tau$-durable $\varepsilon$-triangle and it is reported exactly once.

Next, we prove that we do not miss any $\tau$-durable triangle. Let $(p,q,s)$
be a $\tau$-durable triangle. Without loss of generality, assume that
$I_{p}^{-}\geq\max\\{I_{q}^{-},I_{s}^{-}\\}$. By definition, $\phi(p,q)\leq
1$, $\phi(p,s)\leq 1$, and $\phi(q,s)\leq 1$. Hence, after visiting $p$, by
the definition of the $\tau$-durable ball query
$\mathsf{durableBallQ}(p,\tau,\varepsilon/2)$, there exist indexes $i,j$ such
that $q\in\mathcal{C}_{p,i}$ and $s\in\mathcal{C}_{p,j}$. If $i=j$, then
$(p,q,s)$ must be reported by Line 1 of ReportTriangle. If $i\neq j$, note
that
$\phi(\textsf{Rep}_{i},\textsf{Rep}_{j})\leq\phi(\textsf{Rep}_{i},q)+\phi(q,s)+\phi(s,\textsf{Rep}_{j})\leq\varepsilon/4+1+\varepsilon/4\leq
1+\varepsilon/2$; therefore $(p,q,s)$ must be reported by Line 1. Overall, we
showed that every $\tau$-durable triangle is reported by Algorithm 1.

Time complexity. By Lemma 2.2, we can construct $\mathcal{D}$ in time
$O(n\log^{2}n)$. For each $p\in P$, we run a $\tau$-durable ball query on
$\mathcal{D}$ in $O(\varepsilon^{-O(\rho)}\log n)$ time. Moreover,
$|\mathcal{C}_{p}|=O(\varepsilon^{-O(\rho)})$. Checking pairs in $\mathcal{C}$
in which to search for triangles of Type (2) takes additional
$O(\varepsilon^{-2\cdot O(\rho)})$ time. All pairs of points examined by
ReportTriangle are indeed returned, and together they correspond to all
$\tau$-durable triangles plus some $\varepsilon$-triangles involving $p$.
Hence, the overall additional time incurred is $O(\textsf{OUT})$ where
$|T_{\tau}|\leq\textsf{OUT}\leq|T_{\tau}^{\varepsilon}|$.

###### Theorem 3.1.

Given $(P,\phi,I)$, $\tau>0$, and $\varepsilon>0$, $\varepsilon$-approximate
DurableTriangle can be solved in $O\left(n(\varepsilon^{-O(\rho)}\log
n+\log^{2}n)+\textsf{OUT}\right)$ time, where $n=|P|$, $\rho$ is the doubling
dimension of $P$, and OUT is the number of triangles reported.

Remark 1. For every $\ell_{\alpha}$ norm in $\mathbb{R}^{d}$, we can simplify
the data structure $\mathcal{D}$ using a quadtree instead of a cover tree. The
running time and approximation with respect to the overall number of reported
triangles remain the same.

Remark 2. Our algorithm can be extended to support _delay-guaran-_ teed
enumeration (berkholz2017answering, ; idris2017dynamic, ; agarwal2021dynamic,
) of durable patterns, i.e., the time between reporting two consecutive
patterns is bounded. After spending $O(n(\varepsilon^{-O(\rho)}\log
n+\log^{2}n))$ preprocessing time, we can support
$O(\varepsilon^{-O(\rho)}\log n)$-delay enumeration for
$\varepsilon$-approximate DurableTriangle.

Remark 3. Using a dynamic cover tree, we can extend our algorithm to the
dynamic setting where we do not have all points upfront. If points are
inserted or deleted according to their lifespans, we support $O(\log^{3}n)$
amortized update time. After inserting a point $p$, we can report the new (if
any) triangles that $p$ participates in using Algorithm 1) in time near linear
to the number of new triangles reported. We show the details in Appendix C.

##  4\. Incremental Reporting When Varying $\boldsymbol{\tau}$

We next consider reporting durable triangles when queries with different
durability parameters arrive in an online fashion. As discussed in Section
1.1, the problem, IncrDurableTriangle, boils down to reporting any new result
triangles in $T_{\tau}\setminus T_{\tau_{\prec}}$, where ${\tau_{\prec}}>\tau$
are the previous and current durability parameters, respectively.

As a starter, we can proceed similarly as in Section 3, reporting durable
triangles for each anchor point $p$, but taking care to ensure that we report
only $\tau$-durable triangles that are not ${\tau_{\prec}}$-durable. Doing so
entails retrieving candidate pairs $(q,s)$ as in ReportTriangle, but
additionally guaranteeing that _at least one_ of $q$ and $s$ ends between
$I_{p}^{-}+\tau$ and $I_{p}^{-}+{\tau_{\prec}}$, which leads to $I(p,q,s)$
having durability between $\tau$ and ${\tau_{\prec}}$. This additional search
condition necessitates the modified data structure $\mathcal{D}^{\prime}$
discussed in Section 2.

However, the naive approach above has the following problem. It is possible
that we carry out the search on $\mathcal{D}^{\prime}$ for $p$, only to
realize that in the end no new result triangle needs to be reported. Ideally,
we instead want an _output-sensitive_ algorithm whose running time depends
only on the output size. To this end, we need an efficient way to test whether
$p$ should be _activated_ for output; i.e., there is at least one triangle in
$T_{\tau}\setminus T_{\tau_{\prec}}$ anchored by $p$. This test motivates the
idea of activation thresholds below.

###### Definition 4.1 (Activation threshold).

Given $(P,\phi,I)$ and $\tau>0$, the activation threshold of $p\in P$ with
respect to $\tau$ is defined as:

$\displaystyle\beta^{\tau}_{p}=\max\\{\tau^{\prime}<$
$\displaystyle\tau\mid\exists q,s\in P:I_{q}^{-}\leq I_{p}^{-},\;I_{s}^{-}\leq
I_{p}^{-},\;\text{and}\text{$(p,q,s)$ is $\tau^{\prime}$-durable but not
$\tau$-durable}\\}.$

We set $\beta^{\tau}_{p}=-\infty$ if no such $\tau^{\prime}$ exists. We call
$\beta^{+\infty}_{p}$ the _maximum activation threshold_ of $p$.

With activation thresholds, we can easily determine whether to activate $p$:
the condition is precisely $\beta^{\tau_{\prec}}_{p}\geq\tau$. If
$\beta^{\tau_{\prec}}_{p}<\tau$, by definition of $\beta^{\tau_{\prec}}$, any
$\tau$-durable triangle anchored by $p$ is already ${\tau_{\prec}}$-durable
and hence does not need to be reported; otherwise, we need to at least report
$\beta^{\tau_{\prec}}$-durable triangles anchored by $p$.

In the following subsections, we first describe the algorithm for processing
each activated point (Section 4.1), and then address the problem of computing
activation thresholds efficiently (Section 4.2), which requires maintaining
additional data structures across queries to help future queries. Finally, we
summarize our solution and discuss its complexity (Section 4.3). Appendix B.3
describes our specialized solution for the $\ell_{\infty}$-metric.

###  4.1. Reporting for each activated point

1
$\mathcal{C}_{p}:\\{\mathcal{C}_{p,1},\mathcal{C}_{p,2},\cdots,\mathcal{C}_{p,k}\\}\leftarrow\mathsf{durableBallQ}^{\prime}(p,\tau,{\tau_{\prec}},\varepsilon/2)$,
with $\textsf{Rep}_{i}$ as the representative point of the ball for
$\mathcal{C}_{p,i}$ and
$\mathcal{C}_{p,i}=\Lambda_{p,i}\cup\smash{\overline{\Lambda}}_{p,i}$;

2 foreach  _$j\in[k]$_ do

3 foreach  _$q,s\in\Lambda_{p,j}$ where $q$ precedes $s$_ do

4 report $(p,q,s)$;

5

6 foreach  _$(q,s)\in\Lambda_{p,j}\times\smash{\overline{\Lambda}}_{p,j}$_ do
report $(p,q,s)$ ;

7

8foreach  _$i,j\in[k]$ where $i<j$_ do

9 if  _$\phi(\textsf{Rep}_{i},\textsf{Rep}_{j})\leq 1+\frac{\varepsilon}{2}$_
then

10 foreach  _$(q,s)\in\Lambda_{p,i}\times\Lambda_{p,j}$_ do report $(p,q,s)$ ;

11 foreach  _$(q,s)\in\Lambda_{p,i}\times\smash{\overline{\Lambda}}_{p,j}$_ do
report $(p,q,s)$ ;

12 foreach  _$(q,s)\in\smash{\overline{\Lambda}}_{p,i}\times\Lambda_{p,j}$_ do
report $(p,q,s)$ ;

13

14

Algorithm 2
ReportDeltaTriangle$(\mathcal{D}^{\prime},p,\tau,{\tau_{\prec}},\varepsilon)$

Given an activated point $p\in P$, for which we have already determined that
$\beta^{\tau_{\prec}}_{p}\geq\tau$, we report all $\tau$-durable triangles
anchored by $p$ that are not ${\tau_{\prec}}$-durable, using
ReportDeltaTriangle (Algorithm 2) explained further below.

As discussed at the beginning of this section, reporting triangles $(p,q,s)$
that are $\tau$-durable but not ${\tau_{\prec}}$-durable entails ensuring that
at least one of $q$ and $s$ ends between $I_{p}^{-}+\tau$ and
$I_{p}^{-}+{\tau_{\prec}}$. To this end, we use the modified data structure
$\mathcal{D}^{\prime}$ discussed in Section 2. We query $\mathcal{D}^{\prime}$
using $\mathsf{durableBallQ}^{\prime}(p,\tau,{\tau_{\prec}},\varepsilon/2)$ to
get $k=O(\varepsilon^{-O(\rho)})$ canonical balls of the cover tree in
$\mathcal{D}^{\prime}$ with representative points
$\textsf{Rep}_{1},\textsf{Rep}_{2},\ldots,\textsf{Rep}_{k}$;
$\mathsf{durableBallQ}^{\prime}$ further partitions the result point set
$\mathcal{C}_{p,j}$ associated with each ball centered at $\textsf{Rep}_{j}$
into two subsets

$\Lambda_{p,j}=\smash{\left\\{q\in\mathcal{C}_{p,j}\mid
I_{q}^{+}<I_{p}^{-}+{\tau_{\prec}}\right\\}}\text{,
}\smash{\overline{\Lambda}}_{p,j}=\smash{\left\\{q\in\mathcal{C}_{p,j}\mid
I_{q}^{+}\geq I_{p}^{-}+{\tau_{\prec}}\right\\}}.$

By definition, if $q\in\Lambda_{p,j}$, then $I_{q}^{-}\leq I_{p}^{-}$ and
$I_{p}^{-}+\tau\leq I_{q}^{+}<I_{p}^{+}+{\tau_{\prec}}$, while if
$q\in\smash{\overline{\Lambda}}_{p,j}$ then $I_{q}^{-}\leq I_{p}^{-}$ and
$I_{q}^{+}\geq I_{p}^{-}+{\tau_{\prec}}$. See Figure 2 for an illustration.

Figure 2. An illustration of
$\mathcal{C}_{p,j}=\Lambda_{p,j}\cup\smash{\overline{\Lambda}}_{p,j}$. Here
$q_{1}\in\Lambda_{p,j}$ and $q_{2}\in\smash{\overline{\Lambda}}_{p,j}$.

Recall that $\mathsf{durableBallQ}^{\prime}$ does not explicitly construct
$\Lambda_{p,j}$ and $\smash{\overline{\Lambda}}_{p,j}$; instead, these subsets
correspond to canonical subsets of nodes in the interval trees within
$\mathcal{D}^{\prime}$.

For $(p,q,s)$ to be _not_ ${\tau_{\prec}}$-durable, at least one of $q$ and
$s$ must belong to some $\Lambda_{p,j}$ instead of
$\smash{\overline{\Lambda}}_{p,j}$. Therefore, we can divide all triangles
$(p,q,s)$ that are $\tau$-durable but not ${\tau_{\prec}}$-durable into four
types, which can be computed with the help of the above partitioning: (1)
$q,s\in\Lambda_{p,j}$ for some $j$; (2) $q\in\Lambda_{p,j}$ and
$s\in\smash{\overline{\Lambda}}_{p,j}$ for some $j$; (3) $q\in\Lambda_{p_{i}}$
and $s\in\Lambda_{p,j}$ for some $i\neq j$ where $\textsf{Rep}_{i}$ and
$\textsf{Rep}_{j}$ are sufficiently close; (4) $q\in\Lambda_{p_{i}}$ and
$s\in\smash{\overline{\Lambda}}_{p,j}$ for some $i\neq j$ where
$\textsf{Rep}_{i}$ and $\textsf{Rep}_{j}$ are sufficiently close.
ReportDeltaTriangle (Algorithm 2) covers all these cases. As with
ReportTriangle in Section 3, we enforce an ordering between $q$ and $s$ to
ensure that only one of $(p,q,s)$ and $(p,s,q)$ is reported. Thanks to the
implicit representation of $\Lambda_{p,j}$’s and
$\smash{\overline{\Lambda}}_{p,j}$’s, ReportDeltaTriangle avoids enumerating
points in a subset if they do not contribute to any result triangle. For
example, if $\smash{\overline{\Lambda}}_{p,i}=\emptyset$ (line 2 of Algorithm
2), we short-circuit the computation and avoid enumerating $\Lambda_{p,j}$.

#### Remark.

Note that ReportTriangle (Section 3) can be seen as as special case of
ReportDeltaTriangle whenever ${\tau_{\prec}}>\max_{p\in
P}\beta^{+\infty}_{p}$.

###  4.2. Computing activation thresholds

We turn to the question of how to compute the activation threshold
$\beta^{\tau_{\prec}}$ given $p$ and ${\tau_{\prec}}$, required for
determining whether to activate $p$. Naively, we can find all triangles
anchored by $p$ (regardless of durability) and build a map of all activation
thresholds for $p$. However, we have a more efficient solution that builds on
two ideas. First, consider a sequence of queries with durability parameters
$\tau_{1},\tau_{2},\ldots$. After answering the current query, say $\tau_{i}$,
we compute and remember $\beta^{\tau_{i}}_{p}$ for each (relevant) $p$, so
they are available to help the next query $\tau_{i+1}$. Second, we use a
binary search procedure to look for activation thresholds within a desired
range, by exploiting the extended data structure $\mathcal{D}^{\prime}$ to
quickly test existence of thresholds in a range without enumerating result
triangles therein.

1 $I^{+}\leftarrow\\{I_{q}^{+}\mid q\in P\\}$, $R\leftarrow n-1$, $L\leftarrow
0$, $\tau_{\mathsf{ret}}\leftarrow-\infty$;

2 while  _$L\leq R$_ do

3 $m\leftarrow\lfloor(L+R)/2\rfloor$;

4 if  _$I^{+}[m] >I_{p}^{-}+\tau$_ then $R\leftarrow m-1$;

5 else if  _$I^{+}[m] <I_{p}^{-}$_ then $L\leftarrow m+1$;

6 $\tau^{\prime}\leftarrow I^{+}[m]-I_{p}^{-}$;

7 $B\leftarrow\textsc{DetectTriangle}(\tau^{\prime},\tau)$;

8 if  _$B=\textnormal{{true}}$_ then
$\tau_{\mathsf{ret}}\leftarrow\tau^{\prime}$, $L\leftarrow m+1$;

9 else $R\leftarrow m-1$;

10

11return $\tau_{\mathsf{ret}}$;

12

13Subroutine $\textsc{DetectTriangle}(\tau_{1},\tau_{2})$ begin

14
$\mathcal{C}_{p}:\\{\mathcal{C}_{p,1},\mathcal{C}_{p,2},\cdots,\mathcal{C}_{p,k}\\}\leftarrow\mathsf{durableBallQ}^{\prime}(p,\tau_{1},\tau_{2},\varepsilon/2)$,
with $\textsf{Rep}_{i}$ denoting the representative point of the ball for
$\mathcal{C}_{p,i}$ and
$\mathcal{C}_{p,i}=\Lambda_{p,i}\cup\smash{\overline{\Lambda}}_{p,i}$;

15 foreach  _$j\in[k]$_ do

16 if  _$|\Lambda_{p,j}|\geq 2$_ then return true;

17 if  _$|\Lambda_{p,j}|\geq 1$ and $|\smash{\overline{\Lambda}}_{p,j}|\geq
1$_ then return true;

18

19 foreach  _$i,j\in[k]$ where $i<j$_ do

20 if  _$\phi(\textsf{Rep}_{i},\textsf{Rep}_{j})\leq 1+\frac{\varepsilon}{2}$_
then

21 if  _$|\Lambda_{p,i}|\geq 1$ and $|\Lambda_{p,j}|\geq 1$_ then return true;

22 if  _$|\Lambda_{p,i}|\geq 1$ and $|\smash{\overline{\Lambda}}_{p,j}|\geq
1$_ then return true;

23 if  _$|\smash{\overline{\Lambda}}_{p,i}|\geq 1$ and $|\Lambda_{p,j}|\geq
1$_ then return true;

24

25

26 return false;

27

28

Algorithm 3 ComputeActivation$(\mathcal{D}^{\prime},p,\tau,\varepsilon)$

The second idea is implemented by ComputeActivation (Algorithm 3). It runs a
binary search making guesses for the value of $\beta^{\tau}_{p}$. For each
guess $\tau^{\prime}$ of $\beta^{\tau}_{p}$, we use a primitive called
DetectTriangle to test whether there exists any triangle anchored by $p$ that
is $\tau^{\prime}$-durable but not $\tau$-durable—in other words, whether
$\beta^{\tau}_{p}\in[\tau^{\prime},\tau)$. DetectTriangle mirrors Algorithm 2,
except that it merely checks the existence of triangles for each type
returning true or false instead of reporting them. Using
$\mathsf{durableBallQ}^{\prime}$ for returning implicit representations for
$\Lambda_{p,j}$’s and $\smash{\overline{\Lambda}}_{p,j}$’s, it is quick to
check whether their combinations yield a non-empty result set. Given $p$, the
search space of activation thresholds has only $O(n)$ possibilities: The
lifespan of every triangle $(p,q,s)$ anchored by $p$ is either in
$[I^{-}_{p},I^{+}_{q}]$ or $[I^{-}_{p},I^{+}_{s}]$, thus the durability of any
triangle anchored by $p$ falls into the set $\\{I_{q}^{+}-I_{p}^{-}\mid q\in
P,I_{q}^{+}\geq I_{p}^{-}\\}$. The number of steps in the binary search and
the number of invocations of DetectTriangle is $O(\log n)$.

We are now ready to put together the data structures and procedure for
computing and maintaining activation thresholds. We use two simple binary
search trees $\mathcal{S}_{\alpha}$ and $\mathcal{S}_{\beta}$.
$\mathcal{S}_{\alpha}$ indexes all points $p\in P$ by their maximum activation
thresholds $\beta^{+\infty}_{p}$. We precompute $\mathcal{S}_{\alpha}$ by
calling ComputeActivation for each $p\in P$. Once constructed,
$\mathcal{S}_{\alpha}$ remains unchanged across queries.

$\mathcal{S}_{\beta}$ indexes points by their activation thresholds with
respect to the durability parameter. Suppose the current query parameter is
$\tau$ and the previous one is ${\tau_{\prec}}$. Before executing the current
query, $\mathcal{S}_{\beta}$ indexes each point $p$ by
$\beta^{\tau_{\prec}}_{p}$, so the current query can use $\mathcal{S}_{\beta}$
to find $p$’s with $\beta^{\tau_{\prec}}_{p}\geq\tau$ to activate. After
completing the current query, we update $\mathcal{S}_{\beta}$ for the next
round: as long as there exists a $\tau$-durable triangle anchored by $p$,
$\mathcal{S}_{\beta}$ indexes $p$ by the value of $\beta^{\tau}_{p}$.
Initially, $\mathcal{S}_{\beta}$ starts out as an empty tree, which can be
interpreted as having completed an initial query with durability parameter
$+\infty$.

Maintenance of $\mathcal{S}_{\beta}$ has two cases depending on the current
query. First, consider the more interesting case of ${\tau_{\prec}}>\tau$,
where we need to potentially report new result triangles. For each $p$
activated, i.e., $\beta^{\tau_{\prec}}\geq\tau$, we call
$\textsc{ComputeActivation}(\mathcal{D}^{\prime},p,\tau,\varepsilon)$ to
obtain $\beta^{\tau}_{p}$ and update $p$’s entry in $\mathcal{S}_{\beta}$.
This is all we need to do to maintain $\mathcal{S}_{\beta}$ because, if $p$
were not activated for the current query, we would have
$\beta^{\tau_{\prec}}<\tau$, and therefore
$\beta^{\tau}_{p}=\beta^{\tau_{\prec}}_{p}$.

In the less interesting case of $\tau\geq{\tau_{\prec}}$, there are no new
result triangles to report, but some old ones may need to be invalidated.
Strategies for maintaining $\mathcal{S}_{\beta}$ differ depending on the usage
scenario. In the first scenario, suppose that the client issuing the query
sequence incrementally maintains the query result as lists of triangles
grouped by anchor points, and triangles within each list are sorted by
durability. When $\tau\geq{\tau_{\prec}}$, the client can simply trim its
lists according to $\tau$. During this process, it can easy obtain and pass
information to the server for updating $\mathcal{S}_{\beta}$: for each anchor
$p$, $\beta^{\tau}_{p}$ simply takes on the highest durability value removed
from $p$’s list, or it remains unchanged if no triangle is removed. In the
alternative (and less likely) scenario where the client does not remember
anything, the server can simply rebuild $\mathcal{S}_{\beta}$ by running
ComputeActivation for each $p\in\mathcal{S}_{\alpha}$ with maximum activation
threshold no less than $\tau$.

#### Correctness.

We first show that the values $\beta_{p}^{\tau}$ are updated correctly in
Algorithm 3. Let $\tau^{\prime}$ be the parameter in the binary search that we
checked in Algorithm 3. Point $p$ can only form a $\tau^{\prime}$-durable
$\varepsilon$-triangle with points $q$ whose intervals $I_{q}$ intersect
$I_{p}^{-}$ and either $I_{q}^{+}<I_{p}^{-}+\tau$ or $I_{q}^{+}\geq
I_{p}^{-}+\tau$. $\bigcup_{j}\Lambda_{p,j}$ is the set of points satisfying
the first inequality, and $\bigcup_{j}\smash{\overline{\Lambda}}_{p,j}$ the
set of points in the second inequality. For every pair
$q,s\in\smash{\overline{\Lambda}}_{p,j}$, we do not activate point $p$ with
durability $\tau^{\prime}$. If indeed $\phi(q,s)\leq 1$ and
$q,s\in\smash{\overline{\Lambda}}_{p,j}$, then $(p,q,s)$ is a $\tau$-durable
triangle. So our algorithm does not activate a point $p$ because of a
previously reported $\tau$-durable triangle. By definition, it is also
straightforward to see that $p$ should be activated at durability
$\tau^{\prime}$ if there is a pair of points
$q,s\in\Lambda_{p,j}\cup\smash{\overline{\Lambda}}_{p,j}$ such as either $q$
or $s$ belongs in $\Lambda_{p,j}$. This is because either $I_{q}$ or $I_{s}$
does not overlap with $I_{p}$ for more than $\tau$ and overlaps more than
$\tau^{\prime}$, so $(p,q,s)$ was not a $\tau$-durable
$\varepsilon^{\prime}$-triangle for every $\varepsilon^{\prime}>0$. Next, let
$p$ be a point that is activated because of a triangle $(p,q,s)$. We show that
any $(p,q,s)$ is a $\tau^{\prime}$-durable $\varepsilon$-triangle. As we
mentioned, either $I_{q}$ or $I_{s}$ does not intersect $I_{p}$ for more than
$\tau$ but intersects $I_{p}$ for more than $\tau^{\prime}$ so it remains to
show that $\phi(p,q),\phi(p,s),\phi(q,s)\leq 1+\varepsilon$. By the definition
of $\mathcal{D}^{\prime}$ we have that $\phi(p,q)\leq 1+\varepsilon/2$ and
$\phi(p,s)\leq 1+\varepsilon/2$. If $q,s$ belong in the same subset
$\mathcal{C}_{p,j}$ then it also follows that $\phi(q,s)\leq\varepsilon/4\leq
1+\varepsilon$. If $q\in\mathcal{C}_{p,j}$ and $s\in\mathcal{C}_{p,i}$ for
$i<j$ then in Algorithm 3 we only consider this triangle if and only if
$\phi(\textsf{Rep}_{j},\textsf{Rep}_{i})\leq 1+\varepsilon/2$. We have
$\phi(q,s)\leq\phi(q,\textsf{Rep}_{j})+\phi(\textsf{Rep}_{j},\textsf{Rep}_{i})+\phi(\textsf{Rep}_{i},s)\leq
1+\varepsilon/2+\varepsilon/4+\varepsilon/4=1+\varepsilon$. So $(p,q,s)$ is a
$\tau^{\prime}$-durable $\varepsilon$-triangle that is not $\tau$-durable.

The correctness of Algorithm 2 follows from the same arguments we used to
prove the correctness of Algorithm 3. Overall, Algorithm 2 reports all
$\tau_{i+1}$-durable triangles along with some $\tau_{i+1}$-durable
$\varepsilon$-triangles, that are not $\tau_{i}$-durable
$\varepsilon$-triangles. Hence, $|T_{\tau_{i+1}}\setminus
T_{\tau_{i}}|\leq\textsf{OUT}\leq|T_{\tau_{i+1}}^{\varepsilon}\setminus
T_{\tau_{i}}^{\varepsilon}|$.

###  4.3. Solution summary and complexity

In summary, we build the data structure $\mathcal{D}^{\prime}$ as described in
Section 2.2; its size is $O(n\log^{2}n)$, and it can be constructed in
$O(n\log^{3}n)$ time. We also build the index $\mathcal{S}_{\alpha}$ of
maximum activation thresholds, which has size $O(n)$. To construct
$\mathcal{S}_{\alpha}$, as mentioned, we perform at most $O(\log n)$ guesses
for each point, and each guess invokes DetectTriangle once, which takes
$O(\varepsilon^{-O(\rho)}\log^{2}n)$ time; therefore, the total construction
time for $\mathcal{S}_{\alpha}$ is $O(n\varepsilon^{-O(\rho)}\log^{3}n)$.
Finally, we maintain the index $\mathcal{S}_{\beta}$ of activation thresholds
for the current durability parameter; its size is $O(n)$, its initial
construction time is $O(1)$, and its maintenance time will be further
discussed below.

To report new result triangles when the durability parameter changes from
${\tau_{\prec}}$ to $\tau$, we use $\mathcal{S}_{\beta}$ to search for points
$p$ with $\beta^{\tau_{\prec}}_{p}\geq\tau$ to activate. Each activated point
$p$ requires $O(\textsf{OUT}_{p}+\varepsilon^{-O(\rho)}\log^{2}n)$ time for
ReportDeltaTriangle to report all new durable triangles anchored by $p$, where
$\textsf{OUT}_{p}$ denotes the number of them. Then, to maintain
$\mathcal{S}_{\beta}$, we need $O(\varepsilon^{-O(\rho)}\log^{3}n)$ time for
ComputeActivation, and $O(\log n)$ time to update $\mathcal{S}_{\beta}$ for
each point $p$ activated. For each activated $p$, at least one new durable
triangle is reported, so the number of calls to ComputeActivation is bounded
by the output size. Overall, we spend
$O\left(\textsf{OUT}+\varepsilon^{-O(\rho)}\log^{2}n\right)$ time for
reporting and $O(\textsf{OUT}\cdot\varepsilon^{-O(\rho)}\log^{3}n)$ time for
maintenance, where OUT is the number of results reported.

###### Theorem 4.2.

Given $(P,\phi,I)$, and $\varepsilon>0$, a data structure of size
$O(n\log^{2}n)$ can be constructed in $O(n\varepsilon^{-O(\rho)}\log^{3}n)$
time such that, the $\varepsilon$-approximate IncrDurableTriangle problem can
be solved in $O\left(\textsf{OUT}\cdot\varepsilon^{-O(\rho)}\log^{3}n\right)$
time, where $n=|P|$, $\rho$ is the doubling dimension of $P$, and OUT is the
number of results reported.

##  5\. Reporting Aggregate-Durable Pairs

###  5.1. SUM

We start by describing a data structure that allows us to efficiently compute
the total length of all intersections between a query interval with a given
set of intervals. Then we show how to use this primitive to report all
$\tau$-SUM-durable pairs for AggDurablePair-SUM, along with some $\tau$-SUM-
durable $\varepsilon$-pairs (but no other pairs).

#### Interval-SUM-durability.

Given a set of intervals $\mathcal{I}$, we want a primitive that can
efficiently decide, given any query interval $J$ and $\tau>0$, whether
$\sum_{I\in\mathcal{I}}|I\cap J|\geq\tau$. To this end, we construct a data
structure $\mathsf{IT}^{\Sigma}$ over $\mathcal{I}$, which is a variant of an
interval tree where each tree node $v$ is annotated with the following
information:

  * •

$|v|$, the total number of intervals stored at $v$;

  * •

$\sum_{I\in v}|I|$, the total length of intervals stored at $v$;

  * •

$\sum_{I\in v}I^{+}$, the sum of right endpoints of intervals stored at $v$;

  * •

$\sum_{I\in v}I^{-}$, the sum of left endpoints of intervals stored at $v$.

Given a query interval $J$, we obtain $O(\log^{2}n)$ canonical set of nodes in
$\mathsf{IT}^{\Sigma}$, where each node $v$ falls into: (1) every $I\in v$
completely covers $J$; (2) $J$ completely covers every $I\in v$; (3) every
$I\in v$ partially intersects $J$ with $I^{+}\in J$; (4) every $I\in v$
partially intersects $J$ with $I^{-}\in J$. Then, we can rewrite the SUM-
durability of intervals with respect to $J$ as follows:

$\sum_{I\in\mathcal{I}}|I\cap J|=\sum_{v}\sum_{I\in v}|I\cap
J|=\sum_{v}\left\\{\begin{array}[]{ll}|v|\cdot|J|&\textrm{if (1);}\\\
\sum_{I\in v}|I|&\textrm{if (2);}\\\ \sum_{I\in v}I^{+}-|v|\cdot
J^{-}&\textrm{if (3);}\\\ |v|\cdot J^{+}-\sum_{I\in v}I^{-}&\textrm{if
(4).}\end{array}\right.$

Note that $\mathsf{IT}^{\Sigma}$ can be constructed in $O(n\log^{2}n)$ time
and uses $O(n\log n)$ space. This way, we have a procedure ComputeSumD which,
given $\mathsf{IT}^{\Sigma}$ and $J$, returns $\sum_{I\in\mathcal{I}}|I\cap
J|$ in $O(\log^{2}n)$ time. The interval tree $\mathsf{IT}^{\Sigma}$ can also
be used to find $\mathcal{C}_{p}$.

#### Data structure.

While $\mathsf{IT}^{\Sigma}$ makes it efficient to sum durabilities over a set
of intervals given $I_{p}\cap I_{q}$ for a candidate pair $(p,q)$, we cannot
afford to check all possible pairs, and we have not yet addressed the
challenge of obtaining the intervals of interest (which must come from witness
points incident to both $p$ and $q$) in the first place. The high-level idea
is to leverage the same space decomposition from the previous sections to
efficiently obtain canonical subsets of witness points, in their implicit
representation. These canonical subsets of intervals serve as the basis for
building $\mathsf{IT}^{\Sigma}$ structures. In more detail, we construct
$\smash{\mathcal{D}^{\Sigma}}$ in a similar way as $\mathcal{D}$ in Section
2.2. Like $\mathcal{D}$, $\smash{\mathcal{D}^{\Sigma}}$ is a two-level data
structure consisting of a cover tree and an interval tree variant (as
described above) for every node of the cover tree. For each cover tree node
$u$, let $\mathcal{C}_{u}$ denote the subset of points in $P$ within the ball
of $u$ centered at $\textsf{Rep}_{u}$. We build $\mathsf{IT}^{\Sigma}_{u}$
over $\mathcal{C}_{u}$ with SUM annotations, and for each node in
$\mathsf{IT}^{\Sigma}_{u}$, we also store points in decreasing order of their
right interval endpoints. Overall, we can construct
$\smash{\mathcal{D}^{\Sigma}}$ in $O(n\log^{3}n)$ time having $O(n\log^{2}n)$
space.

1

2$\mathcal{C}_{p}:\\{\mathcal{C}_{p,1},\mathcal{C}_{p,2},\cdots,\mathcal{C}_{p,k}\\}\leftarrow\mathsf{durableBallQ}(p,\tau,\varepsilon/2)$,
with $\textsf{Rep}_{i}$ as the representative point of the cover tree node for
$\mathcal{C}_{p,i}$, and $\mathsf{IT}^{\Sigma}_{p,i}$ as the annotated
interval tree for the cover tree node;

3 foreach  _$j\in[k]$_ do

4 foreach  _$q\in\mathcal{C}_{p,j}$ in descending order of $I_{q}^{+}$_ do

5 $t\leftarrow 0$;

6 foreach  _$i\in[k]$_ do

7 if  _$\phi(\textsf{Rep}_{i},\textsf{Rep}_{j})\leq 1+\frac{\varepsilon}{2}$_
then

8 $t\leftarrow t+\textsc{ComputeSumD}(\mathsf{IT}^{\Sigma}_{p,i},I_{p}\cap
I_{q})$;

9

10

11 if  _$t\geq\tau+2\cdot|I_{p}\cap I_{q}|$_ then report $(p,q)$ ;

12 else break;

13

14

Algorithm 4 ReportSUMPair$(\smash{\mathcal{D}^{\Sigma}},p,\tau,\varepsilon)$

#### Algorithm.

We report all $\tau$-SUM-durable pairs $(p,q)$ where $I_{p}^{-}\geq I_{q}^{-}$
(to avoid duplicates); we say $p$ _anchors_ the pair. For each $p\in P$, we
invoke ReportSUMPair (Algorithm 4) to report $\tau$-SUM-durable
$\varepsilon$-pairs $(p,q)$ anchored by $p$. To this end, ReportSUMPair runs
the $\tau$-durable ball query $\mathsf{durableBallQ}(p,\tau,\varepsilon/2)$
over $\smash{\mathcal{D}^{\Sigma}}$, and obtain a family of result point sets
$\mathcal{C}_{p,1},\mathcal{C}_{p,2},\ldots,\mathcal{C}_{p,k}$ for some
$k=O(\varepsilon^{-\rho})$. Each $\mathcal{C}_{p,j}$ is covered by a cover
tree ball in $\smash{\mathcal{D}^{\Sigma}}$ with diameter of no more than
$\varepsilon/2$, and contains all points $q$ within the ball where
$I_{q}^{-}+\tau\leq I_{p}^{-}+\tau\leq I_{q}^{+}$, as explained in Section
2.2, sorted with respect to $I_{q}^{+}$. Let $\mathsf{IT}^{\Sigma}_{p,j}$
denote the interval tree for the cover tree node corresponding to
$\mathcal{C}_{p,j}$. For each $j$, we go through each point
$q\in\mathcal{C}_{p,j}$ in decreasing order of right endpoints to check
whether $(p,q)$ is $\tau$-SUM-durable. To do this check, we consider witnesses
from point sets
$\mathcal{C}_{p,1},\mathcal{C}_{p,2},\ldots,\mathcal{C}_{p,k}$. We can skip an
entire set $\mathcal{C}_{p,i}$ if its ball center $\textsf{Rep}_{i}$ is too
far from $\textsf{Rep}_{j}$, because all points in $\mathcal{C}_{p,i}$ would
be too far from $q$. Otherwise, we query $\mathsf{IT}^{\Sigma}_{p,i}$ using
interval $I_{p}\cap I_{q}$ to obtain the sum of durabilities over all
witnesses in $\mathcal{C}_{p,i}$. We compute these partial sums together and
compare the total with $\tau+2\cdot|I_{p}\cap I_{q}|$ (note that the second
term accounts for the fact that the partial sums include the contributions of
$p$ and $q$ themselves, which should be discounted). If the total passes the
threshold, we report $(p,q)$. If not, we stop consider any remaining point
$q^{\prime}\in\mathcal{C}_{p,j}$ (which has $I^{+}_{q^{\prime}}<I^{+}_{q}$),
since $I_{p}\cap I_{q^{\prime}}\subset I_{p}\cap I_{q}$ and will surely yield
a lower total durability. This is the key for output-sensitive time.

#### Correctness.

First, each pair $(p,q)$ is reported at most once, as $(p,q)$ is reported if
$I_{p}^{-}\geq I_{q}^{-}$. Next, we show that every pair reported must be a
$\tau$-SUM-durable $\varepsilon$-triangle. Consider a pair $(p,q)$ that is
reported. Note that our algorithm considers a node $u_{i}$ from
$\smash{\mathcal{D}^{\Sigma}}$ with radius $\varepsilon/4$ if and only if
$\phi(p,\textsf{Rep}_{i})\leq 1+\varepsilon/4$. If $q\in u_{i}$, we have
$\phi(p,q)\leq\phi(p,\textsf{Rep}_{i})+\phi(\textsf{Rep}_{i},q)\leq
1+\varepsilon/2$. Hence, in any pair $(p,q)$ we return it holds that
$\phi(p,q)\leq 1+\varepsilon$. Then we only consider points within distance
$1+\varepsilon$ from both $p,q$ to find the sum of their corresponding
intervals. Indeed, we only consider the pairs
$\mathcal{C}_{p,i},\mathcal{C}_{p,j}$ with
$\phi(\textsf{Rep}_{i},\textsf{Rep}_{j})\leq 1+\varepsilon/2$. Let
$q^{\prime}$ be any point from $\mathcal{C}_{p,i}$. We have
$\phi(p,q^{\prime})\leq 1+\varepsilon/2$, and
$\phi(q,q^{\prime})\leq\phi(\textsf{Rep}_{i},q)+\phi(\textsf{Rep}_{i},\textsf{Rep}_{j})+\phi(\textsf{Rep}_{j},q^{\prime})\leq
1+\varepsilon$. Overall, by showing i) $\phi(p,q)\leq 1$, ii) that we only
take the sum of intervals in $I_{p}\cap I_{q}$ among points (witness points)
within distance $1+\varepsilon$ from both $p,q$, and iii) the correctness of
the $\mathsf{IT}^{\Sigma}$ data structure, we conclude that the reporting pair
$(p,q)$ is a $\tau$-durable $\varepsilon$-pair.

Finally, we show that every $\tau$-SUM-durable pair will be reported. Let
$(p,q)$ be an arbitrary $\tau$-SUM-durable pair. Suppose $q\in u_{j}$, where
$u_{j}$ is a node of $\smash{\mathcal{D}^{\Sigma}}$ of radius at most
$\varepsilon/4$, with representative point $\textsf{Rep}_{j}$. Since
$\phi(p,\textsf{Rep}_{j})\leq\phi(p,q)+\phi(q,\textsf{Rep}_{j})\leq
1+\varepsilon/4$, we have that $u_{j}\in\mathcal{C}_{p}$. Without loss of
generality, assume that $q\in\mathcal{C}_{p,j}$. Next, we show that for point
$q^{\prime}\in P$, if $\phi(p,q^{\prime})\leq 1$ and $\phi(q,q^{\prime})\leq
1$, we always consider $q^{\prime}$ in the witness set. Since
$\phi(p,q^{\prime})\leq 1$ we have that $q^{\prime}\in\mathcal{C}_{p}$.
Without loss of generality, assume that $q^{\prime}\in\mathcal{C}_{p,i}$. In
this case,
$\phi(\textsf{Rep}_{j},\textsf{Rep}_{i})\leq\phi(\textsf{Rep}_{j},q)+\phi(q,q^{\prime})+\phi(q^{\prime},\textsf{Rep}_{i})\leq
1+\varepsilon/2$, so $q^{\prime}$ is included in $\mathsf{IT}^{\Sigma}_{p,i}$
considered in line 4 of Algorithm 4. It remains to show that if $(p,q)$ is a
$\tau$-durable pair, $q$ must be visited during the traversal of points in
$\mathcal{C}_{p,j}$. We prove it by contradiction. Let $w\in\mathcal{C}_{p,j}$
be a point such that $I_{w}^{-}\leq I_{p}^{-}\leq I_{q}^{+}\leq I_{w}^{+}$.
Suppose after visiting $w$, the traversal of points in $\mathcal{C}_{p,j}$
stops. Implied by the stopping condition, $(p,w)$ is not a $\tau$-SUM-durable
pair. Meanwhile, as $(p,q)$ is a $\tau$-SUM-durable pair, $(p,w)$ must also be
a $\tau$-SUM-durable pair, implied by $I_{q}\cap I_{p}\subseteq I_{w}\cap
I_{p}$, and the fact that we run the
$\textsc{ComputeSumD}(\mathsf{IT}^{\Sigma}_{p,i},I_{p}\cap I_{q})$ query on
the same sets $\mathcal{C}_{p,i}$, coming to a contradiction. Thus, every
$\tau$-SUM-durable pair must be reported.

#### Time Complexity.

The construction time of $\mathsf{IT}^{\Sigma}$ is $O(n\log^{2}n)$, so it
takes $O(n\log^{3}n)$ time to construct $\smash{\mathcal{D}^{\Sigma}}$. For
each $p$, it takes $O(\varepsilon^{-O(\rho)}+\log n)$ time to derive the
canonical set of nodes $\mathcal{C}_{p}$ and $O(\varepsilon^{-O(\rho)}\log n)$
time to derive the sorted intervals in every node of $\mathcal{C}_{p}$. For
each (sorted) interval $I_{q}$ in $\mathcal{C}_{p,i}$ we visit
$O(\varepsilon^{-O(\rho)})$ other nodes $\mathcal{C}_{p,j}$ and we run a
$O(\log^{2}n)$ time query to find the sum using $\mathsf{IT}^{\Sigma}$. When
we find out that $q$ does not form a $\tau$-SUM-durable pair with $p$ we skip
the rest points in $\mathcal{C}_{p,i}$ so the running time is output-
sensitive. Overall, the running time is bounded by
$O(n\log^{3}n+(n+\textsf{OUT})\cdot\varepsilon^{-O(\rho)}\log^{2}n)$, where
$K_{\tau}\leq\textsf{OUT}\leq K_{\tau}^{\varepsilon}$.

###### Theorem 5.1.

Given $(P,\phi,I)$, $\tau>0$ and $\varepsilon>0$, the
$\varepsilon$-approximate AggDurablePair-SUM problem can be solved in
$O(n\log^{3}n+(n+\textsf{OUT})\cdot\varepsilon^{-O(\rho)}\log^{2}n)$ time,
where $n=|P|$, $\rho$ is the doubling dimension of $P$, and OUT is the number
of pairs reported.

###  5.2. UNION

Solving the general AggDurablePair-UNION problem is challenging because of the
inherent hardness of computing the union of intervals that intersect a query
interval, i.e., we cannot design an efficient primitive for UNION as the
ComputeSumD primitive for SUM. In practice, even if the size of the witness
set $U$ is large, a smaller subset of $U$ may be all that is required for its
union to reach the durability parameter. With this observation, we approach
the problem by designing an algorithm whose performance depends on $\kappa$, a
constraint on the size of the witness set. More precisely, given a durability
parameter $\tau>0$ and a positive integer $\kappa\in\mathbb{Z^{+}}$, we say a
pair $(p_{1},p_{2})\in P\times P$ is $(\tau,\kappa)$-UNION-durable if
$\phi(p_{1},p_{2})\leq 1$ and there exists $U\subseteq\\{u\in
P\mid\phi(p_{1},u),\phi(p_{2},u)\leq 1\\}$ such that $|U|\leq\kappa$ and
$\left|\bigcup_{u\in U}I(u,{p_{1}},{p_{2}})\right|\geq\tau$. An approximate
version is defined by replacing the distance constraint $\leq 1$ with $\leq
1+\varepsilon$. We present an
$\tilde{O}((n+\textsf{OUT})\cdot\kappa\varepsilon^{-O(\rho)})$-time algorithm
for
$\textsf{OUT}\in\left[|K_{\tau,k}|,\big{|}K_{(1-1/e)\tau,\kappa}^{\varepsilon}\big{|}\right]$,
with $K_{\tau,\kappa}$ denoting the set of $(\tau,\kappa)$-UNION durable pairs
and $K_{(1-1/e)\tau,\kappa}^{\varepsilon}$ denoting the set of
$((1-1/e)\tau,\kappa)$-UNION durable $\varepsilon$-pairs.

####  $(\tau,\kappa)$-UNION-durable pair.

Next, we focus on finding $(\tau,\kappa)$-UNION-durable pairs for some known
$\kappa$, which should work well in practical cases where a handful of witness
points are able to provide sufficient coverage for the pair. The overall
algorithm has the high-level idea of leveraging the space decomposition as the
AggDurablePair-SUM case in Section 5.1, but it requires a primitive different
from ComputeSumD and a different way of invoking this primitive across witness
subsets.

#### High-level Idea.

Given a set of intervals $\mathcal{I}$ and a target interval $J$, our approach
is to find a subset of intervals $X\subseteq\mathcal{I}$ of size $\kappa$ that
maximizes the UNION-durability with respect to $J$, namely
$\big{|}\bigcup_{I\in X}(I\cap J)\big{|}$ (to compare with $\tau$). There is
an apparent connection to the maximum $\kappa$-coverage problem, where given a
family of sets over a set of elements, we want to choose $\kappa$ sets to
cover the maximum number of elements. Here, we can regard each set as $I\cap
J$ for each $I\in\mathcal{I}$, and the goal is to choose $\kappa$ such sets to
cover as much of $J$ as possible. The standard greedy algorithm gives an
$(1-1/e)$-approximation for this problem (hochbaum1996approximating, ), which
inspires us to follow a similar approach. We leave details on data structures,
pseudocode, correctness and complexity analysis to Appendix E. Our greedy
approach chooses one interval at time to cover $J$, and the choice is always
the one that maximizes the resulting increase in coverage. In more detail, let
$X\subseteq\mathcal{I}$ denote the set of intervals already chosen, which
leaves $J\setminus\bigcup_{I\in X}I$, the uncovered parts of $J$, as a set $Y$
of intervals. Consider the pair $(I_{x},I_{y})$, where
$I_{x}\in\mathcal{I}\setminus X$, and $I_{y}\in Y$, with the largest overlap,
i.e., $I_{x}\cap I_{y}$; we greedily choose $I_{x}$ as the next interval to
cover $J$.

To implement this greedy approach efficiently, we build a data structure
$\smash{\mathcal{D}^{\cup}}$ similarly as $\smash{\mathcal{D}^{\Sigma}}$ in
Section 5.1. $\smash{\mathcal{D}^{\cup}}$ uses a different variant of the
interval tree $\mathsf{IT}^{\cup}$, which, given a query interval $J$, finds
the indexed interval with the largest overlap with $J$. The overall algorithm
reports all $(\tau,\kappa)$-UNION durable pairs for each anchor point $p$ by
querying $\smash{\mathcal{D}^{\cup}}$, and for each candidate $(p,q)$,
performs the greedy choice $k$ times to compute the UNION-durability of
$(p,q)$. Each greedy choice involves querying the $\mathsf{IT}^{\cup}$
structures for the $O(\varepsilon^{-O(\rho)}\log^{2}n)$ canonical subsets of
witness points; some additional elementary data structures help ensure that
the greedy algorithm takes
$O\left(\kappa\varepsilon^{-O(\rho)}\log^{2}n\right)$ time. In Appendix E, we
show that the overall time is
$O\left(n\log^{3}n+(n+\textsf{OUT})\cdot\varepsilon^{-O(\rho)}\kappa\log^{2}n\right)$,
where
$|K_{\tau,\kappa}|\leq\textsf{OUT}\leq\left|K_{(1-1/e)\tau,\kappa}^{\varepsilon}\right|$.
Putting everything together, we obtain:

###### Theorem 5.2.

Given $(P,\phi,I)$, $\tau>0$, $\varepsilon>0$, and integer
$\kappa\in\mathbb{Z}^{+}$, the $\varepsilon$-approximate AggDurablePair-UNION
problem can be solved in
$O(n\log^{3}n+(n+\textsf{OUT})\cdot\varepsilon^{-O(\rho)}\kappa\log^{2}n)$
time, where $n=|P|$, $\rho$ is the doubling dimension of $P$, and OUT is the
number of pairs reported.

##  6\. Related Work

In database and data mining, there is a large body of literature on finding
patterns in temporal graphs (araujo2016discovery, ; gong2012community, ;
lin2008facetnet, ; franzke2018pattern, ; semertzidis2016durable, ;
yang2016diversified, ; redmond2016subgraph, ). Hu et al. (hu2022computing, )
studied the problem of computing temporal join queries efficiently; the
problem of finding durable triangles is a special case of the problem they
studied with self-joins. While (hu2022computing, ; yang2016diversified, ) have
provable guarantees, the algorithms are expensive, requiring time super-linear
in the number of edges to report all durable triangles. Recently, Deng et al.
(deng2023space, ) proposed algorithms to report or count triangles (and other
simple patterns) in time super-linear in the graph size. In contrast, we work
with an implicit representation of the proximity graph and design algorithms
that run in time near-linear in the number of nodes and output size.

There is another line of work in computational geometry on detecting triangles
and other simple patterns in intersection graphs. Eppstein and Erickson
(eppstein1994iterated, ) gave an $O(n\log n)$ algorithm to detect if an
intersection graph consisting of unit balls in $\mathbb{R}^{d}$ has a constant
clique. Kaplan et al. (kaplan2019triangles, ) can detect a triangle in a unit-
disk graph in $\mathbb{R}^{2}$ in $O(n\log n)$ time where edges can be
weighted. The approach in (chan2013klee, ) can detect in $\tilde{O}(n^{d/2})$
time if a clique of constant size exists in an intersection graph of general
boxes in $\mathbb{R}^{d}$. Chan (chan2022finding, ) recently improved the
results on detecting cliques, cycles, and other simple patterns in
intersection graphs, where the nodes are boxes, general fat objects in
$\mathbb{R}^{d}$, or segments in $\mathbb{R}^{2}$, and two nodes are connected
if the corresponding objects intersect. For example, if nodes are fat objects,
their algorithm can detect a constant cycle or clique in $O(n\log n)$ time.
The problems we focus on in this paper have major differences with this line
of work: (i) previous methods only worked for detecting whether a pattern
exists, while our goal is to report all patterns; (ii) all previous works
focused on non-temporal graphs, while we consider the more challenging
temporal graphs, where nodes have lifespans; (iii) we additionally considered
an incremental reporting setting to support queries with different parameters.

The notion of durability has been studied in other queries, such as durable
top-$k$ queries (gao2018durable, ; gao2021durable, ) and durability prediction
(gao2021efficiently, ). It also has been studied in computational topology,
where the goal is to compute “persistent” (durable) topological features; see
(edelsbrunner2022computational, ; dey2022computational, ).

##  7\. Conclusion

In this paper, we have studied the problem of reporting durable patterns in
proximity graphs. We work with an implicit representation of the input graph,
and propose efficient algorithms that run in near-linear time in the number of
nodes, under any general metric with bounded doubling dimension. For future
work, we believe that some of our algorithms and data structures can also be
used for counting durable patterns in near-linear time (instead of reporting
them). Second, while we have focused on simple patterns such as triangles and
paths, it would be interesting to explore near-linear time algorithms for more
general and complex patterns. Third, we have considered only the case when
nodes have lifespans but otherwise remain stationary; one could further
consider the case when their positions change over time (hence inducing also
lifespans on edges). A possible direction is to use _kinetic data structures_
to maintain the evolving graph topology. Finally, a challenging question is
whether we can extend our approach to a general graph already with an explicit
representation, but without first computing an embedding.

## References

  * [1] Doubling dimension in real-world graphs.  https://slideplayer.com/slide/5331329/.  Accessed: 2023-04-24.
  * [2] A. Abboud and V. V. Williams.  Popular conjectures imply strong lower bounds for dynamic problems.  In FOCS, pages 434–443. IEEE, 2014.
  * [3] P. K. Agarwal, X. Hu, S. Sintos, and J. Yang.  Dynamic enumeration of similarity joins.  In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), 2021.
  * [4] N. Alon, T. Kaufman, M. Krivelevich, and D. Ron.  Testing triangle-freeness in general graphs.  SIAM Journal on Discrete Mathematics, 22(2):786–819, 2008.
  * [5] M. Araujo, S. Günnemann, S. Papadimitriou, C. Faloutsos, P. Basu, A. Swami, E. E. Papalexakis, and D. Koutra.  Discovery of “comet” communities in temporal and labeled graphs com2.  Knowledge and Information Systems, 46(3):657–677, 2016.
  * [6] C. Berkholz, J. Keppeler, and N. Schweikardt.  Answering conjunctive queries under updates.  In proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI symposium on Principles of database systems, pages 303–318, 2017.
  * [7] A. Beygelzimer, S. Kakade, and J. Langford.  Cover trees for nearest neighbor.  In Proceedings of the 23rd international conference on Machine learning, pages 97–104, 2006.
  * [8] A. Björklund, R. Pagh, V. V. Williams, and U. Zwick.  Listing triangles.  In International Colloquium on Automata, Languages, and Programming, pages 223–234. Springer, 2014.
  * [9] M. Borassi, A. Epasto, S. Lattanzi, S. Vassilvitskii, and M. Zadimoghaddam.  Better sliding window algorithms to maximize subadditive and diversity objectives.  In Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 254–268, 2019.
  * [10] N. H. Bshouty, Y. Li, and P. M. Long.  Using the doubling dimension to analyze the generalization of learning algorithms.  Journal of Computer and System Sciences, 75(6):323–335, 2009.
  * [11] H. Cai, V. W. Zheng, and K. C.-C. Chang.  A comprehensive survey of graph embedding: Problems, techniques, and applications.  IEEE transactions on knowledge and data engineering, 30(9):1616–1637, 2018.
  * [12] T. M. Chan.  Optimal partition trees.  Discrete & Computational Geometry, 47(4):661–690, 2012.
  * [13] T. M. Chan.  Klee’s measure problem made easy.  In 2013 IEEE 54th annual symposium on foundations of computer science, pages 410–419. IEEE, 2013.
  * [14] T. M. Chan.  Finding triangles and other small subgraphs in geometric intersection graphs.  arXiv preprint arXiv:2211.05345, 2022.
  * [15] J. Chen.  Algorithmic graph embeddings.  Theoretical Computer Science, 181(2):247–266, 1997.
  * [16] P. Cunningham and S. J. Delany.  k-nearest neighbour classifiers-a tutorial.  ACM computing surveys (CSUR), 54(6):1–25, 2021.
  * [17] M. Damian, S. Pandit, and S. Pemmaraju.  Distributed spanner construction in doubling metric spaces.  In Principles of Distributed Systems: 10th International Conference, OPODIS 2006, Bordeaux, France, December 12-15, 2006. Proceedings 10, pages 157–171. Springer, 2006.
  * [18] S. Deng, S. Lu, and Y. Tao.  Space-query tradeoffs in range subgraph counting and listing.  arXiv preprint arXiv:2301.03390, 2023.
  * [19] T. K. Dey and Y. Wang.  Computational topology for data analysis.  Cambridge University Press, 2022.
  * [20] H. Edelsbrunner and J. L. Harer.  Computational topology: an introduction.  American Mathematical Society, 2022.
  * [21] D. Eppstein and J. Erickson.  Iterated nearest neighbors and finding minimal polytopes.  Discrete & Computational Geometry, 11(3):321–350, 1994.
  * [22] J. Erickson.  Static-to-dynamic transformations.  http://jeffe.cs.illinois.edu/teaching/datastructures/notes/01-statictodynamic.pdf.
  * [23] E. Facco, M. d’Errico, A. Rodriguez, and A. Laio.  Estimating the intrinsic dimension of datasets by a minimal neighborhood information.  Scientific reports, 7(1):12140, 2017.
  * [24] A. E. Feldmann and D. Marx.  The parameterized hardness of the k-center problem in transportation networks.  Algorithmica, 82:1989–2005, 2020.
  * [25] M. Franzke, T. Emrich, A. Züfle, and M. Renz.  Pattern search in temporal social networks.  In Proceedings of the 21st International Conference on Extending Database Technology, 2018.
  * [26] J. Gao, P. K. Agarwal, and J. Yang.  Durable top-k queries on temporal data.  Proceedings of the VLDB Endowment, 11(13):2223–2235, 2018.
  * [27] J. Gao, S. Sintos, P. K. Agarwal, and J. Yang.  Durable top-k instant-stamped temporal records with user-specified scoring functions.  In 2021 IEEE 37th International Conference on Data Engineering (ICDE), pages 720–731. IEEE, 2021.
  * [28] J. Gao, Y. Xu, P. K. Agarwal, and J. Yang.  Efficiently answering durability prediction queries.  In Proceedings of the 2021 International Conference on Management of Data, pages 591–604, 2021.
  * [29] M.-G. Gong, L.-J. Zhang, J.-J. Ma, and L.-C. Jiao.  Community detection in dynamic social networks based on multiobjective immune algorithm.  Journal of computer science and technology, 27(3):455–467, 2012\.
  * [30] S. Har-Peled and M. Mendel.  Fast construction of nets in low dimensional metrics, and their applications.  In Proceedings of the twenty-first annual symposium on Computational geometry, pages 150–158, 2005.
  * [31] D. S. Hochbaum.  Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems.  In Approximation algorithms for NP-hard problems, pages 94–143. 1996.
  * [32] X. Hu, S. Sintos, J. Gao, P. K. Agarwal, and J. Yang.  Computing complex temporal join queries efficiently.  In Proceedings of the 2022 International Conference on Management of Data, pages 2076–2090, 2022.
  * [33] M. Idris, M. Ugarte, and S. Vansummeren.  The dynamic yannakakis algorithm: Compact and efficient query processing under updates.  In Proceedings of the 2017 ACM International Conference on Management of Data, pages 1259–1274, 2017.
  * [34] A. Itai and M. Rodeh.  Finding a minimum circuit in a graph.  In Proceedings of the ninth annual ACM symposium on Theory of computing, pages 1–10, 1977.
  * [35] H. Kaplan, K. Klost, W. Mulzer, L. Roditty, P. Seiferth, and M. Sharir.  Triangles and girth in disk graphs and transmission graphs.  In 27th Annual European Symposium on Algorithms (ESA 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019.
  * [36] N. Kumar, L. Zhang, and S. Nayar.  What is a good nearest neighbors algorithm for finding similar patches in images?  In Computer Vision–ECCV 2008: 10th European Conference on Computer Vision, Marseille, France, October 12-18, 2008, Proceedings, Part II 10, pages 364–378. Springer, 2008.
  * [37] A. Kutuzov, M. Dorgham, O. Oliynyk, C. Biemann, and A. Panchenko.  Making fast graph-based algorithms with graph metric embeddings.  In ACL 2019-57th Annual Meeting of the Association for Computational Linguistics, Proceedings of the Conference, pages 3349–3355, 2020\.
  * [38] Y.-R. Lin, Y. Chi, S. Zhu, H. Sundaram, and B. L. Tseng.  Facetnet: a framework for analyzing communities and their evolutions in dynamic networks.  In Proceedings of the 17th international conference on World Wide Web, pages 685–694, 2008.
  * [39] d. B. Mark, C. Otfried, v. K. Marc, and O. Mark.  Computational geometry algorithms and applications.  Spinger, 2008.
  * [40] T. E. Ng and H. Zhang.  Predicting internet network distance with coordinates-based approaches.  In Proceedings. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies, volume 1, pages 170–179. IEEE, 2002.
  * [41] H. Q. Ngo, E. Porat, C. Ré, and A. Rudra.  Worst-case optimal join algorithms.  Journal of the ACM (JACM), 65(3):1–40, 2018.
  * [42] M. Overmars and J. van Leeuwen.  Worst-case optimal insertion and deletion methods for decomposable searching problems.  Inf. Process. Lett., 12(4):168–173, 1981.
  * [43] M. H. Overmars.  The design of dynamic data structures, volume 156.  Springer Science & Business Media, 1987.
  * [44] M. Patrascu.  Towards polynomial lower bounds for dynamic problems.  In STOC, pages 603–610, 2010.
  * [45] P. Pope, C. Zhu, A. Abdelkader, M. Goldblum, and T. Goldstein.  The intrinsic dimension of images and its impact on learning.  In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021, 2021.
  * [46] U. Redmond and P. Cunningham.  Subgraph isomorphism in temporal networks.  arXiv preprint arXiv:1605.02174, 2016.
  * [47] K. Semertzidis and E. Pitoura.  Durable graph pattern queries on historical graphs.  In 2016 IEEE 32nd International Conference on Data Engineering (ICDE), pages 541–552. IEEE, 2016.
  * [48] J. B. Tenenbaum, V. d. Silva, and J. C. Langford.  A global geometric framework for nonlinear dimensionality reduction.  science, 290(5500):2319–2323, 2000.
  * [49] T. L. Veldhuizen.  Leapfrog triejoin: A simple, worst-case optimal join algorithm.  In Proc. International Conference on Database Theory, 2014.
  * [50] K. Verbeek and S. Suri.  Metric embedding, hyperbolic space, and social networks.  In Proceedings of the thirtieth annual symposium on Computational geometry, pages 501–510, 2014.
  * [51] J. Yang and J. Leskovec.  Defining and evaluating network communities based on ground-truth.  In Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics, pages 1–8, 2012.
  * [52] Y. Yang, D. Yan, H. Wu, J. Cheng, S. Zhou, and J. C. Lui.  Diversified temporal subgraph pattern mining.  In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1965–1974, 2016.
  * [53] H. Zeng, H. Zhou, A. Srivastava, R. Kannan, and V. Prasanna.  Accurate, efficient and scalable graph embedding.  In 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 462–471. IEEE, 2019.
  * [54] X. Zhao, A. Sala, C. Wilson, H. Zheng, and B. Y. Zhao.  Orion: shortest path estimation for large social graphs.  networks, 1:5, 2010.
  * [55] X. Zhao, A. Sala, H. Zheng, and B. Y. Zhao.  Efficient shortest paths on massive social graphs.  In 7th International Conference on Collaborative Computing: Networking, Applications and Worksharing (CollaborateCom), pages 77–86. IEEE, 2011.
  * [56] F. Zhou.  Doubling dimension and treewidth.

##  Appendix A Cover tree for ball reporting queries

We consider the case where the doubling dimension is constant or the expansion
constant is bounded by a constant. Furthermore, we assume that the spread of
the items $P$ is bounded by a polynomial on $n$. Given a query item $q$ and an
error threshold $\varepsilon$ the goal is to find a family of sets
$C=\\{C_{1},\ldots,C_{m}\\}$, with $m=O(\varepsilon^{-O(\rho)})$, such that
$C_{i}\subseteq P$, $C_{i}\cap C_{j}=\emptyset$, for every item $p\in P$ with
$\phi(p,q)\leq 1$, $p\in C_{j}$, for an index $j\leq m$, and for every point
$p\in\bigcup_{i\leq m}C_{i}$ it holds that $\phi(p,q)\leq 1+\varepsilon$.
Finally we require that the distance of any pair of items inside $C_{i}$ to be
at most $\varepsilon$.

When the spread is bounded, the cover tree consists of $O(\log n)$ levels. Let
assume that the root has the highest level and the leaf nodes the lowest
level. Each node $v$ in the cover tree is associated with a representative
point $\textsf{Rep}_{v}\in P$. For each node $v$ in level $i$ of the cover
tree it holds that: i) If $u$ is another node in level $i$ then
$\phi(\textsf{Rep}_{v},\textsf{Rep}_{u})>2^{i}$. ii) If $v$ is not the root
node, it always has a parent $w$ in level $i+1$. It holds that
$\phi(\textsf{Rep}_{v},\textsf{Rep}_{w})<2^{i+1}$. iii) If $v$ is not a leaf
node, $v$ has always a child $w$ such that
$\textsf{Rep}_{v}=\textsf{Rep}_{w}$. Assuming that the doubling dimension is
$\rho$ we have that each node $v$ of the cover tree has $O(2^{O(\rho)})=O(1)$
children. The same, constant bound, holds for bounded expansion constant. The
standard cover tree has space $O(n)$ and can be constructed in $O(n\log n)$
time [7, 30].

Notice that every node in the lowest level contains one item from $P$ and each
item in $P$ appears in one leaf node. Let $P_{v}$ be the set of points stored
in (the leaf nodes of) the subtree rooted at node $v$. We do not explicitly
store $P_{v}$ in every node $v$ of the cover tree. Instead, for every node $v$
we add a pointer to the leftmost leaf node in the subtree rooted at $v$. If we
also link all the leaf nodes, given a node $v$, we can report all points in
$P_{v}$ following the pointers, in $O(|P_{v}|)$ time. Our modified cover tree
has space $O(n)$ and can be constructed in $O(n\log n)$ time. For each node
$v$ in level $i$, let $r_{v}=2^{i}$ be its separating radius and
$e_{v}=2^{i+1}$ be its covering radius.

###### Lemma A.1.

If $p\in P_{v}$ then $\phi(p,\textsf{Rep}_{v})<e_{v}$.

###### Proof.

It follows by induction on the level of the tree. In the leaf nodes it holds
trivially. We assume that it holds for all nodes in level $i-1$. We show that
it holds for every node at level $i$. Let $v$ be a node at level $i$. By
definition we have that if $w$ is a child of $v$ then
$\phi(\textsf{Rep}_{v},\textsf{Rep}_{w})<r_{v}$. By the induction assumption,
if $p\in P_{w}$ it holds that $\phi(p,\textsf{Rep}_{w})<e_{w}$, so
$\phi(p,\textsf{Rep}_{v})\leq\phi(\textsf{Rep}_{v},\textsf{Rep}_{w})+\phi(p,\textsf{Rep}_{w})<r_{v}+e_{w}=2^{i+1}=e_{v}$.
∎

#### Query procedure

Given a query point $q$ and an error threshold $\varepsilon$, we start the
query procedure in the modified cover tree we constructed above. In each level
$i$ we visit the nodes $v$ such that $r_{v}>1$ and
$\phi(q,\textsf{Rep}_{v})\leq 1+e_{v}$. Let $V_{i}$ be the nodes in level $i$
we visit such that $r_{v}=1$ for $v\in V_{i}$. Then we consider each of the
node $v\in V_{i}$ and we get all nodes $u$ in the subtree of $v$ with
$r_{u}=\varepsilon/4$. Let $C^{\prime}$ be the set of all nodes $u$ we found.
We go through each node $w\in C^{\prime}$ and we check whether
$\phi(q,\textsf{Rep}_{w})\leq 1+\varepsilon/2$. If yes, then we add $P_{w}$ in
$C$. Otherwise, we skip it.

###### Lemma A.2.

The query procedure is correct.

###### Proof.

Let $p\in P$ be an item such that $\phi(q,p)\leq 1$. We need to show that $p$
belongs in a set in $C$. Let $i$ be the level of the node $v$ such that $p\in
P_{v}$ and $r_{v}=1$. Since $\phi(q,p)\leq 1$ it also holds that
$\phi(q,\textsf{Rep}_{v})\leq\phi(q,p)+\phi(p,\textsf{Rep}_{v})\leq 1+e_{v}$.
Hence, we will visit node $v$ in the query procedure and we will add it in set
$V_{i}$. Since $p\in P_{v}$ and $v\in V_{i}$, by definition, item $p$ lies in
one of the nodes $w$ in $C^{\prime}$. We have
$\phi(q,\textsf{Rep}_{w})\leq\phi(q,p)+\phi(p,\textsf{Rep}_{w})\leq
1+\varepsilon/2$. So we will keep $w$ in $C$.

Finally, notice that for each $p\in P_{w}$ for a node $w$ in $C$, we have
$\phi(q,p)\leq\phi(q,\textsf{Rep}_{w})+\phi(p,\textsf{Rep}_{w})\leq
1+\varepsilon/2+\varepsilon/2\leq 1+\varepsilon$. So the query procedure is
correct. ∎

###### Lemma A.3.

The query procedure runs in $O(\log n+\varepsilon^{-O(\rho)})$ time.

###### Proof.

We first bound the number of nodes $v$ we visit in level $i$ with $r_{v}=1$.
Recall that we only consider $v$ if $\phi(q,\textsf{Rep}_{v})\leq 1+e_{v}\leq
3$. Equivalently, we can think of a ball $\mathcal{B}$ of radius $3$ and
center $q$. Each node $v$ defines a ball $\mathcal{B}_{v}$ with center
$\textsf{Rep}_{v}$ and radius $1$. Also notice that the centers of any two
balls $\mathcal{B}_{v},\mathcal{B}_{u}$ have distance at least $1$. The number
of nodes we visit in level $i$ is the same as the number of balls
$\mathcal{B}_{v}$ that intersect $\mathcal{B}$. Using the bounded doubling
dimension, it is easy to argue that ball $\mathcal{B}$ of radius $3$ can be
covered by at most $O(2^{O(\rho)})=O(1)$ balls of radius $1$ (a similar
argument holds for bounded expansion constant). Hence, we can argue that in
each level above $i$ we only visit $O(1)$ number of nodes. So in total we
visit $O(\log n)$ nodes until we reach level $i$ with $2^{i}=1$. Next, since
the doubling dimension is $\rho$ each node can have $O(2^{O(\rho)})$ children.
It follows that the number of nodes we visit with $r_{u}=\varepsilon/4$ in the
subtree of any node $v$ (with $r_{v}=1$) in $C^{\prime}$ is
$O(\varepsilon^{-O(\rho)})$. Overall, the query time is $O(\log
n+\varepsilon^{-O(\rho)})$. ∎

##  Appendix B Exact algorithms and data structures for $\ell_{\infty}$

###  B.1. $\tau$-durable ball query

###### Definition B.1 ($\tau$-durable range query).

Given a set of items $P\subseteq\mathbb{R}^{d}$, a durability parameter
$\tau>0$, a query point $p\in P$ and a rectangle $R$, the $\tau$-durable range
query asks to find all points $q\in P\cap R$ such that $|I_{p}\cap
I_{q}|\geq\tau$ and $I^{-}_{p}\in I_{q}$.

Intuitively, this query asks to find all points in $R$ whose intervals trimmed
by $\tau$ from the left endpoint intersect $I_{p}^{-}+\tau$. This query can be
solved by a multi-level data structure built on range tree (or cover tree) and
interval tree. In particular, we construct a range tree $\mathsf{RT}$ over the
set of points in $P$. For each node $u$ in the $d$-th level of $\mathsf{RT}$,
we further construct an interval tree $\mathsf{IT}_{u}$ over the intervals of
the points lying in the rectangle defined by $u$. Let $\mathcal{D}_{R}$ be the
data structured constructed above. By slightly abusing the notation, let
$\mathcal{Q}_{R}(p,\tau,R)$ be the query procedure with parameters $p,\tau,R$.
The data structure $\mathcal{D}_{R}$ uses $O(n\log^{d+1}n)$ space and can be
constructed in $O(n\cdot\log^{d}n)$ time. The query
$\mathcal{Q}_{R}(p,\tau,R)$ can be answered over $\mathcal{D}_{R}$ as follows.
(Step 1) we first query the $\mathsf{RT}$ with the input rectangle $R$, and
will obtain a set of $d$-th level nodes that lie inside $R$; (Step 2) for each
node $u$ returned, we query the $\mathsf{IT}_{u}$ with $I^{-}_{p}$, and will
obtain all $q\in\mathsf{IT}_{u}$, such that $I_{q}^{-}+\tau\leq
I_{p}^{-}+\tau\leq I_{q}^{+}$. By resorting to existing result on range
reporting, we obtain:

###### Lemma B.2.

A data structure can be built in $O(n\cdot\log^{d}n)$ time with
$O(n\log^{d+1}n)$ space, such that any $\tau$-durable range query can be
answered in $O(\log^{d+1}n+\textsf{OUT})$ time, where OUT is the number of
query results.

Using the same data structure, we can also determine whether $K>0$ or not,
i.e., if there exists any query answer for a $\tau$-durable range query, in
$O(\log^{d+1}n)$ time.

###  B.2. DurableTriangle

Assume $G$ is a unit disk graph under the $\ell_{\infty}$-norm distance
function. Recall that $P\in\mathbb{R}^{d}$ is a set of points, where each
point $p$ is associated with the lifespan interval $I_{p}$.

Figure 3. An illustration of Algorithm 5: $p$ is visited.

1

2$\square^{p}\leftarrow\\{\square^{p}_{1},\square^{p}_{2},\ldots,\square^{p}_{2^{d}}\\}$
as canonical unit squares of $p$;

3 foreach  _$j\in[2^{d}]$_ do

4
$\mathcal{C}_{p,j}\leftarrow\mathcal{Q}_{R}\left(p,\tau,\square^{p}_{j}\right)$;

5 Report $(p,q,q^{\prime})$ for every
$(q,q^{\prime})\in\mathcal{C}_{p,j}\times\mathcal{C}_{p,j}$ if $q\neq
q^{\prime}$;

6 foreach  _$q\in\mathcal{C}_{p,j}$_ do

7 foreach  _$j <k\leq 2^{d}$_ do

8
$\mathcal{L}_{p,q}\leftarrow\mathcal{Q}_{R}\left(p,\tau,\square^{q}\cap\square^{p}_{k}\right)$;

9 Report $(p,q,q^{\prime})$ for every $q^{\prime}\in\mathcal{L}_{p,q}$;

10

11

12

13

Algorithm 5 ReportTriangle-I$(p,\tau,\mathcal{D}_{R})$

#### Algorithm.

As a preprocessing step, we construct the data structure $\mathcal{D}_{R}$ as
described in Section B.1 over $P$. We visit every point in $P$. For each point
$p$ visited, we enumerate all $\tau$-durable triangles that contain $p$ such
that $\max\\{I_{q}^{-},I_{q^{\prime}}^{-}\\}+\tau\leq
I_{p}^{-}+\tau\leq\min\\{I_{q}^{+},I_{q^{\prime}}^{+}\\}$ for every
$(p,q,q^{\prime})$ reported. Below, we focus on one specific point $p$, as
described in Algorithm 5.

We construct a square with side-length $2$ and center $p$, and we split it
into $2^{d}$ canonical unit squares
$\square^{p}=\left\\{\square^{p}_{1},\ldots,\square^{p}_{2^{d}}\right\\}$.
Then we consider each $\square^{p}_{j}$ in order, by running a $\tau$-durable
range query $\mathcal{Q}_{R}\left(p,\tau,\square^{p}_{j}\right)$. Let
$\mathcal{C}_{p,j}$ be the set of canonical subsets returned. We also use the
same notation $\mathcal{C}_{p,j}$ for the set of points in the corresponding
canonical subset. We further distinguish a $\tau$-durable triangle
$(p,q,q^{\prime})$ into two types: (1) $q,q^{\prime}\in\square^{q}_{j}$; (2)
$q\in\square^{q}_{j},q^{\prime}\in\square^{q}_{k}$ for $j\neq k$. We only need
to report triangles in type (1) when $|\mathcal{C}_{p,j}|>1$, i.e., there are
multiple points from $\square^{p}_{j}$ within durability threshold, hence
every pair $(q,q^{\prime})\in\mathcal{C}_{p,j}\times\mathcal{C}_{p,j}$ with
$q\neq q^{\prime}$ must form a $\tau$-durable triangle with $p$. To report
triangles in type (2), for each point $q\in\mathcal{C}_{p,j}$ returned, we
issue another $\tau$-durable range query
$\mathcal{Q}_{R}\left(p,\tau,\square^{q}\cap\square^{p}_{k}\right)$ for every
$k\geq j$, whose answer is exactly the set of points that form a
$\tau$-durable triangle in type (2) with $p,q$.

Correctness. It is straightforward to see that if the union of all
$\tau$-durable triangles reported for each point $p$ that intersect
$I_{p}^{-}$, in the end, it is exactly the set of all $\tau$-durable
triangles. Furthermore, each $\tau$-durable triangle is reported once.
Finally, it is easy to show that all $\tau$-durable triangles are reported
with respect to a point $p$ whose intervals intersect $I_{p}^{-}$. When
reporting a triangle $(p,q,q^{\prime})$, we always have $||p-q||\leq 1$,
$||p-q^{\prime}||\leq 1$, $||q-q^{\prime}||\leq 1$ and $|I_{p}\cap I_{q}\cap
I_{q^{\prime}}|\geq\tau$ due to the definition of the unit squares
$\square^{p}$ and data structure $\mathcal{D}_{R}$.

Time Complexity. Implied by Lemma B.2, the data structure $\mathcal{D}_{R}$
can be constructed in $O(n\log^{d+1}n)$ time, and each $\tau$-durable range
query can be answered in $O(\log^{d+1}n)$ time. Then, we count the number of
such range queries issued in total. For each point $p$, it invokes $O(2^{d})$
queries each for one distinct unit square, and $O(|\mathcal{C}_{p,j}|)$
queries each for one point $q\in\mathcal{C}_{p,j}$. We point out two critical
observations:

  * •

there are at most $2^{d}$ different $j$ such that $|\mathcal{C}_{p,j}|=1$;

  * •

if $|\mathcal{C}_{p,j}|\geq 2$, then all points in $\mathcal{C}_{p,j}$ form
$\frac{1}{2}\cdot|\mathcal{C}_{p,j}|\cdot(|\mathcal{C}_{p,j}|-1)$
$\tau$-durable triangles together with $p$.

Combining these two observations yields the following inequality:

$\displaystyle\sum_{j\in[2^{d}]}|\mathcal{C}_{p,j}|$
$\displaystyle\leq\sum_{j\in[2^{d}]:|\mathcal{C}_{p,j}|=1}1+\sum_{j\in[2^{d}]:|\mathcal{C}_{p,j}|\geq
2}|\mathcal{C}_{p,j}|$ $\displaystyle\leq
2^{d}+\sqrt{2\cdot|T_{p,\tau}|}+1=O(\sqrt{|T^{p}_{\tau}|})$

where $T^{p}_{\tau}$ is number of $\tau$-durable triangles that contain $p$.
Then, the total number of invocations would be upper bounded by

$\displaystyle\sum_{p\in P}\left(2^{d}+\sum_{j\in
2^{d}}|\mathcal{C}_{p,j}|\right)=$ $\displaystyle n+\sum_{p\in
P}\sqrt{|T^{p}_{\tau}|}\leq n+\sqrt{n\cdot|T_{\tau}|}\leq n+|T_{\tau}|$

where the second inequality follows Cauchy-Schwarz inequality. Thus, the total
running time is $O\left((n+|T_{\tau}|)\cdot\log^{d+1}n\right)$. We can further
improve the analysis, by a fine-grained analysis:

  * •

If $n\leq|T_{\tau}|\leq n\log^{2d+2}n$, then
$\sqrt{n\cdot|T_{\tau}|}\cdot\log^{d+1}n\leq n\log^{2d+2}n$;

  * •

If $n\geq|T_{\tau}|$, then $\sqrt{n\cdot|T_{\tau}|}\cdot\log^{d+1}\leq
n\log^{d+1}n$;

  * •

If $|T_{\tau}|\geq n\log^{2d+2}n$, then
$\sqrt{n\cdot|T_{\tau}|}\cdot\log^{d+1}n\leq n\log^{d+1}n$;

Overall, the running time can be upper bounded by
$O(n\log^{2d+2}n+|T_{\tau}|)$. Compared with our previous result
$O((n+|T_{\tau}|)\cdot\log^{d+1}n)$, we have removed the logarithmic factor
from $|T_{\tau}|$, but increased the logarithmic factor on the input size $n$.
This is significantly important, since $|T_{\tau}|$ can be as large as
$O(n^{3})$ in the worst case, while the increase on the logarithmic factor can
be negligible.

###### Theorem B.3.

Given $(P,\phi,I)$, and $\tau>0$, where $P$ is a set of $n$ points in
$\mathbb{R}^{d}$ and $\phi$ is the $\ell_{\infty}$ norm, DurableTriangle can
be solved in $O(n\log^{2d+2}n+|T_{\tau}|)$ time, where $T_{\tau}$ is the set
of $\tau$-durable triangles formed by points in $P$.

###  B.3. IncrDurableTriangle for the $\ell_{\infty}$ metric

#### Compute Activation Thresholds.

For a set $P$ of $n$ points, we first build the data structure
$\mathcal{D}_{R}$ as described in Section B.1 over $P$, and then invoke
Algorithm 6. In particular, we construct an extended version of
$\mathcal{D}_{R}$ to handle interval queries with one additional linear
constraint on the endpoints as we will see later. Hence, the query time in
$\mathcal{D}_{R}$ is increased by $\log n$. More specifically, we construct a
square with side-length $2$ centered at $p$, and split it into $2^{d}$
canonical unit squares
$\square^{p}=\\{\square^{p}_{1},\ldots,\square^{p}_{2^{d}}\\}$. Then we
consider each $\square^{p}_{j}$ in order, by running a $\tau$-durable range
query $\mathcal{Q}_{R}\left(p,\tau,\square^{p}_{j}\right)$. Let
$\mathcal{C}_{p,j}$ be the set of points returned. More specifically, using
the extended version of $\mathcal{D}_{R}$, we further partition
$\mathcal{C}_{p,j}$ into two different subsets of points, $\Lambda_{p,j}$ and
$\smash{\overline{\Lambda}}_{p,j}$. Intuitively, for every point $q$ returned
from $\mathcal{C}_{p,j}$, $\tau^{\prime}\leq|I_{q}\cap I_{p}|<\tau$ if
$q\in\Lambda_{p,j}$, and $|I_{q}\cap I_{p}|\geq\tau$ otherwise. We can find
$O(\log^{d+2}n)$ canonical subsets containing
$\Lambda_{p,j},\smash{\overline{\Lambda}}_{p,j}$ using $\mathcal{D}_{R}$. If
there is a unit square $\square_{j}^{p}$ that contains at least 2 points and
at least one of them is in $\Lambda_{p,j}$ then we return that there exists a
$\tau^{\prime}$-durable triangle that is not $\tau$-durable. Otherwise,
similar to Algorithm 5, we check if any point of $\Lambda_{p,j}$ forms a
$\tau^{\prime}$-durable triangle, which is not $\tau$-durable, with any other
point in $C_{p,j}$. If this is the case then we return true. Otherwise, we
return false. As mentioned, we perform at most $O(\log n)$ guesses and it
takes $O(\log^{d+2}n)$ time to run Algorithm 6 for each guess of
$\tau^{\prime}$.

1
$\square^{p}\leftarrow\\{\square^{p}_{1},\square^{p}_{2},\ldots,\square^{p}_{2^{d}}\\}$
as canonical unit squares of $p$;

2 foreach  _$j\in[2^{d}]$_ do

3 $\mathcal{C}_{p,j}\leftarrow\mathcal{Q}_{R}(p,\tau,\square^{p}_{j})$;

4 $\Lambda_{p,j}=\left\\{q\in\mathcal{C}_{p,j}:I^{-}_{q}\leq I_{p}^{-}\textrm{
and }I_{p}^{-}+\tau^{\prime}\leq I^{+}_{q}<I_{p}^{-}+\tau\right\\}$;

5
$\smash{\overline{\Lambda}}_{p,j}=\left\\{q\in\mathcal{C}_{p,j}:I_{q}^{-}\leq
I_{p}^{-}\textrm{ and }I_{q}^{+}\geq I_{p}^{-}+\tau\right\\}$;

6 if  _$|\mathcal{C}_{p,j}|\geq 2$ and $|\Lambda_{p,j}|\geq 1$_ then return
true;

7 foreach  _$q\in\Lambda_{p,j}$_ do

8 foreach  _$1\leq k\leq 2^{d}$_ do

9 if
_$\mathcal{Q}_{R}\left(p,\tau,\square^{q}\cap\square^{p}_{k}\right)\neq\emptyset$_
then return true;

10

11

12

13return false;

Algorithm 6 DetectTriangle-I$(p,\mathcal{D}_{R},\tau,\tau^{\prime})$

#### Reporting Algorithm.

Suppose $\tau_{i+1},\tau_{i}$ are the durability parameters of current and
last query separately. For completeness, we set $\tau_{0}=-\infty$. We
distinguish the following two cases.

#### Case 1: $\tau_{i+1}>\tau_{i}$.

We note that this case degenerates to the offline setting of reporting all
$\tau_{i+1}$-durable triangles. We can simply issue a range query to
$\mathcal{S}_{\alpha}$ to find $P_{\tau_{i+1}}$, i.e., the points that
participate in at least one $\tau$-durable triangle, and then invoke Algorithm
5 for each point $p\in P_{\tau_{i+1}}$. Additionally, we reconstruct
$\mathcal{S}_{\beta}$ from scratch, by adding every point $p\in
P_{\tau_{i+1}}$ into $\mathcal{S}_{\beta}$ with the value of
$\beta^{\tau}_{p}$.

#### Case 2: $\tau_{i+1}<\tau_{i}$.

In this case, our target is to report all triangles in
$T_{\tau_{i+1}}\setminus T_{\tau_{i}}$. We first point out that any triangle
in $T_{\tau_{i+1}}\setminus T_{\tau_{i}}$ falls into one of the following two
cases:

  * •

there exists one point, say $p$, with $\tau_{i+1}\leq\alpha_{p}<\tau_{i}$.

  * •

there exists one point, say $p$ with
$\tau_{i+1}\leq\beta^{\tau_{i}}_{p}<\tau_{i}<\alpha_{p}$.

To report triangles in the former case, we find all points $p$ with
$\tau_{i+1}\leq\alpha_{p}<\tau_{i}$ from $\mathcal{S}_{\alpha}$. Let
$P_{\tau_{i+1}}^{\alpha}$ be the set of such points $p$. For each $p\in
P_{\tau_{i+1}}^{\alpha}$, we invoke Algorithm 5 to report all
$\tau_{i+1}$-durable triangles that contain $p$.

To report triangles in the latter case, we find all points $p$ with
$\tau\leq\beta^{\tau_{i}}_{p}$ from $\mathcal{S}_{\beta}$. Let
$P_{\tau_{i+1}}^{\beta}$ be the set of such points $p$. For each such a point
$p\in P_{\tau_{i+1}}^{\beta}$ we invoke Algorithm 7 to report all triangles in
$T_{\tau_{i+1}}\setminus T_{\tau_{i}}$ that contain each such a point $p$.
Notice that $P_{\tau_{i+1}}=P_{\tau_{i+1}}^{\alpha}\cup
P_{\tau_{i+1}}^{\beta}$

1
$\square^{p}\leftarrow\\{\square^{p}_{1},\square^{p}_{2},\ldots,\square^{p}_{2^{d}}\\}$
as canonical unit squares of $p$;

2 foreach  _$j\in[2^{d}]$_ do

3 $\mathcal{C}_{p,j}\leftarrow\mathcal{Q}_{R}(p,\tau_{i+1},\square^{p}_{j})$;

4 $\Lambda_{p,j}=\left\\{q\in\mathcal{C}_{p,j}:I^{-}_{q}\leq
I_{p}^{-},I_{p}^{-}+\tau_{i+1}\leq I^{+}_{q}<I_{p}^{-}+{\tau_{i}}\right\\}$;

5
$\smash{\overline{\Lambda}}_{p,j}=\left\\{q\in\mathcal{C}_{p,j}:I_{q}^{-}\leq
I_{p}^{-},I_{q}^{+}\geq I_{p}^{-}+{\tau_{i}}\right\\}$;

6 Report $(p,q,q^{\prime})$ for every
$(q,q^{\prime})\in\Lambda_{p,j}\times\Lambda_{p,j}$ if $q\neq q^{\prime}$;

7 Report $(p,q,q^{\prime})$ for every $q\in\Lambda_{p,j}$ and
$q^{\prime}\in\smash{\overline{\Lambda}}_{p,j}$;

8 foreach  _$q\in\Lambda_{p,j}$_ do

9 foreach  _$k\in[2^{d}]$ with $k<j$_ do

10
$\mathcal{L}_{p,q}\leftarrow\mathcal{Q}_{R}(p,\tau_{i+1},\square^{q}\cap\square^{p}_{k})\setminus\Lambda_{p,k}$;

11 Report $(p,q,q^{\prime})$ for every $q^{\prime}\in\mathcal{L}_{p,q}$;

12

13 foreach  _$k\in[2^{d}]$ with $k>j$_ do

14
$\mathcal{L}_{p,q}\leftarrow\mathcal{Q}_{R}(p,\tau_{i+1},\square^{q}\cap\square^{p}_{k})$;

15 Report $(p,q,q^{\prime})$ for every $q^{\prime}\in\mathcal{L}_{p,q}$;

16

17

18

19

Algorithm 7 ReportDeltaTriangle-I$(p,\mathcal{D}_{R},\tau_{i},\tau_{i+1})$

We construct a square with side-length $2$ and center $p$, and we split it
into $2^{d}$ canonical unit squares
$\square^{p}=\\{\square^{p}_{1},\ldots,\square^{p}_{2^{d}}\\}$. We also
partition each $\mathcal{C}_{p,j}$ into two different subsets of points,
$\Lambda_{p,j}$ and $\smash{\overline{\Lambda}}_{p,j}$. We further distinguish
a $\tau_{i+1}$-durable but non ${\tau_{i}}$-durable triangle
$(p,q,q^{\prime})$ that contains $p$ into three types: (1)
$q,q^{\prime}\in\Lambda_{q,j}$; (2) $q\in\Lambda_{q,j}$,
$q^{\prime}\in\smash{\overline{\Lambda}}_{q,j}$; (3)
$q\in\Lambda_{q,j},q^{\prime}\in\smash{\overline{\Lambda}}_{q,k}$ for $j\neq
k$. We only need to report triangles in type (1) when $|\Lambda_{p,j}|>1$,
i.e., there are multiple points from $\mathcal{C}_{p,j}$ with durability
threshold in $[\tau_{i+1},{\tau_{i}})$, hence every pair in the Cartesian
product of $\Lambda_{p,j}\times\Lambda_{p,j}$ must form a $\tau_{i+1}$-durable
but not ${\tau_{i}}$-durable triangle with $p$. We only need to report
triangles in type (2) when $|\Lambda_{p,j}|\geq 1$ and
$|\smash{\overline{\Lambda}}_{p,j}|\geq 1$, i.e., there exists a pair of
points from $\mathcal{C}_{p,j}$ with durability threshold in
$[\tau_{i+1},{\tau_{i}})$ and $[{\tau_{i}},+\infty)$ separately, hence every
pair in the Cartesian product of
$\Lambda_{p,j}\times\smash{\overline{\Lambda}}_{p,j}$ must form a
$\tau_{i+1}$-durable but not ${\tau_{i}}$-durable triangle with $p$. To report
triangles in type (3), for each point $q\in\Lambda_{p,j}$ returned, we issue
another $\tau_{i+1}$-durable range query
$\mathcal{Q}_{R}\left(p,\tau_{i+1},\square^{q}\cap\square^{p}_{k}\right)$ for
every $k\neq j$, whose answer is exactly is the set of points that form a
$\tau_{i+1}$-durable but not ${\tau_{i}}$-durable triangle with $p,q$.

After the end of the enumeration, we update $\mathcal{S}_{\beta}$. By
definition, it suffices to compute $\beta^{\tau_{i+1}}_{p}$ for every point
$p\in P_{\tau_{i+1}}$. We distinguish two cases for each point $p\in
P_{\tau_{i+1}}$:

  * •

if ${\tau_{i+1}}\leq\alpha_{p}<{\tau_{i}}$, we compute
$\beta^{\tau_{i+1}}_{p}$ as described in the beginning of Section B.3.

  * •

otherwise, $\alpha_{p}>{\tau_{i}}$. We further distinguish two more cases:

    * –

if $\beta^{\tau_{i}}_{p}<{\tau_{i+1}}$, we do not need to change the
activation threshold for $p$, since
$\beta^{\tau_{i}}_{p}=\beta^{\tau_{i+1}}_{p}$ in this case.

    * –

otherwise, $\beta^{\tau_{i}}_{p}\geq{\tau_{i+1}}$, we compute
$\beta^{\tau_{i+1}}_{p}$.

#### Correctness.

We show that the values $\beta_{p}^{\tau_{i+1}}$ are updated correctly. Let
$\tau^{\prime}$ be the parameter in the binary search that we checked in
Algorithm 6 Point $p$ can only form $\tau^{\prime}$-durable triangles with
points $q$ whose intervals $I_{q}$ intersect $I_{p}^{-}$ and either
$I_{q}^{+}<I_{p}^{-}+\tau$ or $I_{q}^{+}\geq I_{p}^{-}+\tau$.
$\bigcup_{j}\Lambda_{p,j}$ is the set of points satisfying the first
inequality, and $\bigcup_{j}\smash{\overline{\Lambda}}_{p,j}$ the set of
points in the second inequality. For every pair
$q,s\in\smash{\overline{\Lambda}}_{p,j}$, we do not activate point $p$ with
durability $\tau^{\prime}$. If indeed $||q-s||_{\infty}<1$ and
$q,s\in\smash{\overline{\Lambda}}_{p,j}$, then $(p,q,s)$ is a $\tau$-durable
triangle. So our algorithm will not activate a point $p$ because of a
previously reported $\tau$-durable triangle. It is also straightforward to see
that $p$ should be activated at time $\tau^{\prime}$ if there is a pair of
points $q,s\in\Lambda_{p,j}\cup\smash{\overline{\Lambda}}_{p,j}$ such as
either $q$ or $s$ belongs in $\Lambda_{p,j}$.

We next show the correctness of Algorithm 7. The case with
${\tau_{i+1}}>{\tau_{i}}$ follows from the offline setting. The same arguments
for Algorithm 6 apply here, such that we only consider points in
$P_{\tau_{i+1}}$ that should be activated, and Algorithm 7 only reports new
$\tau_{i+1}$-durable triangles.

#### Time Complexity.

For both cases ${\tau_{i+1}}>{\tau_{i}}$ and ${\tau_{i+1}}<{\tau_{i}}$, we
spend $O\left(|T_{\tau_{i+1}}\setminus T_{\tau_{i}}|\cdot\log^{d+2}n\right)$
time to report all ${\tau_{i+1}}$-durable triangles, and $O(\log^{d+3}n)$ time
to compute $\beta^{\tau_{i+1}}_{p}$ for each point $p\in P_{\tau_{i+1}}$. As
defined, each point $p\in P_{\tau_{i+1}}$ must participate in at least one new
${\tau_{i+1}}$-durable triangle, which is also reported in this case. Hence,
the overall time is bounded by $O\left(|T_{\tau_{i+1}}\setminus
T_{\tau_{i}}|\cdot\log^{d+3}n\right)$.

###### Theorem B.4.

Given $(P,\phi,I)$, where $P$ is a set of $n$ points in $\mathbb{R}^{d}$ and
$\phi$ is the $\ell_{\infty}$ norm, a data structure of size $O(n\log^{d+2}n)$
can be constructed in $O(n\log^{d+3}n)$ time such that, IncrDurableTriangle
can be solved in $O\left(|T_{\tau_{i+1}}\setminus
T_{\tau_{i}}|\cdot\log^{d+3}n\right)$ time.

##  Appendix C Dynamic Setting

In this setting, we assume that we do not know the point set $P$ upfront. We
start with an empty point set $P^{\prime}=\emptyset$, and some input
parameters $\tau,\varepsilon$. The goal is to construct a data structure such
that, if all points are inserted and deleted according to their lifespans, it
supports the following operations: i) if a point is deleted the data structure
is updated efficiently, and ii) if a point $p$ is inserted, the data structure
is updated efficiently and $\tau$-durable triangles (if any) of the form
$(p,q,s)$ are reported such that $I_{p}^{-}\geq\max\\{I_{q}^{-},I_{s}^{-}\\}$
along with some $\tau$-durable $\varepsilon$-triangles that contain $p$. We
call it the DynamicOffDurable problem.

We note that the data structure we need in this dynamic setting is a dynamic
version of $\mathcal{D}$. In particular, we slightly modify the standard
techniques to convert our static data structure to a dynamic one with
amortized update guarantees [42, 22, 43].

We call the new dynamic data structure $\mathcal{D}^{\textsf{dyn}}$. Let
$P^{\prime}$ be the current instance of $O(n)$ “active” points.
$\mathcal{D}^{\textsf{dyn}}$ consists of $K=O(\log n)$ subsets of points
$G_{1},\ldots,G_{K}$ such that for each $i\leq K$, $G_{i}\subseteq P^{\prime}$
and $\bigcup_{i\leq K}G_{i}=P^{\prime}$. For each $i\leq K$, we have a static
data structure $\mathcal{D}$, called $\mathcal{D}^{i}$, over $G_{i}$. It holds
that for each $i\leq K$, $|G_{i}|$ is either $2^{i}$ or $0$. The total space
of the data structure is $O(n\log n)$.

Assume that we have to remove $p\in P$. We identify the group $i$ such that
$p\in G_{i}$. We also identify the leaf node $u$ of the cover tree
$\mathcal{T}_{i}$ that $p$ belongs to. Both of these operations can easily be
executed in $O(\log n)$ time with some auxiliary data structures. Then we
traverse $\mathcal{T}_{i}$ from $u$ to the root removing $p$ from the linked
interval trees. Notice that the structure of $\mathcal{D}^{i}$ does not
change, instead only the information stored in the nodes of the interval trees
containing $p$ are updated.

Next, assume that a new point $p$ is inserted at time $I_{p}^{-}$. We first
place $p$ in a temporary min heap $H$ with value $I_{p}^{-}+\tau$ (the time
instance that $p$ can participate in $\tau$-durable triangles). When we reach
time $I_{p}^{-}+\tau$, we derive $p$ from $H$. At this point $p$ is an active
point for time more than $\tau$. We insert $p$ in $\mathcal{D}^{\textsf{dyn}}$
as follows. We find the smallest $i$ such that $G_{i}=\emptyset$. We move all
points $A=\bigcup_{j<i}G_{j}$ into $G_{i}$ and construct $\mathcal{D}^{i}$
over $A\cup\\{p\\}$. At this point, we also need run a query to find all
$\tau$-durable triangles that contain $p$ (having $I_{p}^{-}$ as the largest
left endpoint). We run the offline query
$\mathsf{durableBallQ}^{i}(p,\tau,\varepsilon/2)$ in each $\mathcal{D}^{i}$
with $G_{i}\neq\emptyset$. As we had in the offline case, for each $i$ we get
a set of $O(\varepsilon^{-\rho})$ canonical nodes of the cover tree. Each
canonical node corresponds a ball of radius at most $\varepsilon/4$. In the
dynamic case there are in total $O(\varepsilon^{-\rho}\log n)$ canonical
nodes, since there are $O(\log n)$ groups. In order to find the durable
triangles, we run Algorithm 1 from the offline case considering
$O(\varepsilon^{-\rho}\log n)$ canonical nodes instead of
$O(\varepsilon^{-\rho})$. Hence, the running time is
$O(\varepsilon^{-\rho}\log^{3}n+\textsf{OUT}_{p})$, where $\textsf{OUT}_{p}$
is the number of $\tau$-durable triangles anchored by $p$ (with $I_{p}^{-}$
being the largest left endpoint) along with a number of additional
$\tau$-durable $\varepsilon$-triangles anchored by $p$. Equivalently, we can
argue that $\textsf{OUT}_{p}$ is the $\tau$-durable triangles that $p$
participates in at the moment $I_{p}^{-}+\tau$ along with some additional
$\tau$-durable $\varepsilon$-triangles that $p$ participates in. Finally, we
re-construct $\mathcal{D}^{\textsf{dyn}}$ from scratch after $n/2$ updates.

Following the analysis in [42, 22, 43] and observing that each point can
change at most $O(\log n)$ groups and the construction time of the offline
$\mathcal{D}$ is $O(n\log^{2}n)$, we have that the insertion of a point takes
$O(\log^{3}n)$ amortized time. The deletion takes $O(\log^{2}n)$ time.

###### Theorem C.1.

Given $(P,\phi,I)$, $\tau>0$, and $\varepsilon>0$, $\varepsilon$-approximate
DynamicOffDurable can be solved using a data structure of $O(n\log n)$ space,
$O(\log^{3}n)$ amortized update time, and
$O(\varepsilon^{O(-\rho)}\log^{3}n+\textsf{OUT}_{p})$ time to report all new
$\tau$-durable triangles (along with some $\varepsilon$-triangles) anchored by
$p$, where $\textsf{OUT}_{p}$ is the output size after inserting point $p$,
where $n=|P|$, and $\rho$ is the doubling dimension of $P$.

##  Appendix D Extensions

We show how we can extend our results in any $\ell_{\alpha}$ norm and we
describe how to report other patterns (except of triangles) of constant size.
Furthermore, we show how to report all durable star patterns. While we only
describe the results in the offline setting, all of them can be extended to
the online setting using the approach as shown in Section 4.

###  D.1. $\ell_{\alpha}$ metric

In order to find all $\tau$-durable triangles in any $\ell_{\alpha}$ metric we
use a quadtree $\mathcal{T}$ instead of a cover tree over the input points
$P$. Each node $u$ of the cover tree is associated with a square
$\square_{u}$. Let $P_{u}-P\cap\square_{u}$. Given a point $p\in P$ we find a
set of $O(\log n+\varepsilon^{-d})$ canonical nodes $C$ in $\mathcal{T}$ such
that for every $u\in C$, the diameter of $\square_{u}$ is at most
$\varepsilon/2$ and $||p-\square_{u}||_{\alpha}\leq 1+\varepsilon/4$. Using
the same procedure we followed for constant doubling dimensions over the
canonical subsets $\mathcal{C}_{p}$, we get the following result.

###### Theorem D.1.

Given $(P,\phi,I)$, $\varepsilon>0$, and $\tau>0$, where $P$ is a set of $n$
points in $\mathbb{R}^{d}$ and $\phi$ is any $\ell_{\alpha}$ norm, the
$\varepsilon$-approximate DurableTriangle can be solved in
$O\left(n(\varepsilon^{-d}\log n+\varepsilon^{-2\cdot
d}+\log^{2}n)+\textsf{OUT}\right)$ time, where OUT is the number of triangles
reported, satisfying $|T_{\tau}|\leq\textsf{OUT}\leq|T^{\varepsilon}_{\tau}|$.

###  D.2. Other patterns

In this subsection we show how we can extend the offline algorithm to report
i) durable cliques of constant size, ii) durable paths of constant size, and
iii) durable $k$-star patters. The algorithms can also be extended to handle
incremental queries, similarly to $tau$-durable triangles.

Cliques. Let $S\subseteq P$ be a subset of points. $S$ is a $\tau$-durable
$m$-clique if i) $|S|=m$, ii) for every pair $p,q\in S\times S$,
$\phi(p,q)\leq 1$, and iii) $|\cap_{p\in S}I_{p}|\geq\tau$. Similarly, $S$ is
called a $\tau$-durable $\varepsilon$-$m$-clique if i, iii remain the same and
for every pair $p,q\in S\times S$, $\phi(p,q)\leq 1+\varepsilon$.

We consider that $m=O(1)$. The algorithm to report all $\tau$-durable
$m$-cliques is similar to Algorithm 1. The only difference is that instead of
considering all pairs $\mathcal{C}_{p,i}$, $\mathcal{C}_{p,j}$ of the nodes in
the cover tree, we consider all possible subsets of size $m$. Let
$\mathcal{C}_{p,j_{1}},\ldots,\mathcal{C}_{p,j_{m}}$ be the family of $m$
subsets. If all pairwise distances among the representative points are at most
$1+\varepsilon/2$ then we report all $m$-cliques
$\mathcal{C}_{p,j_{1}}\times\ldots\times\mathcal{C}_{p,j_{m}}$. The
correctness follows straightforwardly from Section 3. In particular we report
all $\tau$-durable $m$-cliques and we might also report a few $\tau$-durable
$\varepsilon$-$m$-cliques. The running time is also asymptotically the same
with Algorithm 1.

Paths. Let $S\subseteq P$ be a subset of points. $S$ is a $\tau$-durable
$m$-path if i) $|S|=m$, ii) there is an ordering of the points such that the
distance of two consecutive points is at most $1$, and iii) $|\cap_{p\in
S}I_{p}|\geq\tau$. Similarly, $S$ is called a $\tau$-durable
$\varepsilon$-$m$-path if i), iii) remain the same, and the distance between
consecutive points is at most $1+\varepsilon$.

We consider that $m=O(1)$. The algorithm to report all $\tau$-durable
$m$-cliques is similar to Algorithm 1. The only difference is that instead of
considering all pairs $\mathcal{C}_{p,i}$, $\mathcal{C}_{p,j}$ of the nodes in
the cover tree, we consider all possible subsets of size $m$. Let
$\mathcal{C}_{p,j_{1}},\ldots,\mathcal{C}_{p,j_{m}}$ be the family of $m$
subsets. We try all possible $O(m!)=O(1)$ orderings and we check if we find an
ordering $\mathcal{C}_{p,j_{1}},\ldots,\mathcal{C}_{p,j_{m}}$ such that
$\phi(\textsf{Rep}_{j_{1}},\textsf{Rep}_{j_{2}})\leq 1+\varepsilon/2$,
$\phi(\textsf{Rep}_{j_{2}},\textsf{Rep}_{j_{3}})\leq 1+\varepsilon/2$,
…$\phi(\textsf{Rep}_{j_{m-1}},\textsf{Rep}_{j_{m}})\leq 1+\varepsilon/2$. If
this is true then we report all $m$-paths
$\mathcal{C}_{p,j_{1}}\times\ldots\times\mathcal{C}_{p,j_{m}}$. The
correctness follows straightforwardly from Section 3. In particular we report
all $\tau$-durable $m$-paths and we might also report a few $\tau$-durable
$\varepsilon$-$m$-paths. The running time is also asymptotically the same with
Algorithm 1.

$k$-star patterns. Let $S\subseteq P$ be a subset of points. $S$ is a
$\tau$-durable $m$-star if i) $|S|=m$, ii) there is a central point $p\in S$
such that $\phi(p,q)\leq 1$ for every other $q\in S$, and iii) $|\cap_{p\in
S}I_{p}|\geq\tau$. Similarly, $S$ is called a $\tau$-durable
$\varepsilon$-$m$-star if i), iii) remain the same, and the distance between
$p$ and any other point in $S$ is at most $1+\varepsilon$.

We consider that $m=O(1)$. The algorithm to report all $\tau$-durable
$m$-cliques is similar to Algorithm 1. For each point $p\in P$, we run a query
$\mathsf{durableBallQ}(p,\tau,\varepsilon/2)$, but instead of querying points
within distance $1$ from $p$, i.e., points in ball $\mathcal{B}(p,1)$, we
query pints within distance $2$ from $p$, i.e., points in ball
$\mathcal{B}(p,2)$. We need that change because $p$ might belong to an
$m$-star pattern $S$ having the largest left endpoint $I_{p}^{-}\geq\max_{q\in
S}I_{q}^{-}$, while not being the central point. In this case, it is always
true that $S\subseteq P\cap\mathcal{B}(p,2)$. Hence, we get
$\mathcal{C}_{p}=\\{\mathcal{C}_{p,1},\ldots,\mathcal{C}_{p,k}\\}$, for
$k=O(\varepsilon^{-O(\rho)})$ canonical nodes of the cover tree that
approximately cover $\mathcal{B}(p,2)$. Then we visit each node
$\mathcal{C}_{p,j}$. We initialize a counter $c=0$. For every other node
$\mathcal{C}_{p,h}\in\mathcal{C}_{p}$ we check whether
$\phi(\textsf{Rep}_{j},\textsf{Rep}_{h})\leq 1+\varepsilon/2$. If yes then we
update $c=c+|\mathcal{C}_{p,h}|$. In the end, if $c>m$ there exist
$|\mathcal{C}_{p,j}|$, $m$-star patterns to report. Hence, for each point
$q\in\mathcal{C}_{p,j}$ we report $q$ as the central point and then we visit
all nodes $\mathcal{C}_{p,h}$ with
$\phi(\textsf{Rep}_{j},\textsf{Rep}_{h})\leq 1+\varepsilon/2$ to report all