  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.
