Experiments on Range Searching over Untangled Monotonic Chains

by Patrick Nicholson

Motivated by applications in oceanographic information systems, we study
the problem of searching through large two-dimensional datasets. In
particular, we study the problem of orthogonal range search: given a
rectangle as a query, identify all of the points located inside. We
present experimental results for the first adaptive data structure for
orthogonal range search in two-dimensions [Arroyuelo et al.,ISAAC 2009].
The structure is static, requires only linear space for its
representation, and can even be made implicit. Roughly, it works by
preprocessing the dataset by partitioning the points into as few
monotonic chains as possible, which can then be searched individually.
The running time for answering a query is O(lg k lg n + min(k,m) lg n +
m), where n is the number of points, k is the number of non-crossing
monotonic chains into which we can partition the set of points, and m is
the size of the output. Our experimental results show that this structure
is competitive with the state of the art for real datasets, using a
variety of generated query types.

Joint work with Diego Arroyuelo, Francisco Claude, Reza Dorrigiv, Stephane Durocher, 
Meng He, Alejandro López-Ortiz, Ian Munro, Alejandro Salinger, and Matthew Skala.