Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Range Queries over Untangled Chains
verfasst von : Francisco Claude, J. Ian Munro, Patrick K. Nicholson
Erschienen in: String Processing and Information Retrieval
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We present a practical implementation of the first adaptive data structure for orthogonal range queries in 2D [Arroyuelo et al., ISAAC 2009]. The structure is static, requires only linear space for its representation, and can even be made implicit. The running time for a query is
$O(\lg k\lg n + \min(k,m)\lg n + m)$
, where
k
is the number of non-crossing monotonic chains in which we can partition the set of points, and
m
is the size of the output. The space consumption of our implementation is 2
n
+
o
(
n
) words. The experimental results show that this structure is competitive with the state of the art. We also present an alternative construction algorithm for our structure, which in practice outperforms the original proposal by orders of magnitude.