Dynamic stabbing queries with sub-logarithmic local updates for overlapping intervals

Elena Khramtcova, Maarten Löffler

Research output

1 Citation (Scopus)

Abstract

We present a data structure to maintain a set of intervals on the real line subject to fast insertions and deletions of the intervals, stabbing queries, and local updates. Intuitively, a local update replaces an interval by another one of roughly the same size and location. We inves-tigate whether local updates can be implemented faster than a deletion followed by an insertion. We present the first results for this problem for sets of possibly over-lapping intervals. If the maximum depth of the overlap (a.k.a. ply) is bounded by a constant, our data structure performs insertions, dele-tions and stabbing queries in time O(log n), and local updates in time O(log n/ log log n), where n is the number of intervals. We also analyze the dependence on the ply when it is not constant. Our results are adap-tive: the times depend on the current ply at the time of each operation.

Original languageEnglish
Title of host publicationComputer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Proceedings
EditorsPascal Weil
PublisherSpringer
Pages176-190
Number of pages15
ISBN (Print)9783319587462
DOIs
Publication statusPublished - 1 Jan 2017
Externally publishedYes
Event12th International Computer Science Symposium in Russia, CSR 2017 - Kazan
Duration: 8 Jun 201712 Jun 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10304 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference12th International Computer Science Symposium in Russia, CSR 2017
CountryRussian Federation
CityKazan
Period8/06/1712/06/17

Fingerprint

Overlapping
Data structures
Logarithmic
Update
Query
Lapping
Interval
Insertion
Deletion
Data Structures
Real Line
Overlap

Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Khramtcova, E., & Löffler, M. (2017). Dynamic stabbing queries with sub-logarithmic local updates for overlapping intervals. In P. Weil (Ed.), Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Proceedings (pp. 176-190). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10304 LNCS). Springer. https://doi.org/10.1007/978-3-319-58747-9_17
Khramtcova, Elena ; Löffler, Maarten. / Dynamic stabbing queries with sub-logarithmic local updates for overlapping intervals. Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Proceedings. editor / Pascal Weil. Springer, 2017. pp. 176-190 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{6c8f4d0527a74b2093d3a74245ba4519,
title = "Dynamic stabbing queries with sub-logarithmic local updates for overlapping intervals",
abstract = "We present a data structure to maintain a set of intervals on the real line subject to fast insertions and deletions of the intervals, stabbing queries, and local updates. Intuitively, a local update replaces an interval by another one of roughly the same size and location. We inves-tigate whether local updates can be implemented faster than a deletion followed by an insertion. We present the first results for this problem for sets of possibly over-lapping intervals. If the maximum depth of the overlap (a.k.a. ply) is bounded by a constant, our data structure performs insertions, dele-tions and stabbing queries in time O(log n), and local updates in time O(log n/ log log n), where n is the number of intervals. We also analyze the dependence on the ply when it is not constant. Our results are adap-tive: the times depend on the current ply at the time of each operation.",
author = "Elena Khramtcova and Maarten L{\"o}ffler",
year = "2017",
month = "1",
day = "1",
doi = "10.1007/978-3-319-58747-9_17",
language = "English",
isbn = "9783319587462",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "176--190",
editor = "Pascal Weil",
booktitle = "Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Proceedings",
address = "Germany",

}

Khramtcova, E & Löffler, M 2017, Dynamic stabbing queries with sub-logarithmic local updates for overlapping intervals. in P Weil (ed.), Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10304 LNCS, Springer, pp. 176-190, Kazan, 8/06/17. https://doi.org/10.1007/978-3-319-58747-9_17

Dynamic stabbing queries with sub-logarithmic local updates for overlapping intervals. / Khramtcova, Elena; Löffler, Maarten.

Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Proceedings. ed. / Pascal Weil. Springer, 2017. p. 176-190 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10304 LNCS).

Research output

TY - GEN

T1 - Dynamic stabbing queries with sub-logarithmic local updates for overlapping intervals

AU - Khramtcova, Elena

AU - Löffler, Maarten

PY - 2017/1/1

Y1 - 2017/1/1

N2 - We present a data structure to maintain a set of intervals on the real line subject to fast insertions and deletions of the intervals, stabbing queries, and local updates. Intuitively, a local update replaces an interval by another one of roughly the same size and location. We inves-tigate whether local updates can be implemented faster than a deletion followed by an insertion. We present the first results for this problem for sets of possibly over-lapping intervals. If the maximum depth of the overlap (a.k.a. ply) is bounded by a constant, our data structure performs insertions, dele-tions and stabbing queries in time O(log n), and local updates in time O(log n/ log log n), where n is the number of intervals. We also analyze the dependence on the ply when it is not constant. Our results are adap-tive: the times depend on the current ply at the time of each operation.

AB - We present a data structure to maintain a set of intervals on the real line subject to fast insertions and deletions of the intervals, stabbing queries, and local updates. Intuitively, a local update replaces an interval by another one of roughly the same size and location. We inves-tigate whether local updates can be implemented faster than a deletion followed by an insertion. We present the first results for this problem for sets of possibly over-lapping intervals. If the maximum depth of the overlap (a.k.a. ply) is bounded by a constant, our data structure performs insertions, dele-tions and stabbing queries in time O(log n), and local updates in time O(log n/ log log n), where n is the number of intervals. We also analyze the dependence on the ply when it is not constant. Our results are adap-tive: the times depend on the current ply at the time of each operation.

UR - http://www.scopus.com/inward/record.url?scp=85019205428&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-58747-9_17

DO - 10.1007/978-3-319-58747-9_17

M3 - Conference contribution

AN - SCOPUS:85019205428

SN - 9783319587462

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 176

EP - 190

BT - Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Proceedings

A2 - Weil, Pascal

PB - Springer

ER -

Khramtcova E, Löffler M. Dynamic stabbing queries with sub-logarithmic local updates for overlapping intervals. In Weil P, editor, Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Proceedings. Springer. 2017. p. 176-190. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-58747-9_17