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 Nature, 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: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
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 Nature
T2 - 12th International Computer Science Symposium in Russia, CSR 2017
Y2 - 8 June 2017 through 12 June 2017
ER -
ID: 38614417