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

Elena Khramtcova, Maarten Löffler

Результат исследований: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференции

1 цитирование (Scopus)

Выдержка

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.

Язык оригиналаанглийский
Название основной публикацииComputer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Proceedings
РедакторыPascal Weil
ИздательSpringer
Страницы176-190
Число страниц15
ISBN (печатное издание)9783319587462
DOI
СостояниеОпубликовано - 1 янв 2017
Опубликовано для внешнего пользованияДа
Событие12th International Computer Science Symposium in Russia, CSR 2017 - Kazan, Российская Федерация
Продолжительность: 8 июн 201712 июн 2017

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том10304 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция12th International Computer Science Symposium in Russia, CSR 2017
СтранаРоссийская Федерация
ГородKazan
Период8/06/1712/06/17

Отпечаток

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

Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

Цитировать

Khramtcova, E., & Löffler, M. (2017). Dynamic stabbing queries with sub-logarithmic local updates for overlapping intervals. В P. Weil (Ред.), Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Proceedings (стр. 176-190). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 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. редактор / Pascal Weil. Springer, 2017. стр. 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. в P Weil (ред.), 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), том. 10304 LNCS, Springer, стр. 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. ред. / Pascal Weil. Springer, 2017. стр. 176-190 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 10304 LNCS).

Результат исследований: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференции

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. В Weil P, редактор, Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Proceedings. Springer. 2017. стр. 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