Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › Рецензирование
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 Nature |
| Страницы | 176-190 |
| Число страниц | 15 |
| ISBN (печатное издание) | 9783319587462 |
| DOI | |
| Состояние | Опубликовано - 1 янв 2017 |
| Опубликовано для внешнего пользования | Да |
| Событие | 12th International Computer Science Symposium in Russia, CSR 2017 - Kazan, Российская Федерация Продолжительность: 8 июн 2017 → 12 июн 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 |
|---|---|
| Страна/Tерритория | Российская Федерация |
| Город | Kazan |
| Период | 8/06/17 → 12/06/17 |
ID: 38614417