Кинетическая структура данных

Кинетическая структура данных — это структура данных , используемая для отслеживания атрибута геометрической системы, которая непрерывно движется. ^[1]^[2]^[3]^[4]Например, структура данных кинетической выпуклой оболочки поддерживает выпуклую оболочку группы объектов. $n$ движущиеся точки. Разработка кинетических структур данных была мотивирована проблемами вычислительной геометрии , включающими физические объекты в непрерывном движении, такими как обнаружение столкновений или видимости в робототехнике, анимации или компьютерной графике.

Обзор

Кинетические структуры данных используются в системах, где существует набор значений, которые изменяются в зависимости от времени известным образом. Итак, система имеет несколько значений, и для каждого значения $v$ , известно, что $v=f(t)$ .Кинетические структуры данных позволяют выполнять запросы к системе в текущее виртуальное время. $t$ и две дополнительные операции:

${\textrm {advance}}(t)$ : Перемещает систему во времени $t$ .
${\textrm {change}}(v,f(t))$ : Изменяет траекторию стоимости. $v$ к $f(t)$ , по состоянию на настоящее время.

Могут поддерживаться дополнительные операции. Например, часто используются кинетические структуры данных с набором точек. В этом случае структура обычно позволяет вставлять и удалять точки.

Контраст с традиционными структурами данных

Кинетическая структура данных позволяет хранящимся в ней значениям постоянно изменяться со временем. В принципе, это можно аппроксимировать путем выборки положения точек через фиксированные интервалы времени, а также удаления и повторной вставки каждой точки в «статическую» (традиционную) структуру данных. Однако такой подход уязвим для передискретизации или недостаточной выборки, в зависимости от того, какой интервал времени используется, а также может привести к расточительству вычислительных ресурсов.

Сертификаты подход

Для построения кинетических структур данных можно использовать следующий общий подход: ^[5]

Сохранение структуры данных в системе в текущий момент времени $t$ . Эта структура данных позволяет выполнять запросы к системе в текущее виртуальное время.
Дополните структуру данных сертификатами. Сертификаты — это условия, при которых структура данных является точной. Теперь все сертификаты верны, и структура данных перестанет быть точной только тогда, когда один из сертификатов перестанет быть верным.
Вычислите время отказа каждого сертификата, время, когда он перестанет быть правдой.
Храните сертификаты в приоритетной очереди с указанием времени их сбоя.
Чтобы продвинуться во времени $t$ , посмотрите сертификат с наименьшим временем отказа из приоритетной очереди. Если сертификат терпит неудачу раньше времени $t$ , извлеките его из очереди и исправьте структуру данных, чтобы она была точной на момент сбоя, и обновите сертификаты. Повторяйте это до тех пор, пока сертификат с наименьшим временем сбоя в приоритетной очереди не выйдет из строя через некоторое время. $t$ . Если сертификат с наименьшим временем отказа в приоритетной очереди терпит неудачу по истечении времени $t$ , то все сертификаты действительны в данный момент $t$ чтобы структура данных могла правильно отвечать на запросы вовремя $t$ .

Типы событий

Сбои сертификатов называются «событиями». Событие считается внутренним, если свойство, поддерживаемое кинетической структурой данных, не меняется при возникновении события. Событие считается внешним, если свойство, поддерживаемое структурой данных, изменяется при возникновении события.

Производительность

При использовании подхода с использованием сертификатов существует четыре показателя эффективности. Мы говорим, что величина мала, если она является полилогарифмической функцией от $n$ или есть $O(n^{\epsilon })$ для сколь угодно малого $\epsilon$ , где $n$ количество объектов:

Отзывчивость

Время реагирования — это наихудший случай времени, необходимого для исправления структуры данных и расширения сертификатов в случае сбоя сертификата. Кинетическая структура данных реагирует, если в худшем случае время, необходимое для обновления, невелико.

Местность

Максимальное количество сертификатов, в которых участвует какое-либо одно значение. Для структур, включающих движущиеся точки, это максимальное количество сертификатов, в которых участвует любая одна точка. Кинетическая структура данных является локальной, если максимальное количество сертификатов связано с каким-либо одним значением. мал.

Компактность

Максимальное количество сертификатов, используемых для расширения структуры данных в любое время. Кинетическая структура данных является компактной, если количество используемых ею сертификатов не превышает $O(n\operatorname {polylog} n)$ или $O(n^{1+\epsilon })$ для сколь угодно малого $\epsilon$ . (немного больше, чем линейное пространство)

Эффективность

Отношение количества событий в наихудшем случае, которые могут произойти при перемещении структуры $t=\infty$ в худшем случае количество «необходимых изменений» в структуре данных. Определение «необходимых изменений» зависит от проблемы. Например, в случае кинетической структуры данных, поддерживающей кинетическую оболочку набора движущихся точек, количество необходимых изменений будет равно количеству раз, когда кинетическая оболочка изменяется по мере продвижения времени к $t=\infty$ . Кинетическая структура данных считается эффективной, если это соотношение невелико.

Типы траекторий

Характеристики определенной структуры кинетических данных можно анализировать для определенных типов траекторий. Обычно рассматриваются следующие типы траекторий:

Аффинные :(Линейные функции) $f(t)=at+b$
Алгебраика ограниченной степени : (Полиномиальные функции ограниченной степени) $f(t)=\sum _{i=0}^{n}a_{i}t^{i}$ для некоторых фиксированных $n$ .
Псевдоалгебраические : траектории, при которых любой сертификат интереса переключается между истинным и ложным. $O(1)$ раз.

Примеры

Ссылки

^ Баш, Жюльен (1999). Кинетические структуры данных (Диссертация). Стэнфордский университет.
^ Гибас, Леонидас Дж. (2001), «Кинетические структуры данных» (PDF) , в Мехте, Динеш П.; Сахни, Сартадж (ред.), Справочник по структурам данных и приложениям , Чепмен и Холл/CRC, стр. 23-1–23-18, ISBN 978-1-58488-435-4
^ Абам, Мохаммед Али (2007). Новые структуры данных и алгоритмы для мобильных данных (Диссертация). Эйндховенский технологический университет.
^ Рахмати, Захед (2014). Простые и быстрые кинетические структуры данных (Диссертация). Университет Виктории. hdl : 1828/5627 .
^ Гибас, Леонидас Дж. (1998), «Кинетические структуры данных: современный отчет» (PDF) , в Агарвале, Панкадж К.; Кавраки, Лидия Э.; Мейсон, Мэтью Т. (ред.), Робототехника: алгоритмическая перспектива (Материалы 3-го семинара по алгоритмическим основам робототехники) , AK Peters/CRC Press, стр. 191–209, ISBN 978-1-56881-081-2

[JBasch-1] Баш, Жюльен (1999). Кинетические структуры данных (Диссертация). Стэнфордский университет.

[LJGuibas-2] Гибас, Леонидас Дж. (2001), «Кинетические структуры данных» (PDF) , в Мехте, Динеш П.; Сахни, Сартадж (ред.), Справочник по структурам данных и приложениям , Чепмен и Холл/CRC, стр. 23-1–23-18, ISBN 978-1-58488-435-4

[MAAbam-3] Абам, Мохаммед Али (2007). Новые структуры данных и алгоритмы для мобильных данных (Диссертация). Эйндховенский технологический университет.

[ZRahmati-4] Рахмати, Захед (2014). Простые и быстрые кинетические структуры данных (Диссертация). Университет Виктории. hdl : 1828/5627 .

[5] Гибас, Леонидас Дж. (1998), «Кинетические структуры данных: современный отчет» (PDF) , в Агарвале, Панкадж К.; Кавраки, Лидия Э.; Мейсон, Мэтью Т. (ред.), Робототехника: алгоритмическая перспектива (Материалы 3-го семинара по алгоритмическим основам робототехники) , AK Peters/CRC Press, стр. 191–209, ISBN 978-1-56881-081-2

[1]

[2]

[3]

[4]

[5]