Can I read A Lower Bound for Dynamic Fractional Cascading on EtoBox?

A Lower Bound for Dynamic Fractional Cascading by Afshani, Peyman is a scholarly article available to read on EtoBox.

What is A Lower Bound for Dynamic Fractional Cascading about?

We investigate the limits of one of the fundamental ideas in data structures: fractional cascading. This is an important data structure technique to speed up repeated searches for the same key in multiple lists and it has numerous applications. Specifically, the input is a "catalog" graph, $G$, of constant degree together with a list of values assigned to every vertex of $G$. The goal is to preprocess the input such that given a connected subgraph $H$ of $G$ and a single query value $q$, one can find the predecessor of $q$ in every list that belongs to $\scat$. The classical result by Chazelle and Guibas shows that in a pointer machine, this can be done in the optimal time of $\O(\log n + |\scat|)$ where $n$ is the total number of values. However, if insertion and deletion of values are allowed, then the query time slows down to $\O(\log n + |\scat| \log\log n)$. If only insertions (or deletions) are allowed, then once again, an optimal query time can be obtained but by using amortization at update time. We prove a lower bound of $\Omega( \log n \sqrt{\log\log n})$ on the worst-case query time of dynamic fractional cascading, when queries are paths of length $O(\log n)$. The lower

Author

Afshani, Peyman

Published

2020

Language

EN