Efficient pebbling for list traversal synopses

Details Efficient pebbling for list traversal synopses Efficient pebbling for list traversal synopses

2003-06-16

arxiv.org/abs/cs/0306104v1

Computer Science

Data Structures and Algorithms

27 pages

Scientific paper

We show how to support efficient back traversal in a unidirectional list, using small memory and with essentially no slowdown in forward steps. Using $O(\log n)$ memory for a list of size $n$, the $i$'th back-step from the farthest point reached so far takes $O(\log i)$ time in the worst case, while the overhead per forward step is at most $\epsilon$ for arbitrary small constant $\epsilon>0$. An arbitrary sequence of forward and back steps is allowed. A full trade-off between memory usage and time per back-step is presented: $k$ vs. $kn^{1/k}$ and vice versa. Our algorithms are based on a novel pebbling technique which moves pebbles on a virtual binary, or $t$-ary, tree that can only be traversed in a pre-order fashion. The compact data structures used by the pebbling algorithms, called list traversal synopses, extend to general directed graphs, and have other interesting applications, including memory efficient hash-chain implementation. Perhaps the most surprising application is in showing that for any program, arbitrary rollback steps can be efficiently supported with small overhead in memory, and marginal overhead in its ordinary execution. More concretely: Let $P$ be a program that runs for at most $T$ steps, using memory of size $M$. Then, at the cost of recording the input used by the program, and increasing the memory by a factor of $O(\log T)$ to $O(M \log T)$, the program $P$ can be extended to support an arbitrary sequence of forward execution and rollback steps: the $i$'th rollback step takes $O(\log i)$ time in the worst case, while forward steps take O(1) time in the worst case, and $1+\epsilon$ amortized time per step.

Affiliated with

Also associated with

No associations

Rating

Efficient pebbling for list traversal synopses does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Efficient pebbling for list traversal synopses, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient pebbling for list traversal synopses will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-265250