## Abstract

Let a_{1}, a_{2},..., a_{m} be a sequence over [n] = {1,... n}. We say that a sequence a_{1}, a_{2},... a _{m} has the k-radius property if every pair of different elements in [n] occurs at least once within distance at most k; the distance d(a _{i}, a_{j}) = |i-j|. We demonstrate lower and (asymptotically) matching upper bounds for sequences with the k-radius property. Such sequences are applicable, for example, in computations of two-argument functions for all (_{2}^{n}) pairs of large objects such as medical images, bitmaps or matrices, when processing occurs in a memory of size capable of storing k + 1 objects, k < n. We focus on the model when elements are read into the memory in a FIFO fashion that correspond to streaming the data or a special type of caching. We present asymptotically optimal constructions; they are based on the Euler totient theorem and recursion.

Original language | English |
---|---|

Pages (from-to) | 594-605 |

Number of pages | 12 |

Journal | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |

Volume | 3341 |

DOIs | |

State | Published - 2004 |

### Bibliographical note

Funding Information:★★This work was supported in part by the University of Kentucky subcontract of grants 5P20RR016481-03 and 2P20RR016481-04 from NCRR-NIH, and by KY NSF EPSCOR grant EPS-0132295.

## ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science (all)