Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Sequences of Radius k: How to Fetch Many Huge Objects into Small Memory for Pairwise Computations
verfasst von : Jerzy W. Jaromczyk, Zbigniew Lonc
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
$\binom{n}{2}$
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.