Fast Nearest Neighbor Search in Medical Image Databases
Fast Nearest Neighbor Search in Medical Image Databases
Loading...
Files
Publication or External Link
Date
1998-10-15
Authors
Korn, Flip
Sidiropoulos, Nikolaos
Faloutsos, Christos
Siegel, Eliot
Protopapas, Zenon
Advisor
Citation
DRUM DOI
Abstract
We examine the problem of finding similar tumor shapes. Starting
from a natural similarity function (the so-called `max morpholog-
ical distance'), we showed how to lower-bound it and how to
search for nearest neighbors in large collections of tumor-like
shapes.
Specifically, we used state-of-the-art concepts from morphology,
namely the `pattern spectrum' of a shape, to map each shape to a
point in $n$-dimensional space. Following
\cite{Faloutsos94Fast,Jagadish91Retrieval}, we organized the
$n$-d points in an R-tree. We showed that the $L_infty$ (= max)
norm in the $n$-d space lower-bounds the actual distance. This
guarantees no false dismissals for range queries. In addition,
we developed a nearest-neighbor algorithm that also guarantees no
false dismissals.
Finally, we implemented the method, and we tested it against a
testbed of realistic tumor shapes, using an established tumor-
growth model of Murray Eden \cite{Eden:61}. The experiments
showed that our method is up to 27 times faster than straightfor-
ward sequential scanning.
(Also cross-referenced as UMIACS-TR-96-17)