Fast Nearest Neighbor Search in Medical Image Databases

Открыть
Дата
1996Автор
Korn, Flip
Sidiropoulos, N.
Faloutsos, Christos
Metadata
Показать полную информациюАннотации
We examine the problem of finding similar tumor shapes. Starting from a natural similarity function (the so-called ax morphological distance'), we showed how to lower-bound it and how to search for nearest neighbors in large collections of tumor- like shapes.<P>Specifically, we used state-of-the-art concepts from morphology, namely the attern spectrum' of a shape, to map each shape to a point in n-dimensional space. Following [19, 36], we organized the n-d points in an R-tree. We showed that the L (= 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.<P>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 [15]. The experiments showed that our method is up to 27 times faster than straightforward sequential scanning.<P>