Show simple item record

Fast Nearest Neighbor Search in Medical Image Databases

dc.contributor.authorKorn, Flipen_US
dc.contributor.authorSidiropoulos, Nikolaosen_US
dc.contributor.authorFaloutsos, Christosen_US
dc.contributor.authorSiegel, Elioten_US
dc.contributor.authorProtopapas, Zenonen_US
dc.description.abstractWe 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)en_US
dc.format.extent1760599 bytes
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-3613en_US
dc.relation.ispartofseriesUMIACS; UMIACS-TR-96-17en_US
dc.titleFast Nearest Neighbor Search in Medical Image Databasesen_US
dc.typeTechnical Reporten_US
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_US
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_US
dc.relation.isAvailableAtTech Reports in Computer Science and Engineeringen_US
dc.relation.isAvailableAtUMIACS Technical Reportsen_US

Files in this item


This item appears in the following Collection(s)

Show simple item record