Fast Nearest Neighbor Search in Medical Image Databases
| dc.contributor.author | Korn, Flip | en_US |
| dc.contributor.author | Sidiropoulos, Nikolaos | en_US |
| dc.contributor.author | Faloutsos, Christos | en_US |
| dc.contributor.author | Siegel, Eliot | en_US |
| dc.contributor.author | Protopapas, Zenon | en_US |
| dc.date.accessioned | 2004-05-31T22:38:15Z | |
| dc.date.available | 2004-05-31T22:38:15Z | |
| dc.date.created | 1996-03 | en_US |
| dc.date.issued | 1998-10-15 | en_US |
| dc.description.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) | en_US |
| dc.format.extent | 1760599 bytes | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.uri | http://hdl.handle.net/1903/805 | |
| dc.language.iso | en_US | |
| dc.relation.isAvailableAt | Digital Repository at the University of Maryland | en_US |
| dc.relation.isAvailableAt | University of Maryland (College Park, Md.) | en_US |
| dc.relation.isAvailableAt | Tech Reports in Computer Science and Engineering | en_US |
| dc.relation.isAvailableAt | UMIACS Technical Reports | en_US |
| dc.relation.ispartofseries | UM Computer Science Department; CS-TR-3613 | en_US |
| dc.relation.ispartofseries | UMIACS; UMIACS-TR-96-17 | en_US |
| dc.title | Fast Nearest Neighbor Search in Medical Image Databases | en_US |
| dc.type | Technical Report | en_US |