Fast and effective retrieval of medical tumor shapes

Philip Korn, Nicholas Sidiropoulos, Christos Faloutsos, Eliot Siegel, Zenon Protopapas

Research output: Contribution to journalArticlepeer-review

140 Scopus citations


We investigate the problem of retrieving similar shapes from a large database; in particular, we focus on medical tumor shapes ("Find tumors that are similar to a given pattern."). We use a natural similarity function for shape-matching, based on concepts from mathematical morphology, and we show how it can be lower-bounded by a set of shape features for safely pruning candidates, thus giving fast and correct output. These features can be organized in a spatial access method, leading to fast indexing for range queries and nearest-neighbor queries. In addition to the lower-bounding, our second contribution is the design of a fast algorithm for nearest-neighbor search, achieving significant speedup while provably guaranteeing correctness. Our experiments demonstrate that roughly 90 percent of the candidates can be pruned using these techniques, resulting in up to 27 times better performance compared to sequential scan.

Original languageEnglish (US)
Pages (from-to)889-904
Number of pages16
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number6
StatePublished - 1998
Externally publishedYes


  • Content-based retrieval
  • Mathematical morphology
  • Multimedia indexing
  • Pattern spectrum


Dive into the research topics of 'Fast and effective retrieval of medical tumor shapes'. Together they form a unique fingerprint.

Cite this