Fast and effective retrieval of medical tumor shapes

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

Research output: Contribution to journalArticlepeer-review

138 Scopus citations

Abstract

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
Volume10
Issue number6
DOIs
StatePublished - 1998

Keywords

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

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

Cite this