Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Ring-shaped hotspot detection
Eftelioglu E., Shekhar S., Kang J., Farah C. IEEE Transactions on Knowledge and Data Engineering28 (12):3367-3381,2016.Type:Article
Date Reviewed: May 12 2017

What is the best way to search for an annular object? Such problems arise in situations as diverse as meteorite craters and the spread of infections. Previous methods of spatial searching have normally looked for rectangles or ellipses and do not find objects with holes. The sequence of algorithms needed for finding rings, as presented in this paper, are:

(1) How to efficiently locate both the center and radii of the desired circles when the information is presented on a rectangular grid;

(2) How to use different search pruning methods for the search for the center of a ring and the search for the edges of that ring; and

(3) How to verify that a proposed ring has a desired level of statistical significance, by comparing with Monte Carlo random data.

The paper concentrates on efficiency as well as accuracy, by using pruning methods to find answers quickly and adapting search precision to avoid either missing rings or using too much computation. Their acronym DGPLMR includes the concept of dual grid (for center and radii), pruning (in the search), local maxima elimination (find the best ring in each area), multi cell size for searching the ring width, and refine (a final process to choose the ring coordinates accurately).

The method was evaluated on both randomly generated sample data and on a real set of data from an outbreak of Legionnaires’ disease in New York City. They compared it with previous algorithms such as SaTScan (in wide use but not tailored to rings) and also with simpler versions of their approach. Their final algorithm both finds more target rings and runs faster. The paper is mathematical though quite clear, and contains useful code sections as well as theoretical complexity bounds. It is recommended to experts in searching for shapes in image data.

Reviewer:  Michael Lesk Review #: CR145281 (1707-0476)
Bookmark and Share
 
Algorithm Design And Analysis (G.4 ... )
 
 
Statistical (I.5.1 ... )
 
 
Computational Geometry And Object Modeling (I.3.5 )
 
 
Pattern Recognition (I.5 )
 
Would you recommend this review?
yes
no
Other reviews under "Algorithm Design And Analysis": Date
Numerical recipes
Sprott J., Cambridge University Press, New York, NY, 1991. Type: Book (9780521406895)
Dec 1 1992
An interactive calculus theorem-prover for continuity properties
Suppes P., Takahashi S. Journal of Symbolic Computation 7(6): 573-590, 1989. Type: Article
Aug 1 1990
The numerical methods programming projects book
Grandine T., Oxford University Press, Inc., New York, NY, 1990. Type: Book (9789780198533870)
Mar 1 1991
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy