NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Collections About News Help Login
Back to Results
Implementing Connected Component Labeling as a User Defined Operator for SciDBWe have implemented a flexible User Defined Operator (UDO) for labeling connected components of a binary mask expressed as an array in SciDB, a parallel distributed database management system based on the array data model. This UDO is able to process very large multidimensional arrays by exploiting SciDB's memory management mechanism that efficiently manipulates arrays whose memory requirements far exceed available physical memory. The UDO takes as primary inputs a binary mask array and a binary stencil array that specifies the connectivity of a given cell to its neighbors. The UDO returns an array of the same shape as the input mask array with each foreground cell containing the label of the component it belongs to. By default, dimensions are treated as non-periodic, but the UDO also accepts optional input parameters to specify periodicity in any of the array dimensions. The UDO requires four stages to completely label connected components. In the first stage, labels are computed for each subarray or chunk of the mask array in parallel across SciDB instances using the weighted quick union (WQU) with half-path compression algorithm. In the second stage, labels around chunk boundaries from the first stage are stored in a temporary SciDB array that is then replicated across all SciDB instances. Equivalences are resolved by again applying the WQU algorithm to these boundary labels. In the third stage, relabeling is done for each chunk using the resolved equivalences. In the fourth stage, the resolved labels, which so far are "flattened" coordinates of the original binary mask array, are renamed with sequential integers for legibility. The UDO is demonstrated on a 3-D mask of O(1011) elements, with O(108) foreground cells and O(106) connected components. The operator completes in 19 minutes using 84 SciDB instances.
Document ID
20160014542
Acquisition Source
Goddard Space Flight Center
Document Type
Conference Paper
Authors
Oloso, Amidu (Science Systems and Applications, Inc. Greenbelt, MD, United States)
Kuo, Kwo-Sen (Maryland Univ. Greenbelt, MD, United States)
Clune, Thomas (NASA Goddard Space Flight Center Greenbelt, MD, United States)
Brown, Paul (Paradigm4, Inc. Waltham, MA, United States)
Poliakov, Alex (Paradigm4, Inc. Waltham, MA, United States)
Yu, Hongfeng (Nebraska Univ. Lincoln, NE, United States)
Date Acquired
December 7, 2016
Publication Date
December 5, 2016
Subject Category
Meteorology And Climatology
Computer Programming And Software
Report/Patent Number
GSFC-E-DAA-TN34982
Meeting Information
Meeting: 2016 IEEE International Confernece on Big Data(Big Data 2016)
Location: Washingtong, DC
Country: United States
Start Date: December 5, 2016
End Date: December 8, 2016
Sponsors: Institute of Electrical and Electronics Engineers
Funding Number(s)
CONTRACT_GRANT: NNX12AD03A
CONTRACT_GRANT: NNG12HP06C
Distribution Limits
Public
Copyright
Public Use Permitted.
Keywords
UDO
SciDB
WQU

Related Records

There are no records associated with this record.
No Preview Available