Skyline Computation for Low-Latency Image-Activated Cell Identification

Kenichi Koizumi, Kei Hiraki, Mary InabaAAAI 2018 · DOI

Introduction

In biological research and medical diagnostics, identifying extremely rare cells—sometimes one in a trillion—is a critical challenge. Systems like Serendipiter are designed for high-throughput applications such as biofuel production or high-precision blood testing. These systems must analyze high-dimensional data from optical imaging and make sorting decisions in less than 10 milliseconds.

The Serendipiter system workflow, highlighting the role of skyline computation in cell identification.

The authors frame this identification task as a skyline computation problem: finding points that are not "dominated" by any others (i.e., they are the best in at least one category). In a streaming environment where cells are constantly measured and discarded, maintaining this "continuous skyline" is computationally taxing for standard CPUs.

Methods: FPGA-Accelerated JR-tree

To meet the sub-10ms latency requirement, the researchers utilized the JR-tree, a dimension-independent algorithm for continuous skyline computation. Their core innovation involves moving this logic onto a Field-Programmable Gate Array (FPGA) and implementing a "lazy injection" strategy.

Hardware acceleration allows for massive parallelism in comparing data points. The lazy injection optimization recognizes that to output the current skyline, only the immediate "children" of the origin in the tree are needed. Updating deeper, more complex parts of the tree can be delayed, significantly reducing per-cell processing latency. The hardware architecture consists of three main components: a Query Dispatcher, a Skyline Comparator, and a Skyline Enumerator.

Experimental Evaluation

The system was evaluated using both synthetic and real-world datasets:

  • Synthetic Datasets: CORRelated, INDEpendent, and ANTI-correlated distributions were used to test how different spatial arrangements affect performance.
  • Real-World Cell Data: Features were extracted from fluorescence microscope images from the CYTO 2017 Image Analysis Challenge, including structures like Mitochondria, Cytosol, and Focal Adhesion Sites (FAS).

Key Results

The FPGA-based JR-tree significantly outperformed software implementations across all tested scenarios.

Normalized execution time comparison between LookOut, software JR-tree, and the proposed FPGA-based JR-tree across various datasets.

As shown in the results, the hardware implementation achieved a 3.7x speedup for 5D correlated datasets and a 1.7x speedup on the real-world CYTOSOL dataset compared to the software JR-tree. Crucially, the system successfully maintained the sub-10ms latency required to process 10,000 cells per second, meeting the operational goals for high-speed cell sorting.

Conclusion and Future Work

By treating rare cells as geometric boundary points and accelerating skyline computation via FPGA, this research enables real-time identification in high-throughput biological screening. While the system meets current latency goals, future work may address the scalability of hardware resources for even higher dimensions and the physical integration of the FPGA into optical sorting hardware.

Summary updated

BibTeX
@inproceedings{koizumi2018skyline,
  author = {Kenichi Koizumi and Kei Hiraki and Mary Inaba},
  title = {{Skyline Computation for Low-Latency Image-Activated Cell Identification}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.12134},
}

Loading related content...

Figure