Pattern sorting: a computer-controlled multidimensional sorting method using k-d trees.

Abstract

Multidimensional binary trees provide a memory efficient and general method for computing sorting decisions in real time for a flow cytometer. Their fundamental advantage over conventional lookup table sorting techniques is that sort criteria in the full N-dimensional data space which cannot be described by projections onto two-dimensional parameter planes can be effectively implemented. This becomes particularly relevant when multidimensional analysis methods such as principal components or clustering are employed. We describe a prototype implementation of this method and point out other possible implementations.