A parallel algorithm is presented for the problem of range searches on a single-instruction multiple-data (SIMD) computing system with p processing elements. The linearized multiple attribute tree is used as the underlying data structure. The algorithm has complexity of O(kN/p), p less than equivalent to N, where k is the dimensionality and N is the number of points of the data space.
