An apparatus and method for performing similarity searches using hyper-rectangle based multidimensional data segmentation partitions a data set representable by a multidimensional data sequence, such as a video stream, into segments in consideration of the temporal relationship between points, and groups similar segments in one sequence into the same cluster so as to efficiently search a database for a multidimensional data sequence similar to a given query sequence.