I have the following problem with data points as intervals that I want to cluster. So I have my data which are pairs of intervals. I simply want to rule out random outcomes and determine the pairs of intervals that are significant in the data set (e.g., with a simple t-test). However I have got about 1.5-2 million of these intervals. Some of them even only differ by a few values. In the following picture this is illustrated. I have the whole region (1) and different pairs of intervals (2),(3),(4). To further complicate things I also have single intervals (5).
So I need some kind of segmentation to conduct the significance test. Concretely I would just want to count the probability for a specific interval, multiply these to get the pdf and then model each pair of intervals with the multinomial distribution and assign p-values to see which ones of these intervals are not occurring by chance.
I thought to simply consider the start point of each interval and then cluster these based positions. However, as I have many of the intervals clustering with distance matrices is not feasible. Is there a other way to cluster this? Simply sort for both start position and cluster from there. Or is there even a way to cluster intervals efficiently? Or even another way to conduct a significance analysis of theses intervals?