A probabilistic data structure comes to mind, such as Q-Digest. I wonder why it isn't used more for these kinds of problems