Как аппроксимировать x-й процентиль для большого неизвестного количества чисел

Я думаю, вы могли бы использовать выборку из резервуара, чтобы равномерно выбрать k элементов из потока S, а затем аппроксимировать xth процентиль S с x-м процентилем этих k чисел. k зависит от того, сколько у вас памяти и насколько точным должно быть приближение.

ИЗМЕНИТЬ

Вот пример кода для проверки решения:

// create random stream of numbers
Random random = new Random(0);
List<Integer> stream = new ArrayList<Integer>();
for (int i = 0; i < 100000; ++i) {
    stream.add((int) (random.nextGaussian() * 100 + 30));
}
// get approximate percentile
int k = 1000; // sample size
int x = 50; // percentile
// init priority queue for sampling
TreeMap<Double, Integer> queue = new TreeMap<Double, Integer>();
// sample k elements from stream
for (int val : stream) {
    queue.put(random.nextDouble(), val);
    if (queue.size() > k) {
        queue.pollFirstEntry();
    }
}
// get xth percentile from k samples
List<Integer> sample = new ArrayList<Integer>(queue.values());
Collections.sort(sample);
int approxPercent = sample.get(sample.size() * x / 100);
System.out.println("Approximate percentile: " + approxPercent);
// get real value of the xth percentile
Collections.sort(stream);
int percent = stream.get(stream.size() * x / 100);
System.out.println("Real percentile: " + percent);

Результат:

Приблизительный процентиль: 29

Реальный процентиль: 29

Я получил довольно хорошее приближение для каждого x, которое я использовал, и в настоящее время я не понимаю, почему оно не подходит для вашего случая.