다시 계산하지 않고 분수를 갱신하십시오.

Question

데이터 포인트의 추가/제거로 많은 샘플 데이터 세트의 퀴 트릿을 다시 계산하는 대신 갱신 할 수있는 Java 라이브러리가 있습니까? 내 생각 엔 효율적인 알고리즘은 업데이트를위한 일정한 시간이 필요합니다 (이미 존재하는 포인트 수의 함수가 아님).

알려진 알고리즘이 나열되어 있지만, 샘플 세트에서 점을 제거하는 방법이 '그나마 :

• Colt Stream Quantiles :이 하나의 데이터 조각이 한 번
• Apache Math Percentile을 추가 제거 방법이 없습니다 :이 일을 단순히 배열의 quantile을 계산하며 배열에서 데이터를 제거 할 수 없습니다.

다음은 샘플 문제입니다. 풍속 세트의 임의이지만 일정한 백분위 팬 속도 (풍속의 추정치)를 말하고 싶습니다. 팬 속도는 몇 밀리 초마다 비동기 적으로 업데이트됩니다. 이 라이브러리를 사용하면 중간 값을 다시 계산하지 않고 한 번에 하나의 풍차의 풍속을 업데이트 할 수 있습니다.

Answer 1

데이터의 갱신 가능 정렬 된 표현을 유지 보수하는 경우, Quantile을 확보하는 것은 h 열 길이를 사용하는 것만으로 쉽고 효율적입니다. 예를 들어 N 개의 요소가있는 경우 중앙값은 N/2 위치에 있습니다. 데이터 구조에 새 요소를 삽입하면이 요소는 계속 유지됩니다. 효율성은 새로운 요소 삽입에만 달려 있습니다.

Answer 2

여러 개의 데이터 일괄 처리를 할 수 있습니다. 이러한 배치의 백분위 수/4 분위수를 결합하여 집계를 추정 할 수 있습니다. 이점은 다른 배치를 다시 계산할 필요없이 여러 배치를 효율적으로 폐기 할 수 있다는 것입니다.