통계 정보를 활용한 쿼리 응답 처리 과정
STING(STatistical INformation Grid)과 같은 그리드 기반 방식에서 통계 파라미터는 다음과 같은 상향식(top-down) 절차를 통해 쿼리 응답에 활용됩니다.
먼저, 쿼리 응답 절차를 시작할 계층 구조 내의 레이어를 결정합니다. 이 레이어는 일반적으로 소수의 셀(cell)로 구성됩니다. 현재 레이어의 각 셀에 대해 해당 셀이 주어진 쿼리와 얼마나 관련이 있는지를 나타내는 신뢰 구간(confidence interval), 즉 확률의 추정 범위를 계산합니다.
상위 레벨 셀의 통계 파라미터는 하위 레벨 셀의 파라미터로부터 간단히 계산할 수 있습니다. 이러한 파라미터는 다음과 같습니다.
- 속성 독립적 파라미터: count(객체 개수)
- 속성 종속적 파라미터: mean(평균), stdev(표준편차), min(최솟값), max(최댓값)
- 분포 유형: 셀 내 속성 값이 따르는 분포로, 정규 분포(normal), 균등 분포(uniform), 지수 분포(exponential) 또는 알 수 없는 경우 none
쿼리와 관련 없는 셀은 이후 고려 대상에서 제외됩니다. 다음 하위 레벨의 처리 단계에서는 남아 있는 관련 셀만 검사하며, 이 과정은 최하위 레이어에 도달할 때까지 반복됩니다. 마지막으로 쿼리 조건이 충족되면 해당 쿼리와 관련된 셀들의 영역이 결과로 반환됩니다.
STING의 주요 장점
쿼리 독립적인 연산: 그리드 기반 계산은 쿼리와 무관합니다. 각 셀에 저장된 통계 데이터는 쿼리와 별개로 그리드 셀 내부 데이터의 요약 정보를 정의하기 때문입니다.
병렬 처리 및 증분 갱신 지원: 그리드 구조는 병렬 처리와 증분 새로 고침(incremental refresh)을 자연스럽게 지원합니다.
높은 처리 효율: STING은 데이터베이스를 스캔하면서 각 셀의 수치 파라미터를 계산할 수 있으므로, 클러스터 생성의 시간 복잡도는 O(n)입니다. 여기서 n은 전체 객체 수입니다.
빠른 쿼리 응답: 계층 구조를 한 번 구축해 두면 이후 쿼리 처리 시간은 O(g)입니다. g는 최하위 레벨의 전체 그리드 셀 수로, 일반적으로 n보다 훨씬 작습니다.
STING의 한계
입자 크기(granularity) 의존성: STING은 클러스터 분석에 멀티해상도(multiresolution) 방식을 사용하므로, 클러스터링 품질은 그리드 구조 최하위 레벨의 입자 크기에 좌우됩니다. 입자가 매우 세밀하면 처리 비용이 크게 증가하고, 반대로 최하위 레벨이 너무 거칠면 클러스터 분석의 품질이 저하될 수 있습니다.
공간 관계 미고려: STING은 부모 셀을 생성할 때 자식 셀과 인접 셀들 간의 공간적 관계를 고려하지 않습니다. 그 결과 생성되는 클러스터의 경계는 수평 또는 수직 방향(isothetic)으로만 형성되며 대각선 경계는 나타나지 않습니다. 빠른 처리 속도에도 불구하고 이로 인해 클러스터의 품질과 신뢰성이 떨어질 수 있습니다.