STING은 Statistical Information Grid의 약자입니다. STING은 공간 영역을 직사각형 셀로 분할하는 그리드 기반 다중 해상도 클러스터링 방법입니다. 이러한 직사각형 셀에는 여러 해상도 방법에 해당하는 몇 가지 방법이 있으며 이러한 셀은 계층 구조를 형성합니다. 높은 수준의 각 셀은 분리되어 다음 낮은 수준의 여러 셀을 형성합니다.
각 그리드 셀의 속성에 대한 통계 데이터(평균, 최대값, 최소값 포함)는 미리 계산되어 저장됩니다. 상위 수준 셀의 통계 매개변수는 하위 수준 셀의 매개변수에서 간단히 계산할 수 있습니다.
이러한 매개변수에는 다음이 포함됩니다. 속성 독립 매개변수 개수 및 속성 종속 매개변수 평균, stdev(표준 편차), 최소(최소), 최대(최대). 일반, 균일, 지수 또는 없음을 포함하여 셀의 속성 값이 따르는 분포 유형(분포가 익명인 경우)
레코드가 데이터베이스에 로드되면 최하위 셀의 매개변수 count, mean, stdev, min 및 max가 레코드에서 직접 계산됩니다. 분포 값은 분포 유형을 미리 알고 있거나 χ 2 를 포함한 가설 검정으로 얻은 경우 사용자가 할당할 수 있습니다. 테스트.
임계값 필터링 절차와 함께 동등한 하위 수준 셀의 대량 분포 유형을 기반으로 평가할 수 있는 더 큰 수준 셀의 분포 유형입니다. 하위 셀의 분포가 일치하지 않고 임계값 테스트를 거부하는 경우 상위 셀의 분포 유형이 없음으로 설정됩니다.
그리드 기반 클러스터링 방법은 다중 해상도 그리드 데이터 구조를 사용합니다. 객체 공간을 클러스터링을 위한 일부 작업이 구현되는 그리드 구조를 형성하는 다중 셀로 양자화합니다. 이 방법의 이점은 빠른 처리 시간으로, 일반적으로 데이터 개체 수와 무관하며 양자화된 공간의 각 차원에 있는 여러 셀에만 의존합니다.
그리드 기반 접근 방식의 예로는 그리드 셀에 저장된 통계 데이터를 탐색하는 STING, 웨이블릿 변환 접근 방식을 사용하여 개체를 클러스터링하는 WaveCluster, 높은 수준의 클러스터링을 위한 그리드 및 밀도 기반 방법을 정의하는 CLIQUE가 있습니다. 차원 데이터 영역.
이 접근 방식의 장점은 통계 정보가 쿼리와 독립적으로 존재하기 때문에 쿼리 독립적 접근 방식입니다. 이는 각 그리드 셀의 데이터에 대한 일반적인 설명으로, 방대한 쿼리 클래스에 대한 응답을 지원하는 데 사용할 수 있습니다. 계산 복잡도는 O(K)이며, 여기서 K는 가장 낮은 수준의 그리드 셀 수입니다. 일반적으로 K <