소급 데이터 구조

Retroactive data structure

컴퓨터 과학에서 소급 데이터 구조는 구조에서 수행된 일련의 작업에 대한 효율적인 수정을 지원하는 데이터 구조입니다.이러한 변경은 [1]과거에 수행된 작업을 소급하여 삽입, 삭제 또는 업데이트하는 형태를 취할 수 있습니다.

소급 데이터 구조의 일부 적용

실제 세계에서는 일련의 조작으로부터 과거의 조작을 수정하고 싶은 경우가 많다.사용 가능한 어플리케이션의 일부를 다음에 나타냅니다.

  • 오류 수정:데이터입력잘못되었습니다.데이터를 수정하고 잘못된 데이터의 2차적 영향을 모두 제거해야 합니다.
  • 불량 데이터:대규모 시스템(특히 대량의 자동 데이터 전송이 수반되는 시스템)을 취급하는 경우는 드물지 않습니다.예를 들어 날씨 네트워크에 대한 센서 중 하나가 오작동하여 가비지 데이터나 잘못된 데이터를 보고하기 시작한다고 가정합니다.이상적 해결책은 센서가 오작동하여 생성된 모든 데이터와 시스템 전체에 미치는 모든 영향을 제거하는 것입니다.
  • 복구: 하드웨어 센서가 손상되었지만 복구되어 센서에서 데이터를 읽을 수 있다고 가정합니다.처음부터 센서가 손상되지 않은 것처럼 데이터를 시스템에 다시 삽입할 수 있도록 하고 싶습니다.
  • 과거의 조작:과거의 변경은 피해 통제의 경우에 도움이 될 수 있으며 소급 데이터 구조는 과거의 의도적인 조작을 위해 설계된다.

공간 차원으로서의 시간

시간을 추가 공간 차원으로 간주하는 것은 불가능합니다.이를 설명하기 위해 시간 차원을 공간의 축에 매핑한다고 가정합니다.공간 시간 차원을 추가하는 데 사용할 데이터 구조는 최소 힙입니다.y축은 힙 내 항목의 키 값을 나타내고 x축은 공간 시간 치수를 나타냅니다.여러 번 삽입 및 최소 삭제 작업(모두 비소급적으로 수행됨)을 수행하면 그림 1과 같이 최소 히프가 나타납니다.이제 작업 목록의 시작 부분에 0을 소급하여 삽입한다고 가정합니다.우리의 최소합은 그림 2와 같이 나타날 것이다.단일 작업으로 인해 전체 데이터 구조에 영향을 미치는 계단식 효과가 어떻게 발생하는지 주목하십시오.따라서 시간을 공간적 차원으로 그릴 수 있는 반면, 관련된 연산은 시간에 대한 수정이 이루어질 때 파장을 일으키는 의존성을 발생시킨다는 것을 알 수 있다.

그림 1. 타임라인의 Min-Heap.
그림 2소급 수술 후의 Min-Heap과 타임라인.

지속성과의 비교

소급 데이터 구조의 개념은 시간의 차원을 고려하기 때문에 언뜻 보면 영속적인 데이터 구조와 매우 유사해 보인다.영구 데이터 구조와 소급 데이터 구조의 주요 차이점은 시간 요소를 처리하는 방법입니다.영속적인 데이터 구조는 데이터 구조의 여러 버전을 유지하며, 데이터 구조의 다른 버전을 생성하기 위해 한 버전에서 작업을 수행할 수 있습니다.각 작업은 새 버전을 생성하므로 각 버전은 변경할 수 없는 아카이브가 됩니다(새 버전만 생성할 수 있습니다).각 버전은 변경되지 않으므로 각 버전 간의 종속성도 변경되지 않습니다.소급 데이터 구조에서는 이전 버전을 직접 변경할 수 있습니다.각 버전은 상호 의존적이기 때문에 한 번의 변경으로 인해 이후 모든 버전의 변경사항이 발생할 수 있습니다.그림 1과 그림 2는 이 파동 효과의 예를 나타내고 있습니다.

정의.

모든 데이터 구조를 소급 설정으로 재구성할 수 있습니다.일반적으로 데이터 구조에는 일정 기간 동안 수행된 일련의 업데이트 및 쿼리가 포함됩니다.U = [ut1t2, ut3, u, ..., u]를 t < t2 < ..., ttmm ]로1 하는1m 갱신 조작의 시퀀스로 합니다.여기서 가정하는 것은 주어진 시간 t에 대해 최대 1개의 조작을 실행할 수 있다는 것입니다.

부분 소급

현재 업데이트 및 쿼리 작업을 수행할 수 있고 과거에 삽입 및 삭제 작업을 지원할 수 있는 경우 데이터 구조가 부분적으로 소급되도록 정의합니다.따라서 부분 소급에 대해서는 다음 작업에 관심이 있습니다.

  • 삽입(t, u):새로운 조작 u를 시각 t에 리스트 U에 삽입합니다.
  • 삭제(t):U 목록에서 t시 작업을 삭제합니다.

위의 소급 연산을 통해 표준 삽입 연산은 이제 Insert(t, "insert(x)"의 형식이 됩니다.데이터 구조의 운영 이력에 대한 모든 소급 변경은 운영 시점의 모든 작업에 영향을 미칠 수 있습니다.예를 들어 t < ti+1 < t가 있는 경우i-1 Insert(t, insert(x))는 연산i-1 op과i+1 op 사이에 새로운 연산 op을 배치합니다.데이터 구조의 현재 상태(즉, 현재의 데이터 구조)는 운영 운영이 항상 존재하는 것처럼 순차적으로 발생한 운영i-1 op, op 및i+1 op과 같은 상태가 됩니다.그림 1과 그림 2를 참조해 주세요.

완전 소급

데이터 구조는 부분적으로 소급된 작업 외에 과거에 대한 질문도 수행할 수 있는 경우 완전히 소급된 것으로 정의합니다.표준 연산 삽입(x)이 부분 소급 모델에서 Insert(t, "insert(x)"가 되는 방식과 마찬가지로 완전 소급 모델의 연산 쿼리(x)는 Query(t, "query(x)" 형식입니다.

소급 실행 시간

소급 데이터 구조의 실행 시간은 구조물에 대해 수행된 작업 수 m, 소급 작업이 수행되기 전에 수행된 작업 수 r 및 구조물 내 최대 요소 수 n을 기준으로 한다.

자동 복고 활동

데이터 구조에 관한 자동 소급 활동에 관한 주요 질문은 데이터 구조를 효율적인 소급 대응 기법으로 변환할 수 있는 일반적인 기술이 있는지 여부이다.간단한 접근법은 적용할 소급 작업 전에 구조물의 모든 변경에 대해 롤백을 수행하는 것이다.데이터 구조를 적절한 상태로 롤백하면 소급 조작을 적용하여 원하는 변경을 할 수 있습니다.변경이 이루어지면 이전에 롤백했던 모든 변경을 다시 적용하여 데이터 구조를 새로운 상태로 만들어야 합니다.이 방법은 모든 데이터 구조에서 사용할 수 있지만, 특히 롤백에 필요한 변경 수가 많은 경우에는 비효율적이고 낭비적인 경우가 많습니다.효율적인 소급 데이터 구조를 작성하려면 구조 자체의 속성을 살펴보고 속도 향상을 실현할 수 있는 위치를 결정해야 합니다.따라서 어떤 데이터 구조도 효율적인 소급 방식으로 변환할 수 있는 일반적인 방법은 없습니다.에릭 D. 데메인, 존 아이아코노, 스테판 랭거만이 이것을 [1]증명한다.


「 」를 참조해 주세요.

레퍼런스

  1. ^ a b Demaine, Erik D.; Iacono, John; Langerman, Stefan (2007). "Retroactive data structures". ACM Transactions on Algorithms. 3. doi:10.1145/1240233.1240236. Retrieved 21 April 2012.