An adaptive indexing technique using spatio-temporal query workloads

. Spatio-temporal access methods
  . HR-tree
  . 3DR-tree
  . MV3R-tree
  . APR-tree(Adaptive Partitioned R-tree)
  . STR-tree
  . TB-tree

. query
  . trajectory (navigational) quey
  . timestamp(timeslice) quey
  . interval query

. MBR : minimum bounding rectangles

. workload에 따라 adapt함.
. jurisdiction interval length

. 3DR-tree
  . time as another dimension of the R-Tree
  . long lived record가 많으면 손해
  . HR-tree, MV3R tree와 달리 duplicate이 없어서
    size가 가장 작다.

. HR-tree(Historical R-tree)
  . position 내에서 위치가 바뀐 object만 새로 표시하고
    나머지는 position과 object data를 예전 것과 share함

. MV3R-tree
  . MVR(Multi-Version R-tree) + auxiliary 3DR-tree
  . MVR(Multi-Version R-tree) : for timestamp and short interval query
  . auxiliary 3DR-tree : for long interval queries

. ARP-tree
  . jurisdiction interval length을 workload에 따라 조절하여
    search space를 줄인다.
  . data fragmentation이 일어날 때만 duplicate한다.
  . AVG record : the average lifespan length of records.
  . AVG queries : the average time interval length of queries
  . AVG record와 AVG queries를 이용하여 optimize

. Experimental result
  . interval query가 적을 때
    3DR-tree는 느리고 HR-tree는 빠르다.
  . interval query가 많을 때
    HR-tree는 느리고 3DR-tree는 빠르다.
  . MVR-tree는 언제나 빠르고, ARP-tree는 더 빠르다.

  . agility : 각각의 시각에 움직이는 데이터의 비율

. structure
  . HR, MV3R : graph structure(복잡)
    . access list를 저장해 둬야 reaccess를 막을 수 있다.(overhead)
  . 3DR, APR : tree structure(간단)


GSTD method : Generate Spatio-Temporal Data
http://db.cs.ualberta.ca:8080/gstd/

---------------------------------------------
Game save file을 만들 때도 spatio-temporal DB를 쓰면 좋을 것 같다.