MAI
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Trung Quân PHƢƠNG PHÁP TỔ CHỨC CƠ SỞ DỮ LIỆU CHO ĐỐI
TƢỢNG CHUYỂN ĐỘNG LUẬN VĂN THẠC SỸ HỆ THỐNG THÔNG TIN

Chuyên ngành: Hệ thống thông tin
Mã số: 60.48.01.04 LUẬN VĂN THẠC SỸ HỆ THỐNG THÔNG TIN NGƢỜI HƢỚNG DẪN KHOA HỌC
TS. Hoàng Đỗ Thanh Tùng

Hà Nội - 2014 LỜI CAM ĐOAN

Tôi, Nguyễn Trung Quân xin cam đoan toàn bộ nội dung luận văn này
do tôi tự sưu tầm, tra cứu và sắp xếp cho phù hợp với nội dung yêu cầu của đề
tài. Nội dung luận văn này chưa từng được công bố hay xuất bản dưới bất kỳ

Học viên Nguyễn Trung Quân
MỤC LỤC
MỤC LỤC I
DANH SÁCH TỪ VIẾT TẮT III
DANH SÁCH BẢNG IV
DANH SÁCH HÌNH V
PHẦN MỞ ĐẦU 1
1. Tính cấp thiết của đề tài 1
2. Mục tiêu nghiên cứu của đề tài 2
3. Đối tượng và phạm vi nghiên cứu 2
4. Ý nghĩa khoa học của đề tài 2
5. Bố cục luận văn 2
CHƢƠNG 1. TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU KHÔNG THỜI GIAN VÀ
ĐÁNH CHỈ MỤC 3
1.1 Hệ thống cơ sở dữ liệu không gian 3
1.1.1 Cơ sở dữ liệu không gian (Spatial Database) 3
1.1.2 Hạ tầng CSDL không gian 4
1.1.3 Các chức năng của quản lý cơ sở dữ liệu 5
1.1.5 Mô hình cơ sở dữ liệu không gian 6
1.1.6.Khái quát các khái niệm dữ liệu cơ sở trong CSDL không gian 7
1.2 Các cách đánh chỉ số không gian và thời gian 9
1.2.1 Cách đánh chỉ số không gian ( R-tree) 9
1.2.2. Cách đánh chỉ số thời gian ( Snapshot index) 12
CHƢƠNG 2. CÁC PHƢƠNG PHÁP TỔ CHỨC CƠ SỞ DỮ LIỆU CHO ĐỐI
TƢỢNG CHUYỂN ĐỘNG 14
2.1. Lập chỉ mục quá khứ tiến trình không-thời gian 14
2.1.1. Phương pháp tiếp cận đơn giản 15

Global Positioning System
GSM
Global System for Mobile Communications
GPRS
General Packet Radio Service
GIS
Geographic Information System
SMS
Short Message Services
MBR
Minimum Bounding Rectangle
HR-tree
Historical R-tree
2D
2 Dimensional
3D
3 Dimensional
MBB
Minimum Bounding Box
STR-tree
Spatio-Temporal R-tree
TB-tree
Trajectory-Bundle tree
SAM
Spatio Access Methods
MV3R-tree
Multiversion 3D R-tree
TPR-tree
Time Parameterized R-tree
VBR

(d) quadtree tương ứng 7
Hình 1.2: Ví dụ một PR quadtree 8
Hình 1.3: Ví dụ về R-Tree 10
Hình 2.6. Hình hộp giới hạn với chiều thời gian 15
Hình 2.7. (1) Kiểu hình hộp (2) 3DR-tree 16
Hình 2.8. Một ví dụ của truy vấn theo mốc thời gian 17
Hình 2.9. Một R-tree ở thời gian T
0
, T
1
, T
2
17
Hình 2.10. Phương pháp chồng chéo 18
Hình 2.11. Chèn vào một phiên bản mới e
1
thay thế đối tượng e
0
19
Hình 2.12. Chèn một phiên bản mới của e
1
thay thế đối tượng e
0
. 20
Hình 2.13. Nhân đôi một phần tử trung gian 20
Hình 2.14. Xử lý overflow 21
Hình 2.15. Làm dư thừa các phần tử khi bị tràn 21
Hình 2.16. Nhân đôi một phần tử trong khi xoá 22
Hình 2.17. Kết hợp của MVR-tree và 3DR-tree 23
Hình 2.18. Chuyển động của một đối tượng không gian và quỹ đạo tương ứng 24

PHẦN MỞ ĐẦU
1. Tính cấp thiết của đề tài
Năm 2008, Việt Nam đã phóng vệ tinh đầu tiên vào trong quỹ đạo mở ra
nhiều bước tiến mới cho ngành viễn thông. Công nghệ GPS (Global Positioning
System) đã được giới thiệu và nhiều ứng dụng khác nhau trong cuộc sống, việc
khai thác thông tin phục vụ con người là rất cần thiết, mang lại hiệu quả cao
trong nhiều lĩnh vực khoa học công nghệ, phục vụ đời sống sản xuất
Năm 2012, Việt Nam phóng thêm một vệ tinh nữa lên quỹ đạo và đã đưa
những hình ảnh chụp trên lãnh thổ Việt Nam được rõ nét hơn phục vụ đắc lực
trong công tác nghiên cứu khoa học. Với những vệ tinh này việc quản lý, theo
dõi đối tượng chuyển động dễ dàng hơn, việc lưu trữ cơ sở dữ liệu (CSDL) được
thuận tiện khi nó được đánh chỉ mục cho việc theo dõi, quản lý. Cùng với sự
tăng trưởng nhanh chóng của lượng thông tin cũng như sự đa dạng về thể loại
thông tin cần lưu trữ và xử lý, chúng ta ngày càng nhận ra những hạn chế của
các Hệ quản trị CSDL quan hệ truyền thống, và nhu cầu cần phải có các hệ quản
trị CSDL với các dịch vụ phù hợp chính là yếu tố thúc đẩy những nghiên cứu
mới trong lĩnh vực này. Một trong các mô hình CSDL được quan tâm nhất hiện
nay chính là mô hình CSDL không gian - Spatial DataBase (SDB) xử lý các đối
tượng dữ liệu không gian, chẳng hạn dữ liệu bản đồ, dữ liệu multimedia và mở
rộng hơn nữa là kho dữ liệu không gian - Spatial Data. Các nghiên cứu trên lĩnh
vực này đã thu được rất nhiều thành tựu, tuy nhiên cũng còn không ít khó khăn
và thách thức đòi hỏi phải có các giải pháp mới.

Cơ sở dữ liệu không gian tập trung vào hỗ trợ mô hình và truy vấn dạng
hình học liên quan đến các đối tượng trong CSDL còn cơ sở dữ liệu thời gian tập
trung vào tình trạng của đối tượng ở các thời điểm khác nhau. Vì vậy đòi hỏi hai
CSDL không gian và thời gian liên kết chặt chẽ với nhau tạo thành một ứng
dụng quan trọng đó là “cơ sở dữ liệu không – thời gian” hay là cơ sở dữ liệu
cho các đối tượng chuyển động.
Từ thực tiễn trên tác giả lựa chọn đề tài “Phương pháp tổ chức cơ sở dữ

5. Bố cục luận văn
Chƣơng 1: Tổng quan về cơ sở dữ liệu không thời gian và đánh mục
Chƣơng 2: Các phương pháp tổ chức dữ liệu cho đối tượng chuyển động
Chƣơng 3 Xây dựng chương trình thử nghiệm 3
Chƣơng 1. TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU KHÔNG THỜI GIAN VÀ
ĐÁNH CHỈ MỤC

1.1 Hệ thống cơ sở dữ liệu không gian
Hệ thống cơ sở dữ liệu không gian – Spatial Database System – là hệ
thống quản lý dữ liệu liên quan đến các đối tượng không gian (không gian địa
lý), ra đời trước yêu cầu đặt ra trong thực tế là cần một hệ thống để lưu trữ các
dữ liệu trong không gian địa lý. Như vậy việc quản lý hệ CSDL không gian phụ
thuộc vào hai công nghệ: Một là phương tiện lưu trữ cố định và một là CSDL
không gian.
Các không gian:
Không gian hai chiều (2D): Các không gian hình học (Các bề mặt trên
mặt đất ở tỉ lệ co giãn lớn hoặc nhỏ)
Hệ thống thông tin địa lý (GIS – Geographic Information System)

của các đối tượng không gian cùng với đặc điểm thuộc tính của chúng.
Một số hãng phát triển GIS trên thế giới đã có những sản phẩm theo
hướng CSDL không gian như: ERSI, Oracle, Intergraph, MapInfo…
Cơ sở hạ tầng dữ liệu không gian (Spatial Data Infrastructure - SDI) là
nền tảng để dữ liệu không gian và lý lịch dữ liệu cùng với người sử dụng và các
công cụ có thể kết nối trong mối quan hệ tương tác lẫn nhau với mục đích sử
dụng được các thông tin dữ liệu không gian một cách hiệu quả và linh hoạt.
Trong những năm gần đây Hệ thống cơ sở dữ liệu quản lý đối tượng
không gian và thời gian ngày càng nhận được nhiều sự quan tâm. Cơ sở dữ liệu
lưu trữ các đối tượng không gian, mà các thay đổi mức độ, vị trí của các đối
tượng theo thời gian, được gọi là cơ sở dữ liệu không-thời gian. Trong các cơ sở
dữ liệu này việc dự kiến các vị trí tương lai, mức độ của các đối tượng thường
được quan tâm. Những ứng dụng về các đối tượng không thời gian như là: sự
thay đổi toàn cầu(khí hậu,dữ liệu của vùng đất liền), giao thông vận tải( giám sát
giao thông), xã hội( nhân khẩu, sức khỏe), đa phương tiện (phim hoạt hình).
Dưới đây ví dụ về ứng dụng không thời gian
Ví dụ tiên chúng ta xem xét một cơ sở dữ liệu quản lý phương tiện di
chuyển (xe ô tô) trong một hệ thống đường cao tốc. Ngày nay công nghệ GPS
cho phép để xác định vị trí con người và phương tiện ở bất kỳ vị trí trên trái đất,
với độ chính xác cao. Cần phải có một cơ sở dữ liệu lưu trữ các vị trí hiện tại của
phương tiện di chuyển, cũng như định hướng và tốc độ. Từ đó phát sinh những
truy vấn dành riêng cho cơ sở dữ liệu này. Ví dụ một người muốn tìm khách sạn
gần nhất với mình trong 10 phút nữa. Hay là công ty quản lý xe tải muốn tìm
chiếc xe tải gần với nhà kho cụ thể. Hay tìm chiếc xe cứu thương gần nhất với
vụ tai nạn giao thông xảy ra.
Do đặc điểm của thời gian, cơ sở dữ liệu không thời gian phải quản lý
lượng lớn dữ liệu. Một phương pháp để trả lời các câu truy vấn là đọc tất cả dữ
liệu của tất cả đối tượng sau đó trả về đối tượng phù hợp với câu truy vấn. Tuy
nhiên cách này phát sinh vấn đề liên quan đến kích thước của dữ liệu. Một giải
pháp tốt hơn là xây dựng chỉ mục dữ liệu và trả lời truy vấn bằng cách chỉ phải

Hiện nay, hầu hết các quốc gia đều hướng đến xây dựng cơ sở hạ tầng dữ
liệu không gian theo kiến trúc hướng đến dịch vụ (Service Oriented Architecture
- SOA) sử dụng các chuẩn mở quốc tế như OpenGIS (OGC) hoặc ISO/TC.
Đối với Việt Nam và các nước đang phát triển thì thời điểm hiện nay là cơ
hội lớn để chúng ta tiếp cận những tinh hoa từ các tổ chức này để xây dựng
những hệ thống tương tự (đa mục tiêu, đa thành viên). Trên cơ sở đó, Việt Nam
cần tiến hành xây dựng cơ sở hạ tầng dữ liệu không gian cho mình với các tầm
nhìn đều hướng đến một nền tảng để đưa dữ liệu không gian địa lý đến tay
người sử dụng một cách đơn giản, dễ dàng và minh bạch.

6
1.1.4 Các bƣớc thiết kế CSDL không gian
Thiết kế CSDL không gian cần tiến hành qua những bước cơ bản sau
Xác định nội dung CSDL
Chọn cấu trúc CSDL
Thiết kế chi tiết CSDL
Phân phối dữ liệu đến người sử dụng
Duy trì, cập nhật dữ liệu và vận hành hàng ngày
Các thành phần của cơ sở dữ liệu không gian:
 Tập hợp các dữ liệu dạng vector (tập các điểm, đường và vùng)
 Tập hợp các dữ liệu dạng raster (dạng mô hình điểm hoặc ảnh)
 Tập hợp các dữ liệu dạng mạng lưới (đường giao thông, lưới cấp thoát
nước, lưới điện )
 Tập hợp các dữ liệu địa hình 3 chiều và bề mặt khác
 Dữ liệu đo đạc
 Dữ liệu dạng địa chỉ
 Các bảng dữ liệu: Là thành phần quan trọng của cơ sở dữ liệu không

trong của chính nó. Trong phần này, region được hiểu theo cách biểu diễn nội tại
của nó. Một cách biểu diễn thông dụng nhất của region là mảng hình ảnh. Trong
trường hợp này, ta có một tập các phần tử ảnh (gọi là các pixel). Khi số lượng
các phần tử trong mảng quá lớn, phải tiến hành động thái là giảm bớt kích thước
mảng bằng cách kết hợp các pixel tương tự (đồng nhất hay có cùng giá trị). Ở
đây có hai hướng tiếp cận cơ bản. Hướng tiếp cận đầu tiên là của [Rutovitz
1968]: phân chia mảng thành 1*m khối. Đây là cách biểu diễn theo hàng và nó
được biết với tên runlength code. Một hướng tiếp cận khác xem region như là
một tập các khối vuông cực đại (hoặc các khối có hình dạng bất kỳ). Thông
thường các khối được xác định bởi tâm và radii của chúng. Sự biểu diễn này
được gọi là medial axis transformation (MAT).

Hình 1.1: (a)Một region mẫu
(b) Biểu diễn dạng mảng nhị phân của region,
(c) Các khối cực đại và các khối phổ thông đƣợc chia sẻ trong region
(d) quadtree tƣơng ứng
Thuật ngữ quadtree (cây tứ phân) là chỉ số không gian được dùng để phân
chia đệ quy một tập hợp dữ liệu (chẳng hạn, một ảnh) thành các ô vuông cho đến
khi mỗi ô vuông có một giá trị thuần nhất. Cây tứ phân thường được dùng để lưu
trữ dữ liệu raster. Ở đây quadtree được sử dụng để mô tả rất nhiều phần tử của
các cấu trúc dữ liệu có thứ bậc (dựa trên nguyên tắc đệ quy hay còn gọi là các
phương pháp chia để trị).

Dữ liệu điểm - Point Data
Dữ liệu điểm đa chiều có thể được biểu diễn dưới rất nhiều hình thức khác
nhau. Sự lựa chọn sau cùng cho một tác vụ cụ thể sẽ bị ảnh hưởng bởi kiểu
operation sẽ được thực hiện trên dữ liệu. Phần này đề cập chủ yếu đến kiểu biểu
diễn PR quadtree (P: Point và R: Region) là phương thức phân ly chủ đạo. Đây
8


Mỗi một tập interval trong một chiều cụ thể được biểu diễn bởi một grid
file.
Dữ liệu đƣờng - Line Data
Line data là một hình thức biểu diễn xác định các biên của các region.
Cách biểu diễn đơn giản nhất là đa giác gồm có các véc-tơ xác định khuôn dạng
của các liệt kê các cặp giá trị x và y tương xứng với điểm bắt đầu và kết thúc của
chúng. Các véc-tơ thường được sắp xếp theo liên kết của chúng. Một trong
những cách biểu diễn thông dụng nhất là chain code [Freeman 1974].
Dữ liệu không gian - Spatial (High-dimentional) Data
Rất nhiều các cấu trúc SAM (Spatial Access methods) thành công dựa
trên nguồn gốc của sự phân ly không gian có thứ bậc. Ý tưởng ở đây là đánh chỉ
mục một cách liên tục các vùng không gian, như vậy việc tìm kiếm có thể được
xuất phát ở mức cao hướng về những vùng không gian thích hợp.
Một cách thức phổ biến và khả quan để tổ chức và truy cập các đối tượng
đa chiều là sử dụng R-tree hoặc các biến thể của nó bởi vì trong R-tree, không
gian dữ liệu được phân ly liên tiếp nhau thành các rectangle, còn gọi là hyper-
rectangle.
1.2 Các cách đánh chỉ số không gian và thời gian
1.2.1 Cách đánh chỉ số không gian ( R-tree)
Kỹ thuật Phân nhánh-và-giới hạn (branch-and-bound) đang là một kỹthuật
thành công nhất sử dụng trong việc thiết kế các thuật toán giải quyết các câu hỏi
của ngôn ngữ truy vấn trên cấu trúc dạng cây. Hàm chức năng giới hạn thấp hơn
và giới hạn cao hơn là nền tảng cơ bản của hiệu năng tính toán trong thuật toán
phân nhánh-và-giới hạn. Kỹ thuật giả định cơ bản sử dụng trong các thuật toán
truy vấn khoảng cách là các tập dữ liệu không gian được đánh chỉ mục bởi cấu
trúc của họ R-Tree. R-Tree và các biến thể của nó được đánh giá là sự lựa chọn
hoàn hảo trong việc đánh chỉ mục cho rất nhiều loại dữ liệu không gian (điểm,
đoạn thẳng, hình chữ nhật, đa giác…) và vẫn đang được tiếp tục phát triển trong
các hệ thống thương mại như Informix và Oracle. R-Tree là các cấu trúc cây dữ
10

bên trong một khu vực xấp xỉ MBR lại được bao phủ bởi các cây con của các
nút tương ứng. Một thuộc tính quan trọng khác của R-tree là MBR face property
(tạm dịch: thuộc tính bề mặt MBR) – mỗi bề mặt của bất kỳ MBR của mỗi nút
R-tree (tại bất kỳ tầng nào) liền kề ít nhất một điểm của một số đối tượng không
gian trong CSDL không gian
11
Một cách tổng quát, R-tree là một cấu trúc chỉ mục cho các đối tượng
không gian n-chiều và nó tương tự như B-tree. Cấu trúc chỉ mục này là thực sự
linh động, thao tác chèn, xóa, cập nhật có thể kết hợp với phép tìm kiếm và có
thể thực hiện theo chu kỳ.
Các nút lá trong cây chứa chỉ mục vì vậy chúng có khuôn dạng: (MBR,
object_ptr) - trong đó object_ptr tham chiếu đến một bộ dữ liệu trong cơ sở dữ
liệu và MBR là một hình chữ nhật n-chiều chứa các đối tượng không gian nó thể
hiện.
Các nút không phải lá có khuôn dạng: (MBR, chirld_ptr) - trong đó
chirld_ptr là địa chỉ một nút khác trong cây và MBR bao gồm các hình chữ nhật
trong các nút thấp hơn.
Nói cách khác, không gian MBR chứa mọi đối tượng được đánh chỉ mục
trong các cây con có gốc là đầu vào của MBR. Cho M là số lượng tối đa đầu vào
có thể vừa đủ với một nút và cho tham số m xác định số lượng tối thiểu đầu vào
tại một nút.
Một R-tree thỏa mãn các thuộc tính sau:
- Mỗi một nút chứa số lượng nút con trong khoảng m và M ngoại trừ nút
gốc.
- Đối với mỗi đầu vào dạng (MBR, object_ptr) tại nút lá, MBR là một
hình chữ nhật nhỏ nhất có chứa đối tượng dữ liệu n-chiều được biểu
diễn bởi object_ptr.

Chỉ mục Ảnh chụp sử dụng ba cấu trúc cơ bản: một cây cân bằng (time -
tree) chỉ mục dữ liệu trang theo thời gian, một cấu trúc con trỏ (access-forest)
trong các trang dữ liệu và một chương trình băm. Time-tree và access-forestcho
phép trả lời truy vấn nhanh, chương trình băm được sử dụng để cập nhật nhanh
chóng.
Trước tiên chúng ta thảo luận về việc cập nhật. Đối tượng được lưu trữ
liên tục trong trang dữ liệu theo thứ tự như chúng được thêm vào tập S. Khi một
đối tượng mới với OID k được thêm vào tại thời điểm t, một bản ghi mới của
mẫu <k, [t, now]> được tạo ra và được gắn tiếp vào trang dữ liệu. Ngay lập tức
có một trang dữ liệu chấp nhận chứa bản ghi được tạo ra. Khi trang chấp nhận bị
full thì một node mới được tạo ra. Thời gian khi một trang chấp nhận được tạo
ra cùng với địa chỉ trang của nó được lưu trữ trong cây thời gian. Như trang
chấp nhận được tạo ra liên tục thời gian cây có thể dễ dàng duy trì (phân bổ O
(1) I / O cho chỉ mục mỗi trang chấp nhận mới).
Xem xét số lượng bản ghi "alive" của trang chứa sau khi nó bị đầy ( full).
Cho rằng tất cả các trang này chứa các bản ghi sống UB nó được gọi là hữu ích.
Đối với những lần t trang có chứa một phần tốt đẹp của câu trả lời cho S (t). Trả
lời một câu hỏi thuần ảnh chụp về một số thời điểm t chỉ cần xác định vị trí các
trang hữu ích vào thời điểm đó, mỗi trang như vậy sẽ đóng góp ít nhất là đối
tượng UB để trả lời. Tham số u hữu ích là một hằng số mà giai điệu của hành vi
của chỉ mục ảnh chụp.
Một trang được chấp nhận là đặc biệt khi một trang có thể chứa ít hơn các
bản ghi còn sống UB. Theo định nghĩa một trang cũng được gọi là hữu ích cho
13
miễn là nó là trang chấp nhận. Một trang như vậy có thể không cung cấp đủ trả
lời để biện minh cho việc tiếp cận nó, nhưng nó vẫn phải được truy cập. Vì mỗi
lần ngay lập tức có tồn tại chính xác một trang chấp nhận, điều này không ảnh
Chƣơng 2. CÁC PHƢƠNG PHÁP TỔ CHỨC CƠ SỞ DỮ LIỆU CHO ĐỐI
TƢỢNG CHUYỂN ĐỘNG
Nhiều thập kỷ qua có rất nhiều phương pháp tổ chức dữ liệu cho đối
tượng chuyển động được nghiên cứu và phát triển. Phương pháp tổ chức dữ liệu
cho đối tượng chuyển động chủ yếu tập trung vào 02 hướng là: (1) lập chỉ mục
quá khứ, (2) lập chỉ mục hiện tại và dự đoán tương lai. Trong phần này tôi sẽ tìm
hiểu và phân tích một số phương pháp tổ chức dữ liệu dựa trên cấu trúc cơ bản
của các phương pháp lập chỉ mục.
2.1. Lập chỉ mục quá khứ tiến trình không-thời gian
Dữ liệu lịch sử của đối tượng chuyển động là rất hữu ích trong các ứng
dụng như lập kế hoạch và quản lý tài nguyên. Tuy nhiên trong cơ sở như vậy
không gian để lưu trữ thông tin vị trí của đối tượng là rất lớn khi đối tượng
chuyển động. Do đó vấn đề quyết định là dữ liệu lịch sử nào là tốt nhất và lưu
trữ chúng như thế nào để đạt hiệu quả cao.

x
x
x
x
x
t
t
1

t
5

t


o
2

o
2

o
2

o
3

o
3

o
3

o
3

o
1

o
1

o
1

dụng như các hàm tuyến tính theo thời gian vì các đối tượng có thể thay đổi hay
được thu nhỏ/mở rộng theo thời gian. Các bản ghi mới được chèn vào chỉ khi
đối tượng có sự thay đổi vị trí hay kích thước của nó. Các bản ghi mới sẽ duy trì
thời gian tồn tại của đối tượng dưới một hàm chuyển động/kích thước mới.
Trong trường hợp tổng quát số lượng N chèn vào tương ứng với: (1) đối tượng
chèn thường xuyên và (2) đối tượng chèn vào khi tham số của hàm thay đổi.
2.1.1. Phƣơng pháp tiếp cận đơn giản
Một phương pháp tiếp cận đơn giản cho việc lập chỉ mục dữ liệu không-
thời gian là coi trục thời gian như là một chiều giống như những chiều khác của
không gian.
Sau đó mỗi đối tượng có thể lưu trữ như một hình hộp chữ nhật 3 chiều
trong đó độ cao của hình hộp chữ nhật chính là khoảng thời gian tồn tại của đối
tượng. Các phương pháp truy nhập không gian truyền thống SAM (R-tree [2],
Quad-tree[8]) sẽ sử dụng không gian d+1 chiều, trong đó d là số chiều của
không gian tham chiếu và bổ sung thêm chiều của thời gian.
Theo cách tiếp cận này, phương pháp 3DR-tree [11] sử dụng trục thời
gian như là một chiều giống như những chiều khác của không gian. Tại mốc thời
gian ti các đối tượng không gian chỉ đơn giản là được bổ sung vào hay xoá đi.
Khi một đối tượng di chuyển từ vị trí này sang vị trí khác một MBR được tạo ra
để mô tả những thay đổi của đối tượng. MBR này chứa kích thước không gian
và thời gian tồn tại của đối tượng. Đối tượng sẽ được mô tả như một hình hộp 3
chiều, với chiều thời gian chính là thời gian tồn tại của đối tượng như hình 2.6.

x
t
t
1

t
3