International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B4. Istanbul 2004
spaces into sub-space, and then maintains a quad-tree for each
sub-space.
We also implemented TB-tree, STR-tree, 3DR-tree, and HR-
tree as past location indexes. But these trees for indexing past
locations of moving objects are not applied in real world
applications due to the problems described in following section.
Query
Interface
Management
Interface
FEN /
7 te N EN
FN rint
|
+
M
Figure 9. Current Location Indexes (Adaptive Quad-Tree)
S.1 Problems in Whole Indexing Method
The whole indexing method means that a tree is used to index
all of the locations (including past locations) of moving objects.
Figure 10 shows the whole indexing method. Most of past
location indexes are based on R-tree, and therefore, are height-
balanced trees.
DELETE
INSERT
SEARCH
entire time interval
D as time goes
G the performance worsc
Figure 10. Whole Indexing Method
In whole indexing method, all of the locations of moving
objects are managed by single tree during entire time interval.
As shown in Figure 10, [J as time goes, [ increasing the depth
of tree, makes | the performance of INSERT and SEARCH
operation worse.
Another problem is about the DELETE operation. The
DELETE operation of R-tree variables requires the
reorganization of the tree, if the number of entries of node N,
which contained the deleted entry, is less than the minimum
number (m) of entries. Because the reorganization of the tree
requires the deletion and re-insertion of m-1 entries, DELETE
is costly operation in this environment. Therefore, the deletion
of entries during a specific time period, which is probably
usable operation of managing the moving objects, is hardly
performed.
Architecture of Time Segmented Indexing Method
116
SEARCH DELETE
mE
INITIALIZE INSERT
|
2
Virtual Indes
3,12 IN
E a # L—— shown as single
Index Types P B ES LI e ;
a AE NZ PEN 7 tree from outside)
TB, STR = RS
STR... ~ / EB Is
TS! Manager
Division Strategies
Time, Space. ..
© as time goes
/
According to each period.
à time segmented index( SD) is maintained
Figure 11. Time Segmented Indexing Method
(Time Division Framework)
To solve the above problems, we revised the indexing
framework (called Time Division Framework), which could be
applicable regardless of the types of past location indexes.
Figure 11 shows the overall architecture of time segmented
indexing method. In this framework, an index tree is segmented
into several TSIs (Time Segmented Index), but these TSIs
compose a virtual index, which is shown as single tree from
outside. A virtual index has also TSI manager, INSERT
manager, SEARCH manager, and DELETE manager. Due to
the space limitation, we do not explain the detail operations of
the virtual index and the strategies of time segmentation.
6. LOCATION STORAGE MODULE (LSM)
The role of Location Storage Module (LSM) is to insert and
search the locations of moving objects in efficient. As shown in
Figure 12, LSM consists of a storage manager, a server
manager, a connection manager, a disk manager and storage
drivers.
qmm = IX
Rupe [emnt tenen rene |
Index
.——j Server. Monoger Disk Manager ——
| | [ |
Stersge Sterage Storega Storage
brher | Driver brivar briver
——————— - :
a a ES
| | Crock | Fite :
| | Sil s. Zeus | |j
Figure 12. Location Storage Module
The Storage Manager has two main operations, INSERT and
SEARCH, which are usually called by BMM. When BMM
issues INSERT or SEARCH, the Storage Manager looks for a
suitable storage system by referencing the Connect Manager
and the Server Manager. Then, it calls INSERT and SEARCH
Interr
of the
- syster
The S
balan
status
and tl
most
The
datab:
envirc
storag
operat
distrib
Conne
databe
Storag
The D
as Ora
on Set
full, it
systen
system
also pr
IMPO
The S
corres]
predic;
In this
a larg
implen
system
integra
one sy
objects
a meth
support
indexes
applied
As futi
real en
develoj
query p
Becki:
Efficier
Rectang
Erwig,
1999.
Modelii
fomatic
Forlizzi
2000. **
Databas
319-330
