LES-tree: A Spatio-temporal Access Method based on Snapshots and Events

of 25
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report



Views: 52 | Pages: 25

Extension: PDF | Download: 0

LES-tree: A Spatio-temporal Access Method based on Snapshots and Events
  LES-tree: A Spatio-temporal Access Method based on Snapshotsand Events  ∗ Gilberto A. Guti´errezCenter for Web ResearchUniversity of Chile andUniversity of B´ıo-B´ıoAvenida La Castilla S/NChill´an / Chile ggutierr@ubiobio.cl Gonzalo NavarroCenter for Web Research andDepartment of Computer ScienceUniversity of Chile.Avenida Blanco encalada 2120Santiago / Chile gnavarro@dcc.uchile.cl M. Andrea Rodr´ıguezDepartment of Computer ScienceUniversity of Concepci´onEdmundo LarenasConcepci´on / Chile andrea@udec.cl October 14, 2008 Abstract This work presents a new access method (LES-tree)for spatio-temporal databases that handles discretechange events over objects’ spatial attributes. Themain characteristic of this structure is that, inaddition to the traditional database snapshots, LES-tree explicitly stores the events in  log   structuresassociated with space partitions. The definition of this new access method aims to extend capabilities of current spatio-temporal access methods to queries on events  , while competing with current structures fortraditional  time-slice   and  time-interval   queries. Thepaper describes the structure and presents favorableexperimental cost analyses of the structure. ∗ This work was partially funded by Millennium NucleusCenter for Web Research, grant P04-067-F, Mideplan, Chile.Gilberto Guti´errez was also funded by research grant 0732184/R, University of B´ıo-B´ıo, Chile 1 Introduction Spatio-temporal databases are composed of spatialobjects that change their location or shape atdifferent time instants [18]. Their objective is tomodel and represent the dynamic nature of real-worldapplications [10]. Examples of these applicationsare transportation, monitoring, environmental, andmultimedia systems. Spatio-temporal applicationshave been classified into three categories dependingon the type of data they manage [12]:a) Applications that deal with continuous changes,such as the movement of a car on a highway.b) Applications that involve objects that changetheir location in space by modifying their shapeor by a movement in a discrete manner. Anexample is the change in the administrativeboundary of a city over time.1  c) Applications that integrate both previousbehaviors. This type of applications appears inthe environmental area where it is necessary tomodel objects’ movement and objects’ geometricchanges over time.Extending  window/range queries   in spatialdatabases, the most studied types of queries inspatio-temporal databases are  time-slice   and  time-interval   queries [16].  Time-slice   queries retrieveall objects that intersect the query window ata particular time instant.  Time-interval   queriesextend the idea of   time-slice   queries by consideringconsecutive time instants. These queries focus onthe coordinate- or snapshot-based representationsof objects’ movement. In addition to this type of representation, recent studies have emphasized therelevance of handling events, encouraging researchin the integration of coordinate- and event-basedrepresentation [23, 3, 2]. Event representationenables to manage relationships between events,querying about objects’ states, and querying whenand why changes on objects occur.There exist various spatio-temporal access meth-ods that are adequate for applications that handlediscrete changes of spatial objects. Some are RT-tree [24], HR-tree (Historical R-tree) [10, 11], 3D R-tree [21], HR + -tree [14], MV3R-tree [15] and OLQ(Overlapping Linear Quadtree) [22], among others.These structures are designed to answer  time-slice  and  time-interval   queries about the history of thespatial attributes of objects. In addition, several of these existing spatio-temporal access methods alsohandle spatial changes of objects [10, 15, 21], butthey use data about these changes with the purposeof updating the underlying data structure. They donot keep data about changes as records of eventsoccurred over objects and, therefore, they cannotefficiently answer queries about events occurred ina time interval.This work aims to define a new access methodthat can efficiently answer  time-slice   queries,  time-interval   queries, and  queries on events  . To the bestof our knowledge, only the preliminary work in [5]indexes  events   to process traditional time-slice andtime-interval queries. In this work, we also addressevent-based queries that retrieve objects satisfyingan event predicate within a spatio-temporal window.For example, retrieve all objects that entered orcrossed a given spatial window within a time interval.These queries are easily extended to spatio-temporalpattern queries [7], where we may want to retrieveobjects that follow certain patterns of events in aparticular sequence.Our new access method, LES-tree, is based onproducing snapshots after a certain number of changes occurred over objects, and on storing theevents that produce these changes in a data structurecalled a  log  . Consequently, LES-tree enables therepresentation of (1)  temporal snapshots   and (2) events on objects  , as advocated in [23]. This approachhas been briefly discussed in others studies [8, 9],but it has been discarded a priori by arguing thatit is not easy to know how many events determinea new snapshot and that extra time is requiredfor query processing. We show in this paper thatthis is not a serious drawback. The number of snapshots represents a trade-off between space andanswer time, since a larger number of snapshotsdecreases the answer time of a query while increasingthe storage space. Inversely, a smaller number of snapshots decreases the space while increasing theanswer time; and then, the frequency of snapshotscan be adjusted depending on the type of applicationsand the change frequency of objects. For example,there may be applications where it is not of interestto query about objects’ states over some period of time. Our data structures for snapshots and changesare independent, and so are the improvements thatcan be obtained in either structure. Furthermore,integration of existing spatial access methods forhandling snapshots into this approach can be easilyachieved.The idea of snapshots and  logs   has also been usedwith the purpose of maintaining materialized viewsin a database [4]. In this context, a  log   is createdover the master table, from which the initial viewis created. Then, the refreshed view is the result of applying the changes stored in the  log  . These  logs   areeliminated after the actualization of the view, sinceonly the last state of the database is requested. The logs   in our proposal, in contrast, are a part of the2  indexing structure, remain over time, and can derivedifferent temporal states of the database.A preliminary proposal of an access method withthese characteristics is the SEST-Index [5]. Theidea of SEST-Index consists in maintaining thesnapshots of the database for certain time instants(by using an R-tree) and having a global  log   to storethe events occurred between consecutive snapshots.The  log   is stored in time-order and allows us toreconstruct whatever the state of the database wasbetween two consecutive snapshots. Although thisstructure presents some good properties for time-sliceand event queries, it has serious storage cost andscalability problems, and its performance decreasesdrastically as the number of events increases.This paper extends and complements substantiallythe proposal described in [5]. Instead of takingsnapshots at the (global) database granularity, itconsiders snapshots at the region granularity (leaf snapshots). These regions correspond to thespace partitions derived from the R-tree structureassociated with a global snapshot. The maincontributions of this work are:i) It presents a new spatio-temporal access methodbased on snapshots and events. This newaccess method considers snapshots with regiongranularity. These regions are modified by theuse of global snapshots along time.ii) It presents algorithms not only for time-slice,time-interval, but also for event queries.iii) It experimentally compares the proposed datastructure against MVR-tree [15, 16], MV3R-tree[15], and the preliminary proposal SEST-Indexpublished in [5] for the different times of queries.To the best of our knowledge, MVR-tree andits improved varient MV3R-tree are structuresthat outperform previous spatio-temporal accessmethods in terms of time and space requirementsfor  time-slice   and  time-interval   queries. Resultsindicate that our spatio-temporal access methodhas better performance than SEST-Index andcompetes closely, or even overcomes, MVR-tree,including its improved variant .The organization of the paper is as follows. Section2 reviews current spatio-temporal access methods forapplications that handle discrete changes. Section 3describes the proposed access method in terms of itsdata structure and operations. Section 4 describesand evaluates a cost model for LES-tree. Section 5gives experimental evaluations with respect to SEST-Index and MVR-tree. Conclusions and future workare given in Section 6. 2 Spatio-temporal access meth-ods This section describes the main spatio-temporalaccess methods available for applications of category(b) (see Section 1) that have been designed toanswer  time-slice   and  time-interval   queries. Wefocus on the MVR-tree/MV3R-tree and SEST-Indexstructures, against which we compare the newproposed structure. A classification of the existingspatio-temporal access methods is the following: (a)Methods that treat time as another dimension. (b)Methods that incorporate the temporal informationin the nodes of the structure without consideringtime as another dimension. (c) Methods basedon overlapping structures. (d) Methods based onmultiversioning of the structure. (e) Methods basedon snapshots and events.The 3D R-tree [21] considers time as another axisalong with the spatial coordinates. In a three-dimensional space, two line segments (( x i ,y i ,t i ) ,, ( x i ,y i ,t j )) and (( x j ,y j ,t j ) , ( x j ,y j ,t k )) model anobject that initially remains at ( x i ,y i ) during thetime interval [ t i ,t j ), and then it locates at ( x j ,y j )during the time interval [ t j ,t k ). Such line segmentscan be indexed by a 3D R-tree. This idea works wellif all the final limits of the time intervals are knownin advance. The 3D R-tree structure is efficient inspace and in processing  time-interval   queries. It is,however, inefficient for processing  time-slice   queries[16].RT-tree [24] is a structure where the temporalinformation is kept in the nodes of the R-tree.This is an extension to the data content of a3  traditional R-tree. In this type of structure, thetemporal information plays a secondary role becausethe search is guided by the spatial information. Thus,queries with temporal conditions cannot be efficientlyprocessed [10].HR-tree [11, 10] and MR-tree [24] are based onthe concept of overlapping. The basic idea is that,given two trees, the most recent tree corresponds toan evolution of the older tree, and subtrees can beshared between both trees. The major advantage of the HR-tree is its efficiency in processing  time-slice  queries. Its major disadvantage is the excessive spacethat it requires to store the structure. For example,if only one object of each leaf node moves at instant t i , the tree is completely duplicated at instant  t i +1 .MVR-tree [15, 14, 16] is a structure based onhandling multiple versions. It is an extension of MVB-tree [1], where the time-varying attribute isspatial. Similar to the MVB-tree, each entry in theMVR-tree is of the form   S,t s ,t e ,pointer  , where S   corresponds to a MBR. An entry is alive attime instant  t  if   t s  ≤  t < t e  and  dead   otherwise.MVR-tree imposes constraints on the number of entries stored in its nodes. A constraint ensuresthat there exist either zero or at least  b  ·  p version alive entries in any non-leaf node at a time instant t , where  p version  is a parameter of the tree and  b is the capacity of a node. This condition groupsalive entries at time instants for processing  time-slice   queries. Other constraints (namely, strongversion overflow and strong version underflow) ensurea good space usage in the algorithms for insertion anddeletion [15, 14, 16]. Like the MVB-tree, an MVR-tree has multiple R-trees (logical trees) that organizethe spatial information for non-overlapping temporalwindows. This structure outperforms the HR-tree inspace and time when processing short  time-interval  queries. A modification of MVR-tree called MV3R-tree [15] improves the performance of MVR-tree forlong  time-interval   queries by adding an auxiliary 3DR-tree for processing these queries. With the purposeof maintaining the storage within reasonable limits,both indices must share the same leaf pages, whichmakes the insertion algorithm rather complex.A disadvantage of the MVR-tree is the insertionof artificial entries at the leaf nodes as it does notguarantee that the real lifespan of an object is storedin only one node. For example, if an object  O 1 was at position  S  1  in a time interval [1 , 20), theinsertion algorithm of MVR-tree may create twoentries   S  1 , 1 , 8   and   S  1 , 8 , 20   in two different nodes,making it more difficult to obtain the exact instantwhen the object  O 1  arrives or leaves the position  S  1 .SEST-Index [5] is a structure that maintainssnapshots for some time instants and stores theevents that occur between consecutive snapshots.One of the main disadvantages of SEST-Index is therapid growth of its size (storage use) as the numberof changes increases. This disadvantage is explainedbecause each snapshot duplicates all the objects,including those that have undergone no modificationbetween consecutive snapshots. A solution to thisproblem was proposed in [5], but it has two importantlimitations: (i) the objects must be points and (ii)the region where the changes occur must be fixed.The proposal in this paper follows some of the ideasof SEST-Index, but it overcomes the two previouslimitations and achieves good space usage, withoutcompromising time efficiency. 3 LES-tree: A Spatio-temporalAccess Method Based onSnapshots and Events Similar to SEST-Index [5], LES-tree maintainssnapshots for some time instants and stores theevents that occur between consecutive snapshots.One of the main disadvantages of SEST-Index isthe rapid growth of its size (storage use) as thenumber of changes increases. This disadvantageis explained because each snapshot duplicates allthe objects, including those that have undergoneno modification between consecutive snapshots. Asolution to this problem was proposed in [5], butit has two important limitations: (i) the objectsmust be points and (ii) the region where the changesoccur must be fixed. LES-tree overcomes these twolimitations and achieves good space usage, withoutcompromising time efficiency.LES-tree considers two types of snapshots, which4  handle different space granularity. The first typeof snapshots (global snapshot) corresponds to an R-tree (spatial indexing structure) including all objectsexisting at a particular time instant. The second typeof snapshots (leaf snapshot) forms part of the  logs  assigned to leaves of the global snapshots. These  logs  store a sequence of events and several leaf snapshotsalong time. When the number of events stored in a log   after a last leaf snapshot exceeds a threshold, anew leaf snapshot is created and stored in the  log  .Figure 1 shows the general schema of the LES-treewith the two types of snapshots. The objective of global snapshots is to maintain the performance of the query processing along time, since the insertionsof events that produce the growing areas of leavesprovoke deterioration in the selectivity of the leaf snapshots.We refer as LES-tree l  to the structure composedof one global snapshot and its corresponding logs  . Consequently, a LES-tree corresponds to asequence of LES-tree l  generated from consecutivenon-overlapping time intervals of different lengths.These lengths of time intervals are determinedautomatically by LES-tree and can be adjusted toimprove the performance of the indexing structure.In this section we will describe in detail the datastructure, the dynamic of the global snapshots, andthe update and search algorithms. 3.1 LES-tree structure The structure of LES-tree considers an array  S   (seeFigure 1) with an entry of type   t s ,pLES  - tree l   foreach global snapshot, where  t s  corresponds to thetime instant in which the R-tree was created and  pLES  - tree l  is the reference to the correspondingLES-tree l .LES-tree l  (see Figure 2), consists of an R-tree [6]and a set of   logs   assigned to the regions of leavesin the R-tree. Here a  log   (leaf) is a structure thatstores leaf snapshots and events. In this structure,the movement of an object is not inserted directly inthe R-tree, producing the classical node splitting of the R-tree, but they are inserted as events in a logof an R-tree’s leaf. Figure 2 presents a region  A  andits corresponding  log   with three objects at instant t 0 . At instant  t 1 , region  A  has grown to include afourth object, what is reflected on the correspondingleaf snapshot. The changes that occurred between  t 0 and  t 1  are stored as events in the  log   associated with A .In LES-tree l , areas of both the regions to whichthe  logs   are assigned and the MBRs of non-leaf nodesin the R-tree are always growing along time. Due tothis situation, the overlapping areas of non-leaf nodesin the R-tree increase and the efficiency of queryprocessing degrades (see Figure 2), a problem thatSection 3.2 addresses.The LES-tree l  considers an R-tree [6], where theleaves are  logs   and these  logs   are linked lists of blocks.A  log   has two types of entries: event or change entriesand leaf snapshot entries (the first entry is alwaysa leaf snapshot). The entries in the  log   follow atemporal order.An event entry is a tuple with the structure  t,Geometry,Oid,Op  , where  t  corresponds to thetime when the change occurred, and  Oid  is the objectidentifier.  Geometry  corresponds to the spatialcomponent of the object, which depends on thegeometry type (i.e., point, line, polygon or MBR)and dimension (2D or 3D). Finally,  Op  indicates thetype of operation (i.e., type of event or change).This work considers only two types of events: move in  (i.e, an object moves to a new location) and move out  (i.e., an object leaves its current location).Thus an object creation is modeled as a  move in ,an object deletion as a  move out , and an objectmovement as a  move out  followed by a  move in .The structure that stores  move out  entries could onlyinclude attributes  t  and  Oid . This decreases thestorage cost of the structure, at the price of increasingthe time cost for processing queries on events (butnot the classical  time-slice   and  time-interval   queries).Later, in Section 5, we will analyze how much space(and also time) can be saved if the structure onlysupports  time-slice   and  time-interval   queries.The second type of entry, a leaf snapshot entry,stores the snapshot of a leaf node, with one entryper each object alive at the time instant when thesnapshot was created.Like SEST-Index [5], each LES-tree l  also uses aparameter  d , equal for all  logs   in the structure,5
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!