运动轨迹数据在关系数据库中的有效查询
|
摘要
本篇论文着重介绍如何有效处理对于时空数据(Spatio-Temporal Data)的运动轨迹查询。介绍了三种对于多维运动轨迹数据的新型索引结构。EDBS结构通过扫描所有数据获取结果,作为一种最原始的方法成为其他方法的基础。RSTI结构利用B-Tree结构在空间和时间维度上建立索引结构,通过范围查找从而使得查询避免扫描所有的数据。DTI是一种在空间维度上采用Hilbert曲线和网格单元将多维数据转换为一维数据,并使用RI-Tree处理时间区间的索引结构。这三种方法能够很方便在几乎所有的关系数据库中进行实施,论文中也给出了相应的步骤。通过实验,比较了这三种结构对于查询速度的优劣,三种方法中,DTI是最优的方法。并使用DTI与R-Tree索引这一专门处理多维数据的索引结构进行比较,两者的差距并不是十分显著。
This paper focuses on efficiently processing trajectory-based queries for spatio-temporal data. Emphasis of using B-tree as the index method is proposed. Three ways to structure and query data are introduced. EDBS which scan all data set is a naive idea and servers as the baseline. Another idea RSTI utilizes B-tree indices in each dimension to realize the range selection. DTI takes advantage of Hilbert Curve and grid cells methods to transfer the multi-dimensional data to one dimensional data and use RI-Tree in time interval. The performance comparison among the given methods is given through the experiments part, and pick the most efficient structure to compare with R-Tree which is a method special for multi-dimensional method, the gap between them is not significant..
This paper focuses on efficiently processing trajectory-based queries for spatio-temporal data. Emphasis of using B-tree as the index method is proposed. Three ways to structure and query data are introduced. EDBS which scan all data set is a naive idea and servers as the baseline. Another idea RSTI utilizes B-tree indices in each dimension to realize the range selection. DTI takes advantage of Hilbert Curve and grid cells methods to transfer the multi-dimensional data to one dimensional data and use RI-Tree in time interval. The performance comparison among the given methods is given through the experiments part, and pick the most efficient structure to compare with R-Tree which is a method special for multi-dimensional method, the gap between them is not significant..
引文
铩颷1]A.Guttman.R-trees:a dynamic index structure for spatial searching.In Proceedings of the ACM SIGMOD Conference on Management of Data,pages 47-57,1984.
[2]Jignesh M.Patel V.Prasad Chakka,Adam C.Everspaugh.Indexing Large Trajectory Data Sets with SETT,2003.
[3]D.Pfoser,C.S.Jensen,and Y.Theodoridis.Novel Approaches in Query Processing for Moving Object Trajectories.In Proc.of the Intl.Conf.on Very Large Data Bases,VLDB,pages 395-406,Sept.2000.
[4]J.k.Lawder.Calculation of Mappings Betwwen one and n-dimensional Values Using the Hilbert Space-filling Curver.In Technical Report no.JL1/00,August 15,2000
[5]J.K.Lawder and P.J.H.King.Querying Multi-dimensional Data Indexed Using the Hilbert Space-Filling Curve.In SIGMOD Record,Vol.30,No.l,March 2001
[6]Arthur R.Butz.Alternative Algorithm for Hilbert's Space-filling Cureve.IEEE Transactions on Computers,20:424-425,April 1971
[7]Dan Lin,Christian S.Jensen,Beng Chin Ooi and Simonas Saltenis.Efficient Indexing of the Historical,Present,and Future Positions of Moving Objects.MDM 2005 05 Ayia Cyprus
[8]Christian S.Jensen,Dan Lin,Beng Chin Ooi.Query and Update Efficient B+-Tree Based Indexing of Moving Objects
[9]Calin Arens,Jantien Stoter,Peter van Oosterom,Modelling 3D spatial objects in a geo-DBMS using a 3D primitive In 2005 Computers & Geosciences 31
[10]D.Hilbert Ueber stetige Abbidung einer Linie aufein Flachenstuck.Mathematicsche Annalen, 38:459-460,1891
[11]C.Faloutsos and S.Roseman.Fractals for Secondary Key Retrieval.In Proc.PODS,pp. 247-252,1989.
[12]Hans-Peter Kriegel,Marco Potke,Thomas Seidl Managing Intervals Efficiently in Object-Relational Databases In:26th International Conference on Very Large Databases
[13]Oracle Press Oracle Locator Developer Guide 10g B28004-01
[14]Oracle Press Oracle Spatial User's Guide and Reference 10g B14255-03
[15]Dipl.Inform.Volker Markl MISTRAL:Processing Relational Queries using a Multidimensional Access Technique
[16]Frank Ramsak,Volker Markl,Robert Fenk,Martin Zirkel,Klaus Elhardt,Rudolf Bayer Integrating the UB-Tree into a Database System Kernel Proceedings of the 26" International Conference on Very Large Database,Cairo,Egypt,2000
[17]Mohamed F.Mokbel Thanaa M.Ghanem Walid G Aref Spatio-temporal Access Methods
[18]Daniel Mallett,Mario A.Nascimento,Virocia Botea and Joerg Sander RDBMS Support for Efficient Indexing of Historical Spatio-Temporal Point Data
[19]J K Lawder Calculation of Mappings Between One and n-dimensional Values Using the Hilbert Space-filling Curve,Techinical Report no.JLI/00,August 15,3000
[20]Ravi Kanth V Kothuri,Siva Ravada,Daniel Abugov Quadtree and R-tree Indexes in Oracle Spatial:A Comparison using GISData,ACM SIGMOD 2002 June 4-6
[2]Jignesh M.Patel V.Prasad Chakka,Adam C.Everspaugh.Indexing Large Trajectory Data Sets with SETT,2003.
[3]D.Pfoser,C.S.Jensen,and Y.Theodoridis.Novel Approaches in Query Processing for Moving Object Trajectories.In Proc.of the Intl.Conf.on Very Large Data Bases,VLDB,pages 395-406,Sept.2000.
[4]J.k.Lawder.Calculation of Mappings Betwwen one and n-dimensional Values Using the Hilbert Space-filling Curver.In Technical Report no.JL1/00,August 15,2000
[5]J.K.Lawder and P.J.H.King.Querying Multi-dimensional Data Indexed Using the Hilbert Space-Filling Curve.In SIGMOD Record,Vol.30,No.l,March 2001
[6]Arthur R.Butz.Alternative Algorithm for Hilbert's Space-filling Cureve.IEEE Transactions on Computers,20:424-425,April 1971
[7]Dan Lin,Christian S.Jensen,Beng Chin Ooi and Simonas Saltenis.Efficient Indexing of the Historical,Present,and Future Positions of Moving Objects.MDM 2005 05 Ayia Cyprus
[8]Christian S.Jensen,Dan Lin,Beng Chin Ooi.Query and Update Efficient B+-Tree Based Indexing of Moving Objects
[9]Calin Arens,Jantien Stoter,Peter van Oosterom,Modelling 3D spatial objects in a geo-DBMS using a 3D primitive In 2005 Computers & Geosciences 31
[10]D.Hilbert Ueber stetige Abbidung einer Linie aufein Flachenstuck.Mathematicsche Annalen, 38:459-460,1891
[11]C.Faloutsos and S.Roseman.Fractals for Secondary Key Retrieval.In Proc.PODS,pp. 247-252,1989.
[12]Hans-Peter Kriegel,Marco Potke,Thomas Seidl Managing Intervals Efficiently in Object-Relational Databases In:26th International Conference on Very Large Databases
[13]Oracle Press Oracle Locator Developer Guide 10g B28004-01
[14]Oracle Press Oracle Spatial User's Guide and Reference 10g B14255-03
[15]Dipl.Inform.Volker Markl MISTRAL:Processing Relational Queries using a Multidimensional Access Technique
[16]Frank Ramsak,Volker Markl,Robert Fenk,Martin Zirkel,Klaus Elhardt,Rudolf Bayer Integrating the UB-Tree into a Database System Kernel Proceedings of the 26" International Conference on Very Large Database,Cairo,Egypt,2000
[17]Mohamed F.Mokbel Thanaa M.Ghanem Walid G Aref Spatio-temporal Access Methods
[18]Daniel Mallett,Mario A.Nascimento,Virocia Botea and Joerg Sander RDBMS Support for Efficient Indexing of Historical Spatio-Temporal Point Data
[19]J K Lawder Calculation of Mappings Between One and n-dimensional Values Using the Hilbert Space-filling Curve,Techinical Report no.JLI/00,August 15,3000
[20]Ravi Kanth V Kothuri,Siva Ravada,Daniel Abugov Quadtree and R-tree Indexes in Oracle Spatial:A Comparison using GISData,ACM SIGMOD 2002 June 4-6