This paper proposes the cost evaluation model for the existing TB-tree insertion algorithm called BASEINSERT. Factors that may affect its performance are analyzed in a detailed manner. While we search the latest node, the number of nodes being accessed is very prominent. Given this property, the paper comes up with an improved algorithm, named IMPRINSERT by adding the cache structures of root-latest-node path and right-most path, which reduce the number of nodes being accessed while searching for the latest node and right-most path close to zero. Under the bulk data setting, algorithm that inserts the data segment by segment is fairly inefficient, therefore this paper introduces a new insertion algorithm, called BULKINSERT and its cost evaluation model is proposed as well. Verified by a large number of synthesized datasets, it is proved that the cost models are reliable, both IMPRINSERT and BULKINSERT are effective and demonstrate nearly linear scalability.
GütingR.H. and SchneiderM., Moving objects databases, Morgan Kaufmann publishers, 2005.
2.
JensenC.S.LeuteneggerS.T. and LopezM.A., Indexing the positions of continuously moving objects, ACM SIGMOD International Conference on Management of Data ACM (2000), 331–342.
3.
TaoY.F.PapadiasD. and SunJ., The TPR*-tree: An optimized spatio-temporal access method for predictive queries, International Conference on Very Large Data Bases VLDB Endowment (2003), 790–801.
4.
LiaoW.TangG.F.JingN. et al., Hybrid indexing of moving objects based on velocity distribution, Chinese Journal of Computers30 (2007), 661–671.
5.
PrabhakarS.XiaY.KalashnikovD.V. et al., Query indexing and velocity constrained indexing: Scalable techniques for continuous queries on moving objects, IEEE Transactions on Computers51 (2002), 1124–1140.
6.
ChonH.D.AgrawalD. and AbbadiA.E., Storage and retrieval of moving objects, Mobile Data Management (2001), 173–184.
7.
PatelJ.M.ChenY. and ChakkaV.P., STRIPES: An efficient index for predicted trajectories, ACM SIGMOD International Conference on Management of Data (2004), 635–646.
8.
BeckmannN.KriegelH.P.SchneiderR. et al., The R*-tree: An efficient and robust access method for points and rectangles, ACM Sigmod Record19 (1990), 322–331.
9.
PfoserD.JensenC.S. and TheodoridisY., Novel approaches in the indexing of moving object trajectories, Proceedings of International Conference on Very Large Data Bases (2000), 395–406.
10.
JaeL.E.RyuK.H. and NamK.W., Indexing for efficient managing current and past trajectory of moving object, Advanced Web Technologies and Applications, Springer Berlin Heidelberg (2004), 782–787.
11.
ChakkaV.P.EverspaughA.C. and PatelJ.M., Indexing large trajectory data sets with SETI, Ann Arbor, 2003.
12.
ChaC.I.KimS.W.WonJ.I. et al., Efficient indexing in trajectory databases, International Journal of Database Theory and Application1 (2008), 21–28.
13.
AntoineE.RamamohanaraoK.ShaoJ. et al., Recursive partitioning method for trajectory indexing, Australasian Database Conference DBLP (2010), 37–46.
14.
NiJ. and RavishankarC.V., PA-tree: A parametric indexing scheme for spatio-temporal trajectories, Advances in Spatial and Temporal Databases (2005), 254–272.
15.
ChuS.T.YehC.C. and HuangC.L., A cloud-based trajectory index scheme, 2009 IEEE International Conference on e-Business Engineering, IEEE Computer Society (2009), 602–607.
16.
ZhangX. and YuanZ., The GPS trajectory data research based on the intelligent traffic big data analysis platform, Journal of Computational Methods in Sciences & Engineering17 (2017), 1–8.
17.
LangeR.DürrF. and RothermelK., Scalable processing of trajectory-based queries in space-partitioned moving objects databases, Proceedings of the 16th international conference on Advances in geographic information systems, ACM (2008), 31.
18.
GuttmanA., R-trees: A dynamic index structure for spatial searching, ACM Sigmod Record14 (1984), 47–57.
19.
FrentzosE.GratsiasK.PelekisN. et al., Algorithms for nearest neighbor search on moving object trajectories, Geoinformatica11 (2007), 159–193.
20.
GaoY.J.LiC.ChenG.C. et al., Efficient k-nearest neighbor search algorithms for historical moving object trajectories, Journal of Computer Science and Technology22 (2007), 232–244.
21.
GütingR.H.BehrT. and XuJ., Efficient k-nearest neighbor search on moving object trajectories, The VLDB Journal19 (2010), 687–714.
22.
TrajcevskiG.TamassiaR.DingH. et al., Continuous probabilistic nearest-neighbor queries for uncertain trajectories, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, ACM (2009), 874–885.
23.
DingQ. and BoykinR., A framework for distributed nearest neighbor classification using Hadoop, Journal of Computational Methods in Sciences & Engineering17 (2016), 1–9.
24.
BenetisR.JensenC.S.KarciauskasG. et al., Nearest neighbor and reverse nearest neighbor queries for moving objects, Proceedings of Database Engineering and Applications Symposium, IEEE (2002), 44–53.
25.
CheemaM.A.LinX.WangW. et al., Probabilistic reverse nearest neighbor queries on uncertain data, IEEE Transactions on Knowledge and Data Engineering22 (2010), 550–564.
26.
GuohuiL.YanhongL.JianjunL. et al., Continuous reverse k-nearest neighbor monitoring on moving objects in road networks, Information Systems35 (2010), 860–883.
27.
IshikawaY.IijimaY. and YuJ.X., Spatial range querying for Gaussian-based imprecise query objects, Proceedings of 25th International Conference on Data Engineering, IEEE (2009), 676–687.
28.
ZhengK.TrajcevskiG.ZhouX. et al., Probabilistic range queries for uncertain trajectories on road networks, Proceedings of the 14th International Conference on Extending Database Technology, ACM (2011), 283–294.
29.
ChenL.TangY.LvM. et al., Partition-based range query for uncertain trajectories in road networks, Geo Informatica19 (2015), 61–84.
30.
WangZ.WangD.YaoB. et al., Probabilistic range query over uncertain moving objects in constrained two-dimensional space, IEEE Transactions on Knowledge & Data Engineering27 (2015), 866–879.
31.
PatroumpasK.PapamichalisM. and SellisT., Probabilistic range monitoring of streaming uncertain positions in geosocial networks, Proceedings of the 24th International Conference on Scientific and Statistical Database Management, Springer-Verlag (2012), 20–37.
32.
JiX.B.MiH. and ShaoZ.P., Spatial temporal index-based historic closing event query for moving objects, Advances in Information Sciences & Service Sciences5 (2013), 497–509.
33.
KamelI. and FaloutsosC., On packing R-trees, Proceedings of the Second International Conference on Information and Knowledge Management, ACM (1993), 490–499.
34.
TheodoridisY.StefanakisE. and SellisT., Efficient cost models for spatial queries using R-trees, IEEE Transactions on Knowledge & Data Engineering12 (2000), 19–32.
35.
TheodoridisY.SilvaJ.R.O. and NascimentoM.A., On the generation of spatiotemporal datasets, International Symposium on Advances in Spatial Databases, Springer-Verlag (1999), 47–164.
