Top

Published in:

2018 | OriginalPaper | Chapter

Faster and Smaller Two-Level Index for Network-Based Trajectories

Authors : Rodrigo Rivera, M. Andrea Rodríguez, Diego Seco

Published in: String Processing and Information Retrieval

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Two-level indexes have been widely used to handle trajectories of moving objects that are constrained to a network. The top-level of these indexes handles the spatial dimension, whereas the bottom level handles the temporal dimension. The latter turns out to be an instance of the interval-intersection problem, but it has been tackled by non-specialized spatial indexes. In this work, we propose the use of a compact data structure on the bottom level of these indexes. Our experimental evaluation shows that our approach is both faster and smaller than existing solutions.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Fast and Effective Neural Networks for Translating Natural Language into Denotations

This implementation uses sequential search in each node, which is not optimal in theory, but performs well in practice.

de Almeida, V.T., Güting, R.H.: Indexing the trajectories of moving objects in networks*. GeoInformatica 9(1), 33–60 (2005)CrossRef

Barkan, Y.: RTree, GitHub repository (2011). https://github.com/nushoin/RTree

Belazzougui, D., Cunial, F., Gagie, T., Prezza, N., Raffinot, M.: Composite repetition-aware data structures. In: Cicalese, F., Porat, E., Vaccaro, U. (eds.) CPM 2015. LNCS, vol. 9133, pp. 26–39. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-19929-0_3CrossRef

Belazzougui, D., Cunial, F., Gagie, T., Prezza, N., Raffinot, M.: Flexible indexing of repetitive collections. In: Kari, J., Manea, F., Petre, I. (eds.) CiE 2017. LNCS, vol. 10307, pp. 162–174. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-58741-7_17CrossRef

de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer-Verlag TELOS, Heidelberg (2008). https://doi.org/10.1007/978-3-662-03427-9CrossRefMATH

Brinkhoff, T.: A framework for generating network-based moving objects. GeoInformatica 6(2), 153–180 (2002)CrossRef

Brisaboa, N.R., Fariña, A., Galaktionov, D., Rodríguez, M.A.: Compact trip representation over networks. In: Inenaga, S., Sadakane, K., Sakai, T. (eds.) SPIRE 2016. LNCS, vol. 9954, pp. 240–253. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-46049-9_23CrossRef

Brisaboa, N.R., Gagie, T., Gómez-Brandón, A., Navarro, G., Paramá, J.R.: Efficient compression and indexing of trajectories. In: Fici, G., Sciortino, M., Venturini, R. (eds.) SPIRE 2017. LNCS, vol. 10508, pp. 103–115. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-67428-5_10CrossRef

Brisaboa, N.R., Gómez-Brandón, A., Navarro, G., Paramá, J.R.: GraCT: a grammar based compressed representation of trajectories. In: Inenaga, S., Sadakane, K., Sakai, T. (eds.) SPIRE 2016. LNCS, vol. 9954, pp. 218–230. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-46049-9_21CrossRef

10.

Brisaboa, N.R., Ladra, S., Navarro, G.: k²-trees for compact web graph representation. In: Karlgren, J., Tarhio, J., Hyyrö, H. (eds.) SPIRE 2009. LNCS, vol. 5721, pp. 18–30. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03784-9_3CrossRef

11.

Brisaboa, N.R., Luaces, M.R., Navarro, G., Seco, D.: Space-efficient representations of rectangle datasets supporting orthogonal range querying. Inf. Syst. 38(5), 635–655 (2013)CrossRef

12.

Ding, Z., Yang, B., Güting, R.H., Li, Y.: Network-matched trajectory-based moving-object database: models and applications. IEEE Trans. Intell. Transp. Syst. 16(4), 1918–1928 (2015)CrossRef

13.

Fredman, M.L.: On computing the length of longest increasing subsequences. Discret. Math. 11(1), 29–35 (1975)MathSciNetCrossRef

14.

Frentzos, E.: Indexing objects moving on fixed networks. In: Hadzilacos, T., Manolopoulos, Y., Roddick, J., Theodoridis, Y. (eds.) SSTD 2003. LNCS, vol. 2750, pp. 289–305. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45072-6_17CrossRef

15.

Garrison, E.: Intervaltree, GitHub repository (2011). https://github.com/ekg/intervaltree

16.

Gog, S., Beller, T., Moffat, A., Petri, M.: From theory to practice: plug and play with succinct data structures. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 326–337. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-07959-2_28CrossRef

17.

Guttman, A.: R-Trees: a dynamic index structure for spatial searching. SIGMOD Rec. 14(2), 47–57 (1984)CrossRef

18.

Han, Y., Sun, W., Zheng, B.: Compress: a comprehensive framework of trajectory compression in road networks. ACM Trans. Database Syst. 42(2), 11:1–11:49 (2017)MathSciNetCrossRef

19.

Kellaris, G., Pelekis, N., Theodoridis, Y.: Map-matched trajectory compression. J. Syst. Softw. 86(6), 1566–1579 (2013)CrossRef

20.

Koide, S., Tadokoro, Y., Xiao, C., Ishikawa, Y.: CiNCT: compression and retrieval for massive vehicular trajectories via relative movement labeling. In: ICDE, pp. 1097–1108 (2018)

21.

Kreft, S., Navarro, G.: On compressing and indexing repetitive sequences. Theor. Comput. Sci. 483, 115–133 (2013)MathSciNetCrossRef

22.

Krogh, B., Pelekis, N., Theodoridis, Y., Torp, K.: Path-based queries on trajectory data. In: SIGSPATIAL, pp. 341–350 (2014)

23.

Meratnia, N., de By, R.A.: Spatiotemporal Compression Techniques for Moving Point Objects. In: Bertino, E., Christodoulakis, S., Plexousakis, D., Christophides, V., Koubarakis, M., Böhm, K., Ferrari, E. (eds.) EDBT 2004. LNCS, vol. 2992, pp. 765–782. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24741-8_44CrossRef

24.

Navarro, G., Mäkinen, V.: Compressed full-text indexes. ACM Comput. Surv. 39(1), Article No. 2 (2007). https://dl.acm.org/citation.cfm?id=1216372CrossRef

25.

Okanohara, D., Sadakane, K.: Practical entropy-compressed rank/select dictionary. In: ALENEX, pp. 60–70 (2007). http://dl.acm.org/citation.cfm?id=2791188.2791194CrossRef

26.

Pfoser, D., Jensen, C.S., Theodoridis, Y.: Novel approaches in query processing for moving object trajectories. In: VLDB, pp. 395–406 (2000)

27.

Potamias, M., Patroumpas, K., Sellis, T.: Sampling trajectory streams with spatiotemporal criteria. In: SSDBM, pp. 275–284 (2006)

28.

Sandu Popa, I., Zeitouni, K., Oria, V., Barth, D., Vial, S.: Indexing in-network trajectory flows. VLDB J. 20(5), 643 (2011)CrossRef

29.

Schmid, F., Richter, K.-F., Laube, P.: Semantic trajectory compression. In: Mamoulis, N., Seidl, T., Pedersen, T.B., Torp, K., Assent, I. (eds.) SSTD 2009. LNCS, vol. 5644, pp. 411–416. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02982-0_30CrossRef

30.

Schmidt, J.M.: Interval stabbing problems in small integer ranges. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878, pp. 163–172. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10631-6_18CrossRef

31.

Schmidt, J.M.: Publications by J.M. Schmidt. http://www4.tu-ilmenau.de/combinatorial-optimization/ShowPub.html (2018). Accessed 1 May 2018

32.

Tao, Y., Papadias, D.: MV3R-Tree: a spatio-temporal access method for timestamp and interval queries. In: VLDB, pp. 431–440 (2001)

Title: Faster and Smaller Two-Level Index for Network-Based Trajectories
Authors: Rodrigo Rivera
M. Andrea Rodríguez
Diego Seco
Publisher: Springer International Publishing
Book: String Processing and Information Retrieval
Print ISBN: 978-3-030-00478-1

Electronic ISBN: 978-3-030-00479-8

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-030-00479-8_28

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"