Skip to main content
Erschienen in: International Journal of Data Science and Analytics 2/2023

29.01.2022 | Regular Paper

Sampling and sparsification for approximating the packedness of trajectories and detecting gatherings

verfasst von: Sepideh Aghamolaei, Vahideh Keikha, Mohammad Ghodsi, Ali Mohades

Erschienen in: International Journal of Data Science and Analytics | Ausgabe 2/2023

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Packedness is a measure defined for curves as the ratio of maximum curve length inside any disk divided by its radius. Sparsification allows us to reduce the number of candidate disks for maximum packedness to a polynomial amount in terms of the number of vertices of the polygonal curve. This gives an exact algorithm for computing packedness. We prove that using a fat shape, such as a square, instead of a disk gives a constant factor approximation for packedness. Further sparsification using well-separated pair decomposition improves the time complexity at the cost of losing some accuracy. By adjusting the ratio of the separation factor and the size of the query, we improve the approximation factor of the existing algorithm for packedness using square queries. Our experiments show that uniform sampling works well for finding the average packedness of trajectories with almost constant speed. The empirical results confirm that the sparsification method approximates the maximum packedness for arbitrary polygonal curves. In big data models such as massively parallel computations, both sampling and sparsification are efficient and take a constant number of rounds. Most existing algorithms use line-sweeping which is sequential in nature. Also, we design two data-structures for computing the length of the curve inside a query shape: an exact data-structure for disks called hierarchical aggregated queries and an approximate data-structure for a given set of square queries. Using our modified segment tree, we achieve a near-linear time approximation algorithm.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

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!

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!

Literatur
1.
Zurück zum Zitat GPS Trajectories. UCI Machine Learning Repository (2016) GPS Trajectories. UCI Machine Learning Repository (2016)
2.
Zurück zum Zitat Afshar, R., Goodrich, M.T., Matias, P., Osegueda, M.C.: Reconstructing biological and digital phylogenetic trees in parallel. In: 28th Annual European Symposium on Algorithms (ESA 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2020) Afshar, R., Goodrich, M.T., Matias, P., Osegueda, M.C.: Reconstructing biological and digital phylogenetic trees in parallel. In: 28th Annual European Symposium on Algorithms (ESA 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2020)
4.
Zurück zum Zitat Agarwal, P.K., Har-Peled, S., Varadarajan, K.R.: Approximating extent measures of points. J. ACM (JACM) 51(4), 606–635 (2004)MathSciNetCrossRefMATH Agarwal, P.K., Har-Peled, S., Varadarajan, K.R.: Approximating extent measures of points. J. ACM (JACM) 51(4), 606–635 (2004)MathSciNetCrossRefMATH
5.
Zurück zum Zitat Agarwal, P.K., Katz, M.J., Sharir, M.: Computing depth orders for fat objects and related problems. Comput. Geom. 5(4), 187–206 (1995)MathSciNetCrossRefMATH Agarwal, P.K., Katz, M.J., Sharir, M.: Computing depth orders for fat objects and related problems. Comput. Geom. 5(4), 187–206 (1995)MathSciNetCrossRefMATH
6.
Zurück zum Zitat Aghamolaei, S., Baharifard, F., Ghodsi, M.: Geometric spanners in the MapReduce model. In International Computing and Combinatorics Conference, pp. 675–687. Springer, Berlin (2018) Aghamolaei, S., Baharifard, F., Ghodsi, M.: Geometric spanners in the MapReduce model. In International Computing and Combinatorics Conference, pp. 675–687. Springer, Berlin (2018)
7.
Zurück zum Zitat Aghamolaei, S., Keikha, V., Ghodsi, M., Mohades, A.: Windowing queries using Minkowski sum and their extension to MapReduce. J. Supercomput. (2020) Aghamolaei, S., Keikha, V., Ghodsi, M., Mohades, A.: Windowing queries using Minkowski sum and their extension to MapReduce. J. Supercomput. (2020)
8.
9.
Zurück zum Zitat Bringmann, K., Künnemann, M.: Improved approximation for Fréchet distance on c-packed curves matching conditional lower bounds. In International Symposium on Algorithms and Computation, pp. 517–528. Springer, Berlin (2015) Bringmann, K., Künnemann, M.: Improved approximation for Fréchet distance on c-packed curves matching conditional lower bounds. In International Symposium on Algorithms and Computation, pp. 517–528. Springer, Berlin (2015)
11.
Zurück zum Zitat Callahan, P.B.: Dealing with higher dimensions: the well-separated pair decomposition and its applications. Ph.D. thesis, Johns Hopkins University (1995) Callahan, P.B.: Dealing with higher dimensions: the well-separated pair decomposition and its applications. Ph.D. thesis, Johns Hopkins University (1995)
12.
Zurück zum Zitat Chen, D., Driemel, A., Guibas, L.J., Nguyen, A., Wenk, C.: Approximate map matching with respect to the Fréchet distance. In 2011 Proceedings of the Thirteenth Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 75–83. SIAM (2011) Chen, D., Driemel, A., Guibas, L.J., Nguyen, A., Wenk, C.: Approximate map matching with respect to the Fréchet distance. In 2011 Proceedings of the Thirteenth Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 75–83. SIAM (2011)
13.
Zurück zum Zitat Cruz, M.O., Macedo, H., Guimaraes, A.: Grouping similar trajectories for carpooling purposes. In 2015 Brazilian Conference on Intelligent Systems (BRACIS), pp. 234–239. IEEE (2015) Cruz, M.O., Macedo, H., Guimaraes, A.: Grouping similar trajectories for carpooling purposes. In 2015 Brazilian Conference on Intelligent Systems (BRACIS), pp. 234–239. IEEE (2015)
14.
Zurück zum Zitat De Berg, M., Van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational geometry. In Computational Geometry, pp. 1–17. Springer, Berlin (1997) De Berg, M., Van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational geometry. In Computational Geometry, pp. 1–17. Springer, Berlin (1997)
15.
Zurück zum Zitat Driemel, A., Har-Peled, S.: Jaywalking your dog: computing the Fréchet distance with shortcuts. SIAM J. Comput. 42(5), 1830–1866 (2013)MathSciNetCrossRefMATH Driemel, A., Har-Peled, S.: Jaywalking your dog: computing the Fréchet distance with shortcuts. SIAM J. Comput. 42(5), 1830–1866 (2013)MathSciNetCrossRefMATH
16.
Zurück zum Zitat Driemel, A., Har-Peled, S., Wenk, C.: Approximating the Fréchet distance for realistic curves in near linear time. Discrete Comput. Geom. 48(1), 94–127 (2012)MathSciNetCrossRefMATH Driemel, A., Har-Peled, S., Wenk, C.: Approximating the Fréchet distance for realistic curves in near linear time. Discrete Comput. Geom. 48(1), 94–127 (2012)MathSciNetCrossRefMATH
17.
Zurück zum Zitat Driemel, A., Krivošija, A.: Probabilistic embeddings of the Fréchet distance. In International Workshop on Approximation and Online Algorithms, pp. 218–237. Springer, Berlin (2018) Driemel, A., Krivošija, A.: Probabilistic embeddings of the Fréchet distance. In International Workshop on Approximation and Online Algorithms, pp. 218–237. Springer, Berlin (2018)
18.
19.
Zurück zum Zitat Goodrich, M.T., Sitchinava, N., Zhang, Q.: Sorting, searching, and simulation in the MapReduce framework. In International Symposium on Algorithms and Computation, pp. 374–383. Springer, Berlin (2011) Goodrich, M.T., Sitchinava, N., Zhang, Q.: Sorting, searching, and simulation in the MapReduce framework. In International Symposium on Algorithms and Computation, pp. 374–383. Springer, Berlin (2011)
20.
Zurück zum Zitat Goodrich, M.T., Sitchinava, N., Zhang, Q., IT-Parken, A.: Sorting, searching, and simulation in the MapReduce framework. arXiv preprint arXiv:1101.1902 (2011) Goodrich, M.T., Sitchinava, N., Zhang, Q., IT-Parken, A.: Sorting, searching, and simulation in the MapReduce framework. arXiv preprint arXiv:​1101.​1902 (2011)
21.
Zurück zum Zitat Gudmundsson, J., van Kreveld, M., Staals, F.: Algorithms for hotspot computation on trajectory data. In Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 134–143 (2013) Gudmundsson, J., van Kreveld, M., Staals, F.: Algorithms for hotspot computation on trajectory data. In Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 134–143 (2013)
22.
Zurück zum Zitat Gudmundsson, J., Sha, Y., Wong, S.: Approximating the packedness of polygonal curves. In Cao, Y., Cheng, S.W., Li, M. (eds.) 31st International Symposium on Algorithms and Computation (ISAAC 2020), Leibniz International Proceedings in Informatics (LIPIcs), vol. 181, pp. 9:1–9:15. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2020). 10.4230/LIPIcs.ISAAC.2020.9. https://drops.dagstuhl.de/opus/volltexte/2020/13353 Gudmundsson, J., Sha, Y., Wong, S.: Approximating the packedness of polygonal curves. In Cao, Y., Cheng, S.W., Li, M. (eds.) 31st International Symposium on Algorithms and Computation (ISAAC 2020), Leibniz International Proceedings in Informatics (LIPIcs), vol. 181, pp. 9:1–9:15. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2020). 10.4230/LIPIcs.ISAAC.2020.9. https://​drops.​dagstuhl.​de/​opus/​volltexte/​2020/​13353
23.
Zurück zum Zitat Gudmundsson, J., Smid, M.: Fast algorithms for approximate Fréchet matching queries in geometric trees. Comput. Geom. 48(6), 479–494 (2015)MathSciNetCrossRefMATH Gudmundsson, J., Smid, M.: Fast algorithms for approximate Fréchet matching queries in geometric trees. Comput. Geom. 48(6), 479–494 (2015)MathSciNetCrossRefMATH
24.
Zurück zum Zitat Har-Peled, S., Raichel, B.: The Fréchet distance revisited and extended. ACM Trans. Algorithms (TALG) 10(1), 1–22 (2014)CrossRefMATH Har-Peled, S., Raichel, B.: The Fréchet distance revisited and extended. ACM Trans. Algorithms (TALG) 10(1), 1–22 (2014)CrossRefMATH
26.
Zurück zum Zitat Leighton, F.T.: Introduction to parallel algorithms and architectures: Arrays \(\cdot \) trees \(\cdot \) hypercubes. Elsevier, Amsterdam (2014) Leighton, F.T.: Introduction to parallel algorithms and architectures: Arrays \(\cdot \) trees \(\cdot \) hypercubes. Elsevier, Amsterdam (2014)
27.
Zurück zum Zitat Narasimhan, G., Smid, M.: Geometric Spanner Networks. Cambridge University Press, Cambridge (2007)CrossRefMATH Narasimhan, G., Smid, M.: Geometric Spanner Networks. Cambridge University Press, Cambridge (2007)CrossRefMATH
28.
Zurück zum Zitat Parhami, B.: Introduction to Parallel Processing: Algorithms and Architectures. Springer Science and Business Media, Berlin (2006) Parhami, B.: Introduction to Parallel Processing: Algorithms and Architectures. Springer Science and Business Media, Berlin (2006)
29.
Zurück zum Zitat Williams, V.V., Williams, R.R.: Subcubic equivalences between path, matrix, and triangle problems. J. ACM (JACM) 65(5), 1–38 (2018)MathSciNetCrossRefMATH Williams, V.V., Williams, R.R.: Subcubic equivalences between path, matrix, and triangle problems. J. ACM (JACM) 65(5), 1–38 (2018)MathSciNetCrossRefMATH
30.
Zurück zum Zitat Zheng, Y., Li, Q., Chen, Y., Xie, X., Ma, W.Y.: Understanding mobility based on gps data. In Proceedings of the 10th International Conference on Ubiquitous Computing, pp. 312–321 (2008) Zheng, Y., Li, Q., Chen, Y., Xie, X., Ma, W.Y.: Understanding mobility based on gps data. In Proceedings of the 10th International Conference on Ubiquitous Computing, pp. 312–321 (2008)
31.
Zurück zum Zitat Zheng, Y., Xie, X., Ma, W.Y., et al.: Geolife: a collaborative social networking service among user, location and trajectory. IEEE Data Eng. Bull. 33(2), 32–39 (2010) Zheng, Y., Xie, X., Ma, W.Y., et al.: Geolife: a collaborative social networking service among user, location and trajectory. IEEE Data Eng. Bull. 33(2), 32–39 (2010)
32.
Zurück zum Zitat Zheng, Y., Zhang, L., Xie, X., Ma, W.Y.: Mining interesting locations and travel sequences from gps trajectories. In Proceedings of the 18th International Conference on World Wide Web, pp. 791–800 (2009) Zheng, Y., Zhang, L., Xie, X., Ma, W.Y.: Mining interesting locations and travel sequences from gps trajectories. In Proceedings of the 18th International Conference on World Wide Web, pp. 791–800 (2009)
Metadaten
Titel
Sampling and sparsification for approximating the packedness of trajectories and detecting gatherings
verfasst von
Sepideh Aghamolaei
Vahideh Keikha
Mohammad Ghodsi
Ali Mohades
Publikationsdatum
29.01.2022
Verlag
Springer International Publishing
Erschienen in
International Journal of Data Science and Analytics / Ausgabe 2/2023
Print ISSN: 2364-415X
Elektronische ISSN: 2364-4168
DOI
https://doi.org/10.1007/s41060-021-00301-0

Weitere Artikel der Ausgabe 2/2023

International Journal of Data Science and Analytics 2/2023 Zur Ausgabe

Premium Partner