nach oben

GeoInformatica

Erschienen in:

10.11.2016

Multi-core parallelism for plane sweep algorithms as a foundation for GIS operations

verfasst von: Mark McKenney, Roger Frye, Mathew Dellamano, Kevin Anderson, Jeremy Harris

Erschienen in: GeoInformatica | Ausgabe 1/2017

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

The plane sweep algorithm is a foundational algorithm for many geometric and spatial computations; thus, improvements in the algorithm have far reaching effects in many applications. In this paper, we examine the performance of the serial plane sweep algorithm, and introduce a parallelization technique for the algorithm that is suitable to multi-core computers. The parallelization technique is described in detail and shown to be correct. Finally, experiments are performed using multiple data sets on computers with varying numbers of processing cores. We show that our algorithm achieves significant speedups over the serial plane sweep algorithm using a wide range of input parameters; thus, our algorithm achieves good performance without the need to tune the input parameters for specific input cases.

Vorheriger Artikel Finding dense locations in symbolic indoor tracking data: modeling, indexing, and processing

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Egenhofer MJ, Herring J (1990) Categorizing binary topological relations between regions, lines, and points in geographic databases, Technical report, National Center for Geographic Information and Analysis, University of California, Santa Barbara

Schneider M, Behr T (2006) Topological relationships between complex spatial objects. ACM Trans Database Syst (TODS) 31(1):39–81CrossRef

Shamos M, Hoey D (1976) Geometric intersection problems. In: Foundations of computer science

Bentley J, Ottmann T (1979) Algorithms for reporting and counting geometric intersections. IEEE Trans Comput C-28:643–647CrossRef

Nievergelt J, Preparata FP (1982) Plane-sweep algorithms for intersecting geometric figures. Commun ACM 25:739–747CrossRef

Balaban IJ (1995) An optimal algorithm for finding segments intersections. In: ACM annual symposium on computational geometry, pp 211–219

Chazelle B, Edelsbrunner H (1992) An optimal algorithm for intersecting line segments in the plane. J ACM 39(1):1–54. doi:10.1145/147508.147511

Goodrich MT (1989) Intersecting line segments in parallel with an output-sensitive number of processors. In: ACM symposium on parallel algorithms and architectures, pp 127–137. doi:10.1145/72935.72950

McKenney M Parallel plane sweep source code. https://bitbucket.org/marmcke/parallelplanesweep, accessed: 03/07/2016

10.

McKenney M Parallel plane sweep source code documentation, http://www.cs.siue.edu/marmcke/docs/parallelplanesweep/, accessed: 03/07/2016

11.

Kriegel H-P, Brinkhoff T, Schneider R (1991) Combination of spatial access methods and computational geometry in geographic database systems. In: International symposium on advances in spatial databases, pp 5–21

12.

Arge L, Procopiuc O, Ramaswamy S, Suel T, Vitter JS (1998) Scalable sweeping-based spatial join. In: VLDB ’98: Proceedings of the 24rd international conference on very large data bases. Morgan Kaufmann Publishers Inc., San Francisco, pp 570–581

13.

Goodrich M, Tsay J, Vengroff D, Vitter J (1993) External-memory computational geometry. In: Foundations of computer science, pp 714–723. doi:10.1109/SFCS.1993.366816

14.

Franklin W, Narayanaswaml C, Kankanhalli M, Sun D, Zho M-C, Wu PY (1989) Uniform grids: a technique for intersection detection on serial and parallel machines. In: Automated cartogrophy, pp 100–109

15.

Goodrich M, Ghouse M, Bright J (1990) Generalized sweep methods for parallel computational geometry. In: SPAA ’90: proceedings of the 2nd annual ACM symposium on parallel algorithms and architectures. ACM, New York, pp 280–289. doi:10.1145/97444.97695

16.

McKenney M, McGuire T (2009) A Parallel plane sweep algorithm for multi-core systems. In: ACM SIGSPATIAL international symposium on geographic information systems

17.

McKenney M, De Luna G, Hill S, Lowell L (2011) Geospatial overlay computation on the gpu. In: Proceedings of the 19th ACM SIGSPATIAL international conference on advances in geographic information systems, GIS ’11. ACM, New York, pp 473–476. doi:10.1145/2093973.2094051

18.

Audet S, Albertsson C, Murase M, Asahara A (2013) Robust and efficient polygon overlay on parallel stream processors. In: Proceedings of the 21st ACM SIGSPATIAL international conference on advances in geographic information systems, SIGSPATIAL’13. ACM, New York, pp 304–313. doi:10.1145/2525314.2525352

19.

Orenstein J, Manola F (1988) Probe spatial data modeling and query processing in an image database application. IEEE Trans Softw Eng 14(5):611–629. doi:10.1109/32.6139

20.

Patel JM, DeWitt DJ (1996) Partition based spatial-merge join. SIGMOD Rec 25(2):259–270. doi:10.1145/235968.233338

21.

Samet H (1984) The quadtree and related hierarchical data structures. ACM Comput Surv 16(2):187–260. doi:10.1145/356924.356930

22.

Jacox EH, Samet H Spatial join techniques. ACM Trans Database Syst 32 (1). doi:10.1145/1206049.1206056

23.

Arge L, Procopiuc O, Ramaswamy S, Suel T, Vitter JS (1998) Scalable sweeping-based spatial join. In: Proceedings of the 24rd international conference on very large data bases, VLDB ’98. Morgan Kaufmann Publishers Inc., San Francisco, pp 570–581. http://dl.acm.org/citation.cfm?id=645924.671340

24.

Eldawy A, Li Y, Mokbel M, Janardan R (2013) Cg hadoop: computational geometry in mapreduce. In: ACM SIGSPATIAL international conference on advances in geographic information systems

25.

Eldawy A, Mokbel M (2015) Spatialhadoop: a mapreduce framework for spatial data. In: 2015 IEEE 31st international conference on data engineering (ICDE), pp 1352–1363. doi:10.1109/ICDE.2015.7113382

26.

Lu J, Guting R (2012) Parallel secondo: boosting database engines with hadoop. In: 2012 IEEE 18th international conference on parallel and distributed systems (ICPADS), pp 738–743. doi:10.1109/ICPADS.2012.119

27.

Aji A, Wang F, Vo H, Lee R, Liu Q, Zhang X, Saltz J (2013) Hadoop gis: a high performance spatial data warehousing system over mapreduce. Proc VLDB Endow 6(11):1009–1020. doi:10.14778/2536222.2536227

28.

Cary A, Sun Z, Hristidis V, Rishe N (2009) Experiences on processing spatial data with mapreduce. In: Proceedings of the 21st international conference on scientific and statistical database management, SSDBM, vol 2009. Springer-Verlag, Berlin, Heidelberg, pp 302–319

29.

Zhang S, Han J, Liu Z, Wang K, Feng S (2009) Spatial queries evaluation with mapreduce. In: 8th international conference on grid and cooperative computing, 2009. GCC ’09, pp 287–292. doi:10.1109/GCC.2009.16

30.

Liao H, Han J, Fang J (2010) Multi-dimensional index on hadoop distributed file system. In: 2010 IEEE 5th international conference on networking, architecture and storage (NAS), pp 240–249. doi:10.1109/NAS.2010.44

Titel: Multi-core parallelism for plane sweep algorithms as a foundation for GIS operations
verfasst von: Mark McKenney
Roger Frye
Mathew Dellamano
Kevin Anderson
Jeremy Harris
Publikationsdatum: 10.11.2016
Verlag: Springer US
Erschienen in: GeoInformatica / Ausgabe 1/2017
Print ISSN: 1384-6175
Elektronische ISSN: 1573-7624
DOI: https://doi.org/10.1007/s10707-016-0277-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2017

Finding dense locations in symbolic indoor tracking data: modeling, indexing, and processing

Exploiting location-aware social networks for efficient spatial query processing

Constrained energy-efficient routing in time-aware road networks

Enabling time-dependent uncertain eco-weights for road networks

Discovering historic traffic-tolerant paths in road networks