{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,3,11]],"date-time":"2023-03-11T19:33:33Z","timestamp":1678563213091},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,4,30]],"date-time":"2020-04-30T00:00:00Z","timestamp":1588204800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,4,30]],"date-time":"2020-04-30T00:00:00Z","timestamp":1588204800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Supercomput"],"published-print":{"date-parts":[[2021,1]]},"DOI":"10.1007\/s11227-020-03299-7","type":"journal-article","created":{"date-parts":[[2020,4,30]],"date-time":"2020-04-30T16:45:56Z","timestamp":1588265156000},"page":"936-972","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Windowing queries using Minkowski sum and their extension to MapReduce"],"prefix":"10.1007","volume":"77","author":[{"given":"Sepideh","family":"Aghamolaei","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vahideh","family":"Keikha","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohammad","family":"Ghodsi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ali","family":"Mohades","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,4,30]]},"reference":[{"issue":"4","key":"3299_CR1","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1145\/1008731.1008736","volume":"51","author":"PK Agarwal","year":"2004","unstructured":"Agarwal PK, Har-Peled S, Varadarajan KR (2004) Approximating extent measures of points. J ACM 51(4):606\u2013635","journal-title":"J ACM"},{"issue":"2","key":"3299_CR2","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1145\/1240233.1240240","volume":"3","author":"S Arya","year":"2007","unstructured":"Arya S, Malamatos T, Mount DM (2007) A simple entropy-based algorithm for planar point location. ACM Trans Algorithms 3(2):17","journal-title":"ACM Trans Algorithms"},{"issue":"4","key":"3299_CR3","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0925-7721(96)00011-9","volume":"8","author":"G Barequet","year":"1997","unstructured":"Barequet G, Dickerson M, Pau P (1997) Translating a convex polygon to contain a maximum number of points. Comput Geom 8(4):167\u2013179","journal-title":"Comput Geom"},{"key":"3299_CR4","doi-asserted-by":"crossref","unstructured":"Beame P, Koutris P, Suciu D (2013) Communication steps for parallel query processing. In: Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, ACM, pp 273\u2013284","DOI":"10.1145\/2463664.2465224"},{"issue":"01","key":"3299_CR5","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1142\/S0218195910003189","volume":"20","author":"M Benkert","year":"2010","unstructured":"Benkert M, Djordjevic B, Gudmundsson J, Wolle T (2010) Finding popular places. Int J Comput Geom Appl 20(01):19\u201342","journal-title":"Int J Comput Geom Appl"},{"key":"3299_CR6","volume-title":"Euclidean geometry and convexity","author":"RV Benson","year":"1966","unstructured":"Benson RV (1966) Euclidean geometry and convexity. McGraw-Hill, New York"},{"key":"3299_CR7","doi-asserted-by":"crossref","unstructured":"Bringmann K (2014) Why walking the dog takes time: Fr\u00e9chet distance has no strongly subquadratic algorithms unless SETH fails. In: 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, IEEE, pp 661\u2013670","DOI":"10.1109\/FOCS.2014.76"},{"issue":"1\u20132","key":"3299_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02238188","volume":"36","author":"BM Chazelle","year":"1986","unstructured":"Chazelle BM, Lee DT (1986) On a circle placement problem. Computing 36(1\u20132):1\u201316","journal-title":"Computing"},{"key":"3299_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-662-03427-9","volume-title":"Computational geometry","author":"M De Berg","year":"1997","unstructured":"De Berg M, Van Kreveld M, Overmars M, Schwarzkopf O (1997) Computational geometry. Springer, Berlin, pp 1\u201317"},{"issue":"1","key":"3299_CR10","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1007\/s00454-012-9402-z","volume":"48","author":"A Driemel","year":"2012","unstructured":"Driemel A, Har-Peled S, Wenk C (2012) Approximating the Fr\u00e9chet distance for realistic curves in near linear time. Discrete Comput Geom 48(1):94\u2013127","journal-title":"Discrete Comput Geom"},{"issue":"2","key":"3299_CR11","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/0215023","volume":"15","author":"H Edelsbrunner","year":"1986","unstructured":"Edelsbrunner H, Guibas LJ, Stolfi J (1986) Optimal point location in a monotone subdivision. SIAM J Comput 15(2):317\u2013340","journal-title":"SIAM J Comput"},{"issue":"2","key":"3299_CR12","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/0304-3975(92)90319-B","volume":"92","author":"H Edelsbrunner","year":"1992","unstructured":"Edelsbrunner H, Guibas L, Pach J, Pollack R, Seidel R, Sharir M (1992) Arrangements of curves in the plane\u2014topology, combinatorics, and algorithms. Theor Comput Sci 92(2):319\u2013336","journal-title":"Theor Comput Sci"},{"key":"3299_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17283-0","volume-title":"CGAL arrangements and their applications: a step-by-step guide","author":"E Fogel","year":"2012","unstructured":"Fogel E, Halperin D, Wein R (2012) CGAL arrangements and their applications: a step-by-step guide, vol 7. Springer, Berlin"},{"issue":"2","key":"3299_CR14","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/s10115-013-0639-5","volume":"40","author":"M Fort","year":"2014","unstructured":"Fort M, Sellar\u00e8s JA, Valladares N (2014) Computing and visualizing popular places. Knowl Inf Syst 40(2):411\u2013437","journal-title":"Knowl Inf Syst"},{"issue":"6","key":"3299_CR15","doi-asserted-by":"publisher","first-page":"2091","DOI":"10.1137\/S1064827594275339","volume":"19","author":"JR Gilbert","year":"1998","unstructured":"Gilbert JR, Miller GL, Teng SH (1998) Geometric mesh partitioning: implementation and experiments. SIAM J Sci Comput 19(6):2091\u20132110","journal-title":"SIAM J Sci Comput"},{"issue":"4","key":"3299_CR16","doi-asserted-by":"publisher","first-page":"737","DOI":"10.1137\/0220047","volume":"20","author":"MT Goodrich","year":"1991","unstructured":"Goodrich MT (1991) Intersecting line segments in parallel with an output-sensitive number of processors. SIAM J Comput 20(4):737\u2013755","journal-title":"SIAM J Comput"},{"issue":"4","key":"3299_CR17","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/BF02189329","volume":"9","author":"MT Goodrich","year":"1993","unstructured":"Goodrich MT (1993) Constructing arrangements optimally in parallel. Discrete Comput Geom 9(4):371\u2013385","journal-title":"Discrete Comput Geom"},{"key":"3299_CR18","doi-asserted-by":"crossref","unstructured":"Goodrich MT, Sitchinava N, Zhang Q (2011) Sorting, searching, and simulation in the MapReduce framework. arXiv:11011902","DOI":"10.1007\/978-3-642-25591-5_39"},{"key":"3299_CR19","volume-title":"Efficient point location in general planar subdivisions using landmarks","author":"I Haran","year":"2006","unstructured":"Haran I (2006) Efficient point location in general planar subdivisions using landmarks. Tel Aviv University, Tel Aviv"},{"key":"3299_CR20","doi-asserted-by":"crossref","unstructured":"Karloff H, Suri S, Vassilvitskii S (2010) A model of computation for MapReduce. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, pp 938\u2013948","DOI":"10.1137\/1.9781611973075.76"},{"issue":"04","key":"3299_CR21","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1142\/S0218195995000258","volume":"5","author":"A Kaul","year":"1995","unstructured":"Kaul A, Farouki RT (1995) Computing Minkowski sums of plane curves. Int J Comput Geom Appl 5(04):413\u2013432","journal-title":"Int J Comput Geom Appl"},{"issue":"1","key":"3299_CR22","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/BF02187683","volume":"1","author":"K Kedem","year":"1986","unstructured":"Kedem K, Livne R, Pach J, Sharir M (1986) On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles. Discrete Comput Geom 1(1):59\u201371","journal-title":"Discrete Comput Geom"},{"issue":"6","key":"3299_CR23","doi-asserted-by":"publisher","first-page":"639","DOI":"10.1080\/13658810500105572","volume":"19","author":"P Laube","year":"2005","unstructured":"Laube P, Imfeld S, Weibel R (2005) Discovering relative motion patterns in groups of moving point objects. Int J Geogr Inf Sci 19(6):639\u2013668","journal-title":"Int J Geogr Inf Sci"},{"key":"3299_CR24","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/3-540-26772-7_16","volume-title":"Developments in spatial data handling","author":"P Laube","year":"2005","unstructured":"Laube P, van Kreveld M, Imfeld S (2005) Finding REMO\u2014detecting relative motion patterns in geospatial lifelines. Developments in spatial data handling. Springer, Berlin, pp 201\u2013215"},{"key":"3299_CR25","volume-title":"Introduction to parallel algorithms and architectures: arrays$$\\cdot $$ trees$$\\cdot $$ hypercubes","author":"FT Leighton","year":"2014","unstructured":"Leighton FT (2014) Introduction to parallel algorithms and architectures: arrays$$\\cdot$$ trees$$\\cdot$$ hypercubes. Elsevier, Amsterdam"},{"issue":"2","key":"3299_CR26","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/s00454-005-1206-y","volume":"35","author":"E Oks","year":"2006","unstructured":"Oks E, Sharir M (2006) Minkowski sums of monotone and general simple polygons. Discrete Comput Geom 35(2):223\u2013240","journal-title":"Discrete Comput Geom"},{"issue":"6","key":"3299_CR27","doi-asserted-by":"publisher","first-page":"1034","DOI":"10.1137\/0220065","volume":"20","author":"MH Overmars","year":"1991","unstructured":"Overmars MH, Yap CK (1991) New upper bounds in Klee\u2019s measure problem. SIAM J Comput 20(6):1034\u20131045","journal-title":"SIAM J Comput"},{"issue":"2","key":"3299_CR28","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/BF02187902","volume":"3","author":"R Pollack","year":"1988","unstructured":"Pollack R, Sharir M, Sifrony S (1988) Separating two simple polygons by a sequence of translations. Discrete Comput Geom 3(2):123\u2013136","journal-title":"Discrete Comput Geom"},{"issue":"7","key":"3299_CR29","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1145\/6138.6151","volume":"29","author":"N Sarnak","year":"1986","unstructured":"Sarnak N, Tarjan RE (1986) Planar point location using persistent search trees. Commun ACM 29(7):669\u2013679","journal-title":"Commun ACM"},{"key":"3299_CR30","volume-title":"Theory","author":"G Shakhnarovich","year":"2006","unstructured":"Shakhnarovich G, Darrell T, Indyk P (2006) Theory. The MIT Press, Cambridge"},{"key":"3299_CR31","doi-asserted-by":"crossref","unstructured":"Sharir M (1987) Efficient algorithms for planning purely translational collision-free motion in two and three dimensions. In: Proceedings. 1987 IEEE International Conference on Robotics and Automation, Citeseer, vol\u00a04, pp 1326\u20131331","DOI":"10.1109\/ROBOT.1987.1087897"},{"key":"3299_CR32","volume-title":"Handbook of discrete and computational geometry (Chapter 28)","author":"CD Toth","year":"2017","unstructured":"Toth CD, O\u2019Rourke J, Goodman JE (2017) Handbook of discrete and computational geometry (Chapter 28). Chapman and Hall\/CRC, Boca Raton"},{"issue":"8","key":"3299_CR33","doi-asserted-by":"publisher","first-page":"1974","DOI":"10.1109\/TKDE.2013.160","volume":"26","author":"K Zheng","year":"2013","unstructured":"Zheng K, Zheng Y, Yuan NJ, Shang S, Zhou X (2013) Online discovery of gathering patterns over trajectories. IEEE Trans Knowl Data Eng 26(8):1974\u20131988","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"3299_CR34","doi-asserted-by":"crossref","unstructured":"Zheng Y, Li Q, Chen Y, Xie X, Ma WY (2008) Understanding mobility based on GPS data. In: Proceedings of the 10th International Conference on Ubiquitous Computing, pp 312\u2013321","DOI":"10.1145\/1409635.1409677"},{"key":"3299_CR35","doi-asserted-by":"crossref","unstructured":"Zheng Y, Zhang L, Xie X, Ma WY (2009) Mining interesting locations and travel sequences from GPS trajectories. In: Proceedings of the 18th International Conference on World Wide Web, pp 791\u2013800","DOI":"10.1145\/1526709.1526816"},{"issue":"2","key":"3299_CR36","first-page":"32","volume":"33","author":"Y Zheng","year":"2010","unstructured":"Zheng Y, Xie X, Ma WY et al (2010) Geolife: a collaborative social networking service among user, location and trajectory. IEEE Data Eng Bull 33(2):32\u201339","journal-title":"IEEE Data Eng Bull"}],"container-title":["The Journal of Supercomputing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-020-03299-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11227-020-03299-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-020-03299-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,29]],"date-time":"2021-04-29T23:25:10Z","timestamp":1619738710000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11227-020-03299-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,30]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["3299"],"URL":"https:\/\/doi.org\/10.1007\/s11227-020-03299-7","relation":{},"ISSN":["0920-8542","1573-0484"],"issn-type":[{"value":"0920-8542","type":"print"},{"value":"1573-0484","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,4,30]]},"assertion":[{"value":"30 April 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}