{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,9]],"date-time":"2025-07-09T22:59:54Z","timestamp":1752101994376,"version":"3.37.3"},"reference-count":55,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2019,1,16]],"date-time":"2019-01-16T00:00:00Z","timestamp":1547596800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,1,16]],"date-time":"2019-01-16T00:00:00Z","timestamp":1547596800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1525953","CNS-1512877"],"award-info":[{"award-number":["IIS-1525953","CNS-1512877"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1512877"],"award-info":[{"award-number":["CNS-1512877"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2019,8]]},"DOI":"10.1007\/s00778-018-0534-5","type":"journal-article","created":{"date-parts":[[2019,1,16]],"date-time":"2019-01-16T09:09:06Z","timestamp":1547629746000},"page":"523-548","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Scalable computational geometry in MapReduce"],"prefix":"10.1007","volume":"28","author":[{"given":"Yuan","family":"Li","sequence":"first","affiliation":[]},{"given":"Ahmed","family":"Eldawy","sequence":"additional","affiliation":[]},{"given":"Jie","family":"Xue","sequence":"additional","affiliation":[]},{"given":"Nadezda","family":"Knorozova","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6686-1757","authenticated-orcid":false,"given":"Mohamed F.","family":"Mokbel","sequence":"additional","affiliation":[]},{"given":"Ravi","family":"Janardan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,1,16]]},"reference":[{"key":"534_CR1","doi-asserted-by":"crossref","unstructured":"Aji, A., Wang, F., Vo, H., Lee, R., Liu, Q., Zhang, X., Saltz, J.: Hadoop-GIS: a high performance spatial data warehousing system over MapReduce. In: VLDB (2013)","DOI":"10.14778\/2536222.2536227"},{"key":"534_CR2","doi-asserted-by":"crossref","unstructured":"Akdogan, A., Demiryurek, U., Banaei-Kashani, F., Shahabi, C.: Voronoi-based geospatial query processing with MapReduce. In: CLOUDCOM (2010)","DOI":"10.1109\/CloudCom.2010.92"},{"issue":"5","key":"534_CR3","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/0020-0190(79)90072-3","volume":"9","author":"AM Andrew","year":"1979","unstructured":"Andrew, A.M.: Another efficient algorithm for convex hulls in two dimensions. Inf. Process. Lett. 9(5), 216\u2013219 (1979)","journal-title":"Inf. Process. Lett."},{"key":"534_CR4","unstructured":"Apache. Hadoop. \n                    http:\/\/hadoop.apache.org"},{"issue":"4","key":"534_CR5","doi-asserted-by":"publisher","first-page":"536","DOI":"10.1145\/322092.322095","volume":"25","author":"JL Bentley","year":"1978","unstructured":"Bentley, J.L., Kung, H., Schkolnick, M., Thompson, C.D.: On the average number of maxima in a set of vectors and applications. J. ACM: JACM 25(4), 536\u2013543 (1978)","journal-title":"J. ACM: JACM"},{"key":"534_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"MD Berg","year":"2008","unstructured":"Berg, M.D., Cheong, O., Kreveld, M.V., Overmars, M.: Computational Geometry: Algorithms and Applications. Springer, Berlin (2008)"},{"key":"534_CR7","unstructured":"Borne, K.D., Baum, S.A., Fruchter, A., Long, K.S.: The hubble space telescope data archive. In: Astronomical Data Analysis Software and Systems IV, vol.\u00a077 (1995)"},{"key":"534_CR8","unstructured":"B\u00f6rzs\u00f6nyi, S., Kossmann, D., Stocker, K.: The skyline operator. In: ICDE (2001)"},{"key":"534_CR9","doi-asserted-by":"crossref","unstructured":"Cary, A., Sun, Z., Hristidis, V., Rishe, N.: Experiences on processing spatial data with MapReduce. In: SSDBM, pp. 302\u2013319. New Orleans, Louisiana (2009)","DOI":"10.1007\/978-3-642-02279-1_24"},{"key":"534_CR10","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1007\/s00778-018-0504-y","volume":"27","author":"FM Choudhury","year":"2018","unstructured":"Choudhury, F.M., Culpepper, J.S., Bao, Z., Sellis, T.: Finding the optimal location and keywords in obstructed and unobstructed space. VLDB J. 27, 445\u2013470 (2018)","journal-title":"VLDB J."},{"issue":"2","key":"534_CR11","first-page":"1277","volume":"1","author":"BF Cooper","year":"2008","unstructured":"Cooper, B.F., Ramakrishnan, R., Srivastava, U., Silberstein, A., Bohannon, P., Jacobsen, H.A., Puz, N., Weaver, D., Yerneni, R.: PNUTS: Yahoo!\u2019s hosted data serving platform. PVLDB 1(2), 1277\u20131288 (2008)","journal-title":"PVLDB"},{"key":"534_CR12","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leisorson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2009)"},{"issue":"2","key":"534_CR13","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1002\/rsa.10114","volume":"24","author":"K Dalal","year":"2004","unstructured":"Dalal, K.: Counting the onion. Random Struct. Algorithms 24(2), 155\u2013165 (2004)","journal-title":"Random Struct. Algorithms"},{"key":"534_CR14","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1145\/1327452.1327492","volume":"51","author":"J Dean","year":"2008","unstructured":"Dean, J., Ghemawat, S.: MapReduce: simplified data processing on large clusters. Commun. ACM 51, 107\u2013113 (2008)","journal-title":"Commun. ACM"},{"key":"534_CR15","doi-asserted-by":"crossref","unstructured":"Eldawy, A., Alarabi, L., Mokbel, M.F.: Spatial partitioning techniques in SpatialHadoop. In: PVLDB, pp. 1602\u20131605. Kohala Coast, HI (2015)","DOI":"10.14778\/2824032.2824057"},{"key":"534_CR16","doi-asserted-by":"crossref","unstructured":"Eldawy, A., Li, Y., Mokbel, M.F., Janardan, R.: CG\\_Hadoop: computational geometry in MapReduce. In: SIGSPATIAL, pp. 284\u2013293. Orlando, FL (2013)","DOI":"10.1145\/2525314.2525349"},{"key":"534_CR17","doi-asserted-by":"crossref","unstructured":"Eldawy, A., Mokbel, M.F.: A demonstration of SpatialHadoop: an efficient MapReduce framework for spatial data. In: VLDB (2013)","DOI":"10.14778\/2536274.2536283"},{"key":"534_CR18","doi-asserted-by":"crossref","unstructured":"Eldawy, A., Mokbel, M.F.: SpatialHadoop: a MapReduce framework for spatial data. In: ICDE (2015) (to appear)","DOI":"10.1109\/ICDE.2015.7113382"},{"key":"534_CR19","doi-asserted-by":"crossref","unstructured":"Fox, A., Eichelberger, C., Hughes, J., Lyon, S.: Spatio-temporal indexing in non-relational distributed databases. In: BigData, pp. 291\u2013299. Santa Clara, CA (2013)","DOI":"10.1109\/BigData.2013.6691586"},{"key":"534_CR20","doi-asserted-by":"crossref","unstructured":"Garc\u00eda-Garc\u00eda, F., Corral, A., Iribarne, L., Vassilakopoulos, M., Manolopoulos, Y.: Enhancing SpatialHadoop with closest pair queries. In: East European Conference on Advances in Databases and Information Systems, pp. 212\u2013225. Springer, Berlin (2016)","DOI":"10.1007\/978-3-319-44039-2_15"},{"key":"534_CR21","doi-asserted-by":"crossref","unstructured":"Ghoting, A., Krishnamurthy, R., Pednault, E., Reinwald, B., Sindhwani, V., Tatikonda, S., Tian, Y., Vaithyanathan, S.: SystemML: declarative machine learning on MapReduce. In: ICDE (2011)","DOI":"10.1109\/ICDE.2011.5767930"},{"key":"534_CR22","unstructured":"Giraph. \n                    http:\/\/giraph.apache.org\/"},{"key":"534_CR23","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T., Sitchinava, N., Zhang, Q.: Sorting, searching, and simulation in the MapReduce framework. In: ISAAC (2011)","DOI":"10.1007\/978-3-642-25591-5_39"},{"key":"534_CR24","doi-asserted-by":"crossref","unstructured":"Guibas, L.J., Stolfi, J.: Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. In: STOC, pp. 221\u2013234. Boston, MA (1983)","DOI":"10.1145\/800061.808751"},{"key":"534_CR25","doi-asserted-by":"crossref","unstructured":"Guttman, A.: R-Trees: A dynamic index structure for spatial searching. In: SIGMOD (1984)","DOI":"10.1145\/602259.602266"},{"key":"534_CR26","doi-asserted-by":"crossref","unstructured":"Huai, Y., Chauhan, A., Gates, A., Hagleitner, G., Hanson, E.N., O\u2019Malley, O., Pandey, J., Yuan, Y., Lee, R., Zhang, X.: Major technical advancements in apache hive. In: ACM SIGMOD, pp. 1235\u20131246 (2014)","DOI":"10.1145\/2588555.2595630"},{"key":"534_CR27","doi-asserted-by":"crossref","unstructured":"Isard, M., Budiu, M., Yu, Y., Birrell, A., Fetterly, D.: Dryad: distributed data-parallel programs from sequential building blocks. In: EuroSys (2007)","DOI":"10.1145\/1272996.1273005"},{"key":"534_CR28","unstructured":"Java Topology Suite. \n                    http:\/\/hadoop.apache.org\/"},{"key":"534_CR29","doi-asserted-by":"crossref","unstructured":"K\u00f6hler, H., Yang, J., Zhou, X.: Efficient parallel skyline processing using hyperplane projections. In: ACM SIGMOD, pp. 85\u201396. ACM (2011)","DOI":"10.1145\/1989323.1989333"},{"issue":"2","key":"534_CR30","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1145\/1773912.1773922","volume":"44","author":"A Lakshman","year":"2010","unstructured":"Lakshman, A., Malik, P.: Cassandra: a decentralized structured storage system. Oper. Syst. Rev. 44(2), 35\u201340 (2010)","journal-title":"Oper. Syst. Rev."},{"issue":"12","key":"534_CR31","first-page":"1771","volume":"5","author":"G Lee","year":"2012","unstructured":"Lee, G., Lin, J., Liu, C., Lorek, A., Ryaboy, D.V.: The unified logging infrastructure for data analytics at Twitter. PVLDB 5(12), 1771\u20131780 (2012)","journal-title":"PVLDB"},{"key":"534_CR32","doi-asserted-by":"crossref","unstructured":"Liao, H., Han, J., Fang, J.: Multi-dimensional index on Hadoop distributed file system. In: ICNAS, pp. 240\u2013249 (2010)","DOI":"10.1109\/NAS.2010.44"},{"key":"534_CR33","doi-asserted-by":"crossref","unstructured":"Lu, J., Guting, R.H.: Parallel secondo: boosting database engines with Hadoop. In: ICPADS (2012)","DOI":"10.1109\/ICPADS.2012.119"},{"issue":"14","key":"534_CR34","first-page":"1797","volume":"7","author":"P Lu","year":"2014","unstructured":"Lu, P., Chen, G., Ooi, B.C., Vo, H.T., Wu, S.: ScalaGiST: scalable generalized search trees for MapReduce systems. PVLDB 7(14), 1797\u20131808 (2014)","journal-title":"PVLDB"},{"key":"534_CR35","first-page":"1016","volume":"5","author":"W Lu","year":"2012","unstructured":"Lu, W., Shen, Y., Chen, S., Ooi, B.C.: Efficient processing of k nearest neighbor joins using MapReduce. PVLDB 5, 1016\u20131027 (2012)","journal-title":"PVLDB"},{"key":"534_CR36","doi-asserted-by":"crossref","unstructured":"Ma, Q., Yang, B., Qian, W., Zhou, A.: Query processing of massive trajectory data based on MapReduce. In: CLOUDDB (2009)","DOI":"10.1145\/1651263.1651266"},{"key":"534_CR37","doi-asserted-by":"crossref","unstructured":"Nishimura, S., Das, S., Agrawal, D., Abbadi, A.E.: MD-HBase: A scalable multi-dimensional data infrastructure for location aware services. In: MDM (2011)","DOI":"10.1109\/MDM.2011.41"},{"issue":"2","key":"534_CR38","first-page":"289","volume":"31","author":"S Nishimura","year":"2013","unstructured":"Nishimura, S., Das, S., Agrawal, D., El Abbadi, A.: $$\\cal{MD}$$: design and implementation of an elastic data infrastructure for cloud-scale location services. DAPD 31(2), 289\u2013319 (2013)","journal-title":"DAPD"},{"issue":"1","key":"534_CR39","doi-asserted-by":"publisher","first-page":"1095","DOI":"10.14778\/1453856.1453973","volume":"1","author":"S Nutanong","year":"2008","unstructured":"Nutanong, S., Zhang, R., Tanin, E., Kulik, L.: The v*-diagram: a query-dependent approach to moving knn queries. Proc. VLDB Endow. 1(1), 1095\u20131106 (2008)","journal-title":"Proc. VLDB Endow."},{"key":"534_CR40","doi-asserted-by":"crossref","unstructured":"Oliver, D., Steinberger, D.J.: From geography to medicine: exploring innerspace via spatial and temporal databases. In: SSTD (2011)","DOI":"10.1007\/978-3-642-22922-0_32"},{"key":"534_CR41","unstructured":"O\u2019Malley, O.: Terabyte sort on Apache Hadoop. Yahoo! (2008)"},{"key":"534_CR42","unstructured":"OpenStreetMap. \n                    http:\/\/www.openstreetmap.org\/"},{"issue":"1","key":"534_CR43","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1145\/1061318.1061320","volume":"30","author":"D Papadias","year":"2005","unstructured":"Papadias, D., Tao, Y., Fu, G., Seeger, B.: Progressive skyline computation in database systems. TODS 30(1), 41\u201382 (2005)","journal-title":"TODS"},{"issue":"14","key":"534_CR44","doi-asserted-by":"publisher","first-page":"2002","DOI":"10.14778\/2556549.2556580","volume":"6","author":"Y Park","year":"2013","unstructured":"Park, Y., Min, J., Shim, K.: Parallel computation of skyline and reverse skyline queries using mapreduce. Proc. VLDB Endow. 6(14), 2002\u20132013 (2013)","journal-title":"Proc. VLDB Endow."},{"key":"534_CR45","unstructured":"PostGIS. Spatial and Geographic Objects for PostgreSQL. \n                    http:\/\/postgis.net\/"},{"key":"534_CR46","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"F Preparata","year":"1985","unstructured":"Preparata, F., Shamos, M.I.: Computational Geometry: An Introduction. Springer, Berlin (1985)"},{"issue":"2","key":"534_CR47","first-page":"187","volume":"16","author":"H Samet","year":"1984","unstructured":"Samet, H.: The Quadtree and related hierarchical data structures. ACMCS 16(2), 187\u2013260 (1984)","journal-title":"ACMCS"},{"issue":"4","key":"534_CR48","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/s00607-013-0382-5","volume":"97","author":"Y Sun","year":"2015","unstructured":"Sun, Y., Qi, J., Zhang, R., Chen, Y., Du, X.: Mapreduce based location selection algorithm for utility maximization with capacity constraints. Computing 97(4), 403\u2013423 (2015)","journal-title":"Computing"},{"key":"534_CR49","doi-asserted-by":"crossref","unstructured":"Tauheed, F., Biveinis, L., Heinis, T., Sch\u00fcrmann, F., Markram, H., Ailamaki, A.: Accelerating range queries for brain simulations. In: ICDE (2012)","DOI":"10.1109\/ICDE.2012.56"},{"key":"534_CR50","doi-asserted-by":"crossref","unstructured":"Wang, K., Han, J., Tu, B., Dai, J., Zhou, W., Song, X.: Accelerating spatial data processing with MapReduce. In: ICPADS, pp. 229\u2013236. Shanghai, China (2010)","DOI":"10.1109\/ICPADS.2010.76"},{"issue":"11","key":"534_CR51","doi-asserted-by":"publisher","first-page":"1543","DOI":"10.14778\/2350229.2350268","volume":"5","author":"K Wang","year":"2012","unstructured":"Wang, K., Huai, Y., Lee, R., Wang, F., Zhang, X., Saltz, J.: Accelerating pathology image data cross-comparison on cpu-gpu hybrid systems. Proc. VLDB Endow. 5(11), 1543\u20131554 (2012)","journal-title":"Proc. VLDB Endow."},{"key":"534_CR52","doi-asserted-by":"crossref","unstructured":"Whitman, R.T., Park, M.B., Ambrose, S.A., Hoel, E.G.: Spatial indexing and analytics on Hadoop. In: SIGSPATIAL. Dallas, TX (2014)","DOI":"10.1145\/2666310.2666387"},{"key":"534_CR53","doi-asserted-by":"crossref","unstructured":"Zhang, C., Li, F., Jestes, J.: Efficient parallel kNN joins for large data in MapReduce. In: EDBT (2012)","DOI":"10.1145\/2247596.2247602"},{"issue":"99","key":"534_CR54","first-page":"1","volume":"PP","author":"J Zhang","year":"2015","unstructured":"Zhang, J., Jiang, X., Ku, W.S., Qin, X.: Efficient parallel skyline evaluation using MapReduce. TPDS PP(99), 1\u201314 (2015)","journal-title":"TPDS"},{"key":"534_CR55","doi-asserted-by":"crossref","unstructured":"Zhang, S., Han, J., Liu, Z., Wang, K., Feng, S.: Spatial queries evaluation with MapReduce. In: GCC (2009)","DOI":"10.1109\/GCC.2009.16"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-018-0534-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00778-018-0534-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-018-0534-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,16]],"date-time":"2020-05-16T15:36:02Z","timestamp":1589643362000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00778-018-0534-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,16]]},"references-count":55,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,8]]}},"alternative-id":["534"],"URL":"https:\/\/doi.org\/10.1007\/s00778-018-0534-5","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"type":"print","value":"1066-8888"},{"type":"electronic","value":"0949-877X"}],"subject":[],"published":{"date-parts":[[2019,1,16]]},"assertion":[{"value":"12 February 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 August 2018","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 December 2018","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 January 2019","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}