{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,6,2]],"date-time":"2022-06-02T05:11:05Z","timestamp":1654146665731},"reference-count":34,"publisher":"IGI Global","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012,7,1]]},"abstract":"<p>The efficient processing of spatio-temporal data streams is an area of intense research. However, all methods rely on an unsuitable processor (Govindaraju, 2004), namely a CPU, to evaluate concurrent, continuous spatio-temporal queries over these data streams. This paper presents a performance model of the execution of spatio-temporal queries over the authors\u2019 GEDS framework (Cazalas &amp; Guha, 2010). GEDS is a scalable, Graphics Processing Unit (GPU)-based framework, employing computation sharing and parallel processing paradigms to deliver scalability in the evaluation of continuous, spatio-temporal queries over spatio temporal data streams. Experimental evaluation shows the scalability and efficacy of GEDS in spatio-temporal data streaming environments and demonstrates that, despite the costs associated with memory transfers, the parallel processing power provided by GEDS clearly counters and outweighs any associated costs. To move beyond the analysis of specific algorithms over the GEDS framework, the authors developed an abstract performance model, detailing the relationship of the CPU and the GPU. From this model, they are able to extrapolate a list of attributes common to successful GPU-based applications, thereby providing insight into which algorithms and applications are best suited for the GPU and also providing an estimated theoretical speedup for said GPU-based applications.<\/p>","DOI":"10.4018\/jghpc.2012070104","type":"journal-article","created":{"date-parts":[[2012,8,15]],"date-time":"2012-08-15T20:10:21Z","timestamp":1345061421000},"page":"63-84","source":"Crossref","is-referenced-by-count":0,"title":["Performance Modeling of Spatio-Temporal Algorithms Over GEDS Framework"],"prefix":"10.4018","volume":"4","author":[{"given":"Jonathan","family":"Cazalas","sequence":"first","affiliation":[{"name":"University of Central Florida, USA"}]},{"given":"Ratan K.","family":"Guha","sequence":"additional","affiliation":[{"name":"University of Central Florida, USA"}]}],"member":"2432","reference":[{"issue":"2","key":"jghpc.2012070104-0","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1007\/s00778-003-0095-z","article-title":"Aurora: A new model and architecture for data stream management.","volume":"12","author":"D. J.Abadi","year":"2003","journal-title":"Very Large Data Base Journal"},{"key":"jghpc.2012070104-1","doi-asserted-by":"crossref","unstructured":"Amdahl, G. (1967). Validity of the single processor approach to achieving large scale computing capabilities. In Proceedings of the Spring Joint Computer Conference (pp. 483-485).","DOI":"10.1145\/1465482.1465560"},{"issue":"3","key":"jghpc.2012070104-2","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1145\/603867.603884","article-title":"Continuous queries over data streams.","volume":"30","author":"S.Babu","year":"2001","journal-title":"SIGMOD Record"},{"key":"jghpc.2012070104-3","doi-asserted-by":"crossref","unstructured":"Beckmann, N., Kriegel, H., Schneider, R., & Seeger, B. (1990). The R*-tree: An efficient and robust access method for points and rectangles. In Proceedings of the ACM SIGMOD International Conference on Management of Data (pp. 322-331).","DOI":"10.1145\/93605.98741"},{"key":"jghpc.2012070104-4","unstructured":"Berchtold, S., Keim, D. A., & Kriegel, H. (1996). The X-tree: An index structure for high-dimensional data. In Proceedings of the 22th International Conference on Very Large Data Bases (pp. 28-39)."},{"issue":"7","key":"jghpc.2012070104-5","doi-asserted-by":"crossref","first-page":"931","DOI":"10.1109\/TMC.2006.105","article-title":"Real-time processing of range-monitoring queries in heterogeneous mobile databases.","volume":"5","author":"Y.Cai","year":"2006","journal-title":"IEEE Transactions on Mobile Computing"},{"key":"jghpc.2012070104-6","doi-asserted-by":"crossref","unstructured":"Cazalas, J., & Guha, R. (2010). GEDS: GPU execution of continuous queries on spatio-temporal data streams. In Proceedings of the IEEE\/IFIP 8th International Conference on Embedded and Ubiquitous Computing (pp. 112-119).","DOI":"10.1109\/EUC.2010.26"},{"key":"jghpc.2012070104-7","doi-asserted-by":"crossref","unstructured":"Cazalas, J., & Hua, K. (2009). Leveraging computation sharing and parallel processing in location-based services. In Proceedings of the International Conference on Computational Science and Engineering (pp. 221-228).","DOI":"10.1109\/CSE.2009.437"},{"issue":"2","key":"jghpc.2012070104-8","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1007\/s00778-003-0096-y","article-title":"PSoup: A system for streaming queries over streaming data.","volume":"12","author":"S.Chandrasekaran","year":"2003","journal-title":"Very Large Data Base Journal"},{"issue":"4","key":"jghpc.2012070104-9","doi-asserted-by":"crossref","first-page":"740","DOI":"10.1016\/j.csi.2008.09.016","article-title":"Smart phone for mobile commerce.","volume":"31","author":"Y. F.Chang","year":"2009","journal-title":"Computer Standards & Interfaces"},{"issue":"10","key":"jghpc.2012070104-10","doi-asserted-by":"crossref","first-page":"1384","DOI":"10.1109\/TMC.2006.153","article-title":"MobiEyes: A distributed location monitoring service using moving location queries.","volume":"5","author":"B.Gedik","year":"2006","journal-title":"IEEE Transactions on Mobile Computing"},{"issue":"1","key":"jghpc.2012070104-11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1670243.1670244","article-title":"Supporting views in data stream management systems.","volume":"35","author":"T. M.Ghanem","year":"2010","journal-title":"ACM Transactions on Database Systems"},{"issue":"1","key":"jghpc.2012070104-12","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1109\/TKDE.2007.250585","article-title":"Incremental evaluation of sliding-window queries over data streams.","volume":"19","author":"T. M.Ghanem","year":"2007","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"jghpc.2012070104-13","doi-asserted-by":"crossref","unstructured":"Govindaraju, N., Gray, J., Kumar, R., & Manocha, D. (2006). GPUTeraSort: High performance graphics coprocessor sorting for large database management. In Proceedings of the ACM SIGMOD International Conference on Management of Data (pp. 325-336).","DOI":"10.1145\/1142473.1142511"},{"key":"jghpc.2012070104-14","doi-asserted-by":"crossref","unstructured":"Govindaraju, N., Lloyd, B., Wang, W., Lin, M., & Manocha, D. (2004). Fast computation of database operations using graphics processors. In Proceedings of the ACM SIGMOD International Conference on Management of Data (pp. 215-226).","DOI":"10.1145\/1007568.1007594"},{"key":"jghpc.2012070104-15","doi-asserted-by":"crossref","unstructured":"Gregg, C., & Hazelwood, K. (2011). Where is the data? Why you cannot debate CPU vs. GPU performance without the answer. In Proceedings of the IEEE International Symposium on Performance Analysis of Systems and Software (pp. 134-144).","DOI":"10.1109\/ISPASS.2011.5762730"},{"key":"jghpc.2012070104-16","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1145\/42411.42415","article-title":"Reevaluating Amdahl\u2019s Law.","volume":"31","author":"J. L.Gustafson","year":"1988","journal-title":"Communications of the ACM"},{"key":"jghpc.2012070104-17","doi-asserted-by":"crossref","unstructured":"Guttman, A. (1984). R-trees: A dynamic index structure for spatial searching. In Proceedings of the ACM SIGMOD International Conference on Management of Data (pp. 47-57).","DOI":"10.1145\/971697.602266"},{"issue":"4","key":"jghpc.2012070104-18","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1109\/69.63252","article-title":"A relational approach to querying data streams.","volume":"2","author":"C. S.Hartzman","year":"1990","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"jghpc.2012070104-19","doi-asserted-by":"crossref","unstructured":"He, B., Yang, K., Fang, R., Lu, M., Govindaraju, N., Luo, Q., & Sander, P. (2008). Relational joins on graphics processors. In Proceedings of the ACM SIGMOD International Conference on Management of Data (pp. 511-524).","DOI":"10.1145\/1376616.1376670"},{"key":"jghpc.2012070104-20","unstructured":"Huang, X., & Jensen, C. S. (2004). Towards a streams-based framework for defining location-based queries. In Proceedings of the 2nd Workshop on Spatio-Temporal Database Management (pp. 73-80)."},{"issue":"3","key":"jghpc.2012070104-21","first-page":"12","article-title":"Location-dependent query processing: Where we are and where we are heading.","volume":"24","author":"S.Ilarri","year":"2010","journal-title":"ACM Computing Surveys"},{"issue":"1","key":"jghpc.2012070104-22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1508857.1508861","article-title":"Semantics and implementation of continuous sliding window queries over data streams.","volume":"34","author":"J.Kr\u00e4mer","year":"2009","journal-title":"ACM Transactions on Database Systems"},{"key":"jghpc.2012070104-23","unstructured":"Kwon, D., Lee, S., & Lee, S. (2002). Indexing the current positions of moving objects using the lazy update R-tree. In Proceedings of the 3rd International Conference on Mobile Data Management (pp. 113-120)."},{"key":"jghpc.2012070104-24","doi-asserted-by":"crossref","unstructured":"Lieberman, M. D., Sankaranarayanan, J., & Samet, H. (2008). A fast similarity join algorithm using graphics processing units. In Proceedings of the IEEE 24th International Conference on Data Engineering (pp. 1111-1120).","DOI":"10.1109\/ICDE.2008.4497520"},{"issue":"10","key":"jghpc.2012070104-25","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1109\/MC.2003.1236476","article-title":"The GPU enters computing\u2019s mainstream.","volume":"36","author":"M.Macedonia","year":"2003","journal-title":"Computer"},{"issue":"5","key":"jghpc.2012070104-26","doi-asserted-by":"crossref","first-page":"971","DOI":"10.1007\/s00778-007-0046-1","article-title":"SOLE: Scalable on-line execution of continuous queries on spatiotemporal data streams.","volume":"17","author":"M. F.Mokbel","year":"2008","journal-title":"Very Large Data Base Journal"},{"key":"jghpc.2012070104-27","doi-asserted-by":"crossref","unstructured":"Mokbel, M. F., Xiong, X., & Aref, W. G. (2004). SINA: Scalable incremental processing of continuous queries in spatio-temporal databases. In Proceedings of the ACM SIGMOD International Conference on Management of Data (pp. 623-634).","DOI":"10.1145\/1007568.1007638"},{"issue":"4","key":"jghpc.2012070104-28","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/s10707-005-4576-7","article-title":"Continuous query processing of spatiotemporal data streams in PLACE.","volume":"9","author":"M. F.Mokbel","year":"2005","journal-title":"GeoInformatica"},{"key":"jghpc.2012070104-29","unstructured":"Patroumpas, K., & Sellis, T. K. (2004). Managing trajectories of moving objects as data streams. In Proceedings of the 2nd Workshop on Spatio-Temporal Database Management (pp. 41-48)."},{"key":"jghpc.2012070104-30","doi-asserted-by":"crossref","unstructured":"Tao, Y., Papadias, D., & Sun, J. (2003). The TPR*-Tree: An optimized spatio-temporal access method for predictive queries. In Proceedings of the 29th International Conference on Very Large Data Bases (pp. 790-801).","DOI":"10.1016\/B978-012722442-8\/50075-6"},{"issue":"3","key":"jghpc.2012070104-31","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1145\/1016028.1016030","article-title":"Managing uncertainty in moving objects databases.","volume":"29","author":"G.Trajcevski","year":"2004","journal-title":"ACM Transactions on Database Systems"},{"key":"jghpc.2012070104-32","doi-asserted-by":"crossref","unstructured":"Wolfson, O., Jiang, L., Sistla, A. P., Chamberlain, S., Rishe, N., & Deng, M. (1999). Databases for tracking mobile units in real time. In C. Beeri & P. Buneman (Eds.), Proceedings of the 7th International Conference on Database Theory (LNCS 1540, pp. 169-186).","DOI":"10.1007\/3-540-49257-7_12"},{"key":"jghpc.2012070104-33","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1023\/A:1008782710752","article-title":"Updating and querying databases that track mobile units.","volume":"7","author":"O.Wolfson","year":"1999","journal-title":"Distributed and Parallel Databases"}],"container-title":["International Journal of Grid and High Performance Computing"],"original-title":[],"language":"ng","link":[{"URL":"https:\/\/www.igi-global.com\/viewtitle.aspx?TitleId=69806","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,2]],"date-time":"2022-06-02T04:52:49Z","timestamp":1654145569000},"score":1,"resource":{"primary":{"URL":"https:\/\/services.igi-global.com\/resolvedoi\/resolve.aspx?doi=10.4018\/jghpc.2012070104"}},"subtitle":[""],"short-title":[],"issued":{"date-parts":[[2012,7,1]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,7]]}},"URL":"https:\/\/doi.org\/10.4018\/jghpc.2012070104","relation":{},"ISSN":["1938-0259","1938-0267"],"issn-type":[{"value":"1938-0259","type":"print"},{"value":"1938-0267","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,7,1]]}}}