{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:26:29Z","timestamp":1750307189367,"version":"3.41.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2012,7,1]],"date-time":"2012-07-01T00:00:00Z","timestamp":1341100800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2012,7]]},"abstract":"<jats:p>Graphics processing units (GPUs) provide large computational power at a very low price, which position GPUs well as an ubiquitous accelerator. However, GPUs are space constrained, and hence applications developed for GPUs are space sensitive.<\/jats:p>\n          <jats:p>Space-constrained computational devices such as GPUs can greatly benefit from representations that reduce space consumption drastically. One such representation is the succinct representation of trees. Succinct representation of trees generally allows for operations such as parent queries, least common ancestor queries, and so on. Mapping such a robust representation to the GPU for targeted applications can lead to substantial improvement in problem sizes that are processed at a given point of time. Space-saving methods such as succinct data structures remain largely unexplored on the GPU. In this work, a succinct representation of ordered trees on the GPU is explored, with application to discrete range searching (DRS).<\/jats:p>\n          <jats:p>Based on the succinct representations found applicable, a space--saving solution for DRS is presented here. In our method, DRS is mapped to a least common ancestor query on a Cartesian tree. For space-efficient DRS queries, we store the succinct representation of the Cartesian tree of an array. Our method uses a maximum of 7.5 bits of additional space per element. Furthermore, the speed-up achieved by our method is in the range of 20--25 for preprocessing and 25--35 for batch querying over a sequential implementation. Compared to an 8-threaded implementation, our preprocessing and querying methods obtain a speed-up of 6--8.<\/jats:p>\n          <jats:p>We also study the applications of the DRS on the GPU. Efficient primitives expand the range of applications performed on the GPU. DRS is one such primitive with direct applications to string processing, document and text retrieval systems, and least common ancestor queries. We suggest that graph algorithms that use the least common ancestor, can be enabled on the GPU based on DRS primitive. We also show some applications of DRS in tree queries and string querying.<\/jats:p>","DOI":"10.1145\/2133803.2345679","type":"journal-article","created":{"date-parts":[[2012,10,16]],"date-time":"2012-10-16T12:50:57Z","timestamp":1350391857000},"source":"Crossref","is-referenced-by-count":9,"title":["Discrete range searching primitive for the GPU and its applications"],"prefix":"10.1145","volume":"17","author":[{"given":"Jyothish","family":"Soman","sequence":"first","affiliation":[{"name":"IBM India Research Labs, New Delhi, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kishore","family":"Kothapalli","sequence":"additional","affiliation":[{"name":"International Institute of Information Technology, Hyderabad, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P. J.","family":"Narayanan","sequence":"additional","affiliation":[{"name":"International Institute of Information Technology, Hyderabad, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,10,16]]},"reference":[{"volume-title":"UCB\/EECS-2006-183, EECS Department","author":"Asanovic K.","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2009.204"},{"volume-title":"Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'01)","author":"Bender M. A.","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/356789.356797"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63478"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87744-8_21"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/11780441_5"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Fischer J.\n     and \n      Heun V\n  . \n  2007\n  . A new succinct representation of RMQ-information and improvements in the enhanced suffix array. In Proceedings of the 1st International Symposium on Combinatiorics Algorithms Probablistic and Experimental Methodologies (ESCAPE'07) Lecture Notes in Computer Science vol. \n  4614 Springer Berlin 459--470.   Fischer J. and Heun V. 2007. A new succinct representation of RMQ-information and improvements in the enhanced suffix array. In Proceedings of the 1st International Symposium on Combinatiorics Algorithms Probablistic and Experimental Methodologies (ESCAPE'07) Lecture Notes in Computer Science vol. 4614 Springer Berlin 459--470.","DOI":"10.1007\/978-3-540-74450-4_41"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2008.45"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808675"},{"volume-title":"An Introduction to Parallel Algorithms","author":"J\u00e1J\u00e1 J.","key":"e_1_2_1_11_1"},{"volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithm (SODA'07)","author":"Jansson J.","key":"e_1_2_1_12_1"},{"volume-title":"Compute Unified Device Architecture Programming Guide","author":"Nvidia C.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","unstructured":"Patidar S. and Narayanan P. 2009. Scalable split and gather primitives for the gpu. Tech. rep. IIIT\/TR\/2009\/99.  Patidar S. and Narayanan P. 2009. Scalable split and gather primitives for the gpu. Tech. rep. IIIT\/TR\/2009\/99."},{"key":"e_1_2_1_15_1","unstructured":"Rehman M. 2010. Exploring irregular memory access applications on the GPU www.contrib.andrew. cmu.edu\/~suhailr\/thesis.pdf.  Rehman M. 2010. Exploring irregular memory access applications on the GPU www.contrib.andrew. cmu.edu\/~suhailr\/thesis.pdf."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542275.1542311"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-006-1198-x"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2009.5161005"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1230100.1230105"},{"volume-title":"Proceedings of the 22nd ACM SIGGRAPH\/EUROGRAPHICS Symposium on Graphics Hardware. Eurographics Association, 106","author":"Sengupta S.","key":"e_1_2_1_20_1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2008.05.012"},{"volume-title":"Proceedings of the International Conference on High Performance Computing (HiPC'10)","author":"Soman J.","key":"e_1_2_1_22_1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2010.69"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2133803.2345679","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2133803.2345679","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:05:52Z","timestamp":1750241152000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2133803.2345679"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":23,"alternative-id":["10.1145\/2133803.2345679"],"URL":"https:\/\/doi.org\/10.1145\/2133803.2345679","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2012,7]]}}}