{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T09:49:15Z","timestamp":1764841755161,"version":"3.41.0"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2013,12,1]],"date-time":"2013-12-01T00:00:00Z","timestamp":1385856000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100002418","name":"Intel Corporation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100002418","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000083","name":"Directorate for Computer and Information Science and Engineering","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000083","id-type":"DOI","asserted-by":"publisher"}]},{"name":"SaTC program"},{"DOI":"10.13039\/100004316","name":"International Business Machines Corporation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004316","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Intell. Syst. Technol."],"published-print":{"date-parts":[[2013,12]]},"abstract":"<jats:p>\n            With ubiquitous wireless connectivity and technological advances in mobile devices, we witness the growing demands and increasing market shares of mobile intelligent systems and technologies for real-time decision making and location-based knowledge discovery. Spatial alarms are considered as one of the fundamental capabilities for intelligent mobile location-based systems. Like time-based alarms that remind us the arrival of a future time point, spatial alarms remind us the arrival of a future spatial point. Existing approaches for scaling spatial alarm processing are focused on computing Alarm-Free Regions (A\n            <jats:sc>fr<\/jats:sc>\n            ) and Alarm-Free Period (A\n            <jats:sc>fp<\/jats:sc>\n            ) such that mobile objects traveling within an A\n            <jats:sc>fr<\/jats:sc>\n            can safely hibernate the alarm evaluation process for the computed A\n            <jats:sc>fp<\/jats:sc>\n            , to save battery power, until approaching the nearest alarm of interest. A key technical challenge in scaling spatial alarm processing is to efficiently compute A\n            <jats:sc>fr<\/jats:sc>\n            and A\n            <jats:sc>fp<\/jats:sc>\n            such that mobile objects traveling within an A\n            <jats:sc>fr<\/jats:sc>\n            can safely hibernate the alarm evaluation process during the computed A\n            <jats:sc>fp<\/jats:sc>\n            , while maintaining high accuracy. In this article we argue that on-demand computation of A\n            <jats:sc>fr<\/jats:sc>\n            is expensive and may not scale well for dense populations of mobile objects. Instead, we propose to maintain an index for both spatial alarms and empty regions (A\n            <jats:sc>fr<\/jats:sc>\n            ) such that for a given mobile user's location, we can find relevant spatial alarms and whether it is in an alarm-free region more efficiently. We also show that conventional spatial indexing methods, such as R-tree family,\n            <jats:italic>k<\/jats:italic>\n            -d tree, Quadtree, and Grid, are by design not well suited to index empty regions. We present Mondrian Tree \u2013 a region partitioning tree for indexing both spatial alarms and alarm-free regions. We first introduce the Mondrian Tree indexing algorithms, including index construction, search, and maintenance. Then we describe a suite of Mondrian Tree optimizations to further enhance the performance of spatial alarm processing. Our experimental evaluation shows that the Mondrian Tree index, as an intelligent technology for mobile systems, outperforms traditional index methods, such as R-tree, Quadtree, and\n            <jats:italic>k<\/jats:italic>\n            -d tree, for spatial alarm processing.\n          <\/jats:p>","DOI":"10.1145\/2542182.2542186","type":"journal-article","created":{"date-parts":[[2014,1,2]],"date-time":"2014-01-02T13:09:43Z","timestamp":1388668183000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Mondrian tree"],"prefix":"10.1145","volume":"5","author":[{"given":"Myungcheol","family":"Doo","sequence":"first","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ling","family":"Liu","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,1,3]]},"reference":[{"volume-title":"Proceedings of the 15th International Conference on High Performance Computing (HiPC'08)","author":"Bamba B.","key":"e_1_2_1_1_1","unstructured":"Bamba , B. , Liu , L. , Yu , P. S. , Zhang , G. , and Doo , M . 2008. Scalable processing of spatial alarms . In Proceedings of the 15th International Conference on High Performance Computing (HiPC'08) . 232--244. Bamba, B., Liu, L., Yu, P. S., Zhang, G., and Doo, M. 2008. Scalable processing of spatial alarms. In Proceedings of the 15th International Conference on High Performance Computing (HiPC'08). 232--244."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"volume-title":"Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS'84)","author":"Chazelle B.","key":"e_1_2_1_3_1","unstructured":"Chazelle , B. , Drysdale , R. , and Lee , D . 1984. Computing the largest empty rectangle . In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS'84) . 43--54. Chazelle, B., Drysdale, R., and Lee, D. 1984. Computing the largest empty rectangle. In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS'84). 43--54."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288933"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24741-8_6"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2005.48"},{"key":"e_1_2_1_7_1","unstructured":"Grove J. V. 2010. Morbile marketer. http:\/\/mashable.com\/2010\/08\/18\/shopalerts.  Grove J. V. 2010. Morbile marketer. http:\/\/mashable.com\/2010\/08\/18\/shopalerts."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02982-0_24"},{"volume-title":"Proceedings of the 15th International Conference on Very Large Databases (VLDB'89)","author":"Henrich A.","key":"e_1_2_1_10_1","unstructured":"Henrich , A. , Six , H.-W. , and Widmayer , P . 1989. The lsd tree: Spatial access to multidimensional point and non-point objects . In Proceedings of the 15th International Conference on Very Large Databases (VLDB'89) . 45--53. Henrich, A., Six, H.-W., and Widmayer, P. 1989. The lsd tree: Spatial access to multidimensional point and non-point objects. In Proceedings of the 15th International Conference on Very Large Databases (VLDB'89). 45--53."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066212"},{"volume-title":"Proceeding of the 17th International Conference on Software Engineering and Data Engineering (SEDE'08)","author":"Murugappan A.","key":"e_1_2_1_12_1","unstructured":"Murugappan , A. and Liu , L . 2008. Energy-efficient processing of spatial alarms on mobile clients . In Proceeding of the 17th International Conference on Software Engineering and Data Engineering (SEDE'08) . Murugappan, A. and Liu, L. 2008. Energy-efficient processing of spatial alarms on mobile clients. In Proceeding of the 17th International Conference on Software Engineering and Data Engineering (SEDE'08)."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/348.318586"},{"key":"e_1_2_1_14_1","volume-title":"Gtmobisim: A mobile trace generator for road networks. Tech. rep","author":"Pesti P.","year":"2009","unstructured":"Pesti , P. , Bamba , B. , Doo , M. , Liu , L. , Palanisamy , B. , and Weber , M . 2009 . Gtmobisim: A mobile trace generator for road networks. Tech. rep . http:\/\/code.google.com\/p\/gt-mobisim\/. Pesti, P., Bamba, B., Doo, M., Liu, L., Palanisamy, B., and Weber, M. 2009. Gtmobisim: A mobile trace generator for road networks. Tech. rep. http:\/\/code.google.com\/p\/gt-mobisim\/."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1921024"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2002.1039840"},{"key":"e_1_2_1_17_1","unstructured":"Sdt. 2013. Spatial data transfer format. http:\/\/www.mcmcweb.er.usgs.gov\/sdts\/.  Sdt. 2013. Spatial data transfer format. http:\/\/www.mcmcweb.er.usgs.gov\/sdts\/."},{"volume-title":"Proceedings of the 14th International Conference on Very Large Data Bases (VLDB'88)","author":"Seeger B.","key":"e_1_2_1_18_1","unstructured":"Seeger , B. and Kriegel , H. P . 1988. Techniques for design and implementation of efficient spatial access methods . In Proceedings of the 14th International Conference on Very Large Data Bases (VLDB'88) . 360--371. Seeger, B. and Kriegel, H. P. 1988. Techniques for design and implementation of efficient spatial access methods. In Proceedings of the 14th International Conference on Very Large Data Bases (VLDB'88). 360--371."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11551201_14"},{"key":"e_1_2_1_20_1","unstructured":"Usg. 2013. US geological survey. http:\/\/www.usgs.gov\/.  Usg. 2013. US geological survey. http:\/\/www.usgs.gov\/."}],"container-title":["ACM Transactions on Intelligent Systems and Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2542182.2542186","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2542182.2542186","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:09:56Z","timestamp":1750234196000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2542182.2542186"}},"subtitle":["A fast index for spatial alarm processing"],"short-title":[],"issued":{"date-parts":[[2013,12]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,12]]}},"alternative-id":["10.1145\/2542182.2542186"],"URL":"https:\/\/doi.org\/10.1145\/2542182.2542186","relation":{},"ISSN":["2157-6904","2157-6912"],"issn-type":[{"type":"print","value":"2157-6904"},{"type":"electronic","value":"2157-6912"}],"subject":[],"published":{"date-parts":[[2013,12]]},"assertion":[{"value":"2011-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-01-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}