{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:25:24Z","timestamp":1750307124378,"version":"3.41.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2011,10,1]],"date-time":"2011-10-01T00:00:00Z","timestamp":1317427200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA95500610405"],"award-info":[{"award-number":["FA95500610405"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF0910206W911NF0910525"],"award-info":[{"award-number":["W911NF0910206W911NF0910525"]}],"id":[{"id":"10.13039\/100000183","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":[[2011,10]]},"abstract":"<jats:p>\n            There are many applications where we observe various phenomena in space (e.g., locations of victims of a serial killer), and where we want to infer \u201cpartner\u201d locations (e.g., the location where the killer lives) that are geospatially related to the observed phenomena. In this article, we define\n            <jats:italic>geospatial abduction problems<\/jats:italic>\n            (GAPs for short). We analyze the complexity of GAPs, develop exact and approximate algorithms (often with approximation guarantees) for these problems together with analyses of these algorithms, and develop a prototype implementation of our GAP framework. We demonstrate accuracy of our algorithms on a real world data set consisting of insurgent IED (improvised explosive device) attacks against U.S. forces in Iraq (the observations were the locations of the attacks, while the \u201cpartner\u201d locations we were trying to infer were the locations of IED weapons caches).\n          <\/jats:p>","DOI":"10.1145\/2036264.2036271","type":"journal-article","created":{"date-parts":[[2012,10,12]],"date-time":"2012-10-12T20:56:02Z","timestamp":1350075362000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["GAPs"],"prefix":"10.1145","volume":"3","author":[{"given":"Paulo","family":"Shakarian","sequence":"first","affiliation":[{"name":"University of Maryland"}]},{"given":"V. S.","family":"Subrahmanian","sequence":"additional","affiliation":[{"name":"University of Maryland"}]},{"given":"Maria Luisa","family":"Sapino","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Torino"}]}],"member":"320","published-online":{"date-parts":[[2011,10]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Introduction to Machine Learning","author":"Alpaydin E.","unstructured":"Alpaydin , E. 2010. Introduction to Machine Learning 2 nd Ed. MIT Press . Alpaydin, E. 2010. Introduction to Machine Learning 2nd Ed. MIT Press.","edition":"2"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1404506"},{"key":"e_1_2_2_3_1","unstructured":"Brantingham P. and Brantingham P. 2008. Crime pattern theory. In Enviromental Criminology and Crime Analysis R. Wortley and L. Mazerolle Eds. 78--93. Brantingham P. and Brantingham P. 2008. Crime pattern theory. In Enviromental Criminology and Crime Analysis R. Wortley and L. Mazerolle Eds. 78--93."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(91)90005-5"},{"key":"e_1_2_2_5_1","first-page":"2","article-title":"Focussing abductive diagnosis. Arti","volume":"4","author":"Console L.","year":"1991","unstructured":"Console , L. , Portinale , L. , and Theseider Dupr\u00e9 , D. 1991 . Focussing abductive diagnosis. Arti . Intelli. Comm. 4 , 2 -- 3 , 88--97. Console, L., Portinale, L., and Theseider Dupr\u00e9, D. 1991. Focussing abductive diagnosis. Arti. Intelli. Comm. 4, 2--3, 88--97.","journal-title":"Intelli. Comm."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00961655"},{"key":"e_1_2_2_7_1","unstructured":"Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms 2nd Ed. MIT Press. Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms 2nd Ed. MIT Press."},{"volume-title":"Proceedings of the SIAM Data Mining Conference (SDM).","author":"Davidson I.","key":"e_1_2_2_8_1","unstructured":"Davidson , I. and Ravi , S. S . 2005. Clustering with constraints: Feasibility issues and the k-means algorithm . In Proceedings of the SIAM Data Mining Conference (SDM). Davidson, I. and Ravi, S. S. 2005. Clustering with constraints: Feasibility issues and the k-means algorithm. In Proceedings of the SIAM Data Mining Conference (SDM)."},{"key":"e_1_2_2_9_1","series-title":"Lecture Notes in Computer Science Advances in Artificial Intelligence.","volume-title":"Planning with abduction: A logical framework to explore extensions to classical planning","author":"do Lago Pereira S.","unstructured":"do Lago Pereira , S. and de Barros , L. N. 2004. Planning with abduction: A logical framework to explore extensions to classical planning . In Lecture Notes in Computer Science Advances in Artificial Intelligence. do Lago Pereira, S. and de Barros, L. N. 2004. Planning with abduction: A logical framework to explore extensions to classical planning. In Lecture Notes in Computer Science Advances in Artificial Intelligence."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200838"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_2_2_12_1","unstructured":"Freedman D. Purves R. and Pisani R. 2007. Statistics 4th Ed. W. W. Norton and Co. Freedman D. Purves R. and Pisani R. 2007. Statistics 4th Ed. W. W. Norton and Co."},{"key":"e_1_2_2_13_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co. New York NY. Garey M. R. and Johnson D. S. 1979. Computers and Intractability; A Guide to the Theory of NP-Completeness . W. H. Freeman & Co. New York NY."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211045"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1017\/s00446-002-0078-0"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90018-9"},{"volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB).","author":"Kakas A. C.","key":"e_1_2_2_17_1","unstructured":"Kakas , A. C. and Mancarella , P . 1990. Database updates through abduction . In Proceedings of the International Conference on Very Large Databases (VLDB). Kakas, A. C. and Mancarella, P. 1990. Database updates through abduction. In Proceedings of the International Conference on Very Large Databases (VLDB)."},{"key":"e_1_2_2_18_1","doi-asserted-by":"crossref","unstructured":"Karp R. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations R. E. Miller and J. W. Thatcher Eds. 85--103. Karp R. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations R. E. Miller and J. W. Thatcher Eds. 85--103.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/872035.872040"},{"key":"e_1_2_2_20_1","volume-title":"Working Papers of the 10th International Workshop on Qualitative Reasoning about Physical Systems.","author":"Kuipers B.","year":"1996","unstructured":"Kuipers , B. 1996 . A hierarchy of qualitative representations for space . In Working Papers of the 10th International Workshop on Qualitative Reasoning about Physical Systems. Kuipers, B. 1996. A hierarchy of qualitative representations for space. In Working Papers of the 10th International Workshop on Qualitative Reasoning about Physical Systems."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.542029"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/185675.306789"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215031"},{"key":"e_1_2_2_24_1","volume-title":"Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, L. M. L. Cam and J. Neyman Eds.","volume":"1","author":"MacQueen J. B.","year":"1967","unstructured":"MacQueen , J. B. 1967 . Some methods for classification and analysis of multivariate observations . In Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, L. M. L. Cam and J. Neyman Eds. Vol. 1 . University of California Press, 281--297. MacQueen, J. B. 1967. Some methods for classification and analysis of multivariate observations. In Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, L. M. L. Cam and J. Neyman Eds. Vol. 1. University of California Press, 281--297."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210040"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/254180.254190"},{"volume-title":"Philosophical Writings of Peirce, (selected and edited with an introduction by Justus Buchler.)","author":"Peirce C. S.","key":"e_1_2_2_28_1","unstructured":"Peirce , C. S. 1955. Philosophical Writings of Peirce, (selected and edited with an introduction by Justus Buchler.) . Dover Publications , New York . Peirce, C. S. 1955. Philosophical Writings of Peirce, (selected and edited with an introduction by Justus Buchler.). Dover Publications, New York."},{"volume-title":"Proceedings of the 5th National Conference on AI (AAAI). 140--145","author":"Peng Y.","key":"e_1_2_2_29_1","unstructured":"Peng , Y. and Reggia , J. A . 1986. Plausibility of Diagnostic Hypotheses . In Proceedings of the 5th National Conference on AI (AAAI). 140--145 . Peng, Y. and Reggia, J. A. 1986. Plausibility of Diagnostic Hypotheses. In Proceedings of the 5th National Conference on AI (AAAI). 140--145."},{"key":"e_1_2_2_30_1","unstructured":"Reggia J. A. and Peng Y. 1990. Abductive Inference Models for Diagnostic Problem-Solving. Springer-Verlag Berlin Germany. Reggia J. A. and Peng Y. 1990. Abductive Inference Models for Diagnostic Problem-Solving . Springer-Verlag Berlin Germany."},{"key":"e_1_2_2_31_1","unstructured":"Rossmo D. K. and Rombouts S. 2008. Geographic profiling. In Enviromental Criminology and Crime Analysis R. Wortley and L. Mazerolle Eds. 136--149. Rossmo D. K. and Rombouts S. 2008. Geographic profiling. In Enviromental Criminology and Crime Analysis R. Wortley and L. Mazerolle Eds. 136--149."},{"volume-title":"Proceedings of the European Conference on Artificial Intelligence (ECAI).","author":"Santos P.","key":"e_1_2_2_32_1","unstructured":"Santos , P. and Shanahan , M . 2002. Hypothesising object relations from image transitions . In Proceedings of the European Conference on Artificial Intelligence (ECAI). Santos, P. and Shanahan, M. 2002. Hypothesising object relations from image transitions. In Proceedings of the European Conference on Artificial Intelligence (ECAI)."},{"volume-title":"Proceedings of the 3rd International Conference on Computational Cultural Dynamics (ICCCD). AAAI.","author":"Shakarian P.","key":"e_1_2_2_33_1","unstructured":"Shakarian , P. , Subrahmanian , V. , and Sapino , M. L . 2009. SCARE: A Case Study with Baghdad . In Proceedings of the 3rd International Conference on Computational Cultural Dynamics (ICCCD). AAAI. Shakarian, P., Subrahmanian, V., and Sapino, M. L. 2009. SCARE: A Case Study with Baghdad. In Proceedings of the 3rd International Conference on Computational Cultural Dynamics (ICCCD). AAAI."},{"key":"e_1_2_2_34_1","volume-title":"Proceedings of the National Conference on Artifical Intelligence AAAI. 1098","author":"Shanahan M.","year":"1996","unstructured":"Shanahan , M. 1996 . Noise and the common sense informatic situation . In Proceedings of the National Conference on Artifical Intelligence AAAI. 1098 . Shanahan, M. 1996. Noise and the common sense informatic situation. In Proceedings of the National Conference on Artifical Intelligence AAAI. 1098."},{"key":"e_1_2_2_35_1","unstructured":"US Army. 1994. Intelligence Preparation of the Battlefiled (US Army Field Manual). FM 34-130 Ed. US Army . 1994. Intelligence Preparation of the Battlefiled (US Army Field Manual). FM 34-130 Ed."},{"volume-title":"Approximation Algorithms","author":"Vazirani V. V.","key":"e_1_2_2_36_1","unstructured":"Vazirani , V. V. 2004. Approximation Algorithms . Springer . Vazirani, V. V. 2004. Approximation Algorithms. Springer."},{"volume-title":"Proceedings of the 18th International Conference on Machine Learning (ICML). Morgan Kaufmann Publishers Inc.","author":"Wagstaff K.","key":"e_1_2_2_37_1","unstructured":"Wagstaff , K. , Cardie , C. , Rogers , S. , and Schr\u00f6dl , S . 2001. Constrained k-means clustering with background knowledge . In Proceedings of the 18th International Conference on Machine Learning (ICML). Morgan Kaufmann Publishers Inc. , San Francisco, CA, 577--584. Wagstaff, K., Cardie, C., Rogers, S., and Schr\u00f6dl, S. 2001. Constrained k-means clustering with background knowledge. In Proceedings of the 18th International Conference on Machine Learning (ICML). Morgan Kaufmann Publishers Inc., San Francisco, CA, 577--584."},{"key":"e_1_2_2_38_1","unstructured":"WEKA. 2009. WEKA 3 Data Mining http:\/\/www.cs.waikato.ac.nz\/ml\/weka\/. WEKA . 2009. WEKA 3 Data Mining http:\/\/www.cs.waikato.ac.nz\/ml\/weka\/."}],"container-title":["ACM Transactions on Intelligent Systems and Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2036264.2036271","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2036264.2036271","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:48:28Z","timestamp":1750240108000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2036264.2036271"}},"subtitle":["Geospatial Abduction Problems"],"short-title":[],"issued":{"date-parts":[[2011,10]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,10]]}},"alternative-id":["10.1145\/2036264.2036271"],"URL":"https:\/\/doi.org\/10.1145\/2036264.2036271","relation":{},"ISSN":["2157-6904","2157-6912"],"issn-type":[{"type":"print","value":"2157-6904"},{"type":"electronic","value":"2157-6912"}],"subject":[],"published":{"date-parts":[[2011,10]]},"assertion":[{"value":"2010-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}