TY - GEN
T1 - Approximate achievability in event databases
AU - Parker, Austin
AU - Simari, Gerardo I.
AU - Sliva, Amy
AU - Subrahmanian, V. S.
N1 - Funding Information:
Acknowledgements. The authors were funded in part by AFOSR grant FA95500610405 and ARO grant W911NF0910206. This work was also partially supported by the European Research Council under the EU’s 7th Framework Programme (FP7/2007-2013)/ERC grant 246858 – DIADEM.
PY - 2011
Y1 - 2011
N2 - An event DB is a database about states (of the world) and events (taken by an agent) whose effects are not well understood. Event DBs are omnipresent in the social sciences and may include diverse scenarios from political events and the state of a country to education-related actions and their effects on a school system. We consider the following problem: given an event DB representing historical events (what was the state and what actions were done at various past time points), and given a goal we wish to accomplish, what "change attempts" can the agent make so as to "optimize" the potential achievement of the goal? We define a formal version of this problem and derive results on its complexity. We then present a basic algorithm that provably provides a correct solution to finding an optimal state change attempt, as well as an enhanced algorithm that is built on top of the well known trie data structure and is also provably correct. We show correctness and algorithmic complexity results for both algorithms and report on experiments comparing their performance on synthetic data.
AB - An event DB is a database about states (of the world) and events (taken by an agent) whose effects are not well understood. Event DBs are omnipresent in the social sciences and may include diverse scenarios from political events and the state of a country to education-related actions and their effects on a school system. We consider the following problem: given an event DB representing historical events (what was the state and what actions were done at various past time points), and given a goal we wish to accomplish, what "change attempts" can the agent make so as to "optimize" the potential achievement of the goal? We define a formal version of this problem and derive results on its complexity. We then present a basic algorithm that provably provides a correct solution to finding an optimal state change attempt, as well as an enhanced algorithm that is built on top of the well known trie data structure and is also provably correct. We show correctness and algorithmic complexity results for both algorithms and report on experiments comparing their performance on synthetic data.
UR - http://www.scopus.com/inward/record.url?scp=79960132111&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79960132111&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-22152-1_62
DO - 10.1007/978-3-642-22152-1_62
M3 - Conference contribution
AN - SCOPUS:79960132111
SN - 9783642221514
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 737
EP - 748
BT - Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 11th European Conference, ECSQARU 2011, Proceedings
T2 - 11th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU 2011
Y2 - 29 June 2011 through 1 July 2011
ER -