Approximate achievability in event databases

Austin Parker; Gerardo I. Simari; Amy Sliva; V. S. Subrahmanian

doi:10.1007/978-3-642-22152-1_62

Approximate achievability in event databases

Austin Parker^*, Gerardo I. Simari, Amy Sliva, V. S. Subrahmanian

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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.

Original language	English (US)
Title of host publication	Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 11th European Conference, ECSQARU 2011, Proceedings
Pages	737-748
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-22152-1_62
State	Published - 2011
Event	11th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU 2011 - Belfast, United Kingdom Duration: Jun 29 2011 → Jul 1 2011

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6717 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	11th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU 2011
Country/Territory	United Kingdom
City	Belfast
Period	6/29/11 → 7/1/11

Funding

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.

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-22152-1_62

Cite this

Parker, A., Simari, G. I., Sliva, A., & Subrahmanian, V. S. (2011). Approximate achievability in event databases. In Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 11th European Conference, ECSQARU 2011, Proceedings (pp. 737-748). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6717 LNAI). https://doi.org/10.1007/978-3-642-22152-1_62

Parker, Austin ; Simari, Gerardo I. ; Sliva, Amy et al. / Approximate achievability in event databases. Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 11th European Conference, ECSQARU 2011, Proceedings. 2011. pp. 737-748 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{6e29ce75f76f450abb6830900895f84b,

title = "Approximate achievability in event databases",

abstract = "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.",

author = "Austin Parker and Simari, {Gerardo I.} and Amy Sliva and Subrahmanian, {V. S.}",

note = "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{\textquoteright}s 7th Framework Programme (FP7/2007-2013)/ERC grant 246858 – DIADEM.; 11th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU 2011 ; Conference date: 29-06-2011 Through 01-07-2011",

year = "2011",

doi = "10.1007/978-3-642-22152-1_62",

language = "English (US)",

isbn = "9783642221514",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "737--748",

booktitle = "Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 11th European Conference, ECSQARU 2011, Proceedings",

}

Parker, A, Simari, GI, Sliva, A & Subrahmanian, VS 2011, Approximate achievability in event databases. in Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 11th European Conference, ECSQARU 2011, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6717 LNAI, pp. 737-748, 11th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU 2011, Belfast, United Kingdom, 6/29/11. https://doi.org/10.1007/978-3-642-22152-1_62

Approximate achievability in event databases. / Parker, Austin; Simari, Gerardo I.; Sliva, Amy et al.
Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 11th European Conference, ECSQARU 2011, Proceedings. 2011. p. 737-748 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6717 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 -

Parker A, Simari GI, Sliva A, Subrahmanian VS. Approximate achievability in event databases. In Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 11th European Conference, ECSQARU 2011, Proceedings. 2011. p. 737-748. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-22152-1_62

Approximate achievability in event databases

Abstract

Publication series

Conference

Funding

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this