Quite a lot, but not much lately. We've used many of these techniques in
previous research, and actually continue to use them. Currently we are
developing an access policy model (OWL ontology and instances), translating
these to Prolog, then translating the Prolog to efficient representation, i.e.,
by extensionalizing as much as possible (driving rules to ground, tabling,
etc.), bit-encoding, etc. (01)
For the following, I'm not sure all these links still work. Note that some of
the following are graph-partitioning, other optimization papers. (02)
Ait-kaci, Hassan; Robert Boyer; Patrick Lincoln; Roger Nasr. 1989. Efficient
Implementation of Lattice Operations. TOPLAS 11-1-1989.
http://www.csl.sri.com/users/lincoln/papers/toplas89.ps.gz. (03)
Berry, Jonathan; Goldberg, Mark K. 1995. Path Optimization for Graph
Partitioning Problems , DIMACS Technical Report #95-34. Discrete Applied
Mathematics, Volume 90, Issues 1-3, 15 January 1999, Pages 27-50.
www.cs.rpi.edu/~goldberg/publications/Path-opt.pdf. (04)
van Bommel, M. F.; P. Wang. 2003. Encoding multiple inheritance hierarchies for
lattice operations. Data & Knowledge Engineering, Volume 50, Issue 2, August
2004, Pages 175-194. (05)
Cadoli, M. 1996. Panel on ``Knowledge Compilation and Approximation'':
Terminology, Questions, References. Fourth International Symposium on
ARTIFICIAL INTELLIGENCE AND MATHEMATICS, 1996.
http://www.dis.uniroma1.it/pub/AI/papers/cado-96.ps.gz (06)
Cadoli, Marco and Donini, Francesco M. 1997. A Survey on Knowledge
Compilation. AI Communications, The European Journal for Artificial
Intelligence, Vol. 10, pp.
137-150.http://www.dis.uniroma1.it/PUB/AI/citations/cado-doni-97.html (07)
Cadoli, Marco; Eiter, Thomas. 1998. Computational Aspects of Knowledge
Representations. Tutorial MP4, Fifteenth National Conference on Artificial
Intelligence, Madison, WI, July 27, 1998. http://www.dis.uniroma1,it/~cadoli. (08)
Caseau, Y. ; M. Habib; L. Nourine; O. Raynaud. 1999. Encoding of multiple
inheritance hierarchies and partial orders. Computational Intelligence 15 (1)
(1999) 50-62. (09)
Darwiche, Adnan; Pierre Marquis. 2001. A Knowledge Compilation Map.
http://www.cs.ucla.edu/~darwiche/d116.pdf. An earlier version appeared as "A
Perspective on Knowledge Compilation," in Proceedings of the 17th International
Joint Conference on Artificial Intelligence (IJCAI'01), pp. 175-182, 2001. (010)
Demmel, James. 1996a. Graph Partitioning, Part 1. CS267, Applications of
Parallel Computers: Notes for Lectures 20 and 21, March 21, 1996 and April 2,
1996. Spring, 1996, University of California, Berkeley.
http://http.cs.berkeley.edu/~demmel/cs267/lecture18/lecture18.html (011)
Demmel, James. 1996b. Graph Partitioning, Part 2. CS267, Applications of
Parallel Computers: Notes for Lecture 23, April 9, 1996. Spring, 1996,
University of California, Berkeley.
http://http.cs.berkeley.edu/~demmel/cs267/lecture20/lecture20.html (012)
Dershowitz, Nachum. 2008. Bit Inference. Workshop on Practical Aspects of
Automated Reasoning, August, 2008, Sydney, Australia, pp. 26-35.
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.143.341. (013)
Eyal, Amir, and Sheila McIlraith. 2000a. Improving the Efficiency of Reasoning
Through Structure-Based Reformulation.To appear in Proceedings of the Symposium
on Abstraction, Reformulation, and Approximation (SARA2000). Published by
Springer-Verlag in Lecture Notes in Artificial Intelligence, vol. 1864. Lake
LBJ, Texas. July 2000. (014)
Eyal, Amir, and Sheila McIlraith. 2000b. Partition-Based Logical Reasoning.
Proceedings of the Seventh International Conference on Principles of Knowledge
Representation and Reasoning (KR2000). Breckenridge, Colorado, USA. April
12-15, 2000: 389-400. ftp://ftp.ksl.stanford.edu/pub/KSL_Reports/KSL-00-02.ps (015)
Eyal, Amir, and Sheila McIlraith. 2005. Partition-based logical reasoning for
first-order and propositional theories. Artificial Intelligence, Volume 162 ,
Issue 1-2 (February 2005). Special volume on reformulation, pp. 49 - 88. See
the AI special issue on reformulation:
http://www.sciencedirect.com/science?_ob=PublicationURL&_tockey=%23TOC%235617%232005%23998379998%23551202%23FLP%23&_cdi=5617&_pubType=J&_auth=y&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=195c8e553ef6dce8c9b911bfd40eca0a. (016)
Fall, Andrew. 1995a. Heterogeneous Encoding. In Proceedings of International
KRUSE Symposium: Knowledge Retrieval, Use, and Storage for Efficiency, Gerard
Ellis, Robert Levinson, Andrew Fall, Veronica Dahl, eds., Santa Cruz, CA, Aug.
11-13, 1995, pp. 134-146. (017)
Fall, Andrew. 1995b. An Abstract Framework for Taxonomic Encoding. In
Proceedings of International KRUSE Symposium: Knowledge Retrieval, Use, and
Storage for Efficiency, Gerard Ellis, Robert Levinson, Andrew Fall, Veronica
Dahl, eds., Santa Cruz, CA, Aug. 11-13, 1995, pp. 162-167. (018)
Fall, Andrew. 1996. Reasoning with Taxonomies. Ph.D thesis, Simon Fraser
University.Gogic, Goran; Kautz, Henry; Papadimitriou, Christos; Selman, Bart.
1995. The Comparative Linguistics of Knowledge Representation, Proceedings of
IJCAI-95. ftp://ftp.research.att.com/dist/ai/ijcai95comp-ling.ps.Z. (019)
Gogic, Goran; Papadimitriou, Christos; Sideri, Martha. 1998. Incremental
Recompilation of Knowledge. Journal of Artificial Intelligence Research 8
(1998), pp. 23-37. (020)
Gupta, A. 1997. Fast and Effective Algorithms for Graph Partitioning and
Sparse-matrix Ordering. IBM Journal of Research and Development, Vol. 41, No.
1/2 - Optical lithography, 1997.
http://www.almaden.ibm.com/journal/rd/411/gupta.html (021)
Gupta, Ashish; Sagiv, Yehoshua; Ullman, Jeffrey D.; Widom, Jennifer. 1994.
Constraint Checking with Partial Information. In PODS 1994 (May 24-27,
Minneapolis, Minnesota). http://www-db.stanford.edu/pub/gupta/1994/pods94.ps (022)
Karypis, George; Kumar, Vipin. 1998a. Multilevel Algorithms for
Multi-Constraint Graph Partitioning. University of Minnesota, Department of
Computer Science/Army HPC Research Center, Technical Report 98-019, May 5,
1998.
http://www-users.cs.umn.edu/~karypis/publications/Papers/PDF/mlevel-mconstraint.pdf (023)
Karypis, George; Kumar, Vipin. 1998b. METIS: A Software Package for
Partitioning Unstructured Graphs, Partitioning Meshes, and Computing
Fill-Reducing Orderings of Sparse Matrices, Version 4.0. September 20, 1998.
http://www-users.cs.umn.edu/~karypis/metis/metis/files/manual.ps (024)
Kautz, Henry; Selman, Bart. 1994. An Empirical Evaluation of Knowledge
Compilation. Proceedings of AAAI-94, Seattle, WA, July 1994.
ftp://ftp.research.att.com/dist/ai/aaai94knowl-comp.ps.Z (025)
Kautz, Henry; Selman, Bart. A General Framework for Knowledge Compilation.
PDK-91, WOCFAI-91. ftp://ftp.research.att.com/dist/ai/pdk91kc-gen.ps.Z. (026)
Kautz, Henry; Selman, Bart. 1998. The Role of Domain-Specific Knowledge in the
Planning as Satisfiability Framework. In Proceedings of the Fourth
International Conference on AI Planning systems (AIPS-98), Pittsburgh, PA. (027)
Mugnier, Marie-Laure. 2000. Knowledge Representation and Reasonings Based on
Graph Homomorphism, (Invited Conference). Proceedings of the 8th International
Conference on Conceptual Structures (ICCS'00), Darmstadt, Germany, August 2000,
Lecture Notes in AI, volume 1867, pages 172-192. Springer, 2000. A longer
version is available as research report RR-LIRMM 00-098. (028)
Preuveneers, D., Berbers, Y., 2006. Prime numbers considered useful: Ontology
encoding for efficient subsumption testing, Tech. Rep. CW464.
http://www.cs.kuleuven.be/publicaties/rapporten/cw/CW464. abs.html, Department
of Computer Science, Katholieke Universiteit Leuven, Belgium (October 2006). (029)
Samuel, Ken; Leo Obrst; Suzette Stoutenberg; Karen Fox; Paul Franklin; Adrian
Johnson; Ken Laskey; Deborah Nichols; Steve Lopez; and Jason Peterson. 2008.
Applying Prolog to Semantic Web Ontologies & Rules: Moving Toward Description
Logic Programs. The Journal of the Theory and Practice of Logic Programming
(TPLP), Massimo Marchiori, ed., Cambridge University Press, Volume 8, Issue
03, May 2008, pp. 301-322.
http://journals.cambridge.org/action/displayAbstract;jsessionid=564053DB808528C03B8238D8FBAE704C.tomcat1?fromPage=online&aid=1853440http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=1853440. (030)
Schrag, R.; and J.M. Crawford. 1996. Implicates and Prime Implicates In Random
3SAT. Artificial Intelligence, 81:199-222, Frontiers in Problem Solving: Phase
Transitions and Complexity, edited by T. Hogg, B. A. Huberman and C. Williams,
1996 http://www.cirl.uoregon.edu/crawford/papers/implicates.ps. (031)
Selman, Bart; Kautz, Henry. 1991. Knowledge Compilation Using Horn
Approximations. Proceedings of AAAI-91.
ftp://ftp.research.att.com/dist/ai/aaai91knowl-comp.ps.Z (032)
Selman, Bart; Kautz, Henry. 1996. Knowledge Compilation and Theory
Approximation. Journal of the ACM, 1996.
ftp://ftp.research.att.com/dist/ai/jacm96knowl-comp.ps.Z. (033)
Stuckenschmidt, Heiner; and Michel Klein. 2005. Structure-Based Partitioning of
Large Concept Hierarchies. In International Semantic Web Conference, pp.
289-303, 2004. (034)
Subbarayan, Sathiamoorthy; Lucas Bordeaux; Youssef Hamadi. 2007. Knowledge
Compilation Properties of Tree-of-BDDs. AAAI 2007: 502-507. (035)
Tobies, S. 2001. Complexity Results and Practical Algorithms for Logics in
Knowledge Representation. PhD dissertation, University of Dresden.
http://lat.inf.tu-dresden.de/research/phd/Tobies-PhD-2001.pdf. (036)
Van Roy, Peter. 1990. Can Logic Programming Execute as Fast as Imperative
Programming? Ph.D thesis, Department of Computer Science, U.C. Berkeley,
Report UCB/CSD90/600, December 1990. Revised version published as Fast Logic
Program Execution by Intellect Books. (037)
Van Roy, Peter. 1993b. 1983-1993: The Wonder Years of Sequential Prolog
Implementation. PRL Report #36, December 1993.
ftp://ftp.digital.com/pub/DEC/PRL/research-reports/PRL-RR-36.ps.Z. Also
appeared in Journal of Logic Programming, 19:385-441, 1994. (038)
You can also look at SAT/SMT (satisfiability/satisfiability modulo theories)
research. (039)
Thanks,
Leo (040)
-----Original Message-----
From: ontology-summit-bounces@xxxxxxxxxxxxxxxx
[mailto:ontology-summit-bounces@xxxxxxxxxxxxxxxx] On Behalf Of Wartik, Steven P
"Steve"
Sent: Tuesday, April 03, 2012 11:16 AM
To: Ontology Summit 2012 discussion
Subject: Re: [ontology-summit] Clarification re Big Data Challenges Synthesis (041)
Leo, (042)
No argument with anything you wrote, at least in theory. I'm still trying to
wrap my mind around the implications of your step (2). How much research has
been conducted in the area? Can you provide pointers? (043)
Thanks, (044)
Steve Wartik (045)
_________________________________________________________________
Msg Archives: http://ontolog.cim3.net/forum/ontology-summit/
Subscribe/Config: http://ontolog.cim3.net/mailman/listinfo/ontology-summit/
Unsubscribe: mailto:ontology-summit-leave@xxxxxxxxxxxxxxxx
Community Files: http://ontolog.cim3.net/file/work/OntologySummit2012/
Community Wiki: http://ontolog.cim3.net/cgi-bin/wiki.pl?OntologySummit2012
Community Portal: http://ontolog.cim3.net/wiki/ (046)
_________________________________________________________________
Msg Archives: http://ontolog.cim3.net/forum/ontology-summit/
Subscribe/Config: http://ontolog.cim3.net/mailman/listinfo/ontology-summit/
Unsubscribe: mailto:ontology-summit-leave@xxxxxxxxxxxxxxxx
Community Files: http://ontolog.cim3.net/file/work/OntologySummit2012/
Community Wiki: http://ontolog.cim3.net/cgi-bin/wiki.pl?OntologySummit2012
Community Portal: http://ontolog.cim3.net/wiki/ (047)
|