×

zbMATH — the first resource for mathematics

Efficient query processing with reduced implicate tries. (English) Zbl 1113.68044
Summary: The goal of knowledge compilation is to enable fast queries. Prior approaches had the goal of small (i.e., polynomial in the size of the initial knowledge bases) compiled knowledge bases. Typically, query-response time is linear, so that the efficiency of querying the compiled knowledge base depends on its size. In this paper, a target for knowledge compilation called the ri-trie is introduced; it has the property that even if the knowledge bases are large, they nevertheless admit fast queries. Specifically, a query can be processed in time linear in the size of the query regardless of the size of the compiled knowledge base.
MSC:
68P20 Information storage and retrieval of data
68P05 Data structures
68T30 Knowledge representation
Software:
PATRICIA
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bryant, R.E.: Symbolic boolean manipulation with ordered binary decision diagrams. ACM Comput. Surv. 24(3), 293–318 (1992) · doi:10.1145/136035.136043
[2] Cadoli, M., Donini, F.M.: A survey on knowledge compilation. AI Commun. 10, 137–150 (1997)
[3] Coudert, O., Madre, J.: Implicit and incremental computation of primes and essential implicant primes of boolean functions. In: Proceedings of the 29th ACM/IEEE Design Automation Conference, pp. 36–39. (1992)
[4] Darwiche, A.: Compiling devices: a structure-based approach. In: Proceedings, International Conference on Principles of Knowledge Representation and Reasoning (KR98), pp. 156–166. Morgan-Kaufmann, San Francisco, CA (1998)
[5] Darwiche, A.: Decomposable negation normal form. J. Assoc. Comput. Mach. 48(4), 608–647 (2001) · Zbl 1127.03321
[6] de Kleer, J.: An improved incremental algorithm for computing prime implicants. In: Proceedings of AAAI-92, pp. 780–785. San Jose, CA (1992)
[7] Forbus, K.D., de Kleer, J.: Building Problem Solvers. MIT, Cambridge, MA (1993)
[8] Hai, L., Jigui, S.: Knowledge compilation using the extension rule. J. Autom. Reason. 32(2), 93–102 (2004) · Zbl 1073.68078 · doi:10.1023/B:JARS.0000029959.45572.44
[9] Hähnle, R., Murray, N.V., Rosenthal, E.: Normal forms for knowledge dompilation. In: Ras, Z. (ed.) Proceedings of the International Symposium on Methodologies for Intelligent Systems, (ISMIS ’05), In: Lecture Notes in Artificial Intelligence, vol. 3488, pp. 304–313. Springer, Berlin Heidelberg New York (2005) · Zbl 1132.68550
[10] Jackson, P., Pais, J.: Computing prime implicants. In: Proceedings of the 10th International Conference on Automated Deductions, Kaiserslautern, Germany, July 1990. Lecture Notes in Artificial Intelligence, vol. 449, pp. 543–557. Springer, Berlin Heidelberg New York (1990)
[11] Jackson, P.: Computing prime implicants incrementally. In: Proceedings of the 11th International Conference on Automated Deduction, Saratoga Springs, NY, June 1992. Lecture Notes in Artificial Intelligence, vol. 607, pp. 253–267. Springer, Berlin Heidelberg New York (1992) · Zbl 0925.03054
[12] Kautz, H., Selman, B.: A general framework for knowledge compilation. In: Proceedings of the International Workshop on Processing Declarative Knowledge (PDK). Kaiserslautern, Germany (1991) · Zbl 0736.68044
[13] Kean, A., Tsiknis, G.: An incremental method for generating prime implicants/implicates. J. Symb. Comput. 9, 185–206 (1990) · Zbl 0704.68100 · doi:10.1016/S0747-7171(08)80029-6
[14] Kean, A., Tsiknis, G.: Assumption based reasoning and clause management systems. Comput. Intell. 8(1), 1–24 (1992) · doi:10.1111/j.1467-8640.1992.tb00335.x
[15] Marquis, P.: Knowledge compilation using theory prime implicates. In: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp. 837–843. Morgan-Kaufmann, San Mateo, CA (1995)
[16] Morrison, D.R.: PATRICIA – practical algorithm to retrieve information coded in alphanumeric. J. Assoc. Comput. Mach. 15(4), 514–34 (1968)
[17] Murray, N.V., Rosenthal, E.: Dissolution: making paths vanish. J. Assoc. Comput. Mach. 40(3), 504–535 (1993) · Zbl 0785.68083
[18] Murray, N.V., Rosenthal, E.: Duality in knowledge compilation techniques. In: Ras, Z. (ed.) Proceedings of the International Symposium on Methodologies for Intelligent Systems (ISMIS ’05). Lecture Notes in Artificial Intelligence, vol. 3488, pp. 182–190. Springer, Berlin Heidelberg New York (2005) · Zbl 1132.68577
[19] Murray, N.V., Rosenthal, E.: Efficient query processing with compiled knowledge bases. In: Proceedings of the International Conference TABLEAUX 2005 – Analytic Tableaux and Related Methods, Koblenz, Germany, September 2005. Lecture Notes in Artificial Intelligence, vol. 3702, pp. 231–244. Springer, Berlin Heidelberg New York (2005) · Zbl 1133.68326
[20] Murray, N.V., Rosenthal, E.: Tableaux, path dissolution, and decomposable negation normal form for knowledge compilation. In: Proceedings of the International Conference TABLEAUX 2003 – Analytic Tableaux and Related Methods, Rome, Italy, September 2003. Lecture Notes in Artificial Intelligence, vol. 2796, pp. 165–180. Springer, Berlin Heidelberg New York (2003) · Zbl 1274.03023
[21] Ngair, T.: A new algorithm for incremental prime implicate generation. In: Proceedings of IJCAI-93. Chambery, France (1993)
[22] Przymusinski, T.C.: An algorithm to compute circumscription. Artif. Intell. 38, 49–73 (1989) · Zbl 0663.68098 · doi:10.1016/0004-3702(89)90067-2
[23] Ramesh, A., Becker, G., Murray, N.V.: CNF and DNF considered harmful for computing prime implicants/implicates. J. Autom. Reason. 18(3), 337–356 (1997) (Kluwer) · Zbl 0881.68107 · doi:10.1023/A:1005721905269
[24] Ramesh, A., Murray, N.V.: An application of non-clausal deduction in diagnosis. Expert Syst. Appl. 12(1), 119–126 (1997) · doi:10.1016/S0957-4174(96)00086-3
[25] Reiter, R.: A theory of diagnosis from first principles. Artif. Intell. 32, 57–95 (1987) · Zbl 0643.68122 · doi:10.1016/0004-3702(87)90062-2
[26] Selman, B., Kautz, H.: Knowledge compilation and theory approximation. J. Assoc. Comput. Mach. 43(2), 193–224 (1996) · Zbl 0882.68137
[27] Slagle, J.R., Chang, C.L., Lee, R.C.T.: A new algorithm for generating prime implicants. IEEE Trans. Comput. C-19(4), 304–310 (1970) · Zbl 0197.14601 · doi:10.1109/T-C.1970.222917
[28] Strzemecki, T.: Polynomial-time algorithm for generation of prime implicants. J. Complex. 8, 37–63 (1992) · Zbl 0768.68061 · doi:10.1016/0885-064X(92)90033-8
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.