Partition search for non-binary constraint satisfaction. (English) Zbl 1119.68446
Summary: Previous algorithms for unrestricted constraint satisfaction use reduction search, which inferentially removes values from domains in order to prune the backtrack search tree. This paper introduces partition search, which uses an efficient join mechanism instead of removing values from domains. Analytical prediction of quantitative performance of partition search appears to be intractable and evaluation therefore has to be by experimental comparison with reduction search algorithms that represent the state of the art. Instead of working only with available reduction search algorithms, this paper introduces enhancements such as semijoin reduction preprocessing using Bloom filtering.
MSC:
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
Keywords:
constraint satisfaction; non-binary constraints; hash join; multijoin; decision diagram; BDD; consistency; forward checking; semijoin reduction; dual search; partition search; random problemsReferences:
| [1] | Achlioptas, D.; Molloy, M. S.O.; Kirousis, L. M.; Stamatiou, Y. C.; Kranakis, E.; Krizanc, D., Random constraint satisfaction: a more accurate picture, Constraints, 6, 4, 329-344 (2001) · Zbl 0984.68085 |
| [2] | Al-Suwaiyel, M.; Horowitz, E., Algorithms for trie compaction, ACM Trans. Database Syst., 9, 243-263 (1984) · Zbl 0542.68079 |
| [3] | Aoe, J.; Morimoto, K.; Shishibori, M.; Park, K.-H., A trie compaction algorithm for a large set of keys, IEEE Trans. Data Knowledge Eng., 8, 476-491 (1996) |
| [4] | Artymiuk, P. J.; Grindley, H. M.; Poirrette, A. R.; Rice, D. W.; Ujah, E. C.; Willett, P., Identification of β-sheet motifs, of \(ψ\)-loops and of patterns of amino-acid residues in three-dimensional protein structures using a subgraph-isomorphism algorithm, J. Chem. Inform. Comput. Sci., 34, 54-62 (1994) |
| [5] | Babb, E., Implementing a relational database by means of specialized hardware, ACM Trans. Database Syst., 4, 1-29 (1979) |
| [6] | B. Babcock, S. Chaudhuri, Towards a robust query optimizer: a principled and practical approach, in: Proceedings ACM SIGMOD, Baltimore, MD, 2005, pp. 119-130.; B. Babcock, S. Chaudhuri, Towards a robust query optimizer: a principled and practical approach, in: Proceedings ACM SIGMOD, Baltimore, MD, 2005, pp. 119-130. |
| [7] | Bacchus, F.; van Run, P., Dynamic variable ordering in CSPs, Lecture Notes in Computer Science, vol. 976 (1995), Springer: Springer New York, pp. 258-275 |
| [8] | F. Bacchus, P. van Beek, On the conversion between non-binary and binary constraint satisfaction problems, in: Proceedings of AAAI’98, Madison, WI, 1998, pp. 310-318.; F. Bacchus, P. van Beek, On the conversion between non-binary and binary constraint satisfaction problems, in: Proceedings of AAAI’98, Madison, WI, 1998, pp. 310-318. |
| [9] | Bacchus, F.; Chen, X.; van Beek, P.; Walsh, T., Binary vs. non-binary constraints, Artif. Intell., 140, 1-37 (2002) · Zbl 0999.68201 |
| [10] | S. Bandyopadhyay, Q. Fu, A. Sengupta, A cyclic multi-relation semijoin operation for query optimization in distributed databases, in: Proceedings of IEEE International Conference on Performance, Computing, and Communications (IPCCC’00), 2000, pp. 101-107.; S. Bandyopadhyay, Q. Fu, A. Sengupta, A cyclic multi-relation semijoin operation for query optimization in distributed databases, in: Proceedings of IEEE International Conference on Performance, Computing, and Communications (IPCCC’00), 2000, pp. 101-107. |
| [11] | Beacham, A.; Chen, X.; Sillito, J.; van Beek, P., Constraint programming lessons learned from crossword puzzles, Lecture Notes in Computer Science, vol. 2056 (2001), Springer: Springer New York, pp. 78-87 · Zbl 0986.90080 |
| [12] | Bernstein, P. A.; Chiu, D-M. W., Using semi-joins to solve relational queries, JACM, 28, 1, 25-40 (1981) · Zbl 0454.68126 |
| [13] | C. Bessière, J.C. Régin, MAC and combined heuristics: two reasons to forsake FC (and CBJ?) on hard problems, in: Proceedings of CP’96, Cambridge, MA, 1996, pp. 61-75.; C. Bessière, J.C. Régin, MAC and combined heuristics: two reasons to forsake FC (and CBJ?) on hard problems, in: Proceedings of CP’96, Cambridge, MA, 1996, pp. 61-75. |
| [14] | C. Bessière, J.C. Régin, Refining the basic arc consistency algorithm, in: Proceedings of IJCAI-01, Seattle, WA, 2001, pp. 309-315.; C. Bessière, J.C. Régin, Refining the basic arc consistency algorithm, in: Proceedings of IJCAI-01, Seattle, WA, 2001, pp. 309-315. |
| [15] | Bessière, C.; Meseguer, P.; Freuder, E. C.; Larrosa, J., On forward checking for non-binary constraint satisfaction, Artif. Intell., 141, 205-224 (2002) · Zbl 1043.68090 |
| [16] | Bruno, I. J.; Kemp, N. M.; Artymiuk, P. J.; Willett, P., Representation and searching of carbohydrate structures using graph-theoretic techniques, Carbohyd. Res., 304, 61-67 (1997) |
| [17] | Bryant, R. E., Graph-based algorithms for Boolean function manipulation, IEEE Trans. Comput., C-35, 677-691 (1986) · Zbl 0593.94022 |
| [18] | Bryant, R. E., Symbolic Boolean manipulation with ordered binary-decision diagrams, ACM Comput. Surv., 24, 293-318 (1992) |
| [19] | Chen, M-S.; Yu, P. S.; Wu, K-L., Optimization of parallel execution for multi-join queries, IEEE Trans. Knowledge Data Eng., 8, 416-428 (1996) |
| [20] | Cohen, D.; Jeavons, P.; Gault, R., New tractable classes from old, Constraints, 8, 263-282 (2003) · Zbl 1057.68113 |
| [21] | Comer, D., Analysis of a heuristic for full trie minimization, ACM Trans. Database Syst., 6, 513-537 (1981) · Zbl 0461.68068 |
| [22] | Cooper, M. C., Estimating optimal parameters for parallel database hardware, Int. J. Syst. Sci., 23, 119-125 (1992) · Zbl 0742.68017 |
| [23] | Debruyne, R.; Bessière, C., Domain filtering consistencies, J. Artif. Intell. Res., 14, 205-230 (2001) · Zbl 0970.68125 |
| [24] | Dechter, R., Constraint Processing (2003), Morgan Kaufman: Morgan Kaufman San Fransisco |
| [25] | A. Dechter, R. Dechter, Removing redundancies in constraint networks, in: Proceedings of the AAAI-87, Seattle, WA, 1987, pp. 105-109.; A. Dechter, R. Dechter, Removing redundancies in constraint networks, in: Proceedings of the AAAI-87, Seattle, WA, 1987, pp. 105-109. |
| [26] | Dechter, R.; Pearl, J., Network-based heuristics for constraint-satisfaction problems, Artif. Intell., 34, 1-38 (1988) · Zbl 0643.68156 |
| [27] | Dechter, R.; Pearl, J., Tree clustering for constraint networks, Artif. Intell., 38, 253-266 (1989) |
| [28] | Dechter, R.; Rish, I., Mini-buckets: a general scheme for bounded inference, JACM, 50, 107-153 (2003) · Zbl 1326.68335 |
| [29] | Dreschsler, R.; Sieling, D., Binary decision diagrams in theory and practice, Int. J. Software Tools Technol. Transf., 3, 112-136 (2001) · Zbl 1002.68583 |
| [30] | D. Frost, R. Dechter, Look-ahead value ordering for constraint satisfaction problems, in: Proceedings of IJCAI’95, Montreal, Canada, 1995, pp. 572-578.; D. Frost, R. Dechter, Look-ahead value ordering for constraint satisfaction problems, in: Proceedings of IJCAI’95, Montreal, Canada, 1995, pp. 572-578. |
| [31] | Frost, D.; Dechter, R., Maintenance scheduling problems as benchmarks for constraint algorithms, Ann. Math. Artif. Intell., 26, 149-170 (1999) · Zbl 0940.68037 |
| [32] | A. Galindo-Legaria, Outerjoins as disjunctions, in: Proceedings of the 1994 ACM SIGMOD Conference, Minneapolis, MN, 1994, pp. 348-358.; A. Galindo-Legaria, Outerjoins as disjunctions, in: Proceedings of the 1994 ACM SIGMOD Conference, Minneapolis, MN, 1994, pp. 348-358. |
| [33] | Garcia-Molina, H.; Ullman, J. D.; Widom, J., Database Systems: The Complete Book (2002), Prentice Hall: Prentice Hall Upper Saddle River, NJ |
| [34] | Gent, I. P.; Macintyre, E.; Prosser, P.; Smith, B. M.; Walsh, T., Random constraint satisfaction: flaws and structure, Constraints, 6, 345-372 (2001) · Zbl 0992.68193 |
| [35] | M. Ginsberg, M. Frank, M. Halpin, M. Torrance, Search lessons learned from crossword puzzles, in: Proceedings of AAAI-90, Boston, MA, 1990, pp. 210-215.; M. Ginsberg, M. Frank, M. Halpin, M. Torrance, Search lessons learned from crossword puzzles, in: Proceedings of AAAI-90, Boston, MA, 1990, pp. 210-215. |
| [36] | Golomb, S. W.; Baumert, L. D., Backtrack programming, JACM, 12, 4, 516-524 (1965) · Zbl 0139.12305 |
| [37] | Gopal, R. D.; Ramesh, R.; Zionts, S., Criss-cross hash joins: design and analysis, IEEE Trans. Knowledge Data Eng., 13, 4, 637-653 (2001) |
| [38] | Gyssens, M.; Jeavons, P. G.; Cohen, D. A., Decomposing constraint satisfaction problems using database techniques, Artif. Intell., 66, 57-89 (1994) · Zbl 0803.68090 |
| [39] | T. Hadzic, S. Subbarayan, R.M. Jensen, H.R. Andersen, J. Møller, H. Hulgaard, Fast backtrack-free product configuration using a precompiled solution space representation, in: Proceedings of International Conference on Economic, Technical and Organisational Aspects of Product Configuration Systems, Copenhagen, 2004, pp. 131-138.; T. Hadzic, S. Subbarayan, R.M. Jensen, H.R. Andersen, J. Møller, H. Hulgaard, Fast backtrack-free product configuration using a precompiled solution space representation, in: Proceedings of International Conference on Economic, Technical and Organisational Aspects of Product Configuration Systems, Copenhagen, 2004, pp. 131-138. |
| [40] | Haralick, R. M.; Davis, L. S.; Rosenfeld, A.; Milgram, D. L., Reduction operations for constraint satisfaction, Inform. Sci., 14, 199-219 (1978) · Zbl 0416.68042 |
| [41] | Haralick, R. M.; Elliott, G. L., Increasing tree search efficiency for constraint satisfaction problems, Artif. Intell., 14, 263-313 (1980) |
| [42] | Hsiao, H-I.; Chen, C-S.; Yu, P. S., Parallel execution of hash joins in parallel databases, IEEE Trans. Parallel Distrib. Syst., 8, 872-883 (1997) |
| [43] | I.F. Ilyas, V. Markl, P. Haas, P. Brown, A. Aboulnaga, CORDS: automatic discovery of correlations and soft functional dependencies, in: Proceedings of ACM SIGMOD, Paris, France, 2004, pp. 647-658.; I.F. Ilyas, V. Markl, P. Haas, P. Brown, A. Aboulnaga, CORDS: automatic discovery of correlations and soft functional dependencies, in: Proceedings of ACM SIGMOD, Paris, France, 2004, pp. 647-658. |
| [44] | P. Janssen, P. Jégou, R. Nouguier, M.C. Vilarem, A filtering process for general constraint satisfaction problems, in: Proceedings of the IEEE International Workshop on Tools for Artificial Intelligence, Fairfax, VA, 1989, pp. 420-427.; P. Janssen, P. Jégou, R. Nouguier, M.C. Vilarem, A filtering process for general constraint satisfaction problems, in: Proceedings of the IEEE International Workshop on Tools for Artificial Intelligence, Fairfax, VA, 1989, pp. 420-427. |
| [45] | Kossmann, D., State of the art in distributed query processing, ACM Comp. Surv., 32, 422-469 (2000) |
| [46] | Kossmann, D.; Stocker, K., Iterative dynamic programming: a new class of query optimization algorithms, ACM Trans. Database Syst., 25, 43-82 (2001) |
| [47] | Larrosa, J.; Dechter, R., Boosting search with variable elimination in constraint optimization and constraint satisfaction problems, Constraints, 8, 303-326 (2003) · Zbl 1057.68114 |
| [48] | Larrosa, J.; Morancho, E.; Niso, D., On the practical use of variable elimination in constraint optimization problems: ‘Still-life’ as a case study, J. Artif. Intell. Res., 23, 421-440 (2005) · Zbl 1081.90074 |
| [49] | C. Lecoutre, F. Boussemart, F. Hemery, Backjump-based techniques versus conflict directed heuristics, in: Proceedings of the 16th IEEE International Conference on Tools with Artificial Intelligence (ICTAI’04), 2004, pp. 549-557.; C. Lecoutre, F. Boussemart, F. Hemery, Backjump-based techniques versus conflict directed heuristics, in: Proceedings of the 16th IEEE International Conference on Tools with Artificial Intelligence (ICTAI’04), 2004, pp. 549-557. |
| [50] | Z. Li, K.A. Ross, PERF join: an alternative to two-way semijoin and bloomjoin, in: Proceedings of the Fourth International Conference on Information and Knowledge Management, Baltimore, MD, 1995, pp. 137-144.; Z. Li, K.A. Ross, PERF join: an alternative to two-way semijoin and bloomjoin, in: Proceedings of the Fourth International Conference on Information and Knowledge Management, Baltimore, MD, 1995, pp. 137-144. |
| [51] | Lynce, I.; Marques-Silva, J. P., An overview of backtrack search satisfiability algorithms, Ann. Math. Artif. Intell., 37, 3, 307-326 (2003) · Zbl 1010.68069 |
| [52] | Mackworth, A. K., Consistency in networks of relations, Artif. Intell., 8, 1, 99-118 (1977) · Zbl 0341.68061 |
| [53] | Maier, D., The Theory of Relational Databases (1983), Computer Science Press: Computer Science Press Rockville, MD · Zbl 0519.68082 |
| [54] | Mamoulis, N.; Stergiou, K., Solving non-binary CSPs using the hidden variable encoding, (Walsh, T., Proceedings of CP 2001. Proceedings of CP 2001, Lecture Notes in Computer Science, vol. 2239 (2001), Springer: Springer Berlin), 168-182 · Zbl 1067.68651 |
| [55] | V. Markl, V. Raman, D. Simmen, G. Lohman, H. Pirahesh, M. Cilimdzic, Robust query processing through progressive optimization, in: Proceedings of ACM SIGMOD Conference, Paris, France, 2004, pp. 659-670.; V. Markl, V. Raman, D. Simmen, G. Lohman, H. Pirahesh, M. Cilimdzic, Robust query processing through progressive optimization, in: Proceedings of ACM SIGMOD Conference, Paris, France, 2004, pp. 659-670. |
| [56] | McCall, J. T.; Tront, J. G.; Gray, F. G.; Haralick, R. M.; McCormack, W. M., Parallel computer architectures and problem solving strategies for the consistent labelling problem, IEEE Trans. Comput., C-34, 973-980 (1985) |
| [57] | McGregor, J. J., Relational consistency algorithms and their application in finding subgraph and graph isomorphisms, Inform. Sci., 19, 229-250 (1979) · Zbl 0442.68065 |
| [58] | Mishra, P.; Eich, M. H., Join processing in relational databases, ACM Comput. Surv., 24, 63-113 (1992) |
| [59] | Mitzenmacher, M., Compressed Bloom filters, IEEE/ACM Trans. Network., 10, 604-612 (2002) |
| [60] | Montanari, U., Networks of constraints: Fundamental properties and applications to picture processing, Inform. Sci., 7, 95-132 (1974) · Zbl 0284.68074 |
| [61] | J.M. Morrissey, W.K. Osborn, Y. Liang, Collisions and reduction filters in distributed query processing, in: Proceedings of 2000 Canadian Conference on Electrical and Computer Engineering, Halifax, Nova Scotia, vol. 1, 2000, pp. 240-244.; J.M. Morrissey, W.K. Osborn, Y. Liang, Collisions and reduction filters in distributed query processing, in: Proceedings of 2000 Canadian Conference on Electrical and Computer Engineering, Halifax, Nova Scotia, vol. 1, 2000, pp. 240-244. |
| [62] | Mullin, J. K., Optimal semijoins for distributed database systems, IEEE Trans. Software Eng., 16, 558-560 (1990) |
| [63] | Nagarajan, S.; Goodwin, S. D.; Sattar, A., Extending dual arc consistency, Int. J. Pattern Recogn. Artif. Intell., 17, 5, 781-815 (2003) |
| [64] | N. Narodytska, T. Walsh, Constraint and variable ordering heuristics for compiling configuration problems, in: Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, 2007, pp. 149-154.; N. Narodytska, T. Walsh, Constraint and variable ordering heuristics for compiling configuration problems, in: Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, 2007, pp. 149-154. |
| [65] | Prosser, P., An empirical study of phase transitions in binary constraint satisfaction problems, Artif. Intell., 81, 81-109 (1996) · Zbl 1523.68093 |
| [66] | D. Sabin, E.C. Freuder, Contradicting conventional wisdom in constraint satisfaction, in: A. Borning (Ed.), Proceedings of the Second International Workshop on Principles and Practice of Constraint Programming, PPCP’94, Rosario, Orcas Island, Washington, published as Lecture Notes in Computer Science, vol. 874, 1994, pp. 10-20.; D. Sabin, E.C. Freuder, Contradicting conventional wisdom in constraint satisfaction, in: A. Borning (Ed.), Proceedings of the Second International Workshop on Principles and Practice of Constraint Programming, PPCP’94, Rosario, Orcas Island, Washington, published as Lecture Notes in Computer Science, vol. 874, 1994, pp. 10-20. |
| [67] | Samaras, N.; Stergiou, K., Binary encodings of non-binary constraint satisfaction problems: algorithms and experimental results, J. Artif. Intell. Res., 24, 641-684 (2005) · Zbl 1080.68673 |
| [68] | P.G. Selinger, M.M. Astrahan, D.D. Chamberlin, R.A. Lorie, T.G. Price, Access path selection in a relational database management system, in: Proceedings of ACM 1979 SIGMOD Conference, Boston, MA, 1979, pp. 23-34.; P.G. Selinger, M.M. Astrahan, D.D. Chamberlin, R.A. Lorie, T.G. Price, Access path selection in a relational database management system, in: Proceedings of ACM 1979 SIGMOD Conference, Boston, MA, 1979, pp. 23-34. |
| [69] | Shapiro, L. D., Join processing in database systems with large main memories, ACM Trans. Database Syst., 11, 239-264 (1986) |
| [70] | Smith, B. M.; Dyer, M. E., Locating the phase transition in binary constraint satisfaction problems, Artif. Intell., 81, 155-181 (1996) · Zbl 1508.68348 |
| [71] | K. Stergiou, T. Walsh, Encodings of non-binary constraint satisfaction problems, in: Proceedings of AAAI’99, 1999, pp. 163-168.; K. Stergiou, T. Walsh, Encodings of non-binary constraint satisfaction problems, in: Proceedings of AAAI’99, 1999, pp. 163-168. |
| [72] | S. Subbarayan, R.M. Jensen, T. Hadzic, H.R. Andersen, J. Møller, H. Hulgaard, Comparing two implementations of a complete and backtrack-free interactive configurator, in: Proceedings of the CP-04 Workshop on CSP Techniques with Immediate Application, Toronto, Canada, 2004, pp. 97-111.; S. Subbarayan, R.M. Jensen, T. Hadzic, H.R. Andersen, J. Møller, H. Hulgaard, Comparing two implementations of a complete and backtrack-free interactive configurator, in: Proceedings of the CP-04 Workshop on CSP Techniques with Immediate Application, Toronto, Canada, 2004, pp. 97-111. |
| [73] | Tarjan, R. E.; Yannakakis, M., Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. Comput., 13, 566-579 (1984) · Zbl 0545.68062 |
| [74] | Ullman, J. D., Principles of Database and Knowledge-Base systems, vol. 1 (1988), Computer Science Press: Computer Science Press Rockville, MD |
| [75] | Ullmann, J. R., Associating parts of patterns, Inform. Control, 9, 6, 583-601 (1966) · Zbl 0148.40603 |
| [76] | Ullmann, J. R., An algorithm for subgraph isomorphism, JACM, 23, 1, 31-42 (1976) · Zbl 0323.05138 |
| [77] | Ullmann, J. R., A binary n-gram technique for automatic correction of substitution, deletion, insertion and reversal errors in words, Comput. J., 20, 2, 141-147 (1977) · Zbl 0359.68121 |
| [78] | Ullmann, J. R., A relational view of text image processing, (Haralick, R. M.; Simon, J. C., Issues in Digital Image Processing (1980), Sijthoff and Noordhoff, Alphen aan den Rijn: Sijthoff and Noordhoff, Alphen aan den Rijn The Netherlands), 139-169 |
| [79] | Ullmann, J. R., Discrete optimization by relational constraint satisfaction, IEEE Trans. Pattern Anal. Mach. Intell., PAMI-4, 5, 544-550 (1982) · Zbl 0497.49027 |
| [80] | Ullmann, J. R., Fast implementation of relational operations via inverse projection, Comput. J., 31, 2, 147-154 (1988) |
| [81] | Ullmann, J. R.; Haralick, R. M.; Shapiro, L. G., Computer architecture for solving consistent labeling problems, Comput. J., 28, 2, 105-111 (1985) · Zbl 0567.68028 |
| [82] | Van Hentenryck, P.; Deville, Y.; Tang, C-M., A generic arc-consistency algorithm and its specializations, Artif. Intell., 57, 291-321 (1992) · Zbl 0763.68059 |
| [83] | M.Y. Vardi, Constraint satisfaction and database theory: a tutorial, in: Proceedings of the 19th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, Dallas, TX, 2000, pp. 76-85.; M.Y. Vardi, Constraint satisfaction and database theory: a tutorial, in: Proceedings of the 19th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, Dallas, TX, 2000, pp. 76-85. |
| [84] | I. Wegener, Branching programs and binary decision diagrams, SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, PA, 2000.; I. Wegener, Branching programs and binary decision diagrams, SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, PA, 2000. · Zbl 0956.68068 |
| [85] | Xu, K.; Li, W., An average analysis of backtracking on random constraint satisfaction problems, Ann. Math. Artif. Intell., 33, 21-37 (2001) · Zbl 1314.68165 |
| [86] | Y. Zhang, A.K. Mackworth, Parallel and distributed algorithms for finite constraint satisfaction problems, in: Proceedings of the third IEEE Symposium on parallel distributed computing, Dallas, TX, 1991, pp. 394-397.; Y. Zhang, A.K. Mackworth, Parallel and distributed algorithms for finite constraint satisfaction problems, in: Proceedings of the third IEEE Symposium on parallel distributed computing, Dallas, TX, 1991, pp. 394-397. |
| [87] | Y. Zhang, R.Yap, Making AC-3 an optimal algorithm, in: Proceedings of 17th International Joint Conference on Artificial Intelligence, 2001, pp. 316-321.; Y. Zhang, R.Yap, Making AC-3 an optimal algorithm, in: Proceedings of 17th International Joint Conference on Artificial Intelligence, 2001, pp. 316-321. |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
