Efficient Path Consistency Algorithm for Large Qualitative Constraint Networks
Authors: Zhiguo Long, Michael Sioutis, Sanjiang Li
IJCAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our experimental results with both real-world and synthetic datasets also confirm in practice that DPC+ can be significantly more efficient than PPC (and PC). and 5 Experimental Results We evaluate the performance of our implementation of the DPC+ algorithm, against an implementation of the state-of-the-art PPC enforcing algorithm (PPC), for QCNs that are defined over a distributive subalgebra. |
| Researcher Affiliation | Academia | Zhiguo Long QCIS, FEIT University of Technology Sydney Australia zhiguo.long@student.uts.edu.au Michael Sioutis CRIL-CNRS UMR 8188 University of Artois France sioutis@cril.fr Sanjiang Li UTS-AMSS Joint Lab QCIS, FEIT University of Technology Sydney Australia Sanjiang.Li@uts.edu.au |
| Pseudocode | Yes | Algorithm 1: DPC(N, ) and Algorithm 2: DPC+(N, ) |
| Open Source Code | No | The paper mentions that 'All algorithms were coded in Python and run with Py Py 2.2.1 [Py Py Team, 2015], which implements Python 2.7.' but does not provide a link or explicit statement about the availability of *their* specific implementation code. |
| Open Datasets | Yes | We considered random RCC8 networks generated by the BA(n, m) model [Barabasi and Albert, 1999]... Regarding real-world RCC8 datasets, we employed the ones recently used in [Sioutis et al., 2015b; Li et al., 2015], viz., nuts (nomenclature of territorial units)2... adm1 (administrative geography of Great Britain) [Goodwin et al., 2008]... gadm1 (German administrative units)2... gadm2 (the world s administrative areas) [Geo Vocab, 2012]... adm2 (the administrative geography of Greece)2... fprints (geographic footprints in the Southampton area of the UK) [Li et al., 2015]... and stareas (statistical areas in Tasmania) [Li et al., 2015]. and 2Retrieved from: http://www.linkedopendata.gr/ |
| Dataset Splits | No | The paper provides details about the datasets used but does not specify any training, validation, or test splits, nor does it mention cross-validation or stratified splitting. |
| Hardware Specification | Yes | The experimentation was carried out on a computer with an Intel Core i7-2820QM processor with a 2.30 GHz frequency per CPU core, 8 GB of RAM, and the Trusty Tahr x86 64 OS. |
| Software Dependencies | Yes | All algorithms were coded in Python and run with Py Py 2.2.1 [Py Py Team, 2015], which implements Python 2.7. |
| Experiment Setup | Yes | We considered 10 satisfiable RCC8 networks of model BA(n, m) for each order 1000 n 10000 of their constraint graphs with a 1000-vertex step and a preferential attachment value of m = 2. The edges of these graphs were labelled with relations from the maximal distributive subclass D64 8 of RCC8 [Li et al., 2015]. and The maximum cardinality search algorithm [Tarjan and Yannakakis, 1984] was used to obtain a variable elimination ordering for DPC and DPC+, and a triangulation of the constraint graph of a given QCN for PPC as described in [Sioutis et al., 2015a]. |