Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Compressing Optimal Paths with Run Length Encoding
Authors: Ben Strasser, Adi Botea, Daniel Harabor
JAIR 2015 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our algorithm achieves query running times on the 100 nanosecond scale, being significantly faster than state-of-the-art first-move oracles from the literature. Space consumption is competitive, due to a compression approach that rearranges rows and columns in a first-move matrix and then performs run length encoding (RLE) on the contents of the matrix. [...] We undertake a detailed empirical analysis including comparisons of our techniques with state-of-the-art variants of CPDs (Botea, 2012), and Hub-Labeling (Delling, Goldberg, Pajor, & Werneck, 2014). |
| Researcher Affiliation | Collaboration | Ben Strasser EMAIL Karlsruhe Institute of Technology Karlsruhe, Germany Adi Botea EMAIL IBM Research Dublin, Ireland Daniel Harabor EMAIL NICTA Sydney, Australia |
| Pseudocode | No | The paper describes algorithmic steps in paragraph text within Section 9.3 'Compressing Rows with Run Length Encoding' but does not present them in a structured pseudocode block or explicitly labeled algorithm figure. |
| Open Source Code | No | The paper mentions using the original C++ implementations of third-party algorithms (Copa-G, Copa-R) in Section 11.3, but it does not provide any explicit statement or link for the source code of the authors' own methodology (SRC and MRC). |
| Open Datasets | Yes | The first two sets of benchmark instances have appeared in the 2012 Grid-Based Path Planning Competition. The third benchmark set consists of two worst case maps... available as part of Nathan Sturtevant’s extended problem repository at http://movingai.com/benchmarks/. [...] In the case of road graphs we have chosen several smaller benchmarks made available during the 9th DIMACS challenge (Demetrescu et al., 2009). |
| Dataset Splits | Yes | To measure the query performance we run 10^8 random queries with source and target nodes picked uniformly at random and average their running times. |
| Hardware Specification | Yes | Our experiments were performed on a quad core i7-3770 CPU @ 3.40GHz with 8MB of combined cache, 8GB of RAM running Ubuntu 13.10. All algorithms were compiled using g++ 4.8.1 with -O3. All reported query times use a single core. [...] These experiments were carried out on a Xeon E5-2690 @ 2.90 GHz. [...] The ost100d and The Frozen Sea preprocessing experiments were run on an AMD Opteron 6172 with 48 cores @ 2.1 GHz to accelerate the APSP computation. |
| Software Dependencies | Yes | All algorithms were compiled using g++ 4.8.1 with -O3. |
| Experiment Setup | Yes | To measure the query performance we run 10^8 random queries with source and target nodes picked uniformly at random and average their running times. [...] We required node IDs to be encodable in 28 bits and out-edge IDs in 4 bits. We encode each run’s start in the upper 28 bits of a 32-bit machine word and its value in the lower 4 bits. |