Compressing Optimal Paths with Run Length Encoding
Authors: Ben Strasser, Adi Botea, Daniel Harabor
JAIR 2015 | Venue PDF | Archive PDF | Plain Text | 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. |