COL-Trees: Efficient Hierarchical Object Search in Road Networks (Extended Abstract)

Abstract

COL-Trees are a state-of-the-art data structure for hierarchical object search in road network graphs. While initially developed with multi-agent scenarios in mind, we show COL-Trees are highly suitable for single-agent queries as well, in particular, supporting upper-bound based k Farthest Neighbor search for the first time. Along with reducing pre-processing costs, we strengthen the case that COL-Trees are a highly versatile data structure with potential application to other problems by the combinatorial search community. To support such exploration, we also present a highly-optimized COL-Tree implementation as open-source for the first time.