Chapter 9

Conclusion

In this work, we explored the problem of filtering real estate listings based on exact commute times to a specified destination within a fixed time budget. Unlike common radius or isochrone map based methods, our approaches compute exact travel time values for all listings that meet the time constraint.

We adapted and analyzed several shortest path algorithms: Dijkstra's algorithm, Dial's algorithm, Contraction Hierarchies, Hub Labeling, and Full Precomputation. Each method was evaluated in terms of query time, preprocessing effort, and memory usage, both theoretically and through real world performance benchmarks.

Our results show a clear tradeoff between preprocessing cost and query speed. Full Precomputation provides the fastest queries, but also requires very significant memory and preprocessing time. Hub labels and contraction hierarchies also offer very fast queries, though not as fast as full precomputation, at a much lower precomputation and memory cost. Finally, Dial's and Dijkstra's algorithms offer the benefit of no required precomputation.

The optimal choice of algorithm depends on the application’s constraints. These findings provide a practical foundation for implementing commute time based filtering in real estate platforms.