NobleBlocks

Research indexJournal article

Sim-Tree

Xu, Tan

18 May 2014

NobleIDark:/48914/w1/20260515/6E4F0F25DOI10.1145/2601381.2601388

Paywalled

The full text is at the publisher

You can read the abstract here, or open it at the publisher.

Read at the publisher

Abstract

Performance is one of the major concerns in large-scale parallel microscopic traffic simulations. This paper focuses on one of the most time-costly data structures: the two-dimensional spatial index. A drawback of using popular two-dimensional tree-based spatial indexes (e.g. the R*-Tree) in large-scale microscopic traffic simulation is the heavy cost to rebalance the tree structure when a large number of vehicles frequently update their locations. This heavy location update cost also reduces the scalability of parallel microscopic traffic simulations. We observe that in real-world traffic systems the road density during a short period is stable, which is not sensitive to an individual vehicle's location. Thus, why not build a balanced tree structure based on the average road density in a road network? Motivated by this observation, this paper proposes Sim-Tree. The key feature of the Sim-Tree is that there is no need to check or rebalance its tree structure when individual vehicles frequently update their locations. In addition, a rebalance function and a bottom-up region query function are designed to optimize Sim-Tree's region query operations. The results of experiments simulating a city-scale traffic scenario on a 6-core machine show that the Sim-Tree is scalable and performs significantly better than the R*-tree family of spatial indexes.

Discussion

Citations

Topics

More

Suggest a correction or report