MP-trie: Fast spatial queries on moving objects

Abstract

As spatial data being collected by various industries (e.g., telecommunication, insurance, automotive) is on the increase, indexing and answering queries extremely quickly is necessary. This paper proposes a new mechanism, Mobile PATRICIA-trie (MP-trie), for fast queries on moving objects that provides a 1000x improvement in performance over state-ofthe-art spatial indexing mechanisms. We reduce the problem of spatial indexing to that of prefix-matching over binary strings, which is then coupled with off-the-shelf commercially available content-addressable memory (commonly used in IP routers for forwarding table lookups). We validate our approach on data collected from a real-world deployment in Stockholm, Sweden across 2000 cars for a period of one month.