A Cache Sensitive moving object index that supports concurrent access

Current literature on indexing current and future positions of the moving objects lacks of the mechanisms on concurrent access. To solve this problem an efficient moving object index that supports concurrent access is proposed which is called CS²B-tree(Concurrent Space-filling curve enabled Cache Sensitive B⁺-tree). CS²B-tree combines the characteristics of both the B^x-tree and CSB⁺-tree, thus it can support querying the predicted future positions of the moving objects and is cache sensitive. Focus is put on studying a concurrent access mechanism to CS²B-tree which results in a two-level lock mechanism and particularly a lock memo structure is designed. Based on the concurrent access mechanism, a CS²B-tree concurrent location update algorithm and a concurrent predicted range query algorithm are proposed respectively. Experimental results show that compared to B^x-tree, the throughput of the CS²B-tree improves by 15.1%, and the response time decreases by 14.9%.