Developing technologies for utilizing a massive number of trajectories collected from moving objects like cars is one of the most critical issues in modern society. This paper aims to develop an indexing method for the trajectories of moving objects in road networks.

Considering that road networks are represented as directed graphs, trajectories are represented as the sequences of road segment IDs, i.e., strings on the set of edges that is defined as an alphabetical set. Then, we can process several types of path-based queries by applying an FM-index, which is a string indexing algorithm. However, there is an issue that the number of edges is numerous and indexing performance decreases in the case of applying FM-index for big data.

In this paper, we develop a novel compressed index structure based on the fact that road networks have the property of sparse graphs by the physical restriction of the network structure. We also describe associated query processing algorithms on the compressed index structure. Compared with existing methods that are applicable to big data, it is shown that our method can provide high compression performance and fast query processing ability through theoretical analysis. Furthermore, as a result of numerical experiments for several real trajectory datasets, we clarify that our method can process queries several times to several dozen times faster than the existing methods and significantly improves the compression ratio.

This paper has high novelty and utility. The reason is that this paper presents original ideas that are quite different from existing methods and demonstrates the superiority of this method from the viewpoints of both theoretical analysis and numerical experiments. The results of this paper are also expected to be utilized in a data-driven society, and this paper makes a significant contribution to the development of the field of data engineering. Therefore, this paper deserves the IEICE Best Paper Award.