MIDET: A Method for Indexing Traffic Events

• Mariana M. G. Duarte Universidade Federal do Paraná (UFPR)
• Marcos V. Pontarolo Universidade Federal do Paraná (UFPR)
• Rebeca Schroeder Universidade do Estado de Santa Catarina (UDESC)
• Carmem S. Hara Universidade Federal do Paraná (UFPR)

DOI: https://doi.org/10.5753/sbbd.2021.17879

Resumo

Traffic events announcements such as jams and road closures are continuously reported by mobile and Web applications. This collection of spatio-temporal data is an important source of information for urban planning, and can be used to orchestrate a number of actions to mprove the mobility, such as traffic control, traffic lights synchronization and preventive maintenance. Such analysis usually involves computation of spatial relationships among data, and may involve location of landmarks, roads and different types of events. In this paper, we propose a Method for Indexing Traffic Events (MIDET) for querying spatio-temporal data, whose location can be represented as a point or collection of points. MIDET is based on a fixed-grid space-oriented partitioning. In order to tackle the data skew, each grid cell is associated with a set of blocks containing event records. Moreover, a bitmap index is used for filtering out blocks without retrieving the actual data. MIDET provides the following benefits: adoption of a simple bulk loading process to manage dynamic insertion streams, and in-memory spatial joins. We conducted an experimental study using real data obtained from Waze. MIDET’s query performance was compared with Postgis, which adopts an R-tree index structure.

Palavras-chave: index structure, bitmap, traffic events, space-oriented indexing

Referências

Aji, A., Vo, H., and Wang, F. (2015). Effective spatial data partitioning for scalable query processing. CoRR, abs/1509.00910.

Al-Badarneh, A. F., Al-Alaj, A. S., and Mahafzah, B. A. (2013). Multi small index (MSI): A spatial indexing structure. Journal of Information Science, 39(5):643–660.

Antoine, E., Ramamohanarao, K., Shao, J., and Zhang, R. (2011). Accelerating spatial join operations using bit-indices. In Proc. of the 22nd Australasian Database Conference, volume 115, page 123–132.

Chaudhry, N., Yousaf, M. M., and Khan, M. T. (2020). Indexing of real time geospatial data by IoT enabled devices: Opportunities, challenges and design considerations. Journal of Ambient Intelligence and Smart Environments, 12:281–312.

Doraiswamy, H., Vo, H. T., Silva, C. T., and Freire, J. (2016). A GPU-Based Index to Support Interactive Spatio-Temporal Queries over Historical Data. In 2016 IEEE 32nd International Conference on Data Engineering (ICDE), Helsinki, Finland.

Eldawy, A. and Mokbel, M. F. (2015). Spatialhadoop: A mapreduce framework for spatial data. In Proc. of the 31st International Conference on Data Engineering, pages 1352–1363.

Gaede, V. and Günther, O. (1998). Multidimensional access methods. ACM Computing Surveys, 30(2):170–231.

Guttman, A. (1984). R-trees: a dynamic index structure for spatial searching. ACM Sigmod Record, 14(2):47–57.

Imawan, A., Putri, F., and Kwon, J. (2015). TiQ: A Timeline query processing system over Road Traffic Data. In 2015 IEEE International Conference on Smart City, Chengdu, China.

Lemire, D., Ssi-Yan-Kai, G., and Kaser, O. (2018). Consistently faster and smaller compressed bitmaps with roaring. Software: Practice and Experience, 46:1547–1569.

Mahmood, A. R., Punni, S., and Aref, W. G. (2019). Spatio-temporal access methods: a survey (2010-2017). Geoinformatica, 23:1–36.

Neto, C. J., Ciferri, R. R., and Santos, M. T. P. (2013). HSTB-index: A hierarchical spatio-temporal bitmap indexing technique. In SBBD-Workshop de Teses e Dissertações.

Nievergelt, J., Hinterberger, H., and Sevcik, K. C. (1984). The grid file: An adaptable, symmetric multikey file structure. ACM Transactions on Database Systems, 9(1):38–71.

Nobari, S., Qu, Q., and Jensen, C. S. (2017). In-memory spatial join: The data matters! In Proc. of the 20th International Conference on Extending Database Technology (EDBT), pages 462–465.

Patel, J. M. and DeWitt, D. J. (1996). Partition based spatial–merge join. In Proc. of the 1996 ACM SIGMOD international conference on Management of data, pages 259–270.

Patel, J. M., Yu, J., Kabra, N., Tufte, K. A., Nag, B., Burger, J., Hall, N. E., Ramasamy, K., Lueder, R., Ellmann, C. J., Kupsch, J., Guo, S., Larson, J. G., Witt, D. J. D., and Naughton, J. F. (1997). Building a scaleable geo-spatial dbms: technology, implemen- tation, and evaluation. In Proc. of the 1997 ACM SIGMOD international conference on Management of data, pages 336–347.

Pavlovic, M., Heinis, T., Tauheed, F., Karras, P., and Ailamaki, A. (2016). Transformers: Robust spatial joins on non-uniform data distributions. In Proc. of the 32nd International Conference on Data Engineering (ICDE), pages 673–684.

Sevcik, K. C. and Koudas, N. (1996). Filter trees for managing spatial data over a range of size granularities. In Proc. of the 22nd International Conference on Very Large Data Bases (VLDB), page 16–27.

Shin, J., Mahmood, A., and Aref, W. (2019). An investigation of grid-enabled tree indexes for spatial query processing. In Proceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 169–178.

Shohdy, S., Su, Y., and Agrawal, G. (2015). Load balancing and accelerating parallel spatial join operations using bitmap indexing. In Proc of the IEEE 22nd International Conference on High Performance Computing (HiPC), pages 396–405.

Siqueira, T. L. L., de Aguiar Ciferri, C. D., Times, V. C., and Ciferri, R. R. (2012). The SB-index and the HSB-index: efficient indices for spatial data warehouses. Geoinformatica, 16(1):165–205.

Tsitsigkos, D., Bouros, P., Mamoulis, N., and Terrovitis, M. (2019). Parallel in-memory evaluation of spatial joins. In Proc. of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 516–519.

Vo, H., Aji, A., and Wang, F. (2014). SATO: A spatial data partitioning framework for scalable query processing. In Proc. of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, page 545–548.

Wang, J., Lin, Y. C., and S., S. (2017). An experimental study of bitmap compression vs. inverted list compression. In Proceedings of the 2017 ACM SIGMOD International Conference on Management of Data, New York, NY.

Yu, J., Wu, J., and Sarwat, M. (2015). Geospark: A cluster computing framework for processing large-scale spatial data. In Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, New York, NY, USA. Association for Computing Machinery.