Paper Information | SBC BOOKS

Fill in your paper information

Language (*)

Title (*)

Keywords (*)

Abstract (*)

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.

Pages (*)

File Link

English Information

Title

Keywords

Abstract

(*) To change the order drag the item to the new position.

Authors

#	Name
1	Mariana Duarte(mmgduarte@inf.ufpr.br)
2	Marcos Pontarolo(mvp19@inf.ufpr.br)
3	Rebeca Schroeder(rebeca.schroeder@udesc.br)
4	Carmem Hara(carmem@inf.ufpr.br)

(*) To change the order drag the item to the new position.

Reference

#	Reference
1	Aji, A., Vo, H., and Wang, F. (2015). Effective spatial data partitioning for scalable query processing. CoRR, abs/1509.00910
2	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
3	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
4	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
5	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
6	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
7	Gaede, V. and Günther, O. (1998). Multidimensional access methods. ACM Computing Surveys, 30(2):170–231
8	Guttman, A. (1984). R-trees: a dynamic index structure for spatial searching. ACM Sigmod Record, 14(2):47–57
9	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
10	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
11	Mahmood, A. R., Punni, S., and Aref, W. G. (2019). Spatio-temporal access methods: a survey (2010 - 2017). Geoinformatica, 23:1–36
12	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
13	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
14	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
15	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
16	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
17	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
18	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
19	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
20	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
21	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
22	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
23	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
24	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
25	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

Paper Registration

Fill in your paper information

English Information

Authors

Reference