Spatial Join on Positional Uncertain Data

• Welder B. Oliveira Universidade Federal de Goiás
• Sávio S. T. Oliveira Universidade Federal de Goiás
• Vagner J. S. Rodrigues Universidade Federal de Goiás
• Helton S. B. Santos Universidade de Brasília
• Kleber V. Cardoso Universidade Federal de Goiás

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

Resumo

This paper presents a probabilistic spatial join on positional uncertain data designed to be a) generalist; b) accurate and c) efficient. A proposed progressive Monte Carlo algorithm is used in the refinement step and the Chebyshev inequality is applied in the filtering one in order to provide efficiency, efficacy and generality. The experiments show that the current propose is Pareto efficient concerning these requirements, i.e., it is not outperformed by any competing method. Also, the solution’s parameters relating accuracy and efficiency may be adjusted to maximize the gain in one while relaxing the other according to user’s demand.

Palavras-chave: Probabilistic Spatial Join, Monte Carlo algorithm, Chebyshev inequality, Pareto efficient

Referências

Arge, L., Procopiuc, O., Ramaswamy, S., Suel, T., and Vitter, J. S. (1998). Scalable sweeping-based spatial join. In VLDB, volume 98, pages 570–581. Citeseer.

Brinkhoff, T., Kriegel, H.-P., and Seeger, B. (1993). Efficient processing of spatial joins using R-trees, volume 22. ACM.

Dai, X., Yiu, M. L., Mamoulis, N., Tao, Y., and Vaitis, M. (2005). Probabilistic spatial queries on existentially uncertain data. In International Symposium on Spatial and Temporal Databases, pages 400–417. Springer.

Elmasri, R. (2008). Fundamentals of database systems. Pearson Education India.

Huang, Y.-W., Jing, N., and Rundensteiner, E. A. (1997). Spatial joins using r-trees: Breadth-first traversal with global optimizations. In VLDB, volume 97, pages 25–29.Citeseer.

Jacox, E. H. and Samet, H. (2003). Iterative spatial join. ACM Transactions on Database Systems (TODS), 28(3):230–256.

Ljosa, V. and Singh, A. K. (2008). Top-k spatial joins of probabilistic objects. In 2008 IEEE 24th International Conference on Data Engineering, pages 566–575. IEEE.

Lo, M.-L. and Ravishankar, C. V. (1994). Spatial joins using seeded trees. In ACM SIGMOD Record, volume 23, pages 209–220. ACM.

Luo, G., Naughton, J. F., and Ellmann, C. J. (2002). A non-blocking parallel spatial join algorithm. In Data Engineering, 2002. Proceedings. 18th International Conference on, pages 697–705. IEEE.

Mishra, P. and Eich, M. H. (1992). Join processing in relational databases. ACM Computing Surveys (CSUR), 24(1):63–113.

Ni, J., Ravishankar, C. V., and Bhanu, B. (2003). Probabilistic spatial database operations. In International Symposium on Spatial and Temporal Databases, pages 140–158. Springer.

Openshaw, S. (1989). Learning to live with errors in spatial databases. Accuracy of spatial databases, pages 263–276.

Patel, J. M. and DeWitt, D. J. (1996). Partition based spatial-merge join. In ACM SIGMOD Record, volume 25, pages 259–270. ACM.

Patel, J. M. and DeWitt, D. J. (2000). Clone join and shadow join: two parallel spatial join algorithms. In Proceedings of the 8th ACM international symposium on Advances in geographic information systems, pages 54–61. ACM.

Pfoser, D. and Jensen, C. S. (1999). Capturing the uncertainty of moving-object representations. In International Symposium on Spatial Databases, pages 111–131. Springer.

Wolfson, O., Sistla, A. P., Chamberlain, S., and Yesha, Y. (1999). Updating and querying databases that track mobile units. In Mobile Data Management and Applications, pages 3–33. Springer.

Yu, X. and Mehrotra, S. (2003). Capturing uncertainty in spatial queries over imprecise data. In International Conference on Database and Expert Systems Applications, pages 192–201. Springer.

Zhang, R., Qi, J., Lin, D., Wang, W., and Wong, R. C.-W. (2012). A highly optimized algorithm for continuous intersection join queries over moving objects. The VLDB JournalâThe International Journal on Very Large Data Bases, 21(4):561–586.