Abstract
In many applications, including location based services, queries may not be precise. In this paper, we study the problem of efficiently computing range aggregates in a multidimensional space when the query location is uncertain. We propose novel, efficient techniques to solve the problem following the filtering-and-verification paradigm.
Key-Words / Index Term
Uncertainty, Range Aggregates, Filtering-and-Verification
References
[1] P. K. Agarwal, S.-W. Cheng, Y. Tao, and K. Yi. Indexing uncertain data. In Proc. Symp. Principles of Database Systems (PODS), 2009.
[2] C. Aggarwal and P. Yu. On high dimensional indexing of uncertain data. In Proc. Intl Conf. Data Eng. (ICDE), 2008.
[3] C. Bohm, M. Gruber, P. Kunath, A. Pryakhin, and M. Schubert. Prover: Probabilistic video retrieval using the gauss-tree. In Proc. Intl Conf. Data Eng. (ICDE), 2007.
[4] C. Bohm, A. Pryakhin, and M. Schubert. Probabilistic ranking queries on gaussians. In Proc. Intl Conf. Scientific and Statistical Database Management (SSDBM), 2006.
[5] V. Bryant. Metric Spaces: Iteration and Application. Cambridge University Press, 1996.
[6] J. Chen and R. Cheng. Efficient evaluation of imprecise location dependent queries. In Proc. Intl Conf. Data Eng. (ICDE), 2007.
[7] R. Cheng, J. Chen, M. F. Mokbel, and C.-Y. Chow. Probabilistic verifiers: Evaluating constrained nearest-neighbor queries over uncertain data. In Proc. Intl Conf. Data Eng. (ICDE), 2008.
[8] R. Cheng, D. V. Kalashnikov, and S. Prabhakar. Evaluating probabilistic queries over imprecise data. In Proc. ACM SIGMOD, 2003.
[9] R. Cheng, S. Singh, and S. Prabhakar. Efficient join processing over uncertain data. In Proc. Int’l Conf. Information and Knowledge Management (CIKM), 2006.
[10] R. Cheng, Y. Xia, S. Prabhakar, R. Shah, and J. S. Vitter. Effcient indexing methods for probabilistic threshold queries over uncertain data. In Proc. Intl Conf. Very Large Data Bases (VLDB), 2004.
[11] G. W. Cordner. Police patrol work load studies: A review and critique. Police Studies, 2(3):50–60, 1979.
[12] X. Dai, M. Yiu, N. Mamoulis, Y. Tao, and M. Vaitis. Probabilistic spatial queries on existentially uncertain data. In Proc. Intl Symp. Large Spatio-Temporal Databases (SSTD), 2005.
[13] E. Frentzos, K. Gratsias, and Y. Theodoridis. On the effect of location uncertainty in spatial querying. IEEE Trans. Knowl. Data Eng., 21(3):366–383, 2009.
[14] M. Hua, J. Pei, W. Zhang, and X. Lin. Ranking queries on uncertain data: A probabilistic threshold approach. In Proc. ACM SIGMOD, 2008.
[15] Y. Ishikawa, Y. Iijima, and J. X. Yu. Spatial range querying for gaussian-based imprecise query objects. In Proc. Intl Conf. Data Eng. (ICDE), 2009.
[16] H.-P. Kriegel, P. Kunath, M. Pfeifle, and M. Renz. Probabilistic similarity join on uncertain data. In Proc. Intl Conf. Database Systems for Advanced Applications (DASFAA), 2006.
[17] H. P. Kriegel and M. Pfeifle. Density-based clustering of uncertain data. In Proc. ACM SIGKDD, 2005.
[18] X. Lian and L. Chen. Monochromatic and bichromatic reverse skyline search over uncertain databases. In Proc. ACM SIGMOD, 2008.
[19] R. Meester. A Natural Introduction to Probability Theory. Addison Wesley, 2004.
[20] W. K. Ngai, B. Kao, C. K. Chui, R. Cheng, M. Chau, and K. Y. Yip. Efficient clustering of uncertain data. In Proc. Int’l Conf. on Data Mining (ICDM), 2006.
[21] J. Pei, B. Jiang, X. Lin, and Y. Yuan. Probabilistic skyline on uncertain data. In Proc. Intl Conf. Very Large Data Bases (VLDB), 2007.
[22] G. M. Siouris. Missile Guidance and Control Systems. Springer Publication, 2004.
Citation
S.Praveen Kumar and R.V.Krishnaiah, "Efficient Computation of Range Aggregates Against Uncertain Location Based Queries using Filtering-and-Verification Algorithm," International Journal of Scientific Research in Computer Science and Engineering, Vol.1, Issue.3, pp.56-61, 2013