Efficient Computation of Range Aggregates Against Uncertain Location Based Queries using Filtering-and-Verification Algorithm
Keywords:
Uncertainty, Range Aggregates, Filtering-and-VerificationAbstract
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.
References
P. K. Agarwal, S.-W. Cheng, Y. Tao, and K. Yi. Indexing uncertain data. In Proc. Symp. Principles of Database Systems (PODS), 2009.
C. Aggarwal and P. Yu. On high dimensional indexing of uncertain data. In Proc. Intl Conf. Data Eng. (ICDE), 2008.
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.
C. Bohm, A. Pryakhin, and M. Schubert. Probabilistic ranking queries on gaussians. In Proc. Intl Conf. Scientific and Statistical Database Management (SSDBM), 2006.
V. Bryant. Metric Spaces: Iteration and Application. Cambridge University Press, 1996.
J. Chen and R. Cheng. Efficient evaluation of imprecise location dependent queries. In Proc. Intl Conf. Data Eng. (ICDE), 2007.
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.
R. Cheng, D. V. Kalashnikov, and S. Prabhakar. Evaluating probabilistic queries over imprecise data. In Proc. ACM SIGMOD, 2003.
R. Cheng, S. Singh, and S. Prabhakar. Efficient join processing over uncertain data. In Proc. Int’l Conf. Information and Knowledge Management (CIKM), 2006.
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.
G. W. Cordner. Police patrol work load studies: A review and critique. Police Studies, 2(3):50–60, 1979.
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.
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.
M. Hua, J. Pei, W. Zhang, and X. Lin. Ranking queries on uncertain data: A probabilistic threshold approach. In Proc. ACM SIGMOD, 2008.
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.
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.
H. P. Kriegel and M. Pfeifle. Density-based clustering of uncertain data. In Proc. ACM SIGKDD, 2005.
X. Lian and L. Chen. Monochromatic and bichromatic reverse skyline search over uncertain databases. In Proc. ACM SIGMOD, 2008.
R. Meester. A Natural Introduction to Probability Theory. Addison Wesley, 2004.
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.
J. Pei, B. Jiang, X. Lin, and Y. Yuan. Probabilistic skyline on uncertain data. In Proc. Intl Conf. Very Large Data Bases (VLDB), 2007.
G. M. Siouris. Missile Guidance and Control Systems. Springer Publication, 2004.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors contributing to this journal agree to publish their articles under the Creative Commons Attribution 4.0 International License, allowing third parties to share their work (copy, distribute, transmit) and to adapt it, under the condition that the authors are given credit and that in the event of reuse or distribution, the terms of this license are made clear.
