More Web Proxy on the site http://driver.im/

article

Free access

UV-diagram: a voronoi diagram for uncertain spatial databases

Authors:

Jinchuan ChenAuthors Info & Claims

The VLDB Journal — The International Journal on Very Large Data Bases, Volume 22, Issue 3

Pages 319 - 344

https://doi.org/10.1007/s00778-012-0290-x

Published: 01 June 2013 Publication History

Abstract

The Voronoi diagram is an important technique for answering nearest-neighbor queries for spatial databases. We study how the Voronoi diagram can be used for uncertain spatial data, which are inherent in scientific and business applications. Specifically, we propose the Uncertain-Voronoi diagram (or UV-diagram ), which divides the data space into disjoint "UV-partitions". Each UV-partition $$P$$ is associated with a set $$S$$ of objects, such that any point $$q$$ located in $$P$$ has the set $$S$$ as its nearest neighbor with nonzero probabilities. The UV-diagram enables queries that return objects with nonzero chances of being the nearest neighbor (NN) of a given point $$q$$ . It supports "continuous nearest-neighbor search", which refreshes the set of NN objects of $$q$$ , as the position of $$q$$ changes. It also allows the analysis of nearest-neighbor information, for example, to find out the number of objects that are the nearest neighbors of any point in a given area. A UV-diagram requires exponential construction and storage costs. To tackle these problems, we devise an alternative representation of a UV-diagram, by using a set of UV-cells . A UV-cell of an object $$o$$ is the extent $$e$$ for which $$o$$ can be the nearest neighbor of any point $$q \in e$$ . We study how to speed up the derivation of UV-cells by considering its nearby objects. We also use the UV-cells to design the UV-index , which supports different queries, and can be constructed in polynomial time. We have performed extensive experiments on both real and synthetic data to validate the efficiency of our approaches.

References

[1]

Aggarwal, C.C.: On unifying privacy and uncertain data models. In: ICDE (2008).

[2]

Agrawal, R., Srikant, R.: Privacy-preserving data mining. In: SIGMOD (2000).

[3]

Akopyan, A., Zaslavski, A.: Geometry of Conics. American Mathematical Society, Providence, RI (2007).

[4]

Albers, G., Mitchell, J.S., Guibas, L.J., Roos, T.: Voronoi diagrams of moving points. Intl. J. Comput. Geom. Appl. 8 (3), 365-380 (1998).

[5]

Aref, W., Ilyas, I.: Sp-gist: an extensible database index for supporting space partitioning trees. JIS. 17 (1), 215-290 (2001).

[6]

Beckmann, N., Kriegel, H.-P., Schneider, R., Seeger, B.: The R*- tree: an efficient and robust accessmethod for points and rectangles. In: SIGMOD (1990).

[7]

Berchtold, S., Ertl, B., Keim, D.A., peter Kriegel, H., Seidl, T.: Fast nearest neighbor search in high-dimensional space. In: ICDE (1998).

[8]

Beskales, G., Soliman, M., Ilyas, I.: Efficient search for the top-k probable nearest neighbors in uncertain databases. In: VLDB (2008).

[9]

Chazelle, B., Edelsbrunner, H.: An improved algorithm for constructing kth-order voronoi diagrams. IEEE Trans. Comput. 36 (11), 1349-1354 (1987).

[10]

Cheema, M.A., Lin, X., Wang, W., Zhang, W., Pei, J.: Probabilistic reverse nearest neighbor queries on uncertain data. TKDE 16 (9), 550-564 (2009).

[11]

Cheema, M.A., Lin, X., Zhang, W., Zhang, Y.: Influence zone: Efficiently processing reverse k nearest neighbors queries. ICDE (2011).

[12]

Chen, J., Cheng, R., Mokbel, M., Chow, C.-Y.: Scalable processing of snapshot and continuous nearest-neighbor queries over one-dimensional uncertain data. VLDB J. 18 (5), 1219-1240 (2009).

[13]

Cheng, R., Chen, J., Mokbel, M., Chow, C.-Y.: Probabilistic verifiers: Evaluating constrained nearest-neighbor queries over uncertain data. In: ICDE (2008).

[14]

Cheng, R., Kalashnikov, D., Prabhakar, S.: Evaluating probabilistic queries over imprecise data. In: SIGMOD (2003).

[15]

Cheng, R., Kalashnikov, D., Prabhakar, S.: Querying imprecise data in moving object environments. TKDE 16 (9), 1112-1127 (2004).

[16]

Cheng, R., Xia, Y., Prabhakar, S., Shah, R., Vitter, J.S.: Efficient indexing methods for probabilistic threshold queries over uncertain data. In: VLDB (2004).

[17]

Cheng, R., Xie, X., Yiu, M.L., Chen, J., Sun, L.: UV-diagram: a voronoi diagram for uncertain data. In: ICDE (2010).

[18]

Dalvi, N., Suciu, D.: Efficient query evaluation on probabilistic databases. In: VLDB (2004).

[19]

de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf O.: Computational Geometry: Algorithms and Applications. Springer, New York (1997).

[20]

Hua, M., Pei, J., Zhang, W., Lin, X.: A probabilistic threshold approach. In: SIGMOD, ranking queries on uncertain data (2008).

[21]

Jooyandeh, M., Mohades, A., Mirzakhah, M.: Uncertain voronoi diagram. Inf. Process. Lett. 109 (13), 709-712 (2009).

[22]

Kao, B., Lee, S., Cheung, D., Ho, W., Chan, K.: Clustering uncertain data using voronoi diagrams. In: ICDM (2008).

[23]

Karavelas, M.I.: Voronoi diagrams for moving disks and applications. In: WADS (2001).

[24]

Kriegel, H., Kunath, P., Renz, M.: Probabilistic nearest-neighbor query on uncertain objects. In: DASFAA (2007).

[25]

Lian, X., Chen, L.: Monochromatic and bichromatic reverse skyline search over uncertain databases. In: SIGMOD (2008).

[26]

Lian, X., Chen, L.: Probabilistic group nearest neighbor queries in uncertain databases. TKDE 20 (6), 809-824 (2008).

[27]

Lian, X., Chen, L.: Efficient processing of probabilistic reverse nearest neighbor queries over uncertain data. In: VLDBJ (2009).

[28]

Ljosa, V., Singh, A.: APLA: Indexing arbitrary probability distributions. In: ICDE (2007).

[29]

Ljosa V., Singh, A.: Top-k spatial joins of probabilistic objects. In: ICDE (2008).

[30]

Hadjieleftheriou, M.: Spatial index library version 0.44.2b.

[31]

Mokbel, M., Chow, C., Aref, W.: The new casper: query processing for location services without compromising privacy. In: VLDB (2006).

[32]

Nutanong, S., Zhang, R., Tanin, E., Kulik, L.: The V*-diagram: a query-dependent approach to moving knn queries. In: VLDB (2008).

[33]

Okabe, A., Boots, B., Sugihara, K., Chiu, S.: Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. Wiley, New York (2000).

[34]

Oppenheim, N.: Urban Travel Demand Modeling: From Individual Choices to General Equilibrium. Wiley, New York (1995).

[35]

Pedersen, J.: On the stability of crystal lattices. ix. Covariant theory of lattice deformations and the stability of some hexagonal lattices. In: Proceedings of the Cambridge Philosophical Society vol. 38 (1942).

[36]

Pei, J., Jiang, B., Lin, X., Yuan, Y.: Probabilistic skylines on uncertain data. In: VLDB (2007).

[37]

Sember, J., Evans, W.: Guaranteed voronoi diagrams of uncertain sites. In: CCCG (2008).

[38]

Sharifzadeh, M., Shahabi, C.: Vor-tree: R-trees with voronoi diagrams for efficient processing of spatial nearest neighbor queries. In: PVLDB (2010).

[39]

Sistla, P.A., Wolfson, O., Chamberlain, S., Dao, S.: Querying the uncertain position of moving objects. In: Temporal Databases Research and Practice (1998).

[40]

Stallings, W.: Wireless Communications and Networks, 2nd edn. Prentice-Hall Inc, Upper Saddle River, NJ (2004).

[41]

Wang, P., Gonzalez, M.C., Hidalgo, C.A., Barabasi, A.-L.: Understanding the spreading patterns of mobile phone viruses. Sci. Exp. 324 (5930), 1071-1076 (2009).

[42]

Wong, R.C.-W., Özsu, M.T., Yu, P.S., Fu, A.W.-C., Liu, L.: Efficient method for maximizing bichromatic reverse nearest neighbor. PVLDB (2009).

[43]

Xu, J., Zheng, B.: Energy efficient index for querying location-dependent data in mobile broadcast environments. In: ICDE (2003).

[44]

Zhang, J., Zhu, M., Papadias, D., Tao, Y., Lee, D.L.: Location-based spatial queries. In: SIGMOD (2003).

[45]

Zheng, B., Xu, J., Lee, W.-C., Lee, L.: Grid-partition index: a hybrid method for nearest-neighbor queries in wireless location-based services. VLDB J. 15 (1), 21-39 (2006).

Cited By

Chen JDames P(2023)The Convex Uncertain Voronoi Diagram for Safe Multi-Robot Multi-Target Tracking Under Localization UncertaintyJournal of Intelligent and Robotic Systems10.1007/s10846-023-01986-0109:4Online publication date: 22-Nov-2023
https://dl.acm.org/doi/10.1007/s10846-023-01986-0
Chen JDames P(2020)Collision-Free Distributed Multi-Target Tracking Using Teams of Mobile Robots with Localization Uncertainty2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)10.1109/IROS45743.2020.9341126(6968-6974)Online publication date: 24-Oct-2020
https://dl.acm.org/doi/10.1109/IROS45743.2020.9341126
Janani VManikandan M(2018)Mobility Aware Clustering Scheme with Bayesian-Evidence Trust Management for Public Key Infrastructure in Ad Hoc NetworksWireless Personal Communications: An International Journal10.1007/s11277-017-5107-199:1(371-401)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1007/s11277-017-5107-1
Show More Cited By

UV-diagram: a voronoi diagram for uncertain spatial databases
1. Information systems
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory

Recommendations

Probabilistic Group Nearest Neighbors query based on Voronoi diagram
UrbanGIS'15: Proceedings of the 1st International ACM SIGSPATIAL Workshop on Smart Cities and Urban Analytics

In order to solve the problem of probabilistic group nearest neighbor query on uncertain data, we present an effective method based on Voronoi diagram. Probabilistic group nearest neighbor query on uncertain data is to find out the set of uncertain ...
Network Voronoi Diagram on uncertain objects for nearest neighbor queries

In the past decade, probabilistic nearest neighbor (PNN) query processing has received significant research attention due to the development of mobile smart terminals and the advances in wireless communication technologies. However, to the best of our ...
Nearest Neighbor-Based Classification of Uncertain Data

This work deals with the problem of classifying uncertain data. With this aim we introduce the Uncertain Nearest Neighbor (UNN) rule, which represents the generalization of the deterministic nearest neighbor rule to the case in which uncertain objects ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image The VLDB Journal — The International Journal on Very Large Data Bases

The VLDB Journal — The International Journal on Very Large Data Bases Volume 22, Issue 3

June 2013

145 pages

ISSN:1066-8888

Issue’s Table of Contents

Copyright © Copyright © 2013 Springer-Verlag Berlin Heidelberg.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 June 2013

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
139
Total Downloads

Downloads (Last 12 months)16
Downloads (Last 6 weeks)3

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen JDames P(2023)The Convex Uncertain Voronoi Diagram for Safe Multi-Robot Multi-Target Tracking Under Localization UncertaintyJournal of Intelligent and Robotic Systems10.1007/s10846-023-01986-0109:4Online publication date: 22-Nov-2023
https://dl.acm.org/doi/10.1007/s10846-023-01986-0
Chen JDames P(2020)Collision-Free Distributed Multi-Target Tracking Using Teams of Mobile Robots with Localization Uncertainty2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)10.1109/IROS45743.2020.9341126(6968-6974)Online publication date: 24-Oct-2020
https://dl.acm.org/doi/10.1109/IROS45743.2020.9341126
Janani VManikandan M(2018)Mobility Aware Clustering Scheme with Bayesian-Evidence Trust Management for Public Key Infrastructure in Ad Hoc NetworksWireless Personal Communications: An International Journal10.1007/s11277-017-5107-199:1(371-401)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1007/s11277-017-5107-1
Bai LShao ZLin ZCheng S(2017)Fixing inconsistencies of fuzzy spatiotemporal XML dataApplied Intelligence10.5555/3110563.311058447:1(257-275)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.5555/3110563.3110584
Cheng R(2016)Managing uncertainty of large spatial databasesSIGSPATIAL Special10.1145/3024087.30240898:2(11-17)Online publication date: 9-Dec-2016
https://dl.acm.org/doi/10.1145/3024087.3024089
Xie XJin PYiu MDu JYuan MJensen C(2016)Enabling Scalable Geographic Service Sharing with Weighted Imprecise Voronoi CellsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2015.246480428:2(439-453)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1109/TKDE.2015.2464804
Chen YLee C(2015)The σ-neighborhood skyline queriesInformation Sciences: an International Journal10.1016/j.ins.2015.06.015322:C(92-114)Online publication date: 20-Nov-2015
https://dl.acm.org/doi/10.1016/j.ins.2015.06.015
Long CWong RZhang BXie MDyreson CLi FÖzsu M(2014)Hypersphere dominanceProceedings of the 2014 ACM SIGMOD International Conference on Management of Data10.1145/2588555.2593669(111-122)Online publication date: 18-Jun-2014
https://dl.acm.org/doi/10.1145/2588555.2593669

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents