SpringerLink
Log in

Uncertain Spatial Data Management: An Overview

  • Chapter
  • First Online:
Handbook of Big Geospatial Data

  • 1318 Accesses

Abstract

Both the current trends in technology such as smart phones, general mobile devices, stationary sensors, and satellites as we as a new user mentality of using this technology to voluntarily share enriched location information produces a flood of geo-spatial and geo-spatio-temporal data. This data flood provides a tremendous potential of discovering new and useful knowledge. But in addition to the fact that measurements are imprecise, spatial data is often interpolated between discrete observations. To reduce communication and bandwidth utilization, data is often subjected to a reduction, thereby eliminating some of the known/recorded values. These issues introduce the notion of uncertainty in the context of spatio-temporal data management, an aspect raising imminent need for scalable and flexible solutions. The main scope of this chapter is to survey existing techniques for managing, querying, and mining uncertain spatio-temporal data. First, this chapter surveys common data representations for uncertain data, explains the commonly used possible worlds semantics to interpret an uncertain database, and surveys existing system to process uncertain data. Then this chapter defines the notion of different probabilistic result semantics to distinguish the task of enrich individual objects with probabilities rather than enriched entire results with probabilities. To distinguish between result semantics is important, as for many queries, the problem of computing object-level result probabilities can be done efficiently, whereas the problem of computing probabilities of entire results is often exponentially hard. Then, this chapter provides an overview over probabilistic query predicates to quantify the required probability of a result to be included in the result.

Finally, this chapter introduces a novel paradigm to efficiently answer any kind of query on uncertain data: the Paradigm of Equivalent Worlds, which groups the exponential set of possible database worlds into a polynomial number of set of equivalent worlds that can be processed efficiently. Examples and use-cases of querying uncertain spatial data are provided using the example of uncertain range queries.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 189.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 249.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info
Hardcover Book
USD 249.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    #P is the set of counting problems associated with decision problems in the class NP. Thus, for any NP-complete decision problem which asks if there exists a solution to a problem, the corresponding #P problem asks for the number of such solutions.

  2. 2.

    Note that if an exponential large set is partitioned into a polynomial number of subsets, then at least one such subset must have exponential size. This is evident considering that \(O(\frac {2^n}{poly(n)})=O(2^n)\).

  3. 3.

    Note that this automaton is deterministic, despite the process of choosing a successor node being a random event. Once the Bernoulli trial corresponding to a node has been performed, the next node will be chosen deterministically, i.e., the upper node will be chosen if the trial was successful, and the right node will be chosen otherwise. Either way, there is exactly one successor node.

References

  • Agarwal PK, Cheng S-W, Tao Y, Yi K (2009) Indexing uncertain data. In: Proceedings of the Twenty-Eighth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pp 137–146

    Google Scholar 

  • Agarwal PK, Kumar N, Sintos S, Suri S (2018) Range-max queries on uncertain data. J Comput Syst Sci 94:118–134

    Article  MathSciNet  MATH  Google Scholar 

  • Aggarwal CC (2010) Managing and mining uncertain data, vol 35. Springer Science & Business Media, New York

    MATH  Google Scholar 

  • Aggarwal CC, Philip SY (2008) A survey of uncertain data algorithms and applications. IEEE Trans Knowl Data Eng 21(5):609–623

    Article  Google Scholar 

  • Agrawal P, Benjelloun O, Sarma AD, Hayworth C, Nabar S, Sugihara T, Widom J (2006) Trio: a system for data, uncertainty, and lineage. In: Proceedings of VLDB 2006 (Demonstration Description)

    Google Scholar 

  • Aji A, Wang F, Vo H, Lee R, Liu Q, Zhang X, Saltz J (2013) Hadoop-GIS: a high performance spatial data warehousing system over MapReduce. Proc VLDB Endowment 6(11):1009–1020

    Article  Google Scholar 

  • Akdogan A, Demiryurek U, Banaei-Kashani F, Shahabi C (2010) Voronoi-based geospatial query processing with MapReduce. In: 2010 IEEE Second International Conference on Cloud Computing Technology and Science. IEEE, pp 9–16

    Google Scholar 

  • Antova L, Jansen T, Koch C, Olteanu D (2008a) Fast and simple relational processing of uncertain data. In: Proceedings of the 24th International Conference on Data Engineering (ICDE), Cancun, pp 983–992

    Google Scholar 

  • Antova L, Jansen T, Koch C, Olteanu D (2008b) Fast and simple relational processing of uncertain data. In: 2008 IEEE 24th International Conference on Data Engineering. IEEE, pp 983–992

    Google Scholar 

  • Apache. Hadoop. http://hadoop.apache.org/. Accessed 02/03/2021

  • Bacchus F, Grove AJ, Halpern JY, Koller D (1996) From statistical knowledge bases to degrees of belief. Artif Intell 87(1):75–143

    Article  MathSciNet  Google Scholar 

  • Barbará D, Garcia-Molina H, Porter D (1992) The management of probabilistic data. IEEE Trans Knowl Data Eng 4(5):487–502

    Article  Google Scholar 

  • Benjelloun O, Sarma AD, Halevy AY, Widom J (2006) ULDBs: databases with uncertainty and lineage. In: Proceedings of the 32nd International Conference on Very Large Data Bases (VLDB), Seoul, pp 953–964

    Google Scholar 

  • Bernecker T, Kriegel H-P, Renz M (2008) ProUD: probabilistic ranking in uncertain databases. In: Proceedings of the 20th International Conference on Scientific and Statistical Database Management (SSDBM), Hong Kong, pp 558–565

    Google Scholar 

  • Bernecker T, Kriegel H-P, Renz M, Verhein F, Zuefle A (2009) Probabilistic frequent itemset mining in uncertain databases. In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, pp 119–128

    Google Scholar 

  • Bernecker T, Kriegel H-P, Mamoulis N, Renz M, Zuefle A (2010) Scalable probabilistic similarity ranking in uncertain databases. IEEE Trans Knowl Data Eng 22(9):1234–1246

    Article  Google Scholar 

  • Bernecker T, Emrich T, Kriegel H-P, Mamoulis N, Renz M, Züfle A (2011a) A novel probabilistic pruning approach to speed up similarity queries in uncertain databases. In: 2011 IEEE 27th International Conference on Data Engineering. IEEE, pp 339–350

    Google Scholar 

  • Bernecker T, Emrich T, Kriegel H-P, Renz M, Zankl S, Züfle A (2011b) Efficient probabilistic reverse nearest neighbor query processing on uncertain data. Proc VLDB Endowment 4(10):669–680

    Article  Google Scholar 

  • Bernecker T, Emrich T, Kriegel H-P, Renz M, Züfle A (2012) Probabilistic ranking in fuzzy object databases. In: Proceedings of the 21st ACM International Conference on Information and Knowledge Management, pp 2647–2650

    Google Scholar 

  • Bernecker T, Cheng R, Cheung DW, Kriegel H-P, Lee SD, Renz M, Verhein F, Wang L, Zuefle A (2013) Model-based probabilistic frequent itemset mining. Knowl Inf Syst 37(1):181–217

    Article  Google Scholar 

  • Beskales G, Soliman M, Ilyas I (2008) Efficient search for the top-k probable nearest neighbors in uncertain databases. PVLDB 1:326–339

    Google Scholar 

  • Böhm C, Pryakhin A, Schubert M (2006) The Gauss-tree: efficient object identification of probabilistic feature vectors. In: Proceedings of the 22nd International Conference on Data Engineering (ICDE), Atlanta, p 9

    Google Scholar 

  • Boulos J, Dalvi N, Mandhani B, Mathur S, Re C, Suciu D (2005) MYSTIQ: a system for finding more answers by using probabilities. In: Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data. ACM, pp 891–893

    Google Scholar 

  • Casella G, Berger RL (2002) Statistical inference, vol 2. Duxbury, Pacific Grove

    Google Scholar 

  • Cavallo R, Pittarelli M (1987) The theory of probabilistic databases. In: VLDB, vol 87, pp 1–4

    Google Scholar 

  • Chan HK-H, Long C, Yan D, Wong RC-W (2019) Fraction-score: a new support measure for co-location pattern mining. In: 2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, pp 1514–1525

    Google Scholar 

  • Cheema MA, Lin X, Wang W, Zhang W, Pei J (2010) Probabilistic reverse nearest neighbor queries on uncertain data. IEEE Trans Knowl Data Eng 22(4):550–564

    Article  Google Scholar 

  • Chen L, Gao Y, Zhong A, Jensen CS, Chen G, Zheng B (2017) Indexing metric uncertain data for range queries and range joins. VLDB J 26(4):585–610

    Article  Google Scholar 

  • Cheng R, Kalashnikov DV, Prabhakar S (2003) Evaluating probabilistic queries over imprecise data. In: Proceedings of the ACM International Conference on Management of Data (SIGMOD), San Diego, pp 551–562

    Google Scholar 

  • Cheng R, Kalashnikov DV, Prabhakar S (2004a) Querying imprecise data in moving object environments. IEEE Trans Knowl Data Eng 16(9):1112–1127

    Article  Google Scholar 

  • Cheng R, **a Y, Prabhakar S, Shah R, Vitter J (2004b) Efficient indexing methods for probabilistic threshold queries over uncertain data. In: Proceedings of the 30th International Conference on Very Large Data Bases (VLDB), Toronto, pp 876–887

    Google Scholar 

  • Cheng R, Chen J, Mokbel MF, Chow C-Y (2008) Probabilistic verifiers: evaluating constrained nearest-neighbor queries over uncertain data. In: Proceedings of the 24th International Conference on Data Engineering (ICDE), Cancun, pp 973–982

    Google Scholar 

  • Cheng R, Chen L, Chen J, **e X (2009) Evaluating probability threshold k-nearest-neighbor queries over uncertain data. In: Proceedings of the 13th International Conference on Extending Database Technology (EDBT), Saint-Petersburg, pp 672–683

    Google Scholar 

  • Cheng R, Emrich T, Kriegel H-P, Mamoulis N, Renz M, Trajcevski G, Züfle A (2014) Managing uncertainty in spatial and spatio-temporal data. In: 2014 IEEE 30th International Conference on Data Engineering. IEEE, pp 1302–1305

    Google Scholar 

  • Cho E, Myers SA, Leskovec J (2011) Friendship and mobility: user movement in location-based social networks. In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, pp 1082–1090

    Google Scholar 

  • Cormode G, Li F, Yi K (2009a) Semantics of ranking queries for probabilistic data and expected ranks. In: 2009 IEEE 25th International Conference on Data Engineering. IEEE, pp 305–316

    Google Scholar 

  • Cormode G, Li F, Yi K (2009b) Semantics of ranking queries for probabilistic data and expected results. In: Proceedings of the 25th International Conference on Data Engineering (ICDE), Shanghai, pp 305–316

    Google Scholar 

  • Couclelis H (2003) The certainty of uncertainty: GIS and the limits of geographic knowledge. Trans GIS 7(2):165–175

    Article  Google Scholar 

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

    Google Scholar 

  • Dalvi NN, Suciu D (2004) Efficient query evaluation on probabilistic databases. In: Proceedings of the 30th International Conference on Very Large Data Bases (VLDB), Toronto, pp 864–875

    Google Scholar 

  • Dalvi N, Suciu D (2007) Efficient query evaluation on probabilistic databases. VLDB J 16(4):523–544

    Article  Google Scholar 

  • Dalvi NN, Ré C, Suciu D (2009) Probabilistic databases: diamonds in the dirt. Commun ACM 52(7):86–94

    Article  Google Scholar 

  • Dean J, Ghemawat S (2008) MapReduce: simplified data processing on large clusters. Commun ACM 51(1):107–113

    Article  Google Scholar 

  • Deshpande A, Guestrin C, Madden S, Hellerstein JM, Hong W (2004) Model-driven data acquisition in sensor networks. In: Proceedings of the 30th International Conference on Very Large Data Bases (VLDB), Toronto, pp 588–599

    Google Scholar 

  • Ding X, ** H, Xu H, Song W (2014) Probabilistic skyline queries over uncertain moving objects. Comput Inform 32(5):987–1012

    Google Scholar 

  • Emrich T, Kriegel H-P, Mamoulis N, Renz M, Züfle A (2012a) Indexing uncertain spatio-temporal data. In: Proceedings of the 21st ACM International Conference on Information and Knowledge Management. ACM, pp 395–404

    Google Scholar 

  • Emrich T, Kriegel H-P, Mamoulis N, Renz M, Züfle A (2012b) Querying uncertain spatio-temporal data. In: IEEE 28th International Conference on Data Engineering (ICDE). IEEE, pp 354–365

    Google Scholar 

  • Emrich T, Kriegel H-P, Mamoulis N, Niedermayer J, Renz M, Züfle A (2014) Reverse-nearest neighbor queries on uncertain moving object trajectories. In: International Conference on Database Systems for Advanced Applications. Springer, pp 92–107

    Google Scholar 

  • Fegeas RG, Cascio JL, Lazar RA (1992) An overview of FIPS 173, the spatial data transfer standard. Cartograph Geograph Inf Syst 19(5):278–293

    Article  Google Scholar 

  • Fuhr N, Rölleke T (1997a) A probabilistic relational algebra for the integration of information retrieval and database systems. ACM Trans Inf Syst TOIS) 15(1):32–66

    Article  Google Scholar 

  • Fuhr N, Rölleke T (1997b) A probabilistic relational algebra for the integration of information retrieval and database systems. ACM Trans Inf Syst 15(1):32–66

    Article  Google Scholar 

  • Goodchild MF (1998) Uncertainty: the achilles heel of GIS. Geo Inf Syst 8(11):50–52

    Google Scholar 

  • Grira J, Bédard Y, Roche S (2010) Spatial data uncertainty in the VGI world: going from consumer to producer. Geomatica 64(1):61–72

    Google Scholar 

  • Hoeffding W et al (1956) On the distribution of the number of successes in independent trials. Ann Math Stat 27(3):713–721

    Article  MathSciNet  MATH  Google Scholar 

  • Hsu J (1996) Multiple comparisons: theory and methods. Chapman and Hall/CRC, London

    Book  MATH  Google Scholar 

  • Hua M, Pei J, Zhang W, Lin X (2008) Ranking queries on uncertain data: a probabilistic threshold approach. In: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, pp 673–686

    Google Scholar 

  • Iijima Y, Ishikawa Y (2009) Finding probabilistic nearest neighbors for query objects with imprecise locations. In: Proceedings of the 10th International Conference on Mobile Data Management (MDM), Taipei, pp 52–61

    Google Scholar 

  • Jampani R, Xu F, Wu M, Perez LL, Jermaine C, Haas PJ (2008) MCDB: a Monte Carlo approach to managing uncertain data. In: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. ACM, pp 687–700

    Google Scholar 

  • Kolahdouzan M, Shahabi C (2004) Voronoi-based k nearest neighbor search for spatial network databases. In: Proceedings of the Thirtieth International Conference on Very Large Data Bases, vol 30. VLDB Endowment, pp 840–851

    Google Scholar 

  • Kriegel H-P, Pfeifle M (2005) Density-based clustering of uncertain data. In: Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, pp 672–677

    Google Scholar 

  • Kriegel H-P, Kunath P, Renz M (2007) Probabilistic nearest-neighbor query on uncertain objects. In: Proceedings of the 12th International Conference on Database Systems for Advanced Applications (DASFAA), Bangkok, pp 337–348

    Google Scholar 

  • Kumar S, Morstatter F, Liu H (2014) Twitter data analytics. Springer, New York

    Book  Google Scholar 

  • Lakshmanan LV, Leone N, Ross R, Subrahmanian VS (1997) ProbView: a flexible probabilistic database system. ACM Trans Database Syst (TODS) 22(3):419–469

    Article  Google Scholar 

  • Lange K (1999) Numerical analysis for statisticians. In: Statistics and Computing

    Google Scholar 

  • Li J, Deshpande A (2009) Consensus answers for queries over probabilistic databases. In: Symposium on Principles of Database Systems (PODS), Providence, pp 259–268

    Google Scholar 

  • Li J, Deshpande A (2010a) Ranking continuous probabilistic datasets. In: Proceedings of the 36nd International Conference on Very Large Data Bases (VLDB), Singapore 3(1):638–649

    Google Scholar 

  • Li J, Deshpande A (2010b) Ranking continuous probabilistic datasets. Proc VLDB Endowment 3(1–2):638–649

    Article  Google Scholar 

  • Li J, Saha B, Deshpande A (2009a) A unified approach to ranking in probabilistic databases. Proc VLDB Endowment 2(1):502–513

    Article  Google Scholar 

  • Li J, Saha B, Deshpande A (2009b) A unified approach to ranking in probabilistic databases. In: Proceedings of the 35nd International Conference on Very Large Data Bases (VLDB), Lyon 2(1):502–513

    Google Scholar 

  • Li J, Saha B, Deshpande A (2011) A unified approach to ranking in probabilistic databases. VLDB J 20(2):249–275

    Article  Google Scholar 

  • Li L, Wang H, Li J, Gao H (2018) A survey of uncertain data management. Front Comput Sci 9:1–29

    Google Scholar 

  • Lian X, Chen L (2008a) Monochromatic and bichromatic reverse skyline search over uncertain databases. In: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, pp 213–226

    Google Scholar 

  • Lian X, Chen L (2008b) Probabilistic ranked queries in uncertain databases. In: Proceedings of the 12th International Conference on Extending Database Technology (EDBT), Nantes, pp 511–522

    Google Scholar 

  • Lian X, Chen L (2009a) Efficient processing of probabilistic reverse nearest neighbor queries over uncertain data. VLDB J 18(3):787–808

    Article  Google Scholar 

  • Lian X, Chen L (2009b) Probabilistic inverse ranking queries over uncertain data. In: Proceedings of the 14th International Conference on Database Systems for Advanced Applications (DASFAA), Brisbane, pp 35–50

    Google Scholar 

  • Liu Q, Lian X, Chen L (2019) Probabilistic maximum range-sum queries on spatial database. In: Proceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp 159–168

    Google Scholar 

  • Ljosa V, Singh AK (2007) APLA: indexing arbitrary probability distributions. In: Proceedings of the 23rd International Conference on Data Engineering (ICDE), Istanbul, pp 946–955

    Google Scholar 

  • Lu W, Shen Y, Chen S, Ooi BC (2012) Efficient processing of k nearest neighbor joins using MapReduce. Proc VLDB Endowment 5(10):1016–1027

    Article  Google Scholar 

  • Nakayama Y, Amagata D, Hara T (2017) Probabilistic MaxRS queries on uncertain data. In: International Conference on Database and Expert Systems Applications. Springer, pp 111–119

    Google Scholar 

  • Ngai WK, Kao B, Chui CK, Cheng R, Chau M, Yip KY (2006) Efficient clustering of uncertain data. In: Sixth International Conference on Data Mining (ICDM’06). IEEE, pp 436–445

    Google Scholar 

  • Niedermayer J, Züfle A, Emrich T, Renz M, Mamoulis N, Chen L, Kriegel H-P (2013a) Probabilistic nearest neighbor queries on uncertain moving object trajectories. Proc VLDB Endowment 7(3):205–216

    Article  Google Scholar 

  • Niedermayer J, Züfle A, Emrich T, Renz M, Mamoulis N, Chen L, Kriegel H-P (2013b) Similarity search on uncertain spatio-temporal data. In: International Conference on Similarity Search and Applications. Springer, pp 43–49

    Google Scholar 

  • Open Street Map. http://www.openstreetmap.org. Accessed 02/03/2021

  • Patroumpas K, Papamichalis M, Sellis TK (2012) Probabilistic range monitoring of streaming uncertain positions in geosocial networks. In: Proceedings of the 22nd International Conference on Scientific and Statistical Database Management (SSDBM), Crete, pp 20–37

    Google Scholar 

  • Pei J, Jiang B, Lin X, Yuan Y (2007) Probabilistic skylines on uncertain data. In: Proceedings of the 33rd International Conference on Very Large Data Bases. Citeseer, pp 15–26

    Google Scholar 

  • Pei J, Hua M, Tao Y, Lin X (2008) Query answering techniques on uncertain and probabilistic data: tutorial summary. In: Proceedings of the ACM International Conference on Management of Data (SIGMOD), Vancouver, pp 1357–1364

    Google Scholar 

  • Re C, Dalvi NN, Suciu D (2006) Query evaluation on probabilistic databases. IEEE Data Eng Bull 29(1):25–31

    Google Scholar 

  • Re C, Dalvi N, Suciu D (2007) Efficient top-k query evaluation on probalistic databases. In: Proceedings of the 23rd International Conference on Data Engineering (ICDE), Istanbul, pp 886–895

    Google Scholar 

  • Renz M, Cheng R, Kriegel H-P, Züfle A, Bernecker T (2010) Similarity search and mining in uncertain databases. In: Proceedings of the 36nd International Conference on Very Large Data Bases (VLDB), Singapore 3(2):1653–1654

    Google Scholar 

  • Sarma AD, Benjelloun O, Halevy AY, Widom J (2006) Working models for uncertain data. In: Proceedings of the 22nd International Conference on Data Engineering (ICDE), Atlanta, p 7

    Google Scholar 

  • Schmid KA, Züfle A (2019) Representative query answers on uncertain data. In: Proceedings of the 16th International Symposium on Spatial and Temporal Databases, pp 140–149

    Google Scholar 

  • Schubert E, Koos A, Emrich T, Züfle A, Schmid KA, Zimek A (2015) A framework for clustering uncertain data. Proc VLDB Endowment 8(12):1976–1979

    Article  Google Scholar 

  • Schmid KA, Zufle A, Emrich T, Renz M, Cheng R (2017) Uncertain voronoi cell computation based on space decomposition. Geoinformatica 21(4):797–827

    Article  Google Scholar 

  • Sen P, Deshpande A (2007) Representing and querying correlated tuples in probabilistic databases. In: Proceedings of the 23rd International Conference on Data Engineering (ICDE), Istanbul, pp 596–605

    Google Scholar 

  • Soliman M, Ilyas I (2009) Ranking with uncertain scores. In: Proceedings of the 25th International Conference on Data Engineering (ICDE), Shanghai, pp 317–328

    Google Scholar 

  • Soliman MA, Ilyas IF, Chang KC-C (2007) Top-k query processing in uncertain databases. In: Proceedings of the 23rd International Conference on Data Engineering (ICDE), Istanbul, pp 896–905

    Google Scholar 

  • Sui D, Elwood S, Goodchild M (2012) Crowdsourcing geographic knowledge: volunteered geographic information (VGI) in theory and practice. Springer Science & Business Media, Dordrecht

    Google Scholar 

  • Tao Y, Cheng R, **ao X, Ngai WK, Kao B, Prabhakar S (2005) Indexing multi-dimensional uncertain data with arbitrary probability density functions. In: Proceedings of the 31st International Conference on Very Large Data Bases (VLDB), Trondheim, pp 922–933

    Google Scholar 

  • Tran TT, Peng L, Li B, Diao Y, Liu A (2010) PODS: a new model and processing algorithms for uncertain data streams. In: Proceedings of the ACM International Conference on Management of Data (SIGMOD), Indianapolis, pp 159–170

    Google Scholar 

  • United States Geological Survey. USGS science data catalog. https://data.usgs.gov/datacatalog/. Accessed 02/03/2021

  • Valiant L (1979) The complexity of enumeration and reliability problems. SIAM J Comput 8:410–421

    Article  MathSciNet  MATH  Google Scholar 

  • Vu K, Zheng R (2013) Efficient algorithms for spatial skyline query with uncertainty. In: Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp 412–415

    Google Scholar 

  • Wang DZ, Michelakis E, Garofalakis M, Hellerstein JM (2008) BAYESSTORE: managing large, uncertain data repositories with probabilistic graphical models. Proc VLDB Endowment 1(1):340–351

    Article  Google Scholar 

  • Wang K, Han J, Tu B, Dai J, Zhou W, Song X (2010) Accelerating spatial data processing with MapReduce. In: IEEE 16th International Conference on Parallel and Distributed Systems. IEEE, pp 229–236

    Google Scholar 

  • Wang L, Wu P, Chen H (2011) Finding probabilistic prevalent colocations in spatially uncertain data sets. IEEE Trans Knowl Data Eng 25(4):790–804

    Article  Google Scholar 

  • Wang L, Cheung DW-L, Cheng R, Lee SD, Yang XS (2012) Efficient mining of frequent item sets on large uncertain databases. IEEE Trans Knowl Data Eng 24(12):2170–2183

    Article  Google Scholar 

  • Wang Y, Li X, Li X, Wang Y (2013) A survey of queries over uncertain data. Knowl Inf Syst 37(3):485–530

    Article  Google Scholar 

  • Yang Z, Li K, Zhou X, Mei J, Gao Y (2018) Top k probabilistic skyline queries on uncertain data. Neurocomputing 317:1–14

    Article  Google Scholar 

  • Yi K, Li F, Kollios G, Srivastava D (2008a) Efficient processing of top-k queries in uncertain databases. In: Proceedings of the 24th International Conference on Data Engineering (ICDE), Cancun, pp 1406–1408

    Google Scholar 

  • Yi K, Li F, Kollios G, Srivastava D (2008b) Efficient processing of top-k queries in uncertain databases with x-relations. IEEE Trans Knowl Data Eng 20(12):1669–1682

    Article  Google Scholar 

  • Yiu ML, Mamoulis N, Dai X, Tao Y, Vaitis M (2009) Efficient evaluation of probabilistic advanced spatial queries on existentially uncertain data. Knowl Data Eng IEEE Trans 21(1):108–122

    Article  Google Scholar 

  • Zhang M, Chen S, Jensen CS, Ooi BC, Zhang Z (2009) Effectively indexing uncertain moving objects for predictive queries. Proc VLDB Endowment 2(1):1198–1209

    Article  Google Scholar 

  • Zhang C, Li F, Jestes J (2012) Efficient parallel kNN joins for large data in MapReduce. In: Proceedings of the 15th International Conference on Extending Database Technology. ACM, pp 38–49

    Google Scholar 

  • Zhang P, Cheng R, Mamoulis N, Renz M, Züfle A, Tang Y, Emrich T (2013) Voronoi-based nearest neighbor search for multi-dimensional uncertain databases. In: 2013 IEEE 29th International Conference on Data Engineering (ICDE). IEEE, pp 158–169

    Google Scholar 

  • Zhao B, Sui DZ (2017) True lies in geospatial big data: detecting location spoofing in social media. Ann GIS 23(1):1–14

    Article  Google Scholar 

  • Zheng K, Trajcevski G, Zhou X, Scheuermann P (2011) Probabilistic range queries for uncertain trajectories on road networks. In: Proceedings of the 14th International Conference on Extending Database Technology, pp 283–294

    Google Scholar 

  • Zimányi E (1997) Query evaluation in probabilistic relational databases. Theor Comput Sci 171(1–2):179–219

    Article  MathSciNet  MATH  Google Scholar 

  • Züfle A (2013) Similarity search and mining in uncertain spatial and spatio-temporal tatabases. Ph.D. thesis, Ludwig-Maximilians University Munich

    Google Scholar 

  • Züfle A, Emrich T, Schmid KA, Mamoulis N, Zimek A, Renz M (2014) Representative clustering of uncertain data. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, pp 243–252

    Google Scholar 

  • Züfle A, Trajcevski G, Pfoser D, Renz M, Rice MT, Leslie T, Delamater P, Emrich T (2017) Handling uncertainty in geo-spatial data. In: 33rd International Conference on Data Engineering (ICDE). IEEE, pp 1467–1470

    Google Scholar 

  • Züfle A, Trajcevski G, Pfoser D, Joon-Seok K (2020) Managing uncertainty in evolving geo-spatial data. In 2020 21st IEEE International Conference on Mobile Data Management (MDM). IEEE, pp. 5–8.

    Google Scholar 

  • Zwillinger D, Kokoska S (2000) CRC standard probability and statistics tables and formulae. CRC Press, Boca Raton

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Geography and Geoinformation Science, George Mason University, Fairfax, VA, USA

    Andreas Züfle

Authors
  1. Andreas Züfle
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Andreas Züfle .

Editor information

Editors and Affiliations

  1. Professorship Big Geospatial Data Management, Technical University of Munich (TUM), Munich, Germany

    Martin Werner

  2. Spatial Sciences Institute, University of Southern California, Los Angeles, CA, USA

    Yao-Yi Chiang

Rights and permissions

Reprints and permissions

Copyright information

© 2021 Springer Nature Switzerland AG

About this chapter

Check for updates. Verify currency and authenticity via CrossMark

Cite this chapter

Züfle, A. (2021). Uncertain Spatial Data Management: An Overview. In: Werner, M., Chiang, YY. (eds) Handbook of Big Geospatial Data. Springer, Cham. https://doi.org/10.1007/978-3-030-55462-0_14

Download citation

Publish with us

Policies and ethics

Search

Navigation