Incomplete data management: a survey

Abstract

Incomplete data accompanies our life processes and covers almost all fields of scientific studies, as a result of delivery failure, no power of battery, accidental loss, etc. However, how to model, index, and query incomplete data incurs big challenges. For example, the queries struggling with incomplete data usually have dissatisfying query results due to the improper incompleteness handling methods. In this paper, we systematically review the management of incomplete data, including modelling, indexing, querying, and handling methods in terms of incomplete data. We also overview several application scenarios of incomplete data, and summarize the existing systems related to incomplete data. It is our hope that this survey could provide insights to the database community on how incomplete data is managed, and inspire database researchers to develop more advanced processing techniques and tools to cope with the issues resulting from incomplete data in the real world.

Keywords

incomplete data / query processing / indexing / application / system

References

[1] Friedman T, Smith M. Measuring the business value of data quality. Gartner, 2011

[2] Graham J. Missing Data: Analysis and Design. Springer Science & Business Media, 2012

[3] Imieliński T, Lipski Jr W. Incomplete information in relational databases. Journal of the ACM, 1984, 31(4): 761–791

[4] Abiteboul S, Kanellakis P, Grahne G. On the representation and querying of sets of possible worlds. Theoretical Computer Science, 1991, 78(1): 159–187

[5] Green T J, Tannen V. Models for incomplete and probabilistic information. In: Proceedings of International Conference on Extending Database Technology. 2006, 278–296

[6] Antova L, Koch C, Olteanu D. From complete to incomplete information and back. In: Proceedings of ACM SIGMOD International Conference on Management of Data. 2007, 713–724

[7] Libkin L. Incomplete information and certain answers in general data models. In: Proceedings of ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. 2011, 59–70

[8] Ooi B C, Goh C H, Tan K L. Fast high-dimensional data search in incomplete databases. In: Proceedings of International Conference on Very Large Data Bases. 1998, 357–367

[9] Canahuate G, Gibas M, Ferhatosmanoglu H. Indexing incomplete databases. In: Proceedings of International Conference on Extending Database Technology. 2006, 884–901

[10] Khalefa M E, Mokbel M F, Levandoski J J. Skyline query processing for incomplete data. In: Proceedings of the 24th IEEE International Conference on Data Engineering. 2008, 556–565

[11] Gao Y, Miao X, Cui H, Chen G, Li Q. Processing k-skyband, constrained skyline, and group-by skyline queries on incomplete data. Expert Systems with Applications, 2014, 41(10): 4959–4974

[12] Lofi C, El Maarry K, Balke W T. Skyline queries in crowd-enabled databases. In: Proceedings of International Conference on Extending Database Technology. 2013, 465–476

[13] Cheng W, Jin X, Sun J T, Lin X, Zhang X, Wang W. Searching dimension incomplete databases. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(3): 725–738

[14] Olteanu D, Koch C, Antova L. World-set decompositions: Expressiveness and efficient algorithms. Theoretical Computer Science, 2008, 403(2): 265–284

[15] Arenas M, Pérez J, Reutter J. Data exchange beyond complete data. Journal of the ACM, 2013, 60(4): 28

[16] Libkin L. Data exchange and incomplete information. In: Proceedings of ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. 2006

[17] Kharlamov E, Nutt W. Incompleteness in information integration. Proceedings of the VLDB Endowment, 2008, 1(2): 1652–1658

[18] Eiter T, Nowicki B, Leone N, Lembo D, Rosati R, Staniszkis W, Ruzzi M, Terracina G, Lio V, Kalka E, Fink M, Greco G, Faber W, Lenzerini M, Iann i G, Gottlob G. The INFOMIX system for advanced integration of incomplete and inconsistent data. In: Proceedings of ACM SIGMOD International Conference on Management of Data. 2005, 915–917

[19] Van der Meyden R. Logical approaches to incomplete information: a survey. In: Chomicki J, Saake G, . Logics for Databases and Information Systems. Springer, 1998, 307–356

[20] Guttman A. R-trees: A Dynamic Index Structure for Spatial Searching. Vol 14. ACM, 1984

[21] Miao X, Gao Y, Zheng B, Chen G, Cui H. Top-k dominating queries on incomplete data. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(1): 252–266

[22] Miao X, Gao Y, Chen G, Zheng B, Cui H. Processing incomplete k nearest neighbor search. IEEE Transactions on Fuzzy Systems, 2016

[23] Brinis S, Traina A J M, Traina Jr C. Analyzing missing data in metric spaces. Journal of Information and Data Management, 2014, 5(3): 224

[24] Borzsonyi S, Kossmann D, Stocker K. The skyline operator. In: Proceedings of the 11th IEEE International Conference on Data Engineering. 2001, 421–430

[25] Bharuka R, Kumar P S. Finding skylines for incomplete data. In: Proceedings of Australasian Database Conference. 2013, 109–117

[26] Miao X, Gao Y, Chen L, Chen G, Li Q, Jiang T. On efficient k-skyband query processing over incomplete data. In: Proceedings of International Conference on Database Systems for Advanced Applications. 2013, 424–439

[27] Babanejad G, Ibrahim H, Udzir N I, Sidi F, Aljuboori A A A. Finding skyline points over dynamic incomplete database. In: Proceedings of Malaysian National Conference on Databases. 2014

[28] Bharuka R, Kumar P S. Finding superior skyline points from incomplete data. In: Proceedings of International Conference on Management of Data. 2013, 35–44

[29] Soliman M A, Ilyas I F, Ben-David S. Supporting ranking queries on uncertain and incomplete data. The VLDB Journal, 2010, 19(4): 477–501

[30] Zhang Z, Lu H, Ooi B C, Tung A K. Understanding the meaning of a shifted sky: a general framework on extending skyline query. The VLDB Journal, 2010, 19(2): 181–201

[31] Franklin M J, Kossmann D, Kraska T, Ramesh S, Xin R. CrowdDB: Answering queries with crowdsourcing. In: Proceedings of ACM SIGMOD International Conference on Management of Data. 2011, 61–72

[32] Lofi C, El Maarry K, Balke W T. Skyline queries over incomplete data-error models for focused crowd-sourcing. In: Proceedings of International Conference on Conceptual Modeling. 2013, 298–312

[33] Nieke C, Güntzer U, Balke W T. Topcrowd. In: Proceedings of International Conference on Conceptual Modeling. 2014, 122–135

[34] Dixon J K. Pattern recognition with partly missing data. IEEE Transactions on Systems, Man, and Cybernetics, 1979, 9(10): 617–621

[35] Cheng W, Jin X, Sun J T. Probabilistic similarity query on dimension incomplete data. In: Proceedings of IEEE International Conference on Data Mining. 2009, 81–90

[36] Cuzzocrea A, Nucita A. I-SQE: a query engine for answering range queries over incomplete spatial databases. In: Proceedings of International Conference on Knowledge-Based and Intelligent Information and Engineering Systems. 2009, 91–101

[37] Cuzzocrea A, Nucita A. Reasoning on incompleteness of spatial information for effectively and efficiently answering range queries over incomplete spatial databases. In: Proceedings of International Conference on Flexible Query Answering Systems. 2009, 37–52

[38] Haghani P, Michel S, Aberer K. Evaluating top-k queries over incomplete data streams. In: Proceedings of the 18th ACM Conference on Information and Knowledge Management. 2009, 877–886

[39] Kolomvatsos K, Anagnostopoulos C, Hadjiefthymiades S. A time optimized scheme for top-k list maintenance over incomplete data streams. Information Sciences, 2015, 311: 59–73

[40] Ma Z, Zhang K, Wang S, Yu C. A double-index-based k-dominant skyline algorithm for incomplete data stream. In: Proceedings of the 4th IEEE International Conference on Software Engineering and Service Science. 2013, 750–753

[41] Abiteboul S, Segoufin L, Vianu V. Representing and querying XML with incomplete information. ACM Transactions on Database Systems, 2006, 31(1): 208–254

[42] Barceló P, Libkin L, Poggi A, Sirangelo C. XML with incomplete information: models, properties, and query answering. In: Proceedings of ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. 2009, 237–246

[43] Barceló P, Libkin L, Poggi A, Sirangelo C. XML with incomplete information. Journal of the ACM, 2010, 58(1): 4

[44] David C, Libkin L, Murlak F. Certain answers for XML queries. In: Proceedings of ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. 2010, 191–202

[45] Gheerbrant A, Libkin L, Tan T. On the complexity of query answering over incomplete XML documents. In: Proceedings of the 15th ACM International Conference on Database Theory. 2012, 169–181

[46] Gheerbrant A, Libkin L. Certain answers over incomplete XML documents: extending tractability boundary. Theory of Computing Systems, 2015, 57(4): 892–926

[47] Nikolaou C, Koubarakis M. Querying incomplete geospatial information in RDF. In: Proceedings of International Symposium on Spatial and Temporal Databases. 2013, 447–450

[48] Pema E, Tan W C. Query answering over incomplete and uncertain RDF. International Workshop on the Web and Databases, 2014

[49] Twala B, Cartwright M, Shepperd M. Comparison of various methods for handling incomplete data in software engineering databases. In: Proceedings of IEEE International Symposium on Empirical Software Engineering. 2005

[50] Little R J A, Rubin D B. Statistical Analysis with Missing Data. New York: John Wiley & Sons, 2014

[51] García-Laencina P J, Sancho-Gómez J L, Figueiras-Vidal A R. Pattern classification with missing data: a review. Neural Computing and Applications, 2010, 19(2): 263–282

[52] Rubin D B. Multiple Imputation for Nonresponse in Surveys. Vol 81. New York: John Wiley & Sons, 2004

[53] Manly B F J. Multivariate statistical methods: a primer. Boca Raton: CRC Press, 1994

[54] Van Hulle M M. Self-organizing maps. In: Rozenberg G, Bäck T, Kok J N, . Handbook of Natural Computing. Berlin: Springer, 2012, 585–622

[55] Samad T, Harp S A. Self–organization with partial data. Network: Computation in Neural Systems, 2009

[56] Fessant F, Midenet S. Self-organising map for data imputation and correction in surveys. Neural Computing & Applications, 2002, 10(4): 300–310

[57] Farhangfar A, Kurgan L, Pedrycz W. A novel framework for imputation of missing values in databases. IEEE Transactions on Systems, Man, and Cybernetics, 2007, 37(5): 692–709

[58] Jerez J M, Molina I, García-Laencina P J, Alba E, Ribelles N, Martín M, Franco L. Missing data imputation using statistical and machine learning methods in a real breast cancer problem. Artificial Intelligence in Medicine, 2010, 50(2): 105–115

[59] Schmitt P, Mandel J, Guedj M. A comparison of six methods for missing data imputation. Journal of Biometrics & Biostatistics, 2015

[60] Zhu X, Zhang S, Jin Z, Zhang Z, Xu Z. Missing value estimation for mixed-attribute data sets. IEEE Transactions on Knowledge and Data Engineering, 2011, 23(1): 110–121

[61] Lobato F, Sales C, Araujo I, Tadaiesky V, Dias L, Ramos L, Santana A. Multi-objective genetic algorithm for missing data imputation. Pattern Recognition Letters, 2015, 68: 126–131

[62] García J C F, Kalenatic D, Bello C A L. Missing data imputation in multivariate data by evolutionary algorithms. Computers in Human Behavior, 2011, 27(5): 1468–1474

[63] Krishna M, Ravi V. Particle swarm optimization and covariance matrix based data imputation. In: Proceedings of IEEE International Conference on Computational Intelligence and Computing Research. 2013, 1–6

[64] Gautam C, Ravi V. Evolving clustering based data imputation. In: Proceedings of International Conference on Circuit, Power and Computing Technologies. 2014, 1763–1769

[65] Gautam C, Ravi V. Data imputation via evolutionary computation, clustering and a neural network. Neurocomputing, 2015, 156: 134–142

[66] Hung N Q V, Thang D C, Weidlich M, Aberer K. Minimizing efforts in validating crowd answers. In: Proceedings of ACM SIGMOD International Conference on Management of Data. 2015, 999–1014

[67] Trushkowsky B, Kraska T, Franklin M J, Sarkar P. Crowdsourced enumeration queries. In: Proceedings of the 29th IEEE International Conference on Data Engineering. 2013, 673–684

[68] Chu X, Morcos J, Ilyas I F, Ouzzani M, Papotti P, Tang N, Ye Y. KATARA: a data cleaning system powered by knowledge bases and crowdsourcing. In: Proceedings of ACM SIGMOD International Conference on Management of Data. 2015, 1247–1261

[69] Li Z, Sharaf M A, Sitbon L, Sadiq S, Indulska M, Zhou X. A webbased approach to data imputation. World Wide Web, 2014, 17(5): 873–897

[70] Li Z, Shang S, Xie Q, Zhang X. Cost reduction for Web-based data imputation. In: Proceedings of International Conference on Database Systems for Advanced Applications. 2014, 438–452

[71] Li Z, Qin L, Cheng H, Zhang X, Zhou X. TRIP: an interactive retrieving-inferring data imputation approach. IEEE Transactions on Knowledge and Data Engineering, 2015, 27(9): 2550–2563

[72] Elmeleegy H, Madhavan J, Halevy A. Harvesting relational tables from lists on the Web. Proceedings of the VLDB Endowment, 2009, 2(1): 1078–1089

[73] Gupta R, Sarawagi S. Answering table augmentation queries from unstructured lists on theWeb. Proceedings of the VLDB Endowment, 2009, 2(1): 289–300

[74] Yakout M, Ganjam K, Chakrabarti K, Chaudhuri S. Infogather: Entity augmentation and attribute discovery by holistic matching with Web tables. In: Proceedings of ACM SIGMOD International Conference on Management of Data. 2012, 97–108

[75] Fan W, Li J, Ma S, Tang N, Yu W. Towards certain fixes with editing rules and master data. Proceedings of the VLDB Endowment, 2010, 3(1-2): 173–184

[76] Song S, Chen L. Differential dependencies: reasoning and discovery. ACM Transactions on Database Systems, 2011, 36(3): 16

[77] Song S, Zhang A, Chen L, Wang J. Enriching data imputation with extensive similarity neighbors. Proceedings of the VLDB Endowment, 2015, 8(11): 1286–1297

[78] Fan W. Dependencies revisited for improving data quality. In: Proceedings of ACM SIGMOD International Conference on Management of Data. 2008, 159–170

[79] Zhang S, Jin Z, Zhu X. Missing data imputation by utilizing information within incomplete instances. Journal of Systems and Software, 2011, 84(3): 452–459

[80] Aydilek I B, Arslan A. A hybrid method for imputation of missing values using optimized fuzzy c-means with support vector regression and a genetic algorithm. Information Sciences, 2013, 233: 25–35

[81] Nelwamondo F V, Golding D, Marwala T. A dynamic programming approach to missing data estimation using neural networks. Information Sciences, 2013, 237: 49–58

[82] Pan R, Yang T, Cao J, Lu K, Zhang Z. Missing data imputation by k nearest neighbours based on grey relational structure and mutual information. Applied Intelligence, 2015, 43(3): 614–632

[83] Tian J, Yu B, Yu D, Ma S. Missing data analyses: A hybrid multiple imputation algorithm using Gray System Theory and entropy based on clustering. Applied Intelligence, 2014, 40(2): 376–388

[84] Grzymala-Busse J W, Wang A Y. Modified algorithms LEM1 and LEM2 for rule induction from data with missing attribute values. In: Proceedings of the 5th International Workshop on Rough Sets and Soft Computing at the 3rd Joint Conference on Information Sciences. 1997, 69–72

[85] Grzymala-Busse J W. Rough set strategies to data with missing attribute values. In: Lin T Y, Ohsuga S, Liau C J, , . Foundations and Novel Approaches in Data Mining. Studies in Computational Intelligence, Vol 9. Berlin: Springer, 2006, 197–212

[86] Junior J R B, do Carmo Nicoletti M, Zhao L. An embedded imputation method via attribute-based decision graphs. Expert Systems with Applications, 2016, 57: 159–177

[87] Zhong C, Pedrycz W, Wang D, Li L, Li Z. Granular data imputation: a framework of granular computing. Applied Soft Computing, 2016, 46: 307–316

[88] Liu S, Dai H, Gan M. Information-decomposition-model-based missing value estimation for not missing at random dataset. International Journal of Machine Learning and Cybernetics, 2015, 1–11

[89] Leke C, Marwala T, Paul S. Proposition of a theoretical model for missing data imputation using deep learning and evolutionary algorithms. 2015, arXiv:1512.01362

[90] Asif M T, Mitrovic N, Garg L, Dauwels J, Jaillet P. Low-dimensional models for missing data imputation in road networks. In: Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing. 2013, 3527–3531

[91] Cismondi F, Fialho A S, Vieira S M, Reti S R, Sousa J M, Finkelstein S N. Missing data in medical databases: impute, delete or classify? Artificial Intelligence in Medicine, 2013, 58(1): 63–72

[92] Cheema J R. A review of missing data handling methods in education research. Review of Educational Research, 2014, 84(4): 487–508

[93] Enders C K. Dealing with missing data in developmental research. Child Development Perspectives, 2013, 7(1): 27–31

[94] Aste M, Boninsegna M, Freno A, Trentin E. Techniques for dealing with incomplete data: a tutorial and survey. Pattern Analysis and Applications, 2015, 18(1): 1–29

[95] Folch-Fortuny A, Arteaga F, Ferrer A. Missing data imputation toolbox for MATLAB. Chemometrics and Intelligent Laboratory Systems, 2016, 154: 93–100

[96] Templ M, Alfons A, Filzmoser P. Exploring incomplete data using visualization techniques. Advances in Data Analysis and Classification, 2012, 6(1): 29–47

[97] Kuosmanen T, Post T. Measuring economic efficiency with incomplete price information: with an application to European commercial banks. European Journal of Operational Research, 2001, 134(1): 43–58

[98] Fernández-Vázquez E. Recovering matrices of economic flows from incomplete data and a composite prior. Entropy, 2010, 12(3): 516–527

[99] Wang Y, Chen C. Grey markov model forecast in economic system under incomplete information and its application on foreign direct investment. In: Proceedings of International Conference on Information Management, Innovation Management and Industrial Engineering. 2011, 117–120

[100] Hassanzadeh H R, Phan J H, Wang M D. A semi-supervised method for predicting cancer survival using incomplete clinical data. In: Proceedings of the 37th Annual International Conference of the IEEE Engineering in Medicine and Biology Society. 2015, 210–213

[101] Abreu P H, Amaro H, Silva D C, Machado P, Abreu M H, Afonso N, Dourado A. Overall survival prediction for women breast cancer using ensemble methods and incomplete clinical data. In: Proceedings of XIII Mediterranean Conference on Medical and Biological Engineering and Computing 2013. 2014, 1366–1369

[102] Zaffalon M, Wesnes K, Petrini O. Reliable diagnoses of dementia by the naive credal classifier inferred from incomplete cognitive data. Artificial Intelligence in Medicine, 2003, 29(1): 61–79

[103] Schneider T. Analysis of incomplete climate data: Estimation of mean values and covariance matrices and imputation of missing values. Journal of Climate, 2001, 14(5): 853–871

[104] Plaia A, Bondì A L. Single imputation method of missing values in environmental pollution data sets. Atmospheric Environment, 2006, 40(38): 7316–7330

[105] Miyama E, Managi S. Global environmental emissions estimate: application of multiple imputation. Environmental Economics and Policy Studies, 2014, 16(2): 115–135

[106] Antova L, Koch C, Olteanu D. MayBMS: managing incomplete information with probabilistic world-set decompositions. In: Proceedings of the 23rd IEEE International Conference on Data Engineering. 2007, 1479–1480

[107] Huang J, Antova L, Koch C, Olteanu D. MayBMS: a probabilistic database management system. In: Proceedings of ACM SIGMOD International Conference on Management of Data. 2009, 1071–1074

[108] Kambhampati S, Wolf G, Chen Y, Khatri H, Chokshi B, Fan J, Nambiar U. QUIC: handling query imprecision & data incompleteness in autonomous databases. In: Proceedings of Conference on Innovative Data Systems Research. 2007, 7–10

[109] Widom J. Trio: a system for integrated management of data, accuracy, and lineage. Technical Report, 2004

[110] Wolf G, Khatri H, Chokshi B, Fan J, Chen Y, Kambhampati S. Query processing over incomplete autonomous databases. In: Proceedings of the 33rd International Conference on Very Large Data Bases. 2007, 651–662

[111] Wolf G, Kalavagattu A, Khatri H, Balakrishnan R, Chokshi B, Fan J, Chen Y, Kambhampati S. Query processing over incomplete autonomous databases: query rewriting using learned data dependencies. The VLDB Journal, 2009, 18(5): 1167–1190

[112] Raghunathan R, De S, Kambhampati S. Bayesian networks for supporting query processing over incomplete autonomous databases. Journal of Intelligent Information Systems, 2014, 42(3): 595–618

[113] Qarabaqi B, Riedewald M. User-driven refinement of imprecise queries. In: Proceedings of the 30th IEEE International Conference on Data Engineering. 2014, 916–927

RIGHTS & PERMISSIONS

2018 Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature