The DOI matches its Crossref record; 76 of the 76 references it cites were found in a registry or an index.
A survey of data partitioning and sampling methods to support big data analysis
Open accessAbstract
Computer clusters with the shared-nothing architecture are the major computing platforms for big data processing and analysis. In cluster computing, data partitioning and sampling are two fundamental strategies to speed up the computation of big data and increase scalability. In this paper, we present a comprehensive survey of the methods and techniques of data partitioning and sampling with respect to big data processing and analysis. We start with an overview of the mainstream big data frameworks on Hadoop clusters. The basic methods of data partitioning are then discussed including three classical horizontal partitioning schemes: range, hash, and random partitioning. Data partitioning on Hadoop clusters is also discussed with a summary of new strategies for big data partitioning, including the new Random Sample Partition (RSP) distributed model. The classical methods of data sampling are then investigated, including simple random sampling, stratified sampling, and reservoir sampling. Two common methods of big data sampling on computing clusters are also discussed: record-level sampling and block-level sampling. Record-level sampling is not as efficient as block-level sampling on big distributed data. On the other hand, block-level sampling on data blocks generated with the classical data partitioning methods does not necessarily produce good representative samples for approximate computing of big data. In this survey, we also summarize the prevailing strategies and related work on sampling-based approximation on Hadoop clusters. We believe that data partitioning and sampling should be considered together to build approximate cluster computing frameworks that are reliable in both the computational and statistical respects.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Scikit-learn: Machine Learning in Python
Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Müller, A., Nothman, J., Louppe, G., et al. (2012) · arXiv · doi:10.48550/arxiv.1201.0490 · Cited by 71,016
An Introduction to the Bootstrap
Efron, B., & Tibshirani, R. J. (1994) · doi:10.1201/9780429246593 · Cited by 40,500
MapReduce: simplified data processing on large clusters
Dean, J., & Ghemawat, S. (2008) · Communications of the ACM · doi:10.1145/1327452.1327492 · Cited by 18,476
The WEKA data mining software: an update
Hall, M., Frank, E., Holmes, G., Pfahringer, B., Reutemann, P., & Witten, I. H. (2009) · ACM SIGKDD Explorations Newsletter · doi:10.1145/1656274.1656278 · Cited by 17,750
Breiman, L. (1996) · Machine Learning · doi:10.1007/bf00058655 · Cited by 16,325
Classification and regression trees
Praagman, J. (1985) · European Journal of Operational Research · doi:10.1016/0377-2217(85)90321-2 · Cited by 10,053
The Hadoop Distributed File System
Shvachko, K., Kuang, H., Radia, S., & Chansler, R. (2010) · 2010 IEEE 26th Symposium on Mass Storage Systems and Technologies (MSST) · doi:10.1109/msst.2010.5496972 · Cited by 4,834
Resilient distributed datasets: a fault-tolerant abstraction for in-memory cluster computing
Zaharia, M., Chowdhury, M., Das, T., Dave, A., Ma, J. H., McCauley, M., Franklin, M. J. M., Shenker, S. J., & Stoica, I. G. (2012) · Cited by 3,622
Sagi, O., & Rokach, L. (2018) · WIREs Data Mining and Knowledge Discovery · doi:10.1002/widm.1249 · Cited by 3,103
Dryad: distributed data-parallel programs from sequential building blocks
Isard, M., Budiu, M., Yu, Y., Birrell, A., & Fetterly, D. (2007) · Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007 · doi:10.1145/1272996.1273005 · Cited by 2,432
Principles of Distributed Database Systems
Özsu, M. T., & Valduriez, P. (2020) · Springer eBooks · doi:10.1007/978-3-030-26253-2 · Cited by 2,345
Random sampling with a reservoir
Vitter, J. S. (1985) · ACM Transactions on Mathematical Software · doi:10.1145/3147.3165 · Cited by 1,758
Pig latin: a not-so-foreign language for data processing
Olston, C., Reed, B., Srivastava, U., Kumar, R., & Tomkins, A. (2008) · Proceedings of the 2008 ACM SIGMOD international conference on Management of data · doi:10.1145/1376616.1376726 · Cited by 1,730
Scalable SQL and NoSQL data stores
Cattell, R. (2011) · ACM SIGMOD Record · doi:10.1145/1978915.1978919 · Cited by 1,358
Finding frequent items in data streams
Charikar, M., Chen, K., & Farach-Colton, M. (2004) · Theoretical Computer Science · doi:10.1016/s0304-3975(03)00400-6 · Cited by 1,278
Map-Reduce for Machine Learning on Multicore
Chu, C.-T., Kim, S. K., Lin, Y.-A., Yu, Y., Bradski, G., Ng, A. Y., & Olukotun, K. (2007) · Advances in Neural Information Processing Systems 19 · doi:10.7551/mitpress/7503.003.0040 · Cited by 1,229
A Survey of Techniques for Approximate Computing
Mittal, S. (2016) · ACM Computing Surveys · doi:10.1145/2893356 · Cited by 1,058
Big data and its technical challenges.
Jagadish, H. V., Gehrke, J., Labrinidis, A., Papakonstantinou, Y., Patel, J. M., Ramakrishnan, R., & Shahabi, C. (2014) · Communications of the ACM · doi:10.1145/2611567 · Cited by 1,048
Hive - a petabyte scale data warehouse using Hadoop
Thusoo, A., Sarma, J. S., Jain, N., Shao, Z., Chakka, P., Zhang, N., Antony, S., Liu, H., & Murthy, R. (2010) · 2010 IEEE 26th International Conference on Data Engineering (ICDE 2010) · doi:10.1109/icde.2010.5447738 · Cited by 929
An Introduction to the Bootstrap.
Simonoff, J. S., Efron, B., Tibshirani, R. J., & Hjorth, J. S. U. (1994) · Journal of the American Statistical Association · doi:10.2307/2291020 · Cited by 855
SCOPE: easy and efficient parallel processing of massive data sets
Chaiken, R., Jenkins, B., Larson, P.-Å., Ramsey, B., Shakib, D., Weaver, S., & Zhou, J. (2008) · Proceedings of the VLDB Endowment · doi:10.14778/1454159.1454166 · Cited by 727
Dremel: interactive analysis of web-scale datasets
Melnik, S., Gubarev, A., Long, J. J., Romer, G., Shivakumar, S., Tolton, M., & Vassilakis, T. (2010) · Proceedings of the VLDB Endowment · doi:10.14778/1920841.1920886 · Cited by 711
BlinkDB: queries with bounded errors and bounded response times on very large data
Agarwal, S., Mozafari, B., Panda, A., Milner, H., Madden, S., & Stoica, I. (2013) · Proceedings of the 8th ACM European Conference on Computer Systems · doi:10.1145/2465351.2465355 · Cited by 694
Yu, Y., Isard, M., Fetterly, D., Budiu, M., Erlingsson, Ú., Gunda, P. K., & Currey, J. (2008) · doi:10.5555/1855741.1855742 · Cited by 689
Finding Frequent Items in Data Streams
Charikar, M., Chen, K., & Farach-Colton, M. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45465-9_59 · Cited by 650
Megastore: Providing Scalable, Highly Available Storage for Interactive Services
Baker, J. D., Bond, C. T., Corbett, J. C., Furman, J. J., Khorlin, A., Larson, J. A., Leon, J.-M., Li, Y., Lloyd, A., & Yushprakh, V. (2011) · Cited by 645
Jacobs, A. (2009) · Communications of the ACM · doi:10.1145/1536616.1536632 · Cited by 643
Schism: a workload-driven approach to database replication and partitioning
Curino, C., Jones, E., Zhang, Y., & Madden, S. (2010) · Proceedings of the VLDB Endowment · doi:10.14778/1920841.1920853 · Cited by 539
Managing performance vs. accuracy trade-offs with loop perforation
Sidiroglou-Douskos, S., Misailovic, S., Hoffmann, H., & Rinard, M. (2011) · Proceedings of the 19th ACM SIGSOFT symposium and the 13th European conference on Foundations of software engineering · doi:10.1145/2025113.2025133 · Cited by 505
Synopses for Massive Data: Samples, Histograms, Wavelets, Sketches
Cormode, G., Garofalakis, M., Haas, P. J., & Jermaine, C. (2011) · Foundations and Trends in Databases · doi:10.1561/1900000004 · Cited by 468
Enterprise Data Analysis and Visualization: An Interview Study
Kandel, S., Paepcke, A., Hellerstein, J. M., & Heer, J. (2012) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2012.219 · Cited by 439
A survey on platforms for big data analytics
Singh, D., & Reddy, C. K. (2015) · Journal of Big Data · doi:10.1186/s40537-014-0008-6 · Cited by 433
Big data analytics on Apache Spark
Salloum, S., Dautov, R., Chen, X., Peng, P. X., & Huang, J. Z. (2016) · International Journal of Data Science and Analytics · doi:10.1007/s41060-016-0027-9 · Cited by 428
Self-citationVertical partitioning algorithms for database design
Navathe, S., Ceri, S., Wiederhold, G., & Dou, J. (1984) · ACM Transactions on Database Systems · doi:10.1145/1994.2209 · Cited by 420
Exascale computing and big data
Reed, D. A., & Dongarra, J. (2015) · Communications of the ACM · doi:10.1145/2699414 · Cited by 418
Genuer, R., Poggi, J.-M., Tuleau-Malot, C., & Villa-Vialaneix, N. (2017) · Big Data Research · doi:10.1016/j.bdr.2017.07.003 · Cited by 367
On the use of MapReduce for imbalanced big data using Random Forest
del Río, S., López, V., Benítez, J. M., & Herrera, F. (2014) · Information Sciences · doi:10.1016/j.ins.2014.03.043 · Cited by 328
Random sampling for histogram construction: how much is enough?
Chaudhuri, S., Motwani, R., & Narasayya, V. R. (1998) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/276304.276343 · Cited by 265
Jaql: a scripting language for large scale semistructured data analysis
Beyer, K. S., Ercegovac, V., Gemulla, R., Balmin, A., Eltabakh, M., Kanne, C.-C., Ozcan, F., & Shekita, E. J. (2011) · Proceedings of the VLDB Endowment · doi:10.14778/3402755.3402761 · Cited by 218
Considerations for big data: Architecture and approach
Bakshi, K. (2012) · 2012 IEEE Aerospace Conference · doi:10.1109/aero.2012.6187357 · Cited by 216
Relational Cloud: A Database-as-a-Service for the Cloud
Curino, C., Jones, E. P. C., Popa, R. A., et al. (2011) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 190
ApproxHadoop: Bringing Approximations to MapReduce Frameworks
Goiri, I., Bianchini, R., Nagarakatte, S., & Nguyen, T. D. (2015) · Proceedings of the Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems · doi:10.1145/2694344.2694351 · Cited by 178
Approximate Query Processing: Taming the TeraBytes
Garofalakis, M., & Gibbon, P. B. (2001) · Very Large Data Bases · Cited by 174
ElasTraS: An Elastic Transactional Data Store in the CloudPreprint
Das, S., Agrawal, D., & Abbadi, A. E. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1008.3751 · Cited by 165
Scaling big data mining infrastructure: the twitter experience
Lin, J., & Ryaboy, D. (2013) · ACM SIGKDD Explorations Newsletter · doi:10.1145/2481244.2481247 · Cited by 165
A comprehensive view of Hadoop research—A systematic literature review
Polato, I., Ré, R., Goldman, A., & Kon, F. (2014) · Journal of Network and Computer Applications · doi:10.1016/j.jnca.2014.07.022 · Cited by 162
Learning Spark: Lightning-Fast Big Data Analytics
Karau, H., Konwinski, A., Wendell, P., & Zaharia, M. (2015) · O'Reilly Media, Inc. eBooks · Cited by 162
Knowing when you're wrong: building fast and reliable approximate query processing systems
Agarwal, S., Milner, H., Kleiner, A., Talwalkar, A., Jordan, M., Madden, S., Mozafari, B., & Stoica, I. (2014) · Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data · doi:10.1145/2588555.2593667 · Cited by 159
On biased reservoir sampling in the presence of stream evolution
Aggarwal, C. C. (2006) · Very Large Data Bases · doi:10.5555/1182635.1164180 · Cited by 148
MacroBase: Prioritizing Attention in Fast Data
Bailis, P. D., Gan, E., Madden, S. R., Narayanan, D., Rong, K., & Suri, S. (2017) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/3035918.3035928 · Cited by 135
Tenzing a SQL implementation on the MapReduce framework
Chattopadhyay, B., Liang, L., Liu, W., et al. (2011) · Proceedings of the VLDB Endowment · doi:10.14778/3402755.3402765 · Cited by 133
On statistics, computation and scalability
Jordan, M. I. (2013) · Bernoulli · doi:10.3150/12-bejsp17 · Cited by 127
Adapting microsoft SQL server for cloud computing
Bernstein, P. A., Cseri, I., Dani, N., Ellis, N., Kalhan, A., Kakivaya, G., Lomet, D., Manne, R., Novik, L., & Talius, T. (2011) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2011.5767935 · Cited by 123
Approximate computing: Challenges and opportunities
Agrawal, A., Sura, Z., Choi, J., Gopalakrishnan, K., Gupta, S., Nair, R., Oh, J., Prener, D. A., Shukla, S., & Srinivasan, V. (2016) · IEEE International Conference on Rebooting Computing (ICRC) · doi:10.1109/icrc.2016.7738674 · Cited by 102
A survey of peer-to-peer storage techniques for distributed file systems
Hasan, R., Anwar, Z., Yurcik, W. J., Brumbaugh, L. J., & Campbell, R. H. (2005) · International Conference on Information Technology: Coding and Computing (ITCC) · doi:10.1109/itcc.2005.42 · Cited by 99
Scalable Simple Random Sampling and Stratified Sampling
Meng, X. (2013) · Cited by 91
ApproxIoT: Approximate Analytics for Edge Computing
Wen, Z., Quoc, D. L., Bhatotia, P., Chen, R., & Lee, M. (2018) · IEEE International Conference on Distributed Computing Systems (ICDCS) · doi:10.1109/icdcs.2018.00048 · Cited by 79
Research Directions for Engineering Big Data Analytics Software
Otero, C. E., & Peter, A. M. (2014) · IEEE Intelligent Systems · doi:10.1109/mis.2014.76 · Cited by 70
Krishnan, D. R., Quoc, D. L., Bhatotia, P., Fetzer, C. W., & Rodrigues, R. (2016) · International World Wide Web Conference (WWW) · doi:10.1145/2872427.2883026 · Cited by 70
Cormode, G., & Duffield, N. G. (2014) · ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/2623330.2630811 · Cited by 50
An improved partitioning mechanism for optimizing massive data analysis using MapReduce
Slagter, K. D., Hsu, C., Chung, Y., & Zhang, D. (2013) · The Journal of Supercomputing · doi:10.1007/s11227-013-0924-9 · Cited by 49
Sampling techniques to improve big data exploration
Rojas, J. A. R., Kery, M. B., Rosenthal, S. L., & Dey, A. K. (2017) · IEEE Symposium on Large Data Analysis and Visualization · doi:10.1109/ldav.2017.8231848 · Cited by 47
Robust, Scalable, and Fast Bootstrap Method for Analyzing Large Scale Data
Basiri, S., Ollila, E., & Koivunen, V. (2015) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2015.2498121 · Cited by 45
A Two-Stage Data Processing Algorithm to Generate Random Sample Partitions for Big Data Analysis
Wei, C., Salloum, S., Emara, T. Z., Zhang, X., Huang, J. Z., & He, Y. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-94295-7_24 · Cited by 36
Self-citationSynopses for Massive Data: Samples, Histograms, Wavelets, Sketches
Cormode, G. (2011) · doi:10.1561/9781601985170 · Cited by 29
Exploring and cleaning big data with random sample data blocks
Salloum, S., Huang, J. Z., & He, Y. (2019) · Journal Of Big Data · doi:10.1186/s40537-019-0205-4 · Cited by 26
Self-citationAn Asymptotic Ensemble Learning Framework for Big Data Analysis
Salloum, S., Huang, J. Z., He, Y., & Chen, X. (2018) · IEEE Access · doi:10.1109/access.2018.2889355 · Cited by 25
Self-citationScalable transactions in cloud data stores
Ahirrao, S. N., & Ingle, R. (2015) · Journal of Cloud Computing Advances Systems and Applications · doi:10.1186/s13677-015-0047-3 · Cited by 24
Gavagsaz, E., Rezaee, A., & Javadi, H. H. S. (2018) · The Journal of Supercomputing · doi:10.1007/s11227-018-2391-9 · Cited by 17
Optimizing Sequence Alignment in Cloud Using Hadoop and MPP Database
Vijayakumar, S., Bhargavi, A., Praseeda, U., & Ahamed, S. A. (2012) · IEEE ... International Conference on Cloud Computing · doi:10.1109/cloud.2012.34 · Cited by 13
A Literature Review on Hadoop Ecosystem and Various Techniques of Big Data Optimization
Singh, V. K., Taram, M., Agrawal, V., & Baghel, B. S. (2018) · Lecture notes in networks and systems · doi:10.1007/978-981-10-8360-0_22 · Cited by 13
High Performance Database Processing
Taniar, D. (2012) · International Conference on Advanced Information Networking and Applications (AINA) · doi:10.1109/aina.2012.140 · Cited by 9
MacroBase: Prioritizing Attention in Fast DataPreprint
Bailis, P. D., Gan, E., Madden, S. R., Narayanan, D., Rong, K., & Suri, S. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1603.00567 · Cited by 9
State of the Art in Distributed File Systems: Increasing Performance
Bžoch, P., & Safarik, J. (2011) · Eastern European Regional Conference on the Engineering of Computer Based Systems (ECBS-EERC) · doi:10.1109/ecbs-eerc.2011.34 · Cited by 8
Workload-Driven Vertical Partitioning for Effective Query Processing over Raw DataPreprint
Zhao, W., Cheng, Y., & Rusu, F. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1503.08946 · Cited by 4
Green- and heterogeneity-aware partitioning for data analytics
Chakrabarti, A., Parthasarathy, S., & Stewart, C. (2016) · IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS) · doi:10.1109/infcomw.2016.7562103 · Cited by 4
Cited by
Yin, X., Zhu, Y., & Hu, J. (2022) · ACM Computing Surveys · doi:10.1145/3460427 · Cited by 638
Himeur, Y., Elnour, M., Fadli, F., Meskin, N., Petri, I., Rezgui, Y., Bensaali, F., & Amira, A. (2023) · Artificial Intelligence Review · doi:10.1007/s10462-022-10286-2 · Cited by 541
Big data with cloud computing: Discussions and challenges
Sandhu, A. K. (2022) · Big Data Mining and Analytics · doi:10.26599/bdma.2021.9020016 · Cited by 280
A systematic review of privacy techniques in recommendation systems
Ogunseyi, T. B., Avoussoukpo, C. B., & Jiang, Y. (2023) · International Journal of Information Security · doi:10.1007/s10207-023-00710-1 · Cited by 27
“In a distributed data environment, there are three types of data partitioning: horizontal, vertical, and arbitrary partitioning [147].”
BackgroundSemantic Image Analysis on Social Networks and Data Processing: Review and Future Directions
Alzboon, M. S., Alqaraleh, M. K., Aljarrah, E. M., & Alomari, S. A. (2022) · Advances in Business Information Systems and Analytics · doi:10.4018/978-1-7998-9016-4.ch009 · Cited by 1
Metadata
- Authors
- Mahmud, M. S., Huang, J. Z., Salloum, S., Emara, T. Z., & Sadatdiynov, K.
- Venue
- Big Data Mining and Analytics
- Publisher
- Tsinghua University Press
- Published
- 2020-06
- Volume
- 3
- Issue
- 2
- Pages
- 85-101
- ISSN
- 2096-0654 (ISSN-L)
- 2097-406X
- OpenAlex
- W3018761215
- Cited by
- 282
- References
- 76
- FWCI
- 42.31
- Type
- journal article
- Language
- en
- Open access
- diamond
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.