Data Partitioning View of Mining Big Data

Shichao ZhangarXiv 2016 · arXiv

Abstract

Traditional centralized data mining faces significant hurdles when dealing with petabyte-scale datasets, primarily due to the "memory wall" and the loss of localized structural information. This paper proposes a "partition-and-synthesize" framework that divides big data into manageable subsets. This approach not only improves computational efficiency but also enables the discovery of "local" patterns—such as outliers and specific trends—that are typically obscured by global mining techniques.

Introduction: The Memory Wall and Structural Loss

The fundamental challenge in big data mining is the physical limitation of computer memory. In the late 1990s, it became clear that identifying frequent patterns in massive datasets was impossible using traditional in-memory algorithms. However, the problem is not just hardware-related; it is also conceptual. Centralized mining, which aggregates all data to find "global" patterns, often destroys the structural information hidden within subsets. For instance, a global average might suggest stability, while localized segments could reveal high-frequency bursts or anomalies critical for decision-making.

The Partition-and-Synthesize Framework

To address these challenges, the paper outlines a strategy where data is partitioned, mined locally, and then synthesized into a global model.

Figure 1: The conceptual framework for partitioning big data into subsets to mine local patterns and synthesize global insights.

As shown in Figure 1, the process involves partitioning "Big Data" into "Data Subsets." These subsets are mined to identify "Local Patterns," which are then synthesized into "Global Patterns." This workflow allows for an approximation of the patterns that would ideally be found in the entire dataset, while maintaining the integrity of local insights.

Key Methodologies

Several strategies have been developed to implement this view:

  • Local Pattern Analysis (LPA): Nodes share discovered patterns rather than raw data, reducing computational overhead and enhancing privacy.
  • Anytime Mining: Utilizing sequential random sampling, this method provides rapid, approximate results (e.g., 75% accuracy) that refine over time as more samples are processed.
  • Syllogistic (Golden) Partitioning: Data is categorized by "temperature" (Hot, Warm, Cold) based on access frequency, prioritizing the most relevant 5% of data for mining.
  • Incremental and Decremental Mining: These algorithms update patterns as data changes, avoiding the need for full re-mining.

The Significance of Local Patterns

A core insight of this research is the distinction between different pattern types. While Pattern A represents global trends, Pattern B (subspace patterns/outliers) and Pattern C (localized trends) only emerge within specific data segments.

Figure 2: Support levels for Patterns A, B, and C across various data subsets, illustrating how certain patterns only appear in specific partitions.

Figure 2 demonstrates that while Pattern A might be consistently present, Patterns B and C are often localized. In centralized mining, these crucial signals are frequently "washed out." The paper uses the "Tennis Paradox" to illustrate this: a player might win a match by winning two sets (e.g., 6:4, 0:6, 6:4) even if their opponent won more total games (14:12). Centralizing the data (counting total games) loses the "rules of the game"—the structural information that defines the winner.

Conclusion and Future Directions

The data partitioning view makes mining physically impossible datasets feasible. Results from "Anytime Mining" show that even initial samples can yield high approximation accuracy, which improves steadily. Future work focuses on "knowledge evolution" models, where algorithms adapt to real-time changes, similar to how medical treatments evolve with a patient's symptoms. By focusing on local patterns, organizations can gain deeper insights while maintaining data privacy and computational efficiency.

Summary updated

Abstract

There are two main approximations of mining big data in memory. One is to partition a big dataset to several subsets, so as to mine each subset in memory. By this way, global patterns can be obtained by synthesizing all local patterns discovered from these subsets. Another is the statistical sampling method. This indicates that data partitioning should be an important strategy for mining big data. This paper recalls our work on mining big data with a data partitioning and shows some interesting findings among the local patterns discovered from subsets of a dataset.
BibTeX
@misc{zhang2016data,
  author = {Shichao Zhang},
  title = {{Data Partitioning View of Mining Big Data}},
  year = {2016},
  eprint = {1611.09691},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1611.09691},
}
Figure