A general decision framework for structuring computation using Data Directional Scaling to process massive similarity matrices

Daniel J. Lawson, Niall M. AdamsarXiv 2014 · DOI · arXiv

Abstract

As datasets grow, it becomes computationally infeasible to process them completely with complex models. For massive datasets, we frame the order of computation as a decision problem, ensuring that partial computations provide immediate value and early stopping yields useful results. Our approach integrates two components: a decision framework to optimize the sequence of computations and an emulation framework to estimate unobserved values. We apply this to similarity matrices, where costs scale quadratically ($O(N^2)$) with the number of objects. To reason about similarities in the absence of a natural feature space, we introduce 'Data Directional Scaling' (DDS), a computationally efficient form of multidimensional scaling. This method allows for high-quality matrix reconstruction with significantly reduced computation, as demonstrated through applications in population genetics.

The Quadratic Bottleneck in Big Data

In modern data science, similarity matrices—which quantify the relationships between every pair of objects in a dataset—are fundamental to clustering, recommendation engines, and anomaly detection. However, these matrices suffer from a mathematical curse: quadratic scaling. A dataset of $N$ objects requires $N^2$ calculations. While manageable for thousands of samples, this becomes a trillion-operation bottleneck for millions of samples. When the underlying similarity metric is computationally expensive (such as those used in genomic analysis), calculating a full matrix is often impossible.

Rather than discarding data or simplifying the model, this research proposes treating computation as a resource to be budgeted. By viewing the order of operations as a decision problem, we can prioritize the most informative calculations, allowing the essential structure of the data to emerge long before the full matrix is computed.

The Three Pillars of the Framework

The proposed system operates through a sequential loop consisting of three main components:

1. The Emulator

The emulator is a statistical model tasked with predicting the values of uncalculated similarities ($S_{ij}$). Crucially, it does not just provide a point estimate; it provides a measure of uncertainty ($\delta_i$). This uncertainty is vital for the decision-making process, as it identifies which areas of the matrix the model is least confident about.

2. Data Directional Scaling (DDS)

DDS is the core innovation that enables emulation without a pre-defined feature space. Traditional techniques like Principal Component Analysis (PCA) require existing coordinates. DDS, however, creates a dynamic coordinate system using the calculated rows of the matrix as "anchors." It treats evaluated objects as basis vectors and maps unobserved objects into a simplex—a geometric generalization of a triangle—based on their similarities to these anchors. This allows the system to "triangulate" the position of new data points relative to what has already been observed.

3. The Choice Function

The choice function determines the sequence of computation. The authors evaluated several strategies:

  • Random Selection: A baseline approach that samples the matrix uniformly.
  • Furthest Distance Heuristic: An exploratory strategy that selects objects least similar to those already calculated.
  • RMSE Loss: A sophisticated strategy that uses the emulator to identify the specific calculation that will most reduce the overall Root-Mean-Square Error of the entire matrix reconstruction.

Empirical Evaluation: Genetics and Synthetic Data

The framework was tested against two primary benchmarks:

  • Synthetic Clustered Data: Using 500 samples across 10 clusters, the authors tested the emulator's robustness against noise and outliers. The results showed that the decision-based approach significantly outperformed standard matrix completion algorithms, which typically assume data is sampled randomly and the matrix is low-rank.
  • Human Genome Diversity Panel (HGDP): This real-world dataset includes 938 individuals and approximately 800,000 genetic markers. In this high-rank, non-symmetric context, the RMSE Choice criterion reconstructed the population structure much faster than random sampling, proving that intelligent ordering can extract biological insights with a fraction of the total possible computation.

Insights and Future Directions

The primary insight of this work is that statistical reasoning can be applied to the process of computation itself. By treating the unknown parts of a matrix as missing data to be inferred, we can navigate massive datasets more efficiently.

However, a current limitation is that the dimensionality of the DDS space grows as more samples are evaluated, which can eventually slow the emulator. Future work aims to address this through online clustering, where evaluated rows are grouped into "pseudo-directions" to keep the coordinate system's dimensionality constant. Additionally, parallelizing the framework across distributed systems like Spark or Hadoop could enable the processing of datasets with millions of elements, scaling the decision-making process linearly rather than quadratically.

Summary updated

Abstract

As datasets grow it becomes infeasible to process them completely with a desired model. For giant datasets, we frame the order in which computation is performed as a decision problem. The order is designed so that partial computations are of value and early stopping yields useful results. Our approach comprises two related tools: a decision framework to choose the order to perform computations, and an emulation framework to enable estimation of the unevaluated computations. The approach is applied to the problem of computing similarity matrices, for which the cost of computation grows quadratically with the number of objects. Reasoning about similarities before they are observed introduces difficulties as there is no natural space and hence comparisons are difficult. We solve this by introducing a computationally convenient form of multidimensional scaling we call `data directional scaling'. High quality estimation is possible with massively reduced computation from the naive approach, and can be scaled to very large matrices. The approach is applied to the practical problem of assessing genetic similarity in population genetics. The use of statistical reasoning in decision making for large scale problems promises to be an important tool in applying statistical methodology to Big Data.
BibTeX
@misc{lawson2014general,
  author = {Daniel J. Lawson and Niall M. Adams},
  title = {{A general decision framework for structuring computation using Data Directional Scaling to process massive similarity matrices}},
  year = {2014},
  eprint = {1403.4054},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1403.4054},
}
Figure