Distributed Threshold Querying of General Functions by a Difference of Monotonic Representation

Guy Sagy, Daniel Keren, Izchak Sharfman, Assaf SchusterPVLDB 2010 · DOI · OpenReview

TL;DR

This paper introduces a novel method for efficiently querying distributed datasets, even when the scoring functions are complex and non-monotonic. By representing these functions as a difference of two simpler monotonic functions, the authors achieve significant reductions in communication and data access costs compared to naive approaches.

What Problem Does This Paper Address?

In many modern applications, data is spread across multiple distributed nodes (e.g., sensor networks, large web services). A common task is to identify objects whose "score" exceeds a certain threshold. This score is typically calculated by aggregating attribute values from different nodes and then applying a scoring function. The challenge arises when this scoring function is non-linear or non-monotonic, making it difficult to efficiently prune data and reduce the massive communication and storage overhead required to gather all data at a central location. Existing methods are often limited to monotonic functions, leaving a significant gap for more complex, real-world scenarios.

Methods

The core innovation of this paper is the Difference of Monotonic (d.m.) representation. The authors propose to decompose any general, non-monotonic scoring function $f(x)$ into the difference of two monotonic functions: $f(x) = m_1(x) - m_2(x)$. This decomposition is possible for a broad class of functions, including those with bounded variation, which can approximate most continuous functions.

The algorithm, called the TB (Tentative Bound) Algorithm, leverages this d.m. representation. It works in two main phases:

  1. Monotonic Querying (TB-Monotonic): For the monotonic components ($m_1$ and $m_2$), the algorithm uses "tentative upper bounds" (TUBs) and "tentative lower bounds" (TLBs) to define local constraints. These constraints allow each node to identify a "local candidate list" (LCL) of objects that might satisfy the query, drastically reducing the data sent to a central coordinator. The paper also introduces a technique to minimize local data accesses by progressively identifying skyline objects.
  2. General Querying (TB Algorithm): For non-monotonic functions, the TB algorithm introduces a "dividing threshold" ($t_{div}$). By setting local constraints on both $m_1$ (using TUBs) and $m_2$ (using TLBs) relative to this dividing threshold, the algorithm can efficiently identify objects whose score is guaranteed to be below the query threshold. The coordinator then collects the remaining candidates and computes their exact scores.

Datasets

The authors evaluated their approach using three real-world datasets:

  • Reuters Corpus (RCV1-v2): News stories tagged with content categories.
  • AOL Query Log: User search queries.
  • Netflix Prize Dataset: Movie ratings from anonymous users.

These datasets were partitioned to simulate distributed environments with varying numbers of nodes and data distributions (homogeneous and heterogeneous).

Key Insights and Ideas

  • The Power of Decomposition: The most significant insight is that complex, non-monotonic functions can be effectively handled by breaking them down into simpler, monotonic components. This d.m. representation is the key to generalizing distributed threshold querying.
  • Geometric Constraints for Pruning: The use of geometric constraints (bounding spheres) on local data vectors is crucial for efficiently pruning objects that cannot possibly meet the threshold, even before considering the scoring function.
  • Minimizing Local Accesses: The progressive detection of skyline objects significantly reduces the number of data points each node needs to examine, further optimizing performance.
  • Scalability is Maintained: The proposed method shows consistent performance gains even as the number of distributed nodes increases, a critical factor for large-scale systems.

Key Results

  • Communication Cost Reduction: The TB algorithm achieved a reduction in communication cost of two to three orders of magnitude compared to a naive approach that collects all data centrally.
  • Storage Access Cost Reduction: The method also significantly reduced local storage access costs, by two orders of magnitude compared to the naive approach.
  • Scalability: The communication cost reduction was maintained when increasing the number of nodes.
  • Comparison to OPC: While the TB algorithm is highly efficient, its communication cost was at most one order of magnitude worse than the theoretical optimal constraint algorithm (OPC), suggesting it's very close to optimal in practice.

Limitations and Future Work

  • Approximation of Total Variation: While the paper provides a method for approximating total variation, exact computation can be challenging for complex functions.
  • Optimal Dividing Threshold: The paper presents a practical method for selecting the dividing threshold ($t_{div}$), but it acknowledges that finding the absolute optimal value might require more complex optimization.
  • Future Work: The authors plan to apply the d.m. representation to other types of database queries that are currently limited to monotonic functions. They also suggest exploring more sophisticated methods for approximating total variation and finding optimal dividing thresholds.

Summary updated

BibTeX
@article{sagy2010distributed,
  author = {Guy Sagy and Daniel Keren and Izchak Sharfman and Assaf Schuster},
  title = {{Distributed Threshold Querying of General Functions by a Difference of Monotonic Representation}},
  journal = {Proc. VLDB Endow.},
  year = {2010},
  doi = {10.14778/1921071.1921072},
}
Figure