PaperlayerView exact revision on arXiv

Source-linked AI summary

A Unified Approach to Ranking in Probabilistic Databases

Jian Li, Barna Saha, Amol Deshpande

arXiv:0904.1366v4cs.DBcs.DS

TL;DR

Probabilistic databases need ranking methods that reconcile uncertain tuple existence with relevance scores across many decision-support applications. The paper formulates ranking as multi-criteria optimization, introduces parameterized PRFω and PRFe functions with generating-functions algorithms, and studies approximation, learning, and consensus interpretations. It reports scalable exact or approximate ranking over large and correlated datasets, while identifying limitations for deep correlations, DFT approximation, and diverse multi-user preferences.

  • Problem

    Ranking uncertain data is difficult because score distributions and tuple uncertainties create competing criteria, while applications need top-k decisions over large datasets.

  • Method

    The paper derives dataset features, proposes parameterized PRFω and PRFe ranking functions, and develops generating-functions algorithms for correlated probabilistic datasets, approximation, and preference learning.

  • Results

    The proposed algorithms support efficient exact or approximate ranking on large, possibly correlated datasets, and PRFω rankings admit a consensus-answer interpretation.

  • Takeaways & Limitations

    Parameterized functions let users control top-k results while the framework connects ranking, approximation, preference learning, and consensus answers within one approach.

  • Takeaways & Limitations

    The running time depends on correlation-tree height, DFT approximation can require many exponentials and large N, and one PRF function models only one user.

Abstract

from arXiv · show

The dramatic growth in the number of application domains that naturally generate probabilistic, uncertain data has resulted in a need for efficiently supporting complex querying and decision-making over such data. In this paper, we present a unified approach to ranking and top-k query processing in probabilistic databases by viewing it as a multi-criteria optimization problem, and by deriving a set of features that capture the key properties of a probabilistic dataset that dictate the ranked result. We contend that a single, specific ranking function may not suffice for probabilistic databases, and we instead propose two parameterized ranking functions, called PRF-w and PRF-e, that generalize or can approximate many of the previously proposed ranking functions. We present novel generating functions-based algorithms for efficiently ranking large datasets according to these ranking functions, even if the datasets exhibit complex correlations modeled using probabilistic and/xor trees or Markov networks. We further propose that the parameters of the ranking function be learned from user preferences, and we develop an approach to learn those parameters. Finally, we present a comprehensive experimental study that illustrates the effectiveness of our parameterized ranking functions, especially PRF-e, at approximating other ranking functions and the scalability of our proposed algorithms for exact or approximate ranking.

1 Introduction

Ranking in probabilistic databases must balance score distributions, tuple uncertainty, and user preferences rather than rely on one universally appropriate function. The paper proposes parameterized ranking functions and scalable algorithms for exact, approximate, correlated-data ranking.

  • Motivation: Uncertain-data applications require ranking or top-k processing to select relevant objects from large datasets for decision support.Examples include house search, financial investment, feature selection, and sensor or scientific data analysis.
  • Motivation: Ranking is inherently a multi-criteria optimization problem because score and probability can favor different tuples.The preferred trade-off depends on the application domain or user preferences.
  • Parameterized ranking: The framework identifies key dataset features, proposes parameterized ranking functions, and learns their parameters from user preferences or feedback.The proposed functions are designed to support user-controlled ranking choices.
  • Algorithms: Generating-functions algorithms efficiently rank large datasets using PRF functions, including datasets with arbitrary correlations and especially probabilistic and/xor trees.For constant-height and/xor trees, evaluating PRFe takes O(n log(n)) time, or O(n) when pre-sorted by score.
  • Algorithms: A polynomial-time algorithm ranks correlated datasets represented by bounded-treewidth graphical models by computing tuple-position probabilities.The position-probability computation is also presented as independently useful.
  • Approximation and consensus: The paper develops DFT-based approximation of arbitrary weighted ranking functions with linear combinations of PRFe functions and connects PRFω rankings to consensus answers.The consensus interpretation uses a suitably defined distance function over possible-world answers.

2 Related Work

Prior work addressed uncertain-data management, probabilistic top-k, continuous distributions, nearest-neighbor queries, and document ranking, but these lines differ in assumptions and scope. The paper’s approach relates to these areas while extending ranking semantics to uncertain data and correlated settings.

  • Uncertain-data management: Probabilistic-database research spans data models, query languages, indexing, and systems for managing uncertain, incomplete, or fuzzy data.Examples include MYSTIQ, Trio, ORION, MayBMS, and PrDB.
  • Probabilistic top-k: Prior probabilistic top-k work ranked tuples by result probabilities, whereas this paper assumes probability and score are given or easily computed.The earlier work primarily faced efficient probability computation as its central challenge.
  • Continuous uncertainty: Research on continuous distributions obtained exact polynomial-time algorithms for some classes and approximation schemes with guarantees for arbitrary distributions.Those methods use an extension of the generating function introduced in this paper.
  • Nearest neighbors: Nearest-neighbor queries over uncertain points can be viewed as ranking queries whose scores are distances to a query point.The paper’s ranking semantics and algorithms therefore directly apply to discrete probability distributions in uncertain-point data.
  • Information retrieval: Information-retrieval ranking and learning-to-rank methods are generally document-specific and usually do not model existence uncertainty.Their focus includes keywords, terms, relevance, ranking models, loss functions, and scoring techniques.
  • Open directions: A single PRF function models one user’s preferences, leaving diverse multi-user preferences and uncertainty-aware diversity as an open research direction.Existing multi-user theoretical models cited here assume certain inputs.

3 Problem Formulation

The paper formulates probabilistic-database ranking as a multi-criteria problem over uncertain tuples, possible worlds, scores, and correlations. It proposes parameterized ranking functions that unify prior approaches and support efficient computation under several correlation models.

  • 3 Problem Formulation: The model uses possible-worlds semantics, where each tuple has an existence probability and score, and absent tuples receive infinite rank.Tuple ranks are defined within each possible world according to score.
  • 3.1 Probabilistic Database Model: Positional probability Pr(r(t) = k) measures the total probability that tuple t occupies position k across possible worlds.The collection of positional probabilities forms each tuple’s rank distribution.
  • 3.1 Probabilistic Database Model: Probabilistic and/xor trees represent mutual exclusivity and mutual co-existence correlations, with leaves denoting tuples and marked internal nodes encoding dependencies.The model includes a possible-worlds key constraint for tuples sharing a key.
  • 3.1 Probabilistic Database Model: An and/xor tree can represent finite possible worlds, including a three-world correlated example shown in Figure 2.The example combines tuple-existence probabilities, exclusive alternatives, and coexisting random sets.
  • 3.3 Parameterized Ranking Functions: Probabilistic-database ranking must balance tuple scores, existence probabilities, and score distributions rather than apply one universally appropriate criterion.The paper frames this balance as a risk-reward trade-off whose resolution depends on application or user preferences.
  • 3.3 Parameterized Ranking Functions: PRF uses features derived from positional probabilities and parameters learned from user preferences to adapt ranking across application scenarios.The framework can directly subsume some prior ranking functions and approximate others.
  • 3.3 Parameterized Ranking Functions: PRF-e can be evaluated in O(n log(n)) time for low-height and/xor-tree correlations and in O(n) time when scores are pre-sorted.The paper also develops a DFT-based approximation using linear combinations of PRF-e functions.
  • 3.3 Parameterized Ranking Functions: Generating-function methods support efficient ranking under arbitrary correlations, while bounded-treewidth graphical models admit polynomial-time positional-rank computation.For tuple-independent datasets, expected ranks can be computed in the same time as PRFℓ; analogous efficient computation extends to several correlated settings.

4 Ranking Algorithms

The paper develops generating-function algorithms for ranking tuples under independence, and/xor-tree correlations, and uncertain scores. These methods compute rank probabilities and achieve faster bounds for specialized ranking functions.

  • General approach: The algorithms first sort tuples by non-increasing deterministic scores and compute the probability that each tuple occupies each rank.Rank probabilities can then be combined with the ranking function to obtain each tuple’s score.
  • General approach: Generating functions encode rank probabilities as polynomial coefficients, avoiding exponential enumeration of possible worlds.For tuple ti, the coefficient of x^j in Fi equals Pr(r(ti) = j).
  • Tuple independence: O(n^2) computes all tuple ranking-function values for a general weight function, matching the number of rank probabilities that must be considered.Incrementally expanding Fi from Fi−1 reduces the total cost from O(n^3) to O(n^2).
  • Tuple independence: O(n · h + n log(n)) evaluates PRFω(h) on independent tuples, because only the first h rank terms require expansion.The same technique supports U-Rank top-k queries within this bound.
  • Probabilistic And/Xor Trees: For and/xor trees, assigning x to higher-scoring leaves and y to the target makes the coefficient of x^(j−1)y equal Pr(r(ti) = j).This construction extends generating-function rank computation to mutual exclusivity and co-existence correlations.
  • Attribute Uncertainty or Uncertain Scores: For uncertain scores, alternative tuples receive separate Υ scores that are summed for each original tuple; independent inputs require O(n^2) for PRF and O(n log(n)) for PRFe.The method treats discrete score distributions as score alternatives when those scores affect ranking.

5 Approximating and Learning Ranking Functions

The section develops DFT-based approximations for PRFω using linear combinations of PRFe functions, then discusses approximation and preference-based parameter learning. Adaptations involving damping, scaling, and shifting improve approximation quality while preserving efficient ranking.

  • Choosing and learning ranking functions: The authors choose between simulating or approximating a known ranking function and learning parameters from user preferences.They prefer PRFe when possible because it supports highly efficient ranking algorithms.
  • Efficiency: The DFT approximation reduces independent-tuple ranking from exact O(n^2) computation to O(n log(n)+nL) time.Each of the L PRFe computations takes linear time.
  • DFT approximation: DFT represents ω(i) as complex exponentials, and selecting L coefficients with maximum absolute value yields a lower-dimensional approximation.The paper uses DFT as the basis for approximating ranking-weight functions with fewer exponentials.
  • DFT approximation: DFT alone is periodic, computationally difficult for very large N, and poorly suited to unknown tuple counts or monotonically non-increasing ranking weights.The periodicity can assign high weights again after the chosen period, motivating additional adaptations.
  • DFT approximation: Damping, initial scaling, and extending-and-shifting adapt DFT to reduce periodicity, correct small-index bias, and improve behavior near i = 0.The final adaptation shifts an extrapolated function, applies scaling and DFT, then shifts the approximation back.
  • Empirical approximation: 20 or 30 coefficients approximate the step function well, while piecewise linear and continuous functions are easier to approximate.Figure 4 illustrates the adaptation steps for N = 1000 and L = 20.
  • Choosing and learning ranking functions: The paper proposes learning a PRFω function from preferences and then approximating it with PRFe functions, while learning a single PRFe parameter α by minimizing Kendall distance.The α search is binary-search-like and may converge only to a local minimum, although the experiments observed uni-valley behavior for prior ranking functions.

6 PRF as a Consensus Top-k Answer

This section connects probabilistic ranking to consensus top-k optimization. It shows that PT(h) and general PRFω rankings minimize expected weighted symmetric-difference distance to possible-world answers.

  • Consensus top-k: A consensus top-k answer minimizes expected distance between a selected ranking and the top-k rankings produced by possible worlds.The distance function may be chosen from several top-k ranking distances.
  • Symmetric difference and PT-k: Under symmetric difference, the k tuples with largest Pr(r(t) ≤ k) form the consensus top-k answer.This is exactly the PT(h)(k) result when h = k.
  • Symmetric difference and PT-k: The proof observes that terms independent of the selected ranking leave the largest top-k probabilities as the minimizing choice.The invariant terms do not affect which tuples minimize expected symmetric difference.
  • Weighted symmetric difference and PRFω: For positive ω supported on the first k ranks, selecting the k tuples with largest Υω(t) values minimizes expected weighted symmetric-difference distance.This generalizes the symmetric-difference equivalence from PT(h) to every PRFω function.
  • Weighted symmetric difference and PRFω: Weighted symmetric difference penalizes missing higher-ranked items according to ω(i), but the paper notes that its relationship to Spearman’s rho and Kendall’s tau remains open.The distance reduces to ordinary symmetric difference when ω is constant and is not necessarily symmetric.

7 An Interesting Property of PRFe

The section characterizes how PRFe rankings change as α ranges from 0 to 1. Pairwise orderings are stable when endpoints agree and otherwise switch at most once, producing a bubble-sort-like progression.

  • Endpoint rankings: At α = 1, PRFe ranks tuples by existence probability, while as α approaches 0 it tends toward ranking by Pr(r(t) = 1).These endpoint rankings are denoted τ1 and τ0, respectively.
  • Pairwise ranking behavior: If one tuple outranks another in both endpoint rankings, it outranks it for every α between 0 and 1.The theorem assumes a unique ranking and ignores ties.
  • Pairwise ranking behavior: If two tuples reverse order between the endpoint rankings, exactly one β determines their switch: one tuple leads below β and the other above β.The proof relies on monotonicity of the relevant ratio in α.
  • Ranking progression: As α increases, ranking changes occur through adjacent swaps, and two tuples that change positions never change back.The paper compares this progression to bubble sort.
  • Illustrative example: In the four-tuple example, each curve represents Υα(ti), and pairwise curve intersections mark ranking changes.The example states that any two curves intersect at most once on (0, 1].
  • Ranking progression: PT(h) explores at most n rankings as h varies, whereas PRFe may explore O(n^2) rankings between its endpoint orders.This gives PRFe a finer range of rankings than the discrete PT(h) parameterization.

8 Experimental Study

Experiments evaluate parameterized ranking functions, their ability to approximate prior functions, learning from preferences, and algorithmic scalability across real and synthetic datasets. PRF-e is especially effective and efficient, including under correlations.

  • Overall findings: Together, strong approximation quality and efficient computation support the paper’s unified ranking approach.The experimental study covers real and synthetic datasets, competing ranking functions, and exact or approximate algorithms.
  • Datasets: The study uses the IIP Iceberg Sighting Dataset and synthetic datasets with independent, mutually exclusive, and more complex correlations.Synthetic tuple scores are sampled uniformly from [0, 10000], with correlations generated through probabilistic and/xor trees.
  • Approximating ranking functions: PRF-e spans rankings close to score-based ranking for small α and probability-of-being-Top-1 ranking at α = 0.Its ranking behavior changes sharply as α approaches 1, producing a broad spectrum of rankings.
  • Approximating ranking functions: A linear combination of PRF-e functions approximates PT(1000), while vanilla DFT produces a Kendall distance near 0.8 and 20 exponentials achieve distance below 0.05 for sfunc.The linear combination is evaluated for top-k answers with h = 1000 and k = 1000.
  • Learning ranking functions: PRF-e parameters can be learned perfectly when PRF-e is the underlying ranking function, whereas E-Rank requires samples approaching the full dataset.PT(h) and U-Rank can be learned with fairly small samples, but E-Rank has a sharp low-distance region and strong dataset-size sensitivity.
  • Learning ranking functions: PRFω and PRF-e are learned well from small samples, while U-Rank is less accurately learned because it cannot be represented by a single PRFω function.The reported experiments restrict SVM-lite sample sizes to at most 200 because larger samples become drastically slow.
  • Scalability: Ignoring correlations can produce significantly inaccurate top-k answers, while PRF-e ranks one million tuples within 1–2 seconds and remains efficient on highly correlated datasets.After score sorting, PRF-e requires one dataset scan, and its running time is not significantly affected by k.
  • Scalability: For large datasets and higher k, exact PT(h) computation takes several orders of magnitude longer than its PRF-e-based approximation.The experiments compare exact PT(h) with linear combinations using 50 exponentials.

9 PRF Computation for Arbitrary Correlations

The paper computes PRF values under arbitrary correlations by conditioning and processing junction trees, using generating-function-style probability computations. The general graphical-model algorithm is polynomial for bounded treewidth, while specialized cases have distinct complexity bounds.

  • Definitions: Graphical models represent tuple correlations through conditional independences, and junction trees encode these relationships using cliques, separators, and calibrated potentials.A separator disconnects parts of the graphical model and induces conditional independence between them.
  • Complexity: The graphical-model algorithm runs in polynomial time when the junction tree has bounded treewidth, but this result does not subsume the and/xor-tree algorithm.The moralized graph of a probabilistic and/xor tree may have unbounded treewidth.
  • Algorithm: The algorithm conditions on Xi = 1, recalibrates affected junction-tree potentials, and computes the distribution of higher-scoring tuples present.If conditioning splits the tree, the resulting components can be processed independently and their partial-sum distributions combined.
  • Algorithm: Conditioning on a separator can produce multiple junction trees whose variables are independent under the Markov property.The partial-sum distributions from these trees are combined into one distribution before ranking.
  • Markov chains: For Markov chains, computing Pr(Pm) takes O(m^2) per tuple, yielding overall ranking complexity O(n^3).The per-tuple computation grows because Pr(Yj+1, Pj) contains 2(j + 1) terms at step j.
  • General junction trees: For a clique C in a general junction tree, the overall ranking complexity is O(n^4 2^tw), where tw denotes treewidth.The bound is dominated by computing O(n) distributions involving partial sums for each clique and tuple.

10 Conclusions

The conclusion presents a unified framework for probabilistic-database ranking based on two parameterized functions and algorithms for exact, approximate, and preference-learned ranking. It also identifies several directions that remain open.

  • Contributions: The paper proposes PRFω and PRF-e so users can control which tuples appear in top-k answers.The functions address the complex interaction between tuple probabilities and scores.
  • Contributions: The authors develop algorithms for evaluating these functions over large, possibly correlated probabilistic datasets.They also propose linear combinations of PRF-e functions for efficient approximate computation and methods for learning ranking functions from user preferences.
  • Open problems: Open questions include other efficiently computable PRF subclasses and relationships among ranking functions across diverse uncertainty and correlation structures.These issues are identified as avenues for further research.

A Proofs

The proofs establish generating-function identities by induction on probabilistic and/xor-tree height. They show that polynomial coefficients correspond to probabilities of possible-world configurations.

  • Theorem: The proof’s central theorem identifies each coefficient of the generating function with the total probability of possible worlds having specified leaf counts.The coefficient associated with index vector i equals Pr(S ≅ i).
  • Inductive proof: The argument proceeds by induction on tree height and separates conjunction-node and disjunction-node cases.For conjunction nodes, the generated leaf set is formed from the union of child-generated sets.
  • Inductive proof: The conjunction case combines child generating functions through products, with induction supplying the child-event probabilities.This establishes the coefficient identity for the parent tree.
  • Conclusion: The proof concludes after establishing the remaining disjunction-node case, completing the generating-function correspondence.The text explicitly marks the induction as complete.

B Expanding Polynomials

This section presents algorithms for expanding polynomials into standard forms.

  • The section focuses on algorithms for expanding polynomials into standard forms.
  • Its subject is polynomial expansion rather than ranking or database modeling.
  • The stated goal is to obtain standard-form polynomial representations.

B.1 Multiplication of a Set of Polynomials

The section studies multiplying a set of univariate polynomials and develops divide-and-conquer FFT methods that improve over naive multiplication.

  • Multiplying a set of polynomials requires computing the coefficients of their product in standard form.
  • Naive Method: The naive method takes O(n2) time by multiplying the polynomials one by one.
  • Divide-and-Conquer: Divide-and-conquer with FFT achieves O(n log2 n) time for multiplying the polynomial set.The method recursively partitions or isolates factors and combines polynomial products using FFT.
  • Divide-and-Conquer: O(n log2 n) follows from the recursive running-time formula under the stated balanced partition bounds.

B.2 Expanding a Nested Formula

The section addresses expanding nested univariate-polynomial formulas into standard form and presents two O(n2) algorithms after faster expansion strategies are considered.

  • A nested formula uses constants, x, addition, multiplication, and parentheses to represent a univariate polynomial expression.
  • The degree and expression length are assumed to be O(n).
  • The naive nested-expansion method takes O(n3), while divide-and-conquer gives O(n2 log2 n).
  • Two improved algorithms reduce nested-formula expansion to O(n2).The first is conceptually simpler, while the second is easier to implement.
  • Polynomial interpolation evaluates the formula at n + 1 points and recovers its coefficients through a Vandermonde system.The evaluation step takes O(n2) time in total, and Vandermonde inversion can also be done in O(n2) time.
  • The alternative algorithm avoids matrix inversion and retains O(n2) running time.It uses complex roots of unity and the discrete Fourier transform.
Loading 0904.1366v4…