Package org.drip.graph.softheap

Class KaplanZwickTargetSize

java.lang.Object
org.drip.graph.softheap.KaplanZwickTargetSize
public class KaplanZwickTargetSize
extends java.lang.Object
KaplanZwickTargetSize implements the Target Size Metrics described in Kaplan and Zwick (2009). The References are:

  • Chazelle, B. (2000): The Discrepancy Method: Randomness and Complexity https://www.cs.princeton.edu/~chazelle/pubs/book.pdf
  • Chazelle, B. (2000): The Soft Heap: An Approximate Priority Queue with Optimal Error Rate Journal of the Association for Computing Machinery 47 (6) 1012-1027
  • Chazelle, B. (2000): A Minimum Spanning Tree Algorithm with Inverse-Ackerman Type Complexity Journal of the Association for Computing Machinery 47 (6) 1028-1047
  • Kaplan, H., and U. Zwick (2009): A simpler implementation and analysis of Chazelle's Soft Heaps https://epubs.siam.org/doi/abs/10.1137/1.9781611973068.53?mobileUi=0
  • Pettie, S., and V. Ramachandran (2008): Randomized Minimum Spanning Tree Algorithms using Exponentially Fewer Random Bits ACM Transactions on Algorithms 4 (1) 1-27




Author:
Lakshmi Krishnamurthy

  • Field Summary

    Fields
    Modifier and Type Field Description
    static double STANDARD_RANK_SCALER
    Retrieve the Rank Scaler used in Kaplan and Zwick (2009)

  • Constructor Summary

    Constructors
    Constructor Description
    KaplanZwickTargetSize​(double rankScaler, int estimate, double lowerBound, double upperBound)
    KaplanZwickTargetSize Constructor

  • Method Summary

    Modifier and Type Method Description
    int estimate()
    Retrieve the Target Size Estimate
    double lowerBound()
    Retrieve the Target Size Lower Bound
    double rankScaler()
    Retrieve the Target Size Rank Scaler
    static KaplanZwickTargetSize Standard​(int k, int r)
    Compute the Standard Kaplan-Zwick Target Size Metrics Using the Standard Rank Scaler
    static KaplanZwickTargetSize Standard​(int k, int r, double rankScaler)
    Compute the Standard Kaplan-Zwick Target Size Metrics
    double upperBound()
    Retrieve the Target Size Upper Bound

    Methods inherited from class java.lang.Object

    equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Field Details

    • STANDARD_RANK_SCALER

      public static final double STANDARD_RANK_SCALER
      Retrieve the Rank Scaler used in Kaplan and Zwick (2009)
      See Also:
      Constant Field Values

  • Constructor Details

    • KaplanZwickTargetSize

      public KaplanZwickTargetSize​(double rankScaler, int estimate, double lowerBound, double upperBound) throws java.lang.Exception
      KaplanZwickTargetSize Constructor
      Parameters:
      rankScaler - Target Size Rank Scaler
      estimate - Target Size Estimate
      lowerBound - Target Size Lower Bound
      upperBound - Target Size Upper Bound
      Throws:
      java.lang.Exception - Thrown if the Inputs are Invalid

  • Method Details

    • Standard

      public static final KaplanZwickTargetSize Standard​(int k, int r, double rankScaler)
      Compute the Standard Kaplan-Zwick Target Size Metrics
      Parameters:
      k - The Heap Rank
      r - The R Parameter
      rankScaler - The Rank Scaler
      Returns:
      Kaplan-Zwick Target Size Metrics

    • Standard

      public static final KaplanZwickTargetSize Standard​(int k, int r)
      Compute the Standard Kaplan-Zwick Target Size Metrics Using the Standard Rank Scaler
      Parameters:
      k - The Heap Rank
      r - The R Parameter
      Returns:
      Kaplan-Zwick Target Size Metrics

    • rankScaler

      public double rankScaler()
      Retrieve the Target Size Rank Scaler
      Returns:
      The Target Size Rank Scaler

    • estimate

      public int estimate()
      Retrieve the Target Size Estimate
      Returns:
      The Target Size Estimate

    • lowerBound

      public double lowerBound()
      Retrieve the Target Size Lower Bound
      Returns:
      The Target Size Lower Bound

    • upperBound

      public double upperBound()
      Retrieve the Target Size Upper Bound
      Returns:
      The Target Size Upper Bound