PBBS Listing of Benchmarks

Here we include a listing for each benchmark. Follow the link for the benchmark to get more details, including the input/output specification and the default distributions.

We break the benchmarks into four broad categories, and other.

Basic Building Blocks

• comparisonSort (SORT)
  Returns the sorted input based on a comparison-based sort.

• histogram (HIST)
  Returns the histogram for a sequence of integers.

• integerSort (ISORT)
  Sorts a sequence of integers, possibly with tag-along values.

• removeDuplicates (DDUP)
  Returns the input sequence with duplicates removed.

Graph Algorithms

• breadthFirstSearch (BFS)
  Returns a breadth-first-search tree from a given vertex in a graph.

• maximalIndependentSet (MIS)
  Returns a maximal independent set for an undirected graph.

• maximalMatching (MM)
  Returns a maximal matching for an undirected graph.

• minSpanningForest (MSF)
  Returns a minimum spanning forest of a weighed undirected graph.

• spanningForest (SF)
  Returns a spanning forest of an undirected graph.

Text Processing

• BWDecode (BWD)
  Decodes a string encoded with the Burrows-Wheeler transform.

• invertedIndex (IIDX)
  Returns an inverted index given a string of documents.

• longestRepeatedSubstring (LRS)
  Returns the longest repeated substring in a string.

• suffixArray (SA)
  Returns the suffix array for a string.

• wordCounts (WC)
  Counts the number of occurrences of each word in a string.

Computational Geometry/Graphics

• convexHull (CH)
  Returns the convex hull for a set of points in 2 dimensions.

• delaunayRefine (DR)
  Adds points to a Delaunay triangulation (DT) in 2d, so resulting DT has no small angles.

• delaunayTriangulation (DT)
  Returns the Delaunay triangulation of points in 2d.

• nearestNeighbors (KNN)
  Returns the k nearest neighbors for points in 2d and 3d.

• rayCast (RAY)
  For a set of rays and a set of triangles returns the first triangle each ray intersects.

• rangeQuery2d (RQ)
  For a set of points and a set of rectangles, returns a count of the number of points in each rectangle.

Other

• classify (CLAS)
  Predicts labels for feature vectors based on a training vectors with attached labels.

• nBody (NBODY)
  Returns gravitational forces among points in 3d.