Package dev.roanh.cpqindex

Class Index

java.lang.Object
dev.roanh.cpqindex.Index
public class Index extends Object
Implementation of a graph database index based on k-path-bisimulation and with support for indexing by CPQ cores. This index is inspired by the path index proposed by Yuya Sasaki, George Fletcher and Makoto Onizuka.
See Also:

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    final class 
    Index.Block
    Representation of a single block in the index containing the paths, labels and cores of the partition it represents.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private List<Index.Block>
    blocks
    List of all blocks in the final layer of this index.
    private boolean
    computeCores
    Whether CPQ cores should be or have been computed for this index.
    private final boolean
    computeLabels
    Boolean indicating whether explicit representations of cores and label sequences should be saved for the computed blocks.
    private Map<CanonForm.CoreHash,List<Index.Block>>
    coreToBlock
    Map from CPQ core hash to the blocks this CPQ is present in.
    private final int
    k
    The value of k (the CPQ diameter) this index was computed for.
    private dev.roanh.gmark.util.RangeList<List<Index.Block>>
    layers
    List of blocks in this index by layer (index 0 is k = 1, etc).
    private int
    maxIntersections
    The maximum number of same layer CPQs allowed in a single intersection.
    private dev.roanh.gmark.util.RangeList<dev.roanh.gmark.core.graph.Predicate>
    predicates
    List of predicates (labels) that appear in this index by ID.
    private ProgressListener
    progress
    Progress listener to inform of any computation updates.

  • Constructor Summary

    Constructors
    Constructor
    Description
    Index(dev.roanh.gmark.util.UniqueGraph<Integer,dev.roanh.gmark.core.graph.Predicate> g, int k, boolean computeCores, boolean computeLabels, int threads)
    Constructs a new CPQ-native index for the given graph, diameter.
    Index(dev.roanh.gmark.util.UniqueGraph<Integer,dev.roanh.gmark.core.graph.Predicate> g, int k, boolean computeCores, boolean computeLabels, int threads, int maxIntersections, ProgressListener listener)
    Constructs a new CPQ-native index for the given graph, diameter.
    Index(dev.roanh.gmark.util.UniqueGraph<Integer,dev.roanh.gmark.core.graph.Predicate> g, int k, int threads)
    Constructs a new CPQ-native index for the given graph and diameter.
    Index(dev.roanh.gmark.util.UniqueGraph<Integer,dev.roanh.gmark.core.graph.Predicate> g, int k, int threads, int maxIntersections)
    Constructs a new CPQ-native index for the given graph, diameter and diameter limit.
    Index(InputStream source)
    Reads a previously saved index.

  • Method Summary

    Modifier and Type
    Method
    Description
    private final void
    computeBlocks(dev.roanh.gmark.util.RangeList<List<LabelledPath>> segments)
    After graph partitioning computes the index blocks.
    final void
    computeCores(int threads)
    Computes CPQ cores for each block in this index.
    final List<Index.Block>
    getBlocks()
    Gets all the blocks in this index.
    final long
    getTotalCores()
    Gets the total number of cores in this index, this is the sum of all cores in each block.
    final int
    getUniqueCores()
    Gets the total number of unique cores in this index, this is the number of unique index keys.
    private final void
    mapCoresToBlocks()
    Constructs the map from CPQ core has to the blocks this core occurs in.
    private final dev.roanh.gmark.util.RangeList<List<LabelledPath>>
    partition(dev.roanh.gmark.util.UniqueGraph<Integer,dev.roanh.gmark.core.graph.Predicate> g)
    Partitions all the paths in the given graph according to k-path-bisimulation.
    final void
    print()
    Prints the index to standard output.
    final List<Pair>
    query(dev.roanh.gmark.conjunct.cpq.CPQ cpq)
    Runs the given query on this index and returns the result.
    final void
    setIntersections(int intersections)
    Sets the maximum number of same level CPQ intersections allowed.
    final void
    setProgressListener(ProgressListener listener)
    Sets the progress listener to send computation updates to.
    final void
    sort()
    Sorts all the list of blocks of this index.
    private static final int
    sortOnePath(LabelledPath a, LabelledPath b)
    Compares the given paths based on their labels, cyclic properties, source and target.
    private static final int
    sortPaths(LabelledPath a, LabelledPath b)
    Compares the given paths based on their segments, cyclic properties, source and target.
    final void
    write(OutputStream target, boolean full)
    Write this index to the given output stream.

    Methods inherited from class java.lang.Object

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

  • Field Details

    • computeLabels

      private final boolean computeLabels
      Boolean indicating whether explicit representations of cores and label sequences should be saved for the computed blocks. Saving these will take significantly more memory and is only really relevant when printing the index with print(), calling Index.Block.getCores() or calling Index.Block.getLabels().

    • k

      private final int k
      The value of k (the CPQ diameter) this index was computed for.

    • maxIntersections

      private int maxIntersections
      The maximum number of same layer CPQs allowed in a single intersection.

    • computeCores

      private boolean computeCores
      Whether CPQ cores should be or have been computed for this index.

    • predicates

      private dev.roanh.gmark.util.RangeList<dev.roanh.gmark.core.graph.Predicate> predicates
      List of predicates (labels) that appear in this index by ID.

    • layers

      private dev.roanh.gmark.util.RangeList<List<Index.Block>> layers
      List of blocks in this index by layer (index 0 is k = 1, etc).

    • blocks

      private List<Index.Block> blocks
      List of all blocks in the final layer of this index. This is the layer for k equal to k.

    • coreToBlock

      private Map<CanonForm.CoreHash,List<Index.Block>> coreToBlock
      Map from CPQ core hash to the blocks this CPQ is present in.

    • progress

      private ProgressListener progress
      Progress listener to inform of any computation updates.

  • Constructor Details

    • Index

      public Index(dev.roanh.gmark.util.UniqueGraph<Integer,dev.roanh.gmark.core.graph.Predicate> g, int k, int threads) throws IllegalArgumentException, InterruptedException
      Constructs a new CPQ-native index for the given graph and diameter.
      Parameters:
      g - The graph to compute and index for.
      k - The CPQ diameter k to compute the index for.
      threads - The number of CPU threads to use for computing cores.
      Throws:
      IllegalArgumentException - When k is less than 1.
      InterruptedException - When the current thread is interrupted during core computation.

    • Index

      public Index(dev.roanh.gmark.util.UniqueGraph<Integer,dev.roanh.gmark.core.graph.Predicate> g, int k, int threads, int maxIntersections) throws IllegalArgumentException, InterruptedException
      Constructs a new CPQ-native index for the given graph, diameter and diameter limit.
      Parameters:
      g - The graph to compute and index for.
      k - The CPQ diameter k to compute the index for.
      threads - The number of CPU threads to use for computing cores.
      maxIntersections - The maximum number of same level CPQs allowed in intersections. Limiting intersection CPQs greatly decreases the number of cores that need to be computed.
      Throws:
      IllegalArgumentException - When k is less than 1.
      InterruptedException - When the current thread is interrupted during core computation.

    • Index

      public Index(dev.roanh.gmark.util.UniqueGraph<Integer,dev.roanh.gmark.core.graph.Predicate> g, int k, boolean computeCores, boolean computeLabels, int threads) throws IllegalArgumentException, InterruptedException
      Constructs a new CPQ-native index for the given graph, diameter.
      Parameters:
      g - The graph to compute and index for.
      k - The CPQ diameter k to compute the index for.
      computeCores - True to compute cores, if false cores are not computed and can instead later be computed using computeCores(int) if desired.
      computeLabels - True to compute core and label sequence labels for each index block.
      threads - The number of CPU threads to use for computing cores.
      Throws:
      IllegalArgumentException - When k is less than 1.
      InterruptedException - When the current thread is interrupted during core computation.
      See Also:

    • Index

      public Index(dev.roanh.gmark.util.UniqueGraph<Integer,dev.roanh.gmark.core.graph.Predicate> g, int k, boolean computeCores, boolean computeLabels, int threads, int maxIntersections, ProgressListener listener) throws IllegalArgumentException, InterruptedException
      Constructs a new CPQ-native index for the given graph, diameter.
      Parameters:
      g - The graph to compute and index for.
      k - The CPQ diameter k to compute the index for.
      computeCores - True to compute cores, if false cores are not computed and can instead later be computed using computeCores(int) if desired.
      computeLabels - True to compute core and label sequence labels for each index block.
      threads - The number of CPU threads to use for computing cores.
      maxIntersections - The maximum number of same level CPQs allowed in intersections. Limiting intersection CPQs greatly decreases the number of cores that need to be computed.
      listener - The progress listener to send computation progress updates to.
      Throws:
      IllegalArgumentException - When k is less than 1.
      InterruptedException - When the current thread is interrupted during core computation.
      See Also:

    • Index

      public Index(InputStream source) throws IOException
      Reads a previously saved index. Any previously attached progress listeners will be detached.
      Parameters:
      source - The input stream to read from.
      Throws:
      IOException - When an IOException occurs.
      See Also:

  • Method Details

    • setIntersections

      public final void setIntersections(int intersections) throws IllegalStateException
      Sets the maximum number of same level CPQ intersections allowed. Limiting intersection CPQs greatly decreases the number of cores that need to be computed. Note that this limit does not count intersection with identity.
      Parameters:
      intersections - The maximum number of CPQs in an intersection.
      Throws:
      IllegalStateException - When cores have already been computed for this index.

    • write

      public final void write(OutputStream target, boolean full) throws IOException
      Write this index to the given output stream.
      Parameters:
      target - The output stream to write to.
      full - When true extra information is saved that is required for core computation.
      Throws:
      IOException - When an IOException occurs.
      See Also:

    • query

      public final List<Pair> query(dev.roanh.gmark.conjunct.cpq.CPQ cpq) throws IllegalArgumentException
      Runs the given query on this index and returns the result. Note that the intersection limit has to be respect if a limit was set.
      Parameters:
      cpq - The query to run.
      Returns:
      The paths matched by the query.
      Throws:
      IllegalArgumentException - When the query has a diameter that is larger than the diameter of this index.
      See Also:

    • setProgressListener

      public final void setProgressListener(ProgressListener listener)
      Sets the progress listener to send computation updates to.
      Parameters:
      listener - The listener to send computation updates to.
      See Also:

    • getBlocks

      public final List<Index.Block> getBlocks()
      Gets all the blocks in this index.
      Returns:
      All the blocks in this index.

    • sort

      public final void sort()
      Sorts all the list of blocks of this index. There's is no real reason to do this other than to make the output of print() more organised.
      See Also:

    • print

      public final void print()
      Prints the index to standard output.
      See Also:

    • mapCoresToBlocks

      private final void mapCoresToBlocks()
      Constructs the map from CPQ core has to the blocks this core occurs in.

    • getTotalCores

      public final long getTotalCores()
      Gets the total number of cores in this index, this is the sum of all cores in each block.
      Returns:
      The total number of cores.
      See Also:

    • getUniqueCores

      public final int getUniqueCores()
      Gets the total number of unique cores in this index, this is the number of unique index keys.
      Returns:
      The total number of unique cores.
      See Also:

    • computeBlocks

      private final void computeBlocks(dev.roanh.gmark.util.RangeList<List<LabelledPath>> segments)
      After graph partitioning computes the index blocks.
      Parameters:
      segments - The partitioned segments of the graph.
      See Also:

    • computeCores

      public final void computeCores(int threads) throws InterruptedException, IllegalStateException
      Computes CPQ cores for each block in this index. Note that if this index was saved and read back that it is only possible to compute cores if the index was fully saved with extra state information.
      Parameters:
      threads - The number of CPU threads to use to compute cores.
      Throws:
      InterruptedException - When the current thread is interrupted.
      IllegalStateException - When cores have already been computed for this index of when this index is read back and was not fully saved.
      See Also:

    • partition

      private final dev.roanh.gmark.util.RangeList<List<LabelledPath>> partition(dev.roanh.gmark.util.UniqueGraph<Integer,dev.roanh.gmark.core.graph.Predicate> g) throws IllegalArgumentException
      Partitions all the paths in the given graph according to k-path-bisimulation.
      Parameters:
      g - The graph to partition.
      Returns:
      The partitioned paths in the graph.
      Throws:
      IllegalArgumentException - When the diameter of this index k is less than 1.

    • sortPaths

      private static final int sortPaths(LabelledPath a, LabelledPath b)
      Compares the given paths based on their segments, cyclic properties, source and target.
      Parameters:
      a - The first path.
      b - The second path.
      Returns:
      A value less than 0 if a < b, a value equal to 0 if a == b and a value greater than 0 if a > b.

    • sortOnePath

      private static final int sortOnePath(LabelledPath a, LabelledPath b)
      Compares the given paths based on their labels, cyclic properties, source and target.
      Parameters:
      a - The first path.
      b - The second path.
      Returns:
      A value less than 0 if a < b, a value equal to 0 if a == b and a value greater than 0 if a > b.