Packages

class ExtendedQuadTree[T] extends PartitioningUtils with Serializable

The ExtendedQuadTree class uses a modified quad-tree approach for partitioning spatial data, as described in "Simba: Efficient In-Memory Spatial Analytics".

In this approach, a global R-tree index is constructed by taking a set of random samples from the dataset and building the R-tree on the master node. For each partition, the distance from the furthest point in the partition to its centroid is calculated. Using the R-tree, the k-nearest neighbors of each centroid are found, and a distance bound is derived for each partition. This bound ensures that the k-nearest neighbors of any point in a partition can be found within a subset of the data identified by a circle range query centered at the centroid with the derived radius. This method guarantees efficient and accurate k-nearest neighbor joins by leveraging both local and global spatial indexing.

Linear Supertypes
Serializable, PartitioningUtils, AnyRef, Any
Ordering
  1. Alphabetic
  2. By Inheritance
Inherited
  1. ExtendedQuadTree
  2. Serializable
  3. PartitioningUtils
  4. AnyRef
  5. Any
  1. Hide All
  2. Show All
Visibility
  1. Public
  2. All

Instance Constructors

  1. new ExtendedQuadTree(extendedQuadTree: ExtendedQuadTree[_], useNonOverlapped: Boolean)

    Constructor to initialize the partitions list with non-overlapped boundaries.

  2. new ExtendedQuadTree(boundary: Envelope, numPartitions: Int)

Value Members

  1. final def !=(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  2. final def ##(): Int
    Definition Classes
    AnyRef → Any
  3. final def ==(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  4. final def asInstanceOf[T0]: T0
    Definition Classes
    Any
  5. def build(neighborSampleNumber: Int): Unit

    Builds the quad-tree partitioning structure and calculates the expanded boundaries for efficient spatial partitioning.

    Builds the quad-tree partitioning structure and calculates the expanded boundaries for efficient spatial partitioning.

    This method performs the following steps: 1. Forces the quad-tree to grow to a minimum level to ensure a sufficient number of partitions, which might slightly differ from the specified number. 2. Constructs the quad-tree partitioning using the given samples and boundary, initializing it to the calculated minimum level. 3. Creates the expanded boundaries by building an STR (Sort-Tile-Recursive) tree using the provided number of neighbor samples and sampling probability. 4. Clears the samples to avoid broadcasting them to all nodes involved in partitioning.

    neighborSampleNumber

    the number of neighbor samples to consider for building the STR tree.

  6. def clone(): AnyRef
    Attributes
    protected[lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( ... ) @native()
  7. final def eq(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  8. def equals(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  9. def fetchLeafZones(): List[Envelope]
    Definition Classes
    ExtendedQuadTree → PartitioningUtils
    Annotations
    @Override()
  10. def finalize(): Unit
    Attributes
    protected[lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( classOf[java.lang.Throwable] )
  11. def getBoundary(): Envelope

    Returns the boundary of the partition zones.

  12. final def getClass(): Class[_]
    Definition Classes
    AnyRef → Any
    Annotations
    @native()
  13. def getExpandedBoundaries(): HashMap[Integer, List[Envelope]]
  14. def getKeys(geometry: Geometry): Set[Integer]

    Check the geometry against the partition zones to find the IDs of overlapping ranges.

    Check the geometry against the partition zones to find the IDs of overlapping ranges. Only returns the IDs of the overlapping partitions. Note that the geometry can be in multiple ranges because ranges can overlap.

    geometry

    Geometry object to be checked.

    returns

    Set of integers representing the IDs of the overlapping partitions.

    Definition Classes
    ExtendedQuadTree → PartitioningUtils
    Annotations
    @Override()
  15. def getPartitionNum(): Int

    Returns the number of partitions.

  16. def getQuadTree(): StandardQuadTree[_]
  17. def getSpatialExpandedBoundaryIndex(): STRtree
  18. def hashCode(): Int
    Definition Classes
    AnyRef → Any
    Annotations
    @native()
  19. def insert(sample: Envelope): Unit

    Insert a new sample into the sample list.

    Insert a new sample into the sample list.

    sample

    Envelope object to be inserted.

  20. final def isInstanceOf[T0]: Boolean
    Definition Classes
    Any
  21. final def ne(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  22. final def notify(): Unit
    Definition Classes
    AnyRef
    Annotations
    @native()
  23. final def notifyAll(): Unit
    Definition Classes
    AnyRef
    Annotations
    @native()
  24. def placeObject(geometry: Geometry): Iterator[(Integer, Geometry)]

    Check the geometry against the partition zones to find the IDs of overlapping ranges.

    Check the geometry against the partition zones to find the IDs of overlapping ranges. Note that the geometry can be in multiple ranges because ranges can overlap.

    geometry

    Geometry object to be placed.

    returns

    Iterator of Tuple2 containing partition ID and the corresponding geometry.

    Definition Classes
    ExtendedQuadTree → PartitioningUtils
    Annotations
    @Override()
  25. final def synchronized[T0](arg0: ⇒ T0): T0
    Definition Classes
    AnyRef
  26. def toString(): String
    Definition Classes
    AnyRef → Any
  27. final def wait(): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  28. final def wait(arg0: Long, arg1: Int): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  29. final def wait(arg0: Long): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... ) @native()

Inherited from Serializable

Inherited from PartitioningUtils

Inherited from AnyRef

Inherited from Any

Ungrouped