class QuadTreeRTPartitioner extends QuadTreePartitioner
This class implements spatial partitioner based on the principles outlined in:
It uses the Quad-tree partitioning strategy to create balanced partitions This partitioning is essential for efficiently executing kNN joins. The process involves the following steps:
1. **Quad-tree Partitioning**: - Data is partitioned into partitions using the Quad-tree data structure. - This ensures balanced partitions and spatial locality preservation.
2. **Global R-Tree Index Construction**: - A set of random samples S' from the dataset S is taken. - An R-tree T is built over S' in the master node (driver program).
3. **Distance Bound Calculation**: - For each partition Ri, the distance ui from the furthest point in Ri to the centroid cri is calculated. - k-nearest neighbors of each centroid cri are found using the R-tree T. - A distance bound γi is derived for each Ri, defined as γi = 2ui +
|cri, sk|, where sk is the k-th nearest neighbor of cri.
4. **Partitioning Neighbors**: - For each partition Ri, a subset Si ⊂ S is identified such that for any r ∈ Ri, knn(r, S) = knn(r, Si) using a circle range query centered at cri with radius γi. - This guarantees that the k-nearest neighbors of any point in Ri can be found within the subset Si.
5. **Parallel Local kNN Joins**: - Each combined partition (Ri, Si) is processed in parallel. - An R-tree is built over Si, and a local kNN join is performed for each record in Ri. - The results from all partitions are combined to produce the final kNN join results.
Reference: Xie, Dong, et al. "Simba: Efficient in-memory spatial analytics." In Proceedings of the 2016 ACM SIGMOD International Conference on Management of Data (SIGMOD '16), 2016, DOI: 10.1145/2882903.2915237.
- Alphabetic
- By Inheritance
- QuadTreeRTPartitioner
- QuadTreePartitioner
- SpatialPartitioner
- Partitioner
- Serializable
- Serializable
- AnyRef
- Any
- Hide All
- Show All
- Public
- All
Instance Constructors
- new QuadTreeRTPartitioner(extendedQuadTree: ExtendedQuadTree[_])
Abstract Value Members
-
abstract
def
placeObject[T <: Geometry](spatialObject: T): Iterator[(Integer, T)]
Given a geometry, returns a list of partitions it overlaps.
Given a geometry, returns a list of partitions it overlaps.
For points, returns exactly one partition as long as grid type is non-overlapping. For other geometry types or for overlapping grid types, may return multiple partitions.
- Definition Classes
- SpatialPartitioner
Concrete Value Members
-
final
def
!=(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
-
final
def
##(): Int
- Definition Classes
- AnyRef → Any
-
final
def
==(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
-
final
def
asInstanceOf[T0]: T0
- Definition Classes
- Any
-
def
clone(): AnyRef
- Attributes
- protected[lang]
- Definition Classes
- AnyRef
- Annotations
- @throws( ... ) @native()
-
final
def
eq(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
-
def
equals(o: Any): Boolean
- Definition Classes
- QuadTreePartitioner → AnyRef → Any
- Annotations
- @Override()
-
def
finalize(): Unit
- Attributes
- protected[lang]
- Definition Classes
- AnyRef
- Annotations
- @throws( classOf[java.lang.Throwable] )
- def getBoundary(): Envelope
-
final
def
getClass(): Class[_]
- Definition Classes
- AnyRef → Any
- Annotations
- @native()
-
def
getDedupParams(): DedupParams
- Definition Classes
- QuadTreeRTPartitioner → QuadTreePartitioner → SpatialPartitioner
- Annotations
- @Override()
-
def
getGridType(): GridType
- Definition Classes
- SpatialPartitioner
-
def
getGrids(): List[Envelope]
- Definition Classes
- QuadTreeRTPartitioner → SpatialPartitioner
- Annotations
- @Override()
- def getOverlappedGrids(): Map[Integer, List[Envelope]]
-
def
getPartition(key: Any): Int
- Definition Classes
- SpatialPartitioner → Partitioner
- Annotations
- @Override()
- def getSTRForOverlappedGrids(): STRtree
-
def
hashCode(): Int
- Definition Classes
- AnyRef → Any
- Annotations
- @native()
-
final
def
isInstanceOf[T0]: Boolean
- Definition Classes
- Any
-
final
def
ne(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
- def nonOverlappedPartitioner(): QuadTreeRTPartitioner
-
final
def
notify(): Unit
- Definition Classes
- AnyRef
- Annotations
- @native()
-
final
def
notifyAll(): Unit
- Definition Classes
- AnyRef
- Annotations
- @native()
-
def
numPartitions(): Int
- Definition Classes
- QuadTreeRTPartitioner → QuadTreePartitioner → Partitioner
- Annotations
- @Override()
-
def
placeObject(spatialObject: Geometry): Iterator[(Integer, Geometry)]
Depending on overlappedPartitioner, return the expanded boundaries or the original boundaries.
Depending on overlappedPartitioner, return the expanded boundaries or the original boundaries.
- spatialObject
the spatial object
- returns
Iterator<Tuple2<Integer, Geometry>>
- Definition Classes
- QuadTreeRTPartitioner → QuadTreePartitioner
- Annotations
- @Override()
- Exceptions thrown
-
final
def
synchronized[T0](arg0: ⇒ T0): T0
- Definition Classes
- AnyRef
-
def
toString(): String
- Definition Classes
- AnyRef → Any
-
final
def
wait(): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws( ... )
-
final
def
wait(arg0: Long, arg1: Int): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws( ... )
-
final
def
wait(arg0: Long): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws( ... ) @native()