PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Processing of k Nearest Neighbor Joins using MapReduce

Wei Lu, Yanyan Shen, Su Chen, Beng Chin Ooi

arXiv:1207.0141v1cs.DB

TL;DR

The paper tackles the cost and scalability limits of kNN joins on centralized machines and implements the operation with MapReduce. Its mappers form groups using partitioning and pruning, while reducers perform local joins; experiments report efficient, robust, and scalable methods.

  • Problem

    kNN join is expensive, with centralized processing becoming difficult as datasets grow and existing centralized indexes do not readily fit MapReduce.

  • Method

    The paper implements kNN join in MapReduce using mapper-assigned groups, reducer-local joins, Voronoi-based partitioning, pruning rules, and replica-reduction strategies.

  • Results

    Experiments on real and synthetic datasets demonstrate that the proposed methods are efficient, robust, and scalable.

  • Takeaways & Limitations

    MapReduce provides the paper’s distributed framework for processing kNN joins over large, multi-dimensional datasets without modifying the framework.

  • Takeaways & Limitations

    The method assumes k ≤ |S|; otherwise, kNN join becomes a Cartesian-product cross join.

Abstract

from arXiv · show

k nearest neighbor join (kNN join), designed to find k nearest neighbors from a dataset S for every object in another dataset R, is a primitive operation widely adopted by many data mining applications. As a combination of the k nearest neighbor query and the join operation, kNN join is an expensive operation. Given the increasing volume of data, it is difficult to perform a kNN join on a centralized machine efficiently. In this paper, we investigate how to perform kNN join using MapReduce which is a well-accepted framework for data-intensive applications over clusters of computers. In brief, the mappers cluster objects into groups; the reducers perform the kNN join on each group of objects separately. We design an effective mapping mechanism that exploits pruning rules for distance filtering, and hence reduces both the shuffling and computational costs. To reduce the shuffling cost, we propose two approximate algorithms to minimize the number of replicas. Extensive experiments on our in-house cluster demonstrate that our proposed methods are efficient, robust and scalable.

1. INTRODUCTION

The paper addresses the scalability limits of centralized kNN joins by implementing the operation in MapReduce. It combines Voronoi-based grouping, pruning, replica-reduction strategies, and experiments demonstrating efficient, robust, and scalable behavior.

  • kNN join combines each object in R with its k closest objects in S and supports data-mining applications such as clustering and outlier detection.
  • O(|R| · |S|) complexity makes naive kNN join expensive, while centralized methods deteriorate as data volume and dimensionality increase.
  • Existing centralized indexing techniques cannot be incorporated into MapReduce easily, motivating a distributed implementation without framework modifications.
  • Mappers assign objects from R and S to groups, and reducers perform the kNN join separately on each group while preserving correctness through necessary object replication.
  • Voronoi partitions and distance bounds group closely related partitions, enabling pruning of objects unlikely to participate in the kNN join.
  • A replica cost model supports two greedy grouping strategies, and extensive real and synthetic-data experiments report efficient, robust, and scalable methods.

2. PRELIMINARIES

The preliminaries define kNN join, MapReduce processing, Voronoi partitioning, and distance-based range-selection pruning. These concepts establish how objects are partitioned and filtered before distributed processing.

  • 2.1 kNN Join: kNN join combines every object r in R with its k nearest neighbors from S and is asymmetric between the two datasets.
  • 2.1 kNN Join: When k ≤ |S|, the kNN join contains k × |R| pairs; otherwise, it degenerates to the Cartesian product R × S.
  • 2.2 MapReduce Framework: MapReduce maps input key-value pairs to intermediate pairs, groups values by key, and applies reducer logic to produce final outputs.
  • 2.3 Voronoi Diagram-based Partitioning: Voronoi partitioning selects pivots and assigns each object to its closest pivot, dividing the data space into disjoint generalized Voronoi cells.
  • 2.3 Voronoi Diagram-based Partitioning: Range selection returns all objects within distance θ of a query, checking only objects inside each partition’s derived bounding area.
  • 2.3 Voronoi Diagram-based Partitioning: If a partition is farther than threshold θ from a query according to the pivot-based hyperplane bound, its objects can be discarded from range selection.

3. AN OVERVIEW OF KNN JOIN USING MAPREDUCE

This section frames MapReduce kNN join around assigning R and S partitions to reducers while controlling shuffling and reducer computation. It contrasts a basic strategy that replicates S broadly with partition-specific subsets that reduce unnecessary data movement and distance calculations.

  • MapReduce mappers assign objects to keyed subsets, and reducers perform kNN joins on the objects sharing each key.
  • The basic strategy sends the entire S to every reducer, making each reducer join its R subset with all of S.This can exceed reducer capacity when S is large.
  • The design targets two costs: shuffling intermediate results and performing the kNN join on reducers.
  • Partition-specific subsets Si let each reducer join Ri only with the S objects assigned to it, avoiding replication of R and full replication of S.Correctness requires Si to contain every k nearest neighbor of every object in Ri.
  • The shuffling cost is |R| + α·|S|, so reducing the average replica count α reduces both shuffling and the considered computational cost.
  • Clustering nearby objects in R increases shared neighbors in S, producing smaller Si and fewer distance calculations.

4. HANDLING KNN JOIN USING MAPREDUCE

The implementation partitions R and S around selected pivots, collects partition statistics, and uses them to derive candidate subsets and distance bounds for reducer-side joins. A preprocessing step and two MapReduce jobs organize this pruning-oriented workflow.

  • The workflow uses a preprocessing step followed by two MapReduce jobs to perform the kNN join.
  • Preprocessing selects pivots for a Voronoi diagram that partitions objects while preserving proximity.
  • The first MapReduce job assigns each object in R ∪ S to its nearest pivot and collects statistics for each partition.The mapper records partition identity, dataset name, and distance to the closest pivot.
  • The second MapReduce job uses collected statistics to find Si for each Ri, then each reducer performs the join between the corresponding pair.
  • Summary tables TR and TS store partition sizes, minimum and maximum pivot distances, and selected pivot-to-object distances for S partitions.TS retains distances to the k nearest objects in each S partition for its pivot.
  • Distance bounds use upper-bound candidates and priority-queue pruning to bound kNN distances for all objects in an R partition.The procedure retains k smallest pivot distances from each S partition and returns the queue’s top value as θi.
  • Corollary 2 avoids repeatedly computing pivot-to-pivot distances when many R partitions exist by determining assignments from distances to S pivots.

5. MINIMIZING REPLICATION OF S

The paper models and reduces replication of S by partitioning R with Voronoi cells, grouping related partitions, and assigning S objects selectively to reducers. It proposes geometric and greedy grouping strategies that approximately minimize replicas while maintaining balanced processing.

  • Partitioning and bounds: Voronoi partitions use distance bounds to identify which S objects can contain k nearest neighbors for each R partition.More pivots tighten the bounds and reduce potential assignments, although they increase pivot-distance computations.
  • Partitioning and bounds: Partitions of R are grouped into disjoint reducer workloads, with corresponding S assignments refined for each group.Grouping avoids requiring one reducer per partition while preserving the assignment framework.
  • Replication cost model: The replication cost model counts S objects assigned to reducers across groups, eliminating duplicate assignments within each S subset.The resulting quantity RP(S) formalizes the total number of S replicas.
  • Grouping strategies: Two grouping strategies approximately minimize RP(S): geometric grouping uses pivot proximity, while greedy grouping reduces incremental replication.Greedy grouping directly targets the replication increase from adding a partition, whereas geometric grouping uses distances among pivots as a cheaper proxy.
  • Grouping strategies: Geometric grouping initially separates distant pivots, then assigns remaining partitions to nearby groups while balancing group object counts.The procedure selects distant initial pivots and subsequently adds partitions to the smallest nearby group.

6. EXPERIMENTAL EVALUATION

The evaluation measures the proposed MapReduce joins on Forest, expanded Forest, and OSM datasets using an in-house Hadoop cluster. It compares the proposed partitioning and grouping methods with H-BRJ and reports runtime, computation selectivity, and shuffling cost.

  • Experimental setup: Experiments run on a 72-node in-house cluster using Hadoop 0.20.2 and gigabit Ethernet.Each node has an Intel X3430 2.4GHz processor, 8GB memory, and two 500GB disks.
  • Compared algorithms: The comparison includes H-BRJ, PGBJ with partitioning and grouping, and PBJ without grouping.PBJ also requires an extra MapReduce job to merge final results.
  • Datasets: The datasets include Forest with 580K objects, expanded Forest datasets scaled from 5 to 25 times, and OSM with 10 million records.Forest experiments use 10 integer attributes, while OSM records contain longitude, latitude, and variable-length descriptions.
  • Metrics and defaults: The default evaluation uses k=10 on Forest ×10 with 36 computing nodes and measures query time, computation selectivity, and shuffling cost.Computation selectivity is evaluated alongside runtime and replication-related communication.

6.1 Study of Parameters of Our Techniques

Parameter studies compare pivot-selection and grouping strategies through partition balance, execution time, computation selectivity, and replication. Random selection with geometric grouping provides the lowest reported overall execution time under the chosen configuration, while k-means improves pruning during the join phase.

  • Parameter configurations: Six PGBJ configurations combine random, farthest, or k-means pivot selection with geometric or greedy grouping.The configurations are RGE, FGE, KGE, RGR, FGR, and KGR.
  • Partition and group balance: Increasing the number of pivots rapidly reduces partition-size deviation, but farthest selection creates severe workload imbalance.With 2000 farthest-selected pivots, the largest partition contains 1,130,678 objects, about one-fifth of the dataset.
  • Partition and group balance: Random and k-means selection produce approximately equal group sizes under geometric grouping.Farthest selection instead yields substantial variation in group sizes because outliers become pivots.
  • Execution time: Farthest selection takes more than 10,000s, while random selection outperforms k-means overall as the pivot count increases.K-means incurs many distance computations during selection, widening its overall execution-time gap from random selection.
  • Computation selectivity: K-means selection achieves slightly lower computation selectivity than random selection during the kNN join phase, with a maximum reported selectivity of 2.38.The difference shrinks as the number of pivots grows because k-means selection deteriorates toward random selection.
  • Pivot-count trade-off: Increasing the pivot count tightens pruning bounds and reduces R-S distance computations and S replication, but increases distances computed to pivots.The reported balance minimizes overall execution time at |P| = 4000 with the RGE strategy.

6.2 Effect of k

The study varies k from 10 to 50 on Forest ×10 and OSM. PGBJ has the best running time, while its shuffling cost remains nearly stable as k increases, unlike PBJ and H-BRJ.

  • Experimental range: The experiments vary k from 10 to 50 on the Forest ×10 and OSM datasets.Both datasets are used to examine how neighborhood size affects the proposed techniques.
  • Running time: PGBJ consistently has the shortest running time, followed by PBJ and H-BRJ.The ordering is consistent with the reported computation-selectivity results.
  • Shuffling cost: As k increases, PGBJ shuffling cost remains nearly unchanged, whereas PBJ and H-BRJ shuffling costs increase linearly.The result indicates that PGBJ replication of S is insensitive to k in the reported experiments.

6.3 Effect of Dimensionality

As dimensionality and dataset size increase, the approaches differ in execution-time sensitivity, selectivity, and shuffling behavior. PGBJ scales better than PBJ and H-BRJ, including nearly 6 times faster execution on “Forest × 25” than H-BRJ.

  • Dimensionality: H-BRJ is more sensitive to dimensionality than PBJ and PGBJ, with execution time increasing exponentially from 2 to 6 dimensions.From 6 to 10 dimensions, execution time increases smoothly because attributes in that range have low variance.
  • Dimensionality: PGBJ’s shuffling cost increases exponentially from 2 to 6 dimensions because replication of S grows exponentially, then converges to |R| + N × |S| in the worst case.PBJ can replace PGBJ when shuffling cost is the primary concern.
  • Scalability: As data size increases, all three approaches’ execution times grow quadratically, while PGBJ scales better than PBJ and H-BRJ.The quadratic increase follows from the quadratic growth in object pairs.
  • Scalability: PGBJ is nearly 6 times faster than H-BRJ on “Forest × 25” despite only a small difference in computation selectivity.PGBJ also has lower shuffling cost than PBJ and H-BRJ, with increasing returns as data size grows.

6.5 Speedup

Increasing the number of computing nodes narrows the running-time gap among the three approaches, while PGBJ maintains constant computation selectivity. Shuffling cost rises linearly, preventing linear speedup.

  • Speedup: The running-time gap among H-BRJ, PBJ, and PGBJ becomes smaller as the number of computing nodes increases from 9 to 36.The comparison is based on Figure 12(a).
  • Speedup: PGBJ’s computation selectivity remains constant as computing nodes increase, while H-BRJ and PBJ become less selective.The approaches do not speed up linearly because nodes must read pivots and shuffling cost increases.
  • Speedup: Shuffling cost increases linearly with the number of computing nodes.This increase contributes to the approaches’ sublinear speedup.

7. RELATED WORK

Prior kNN join research includes centralized index-based methods and MapReduce similarity-join frameworks, but these approaches do not directly address the paper’s MapReduce kNN join setting.

  • Centralized kNN join: Centralized kNN join methods use structures such as R-trees, pages, secondary structures, or grid partitioning to reduce I/O and computation costs.Mux is R-tree based, while Gorder uses grid partitioning and pivots.
  • MapReduce similarity joins: Set-similarity join techniques developed for MapReduce are not applicable because they return pairs satisfying a similarity threshold rather than k nearest neighbors.The differing problem definitions prevent direct extension to kNN join.
  • MapReduce join frameworks: A general MapReduce framework supports join queries with arbitrary join conditions and optimization techniques for reducing communication cost.The passage presents this as related work rather than as a direct solution to kNN join.

8. CONCLUSION

The paper answers k nearest neighbor joins in MapReduce by partitioning data with Voronoi diagrams, checking pairs within groups, and applying pruning rules to reduce costs.

  • Conclusion: Voronoi diagram-based partitioning divides the input datasets into groups so the kNN join checks object pairs only within each group.The partitioning method selects pivots and assigns objects to generalized Voronoi cells.
  • Conclusion: Pruning rules reduce both shuffling cost and computation cost.The conclusion reports this as a central property of the proposed approach.
Loading 1207.0141v1…