Source-linked AI summary
V-SMART-Join: A Scalable MapReduce Framework for All-Pair Similarity Joins of Multisets and Vectors
Ahmed Metwally, Christos Faloutsos
TL;DR
All-pair similarity joins must scale to Internet-traffic-sized data and support sets, multisets, and vectors. V-SMART-Join uses a two-stage MapReduce framework that joins partial results before computing exact similarities for candidate pairs. It was up to 30 times faster than VCL on real small datasets and scaled to a realistic dataset where VCL’s mapper never finished.
Problem
Internet-scale similarity discovery requires scalable all-pair joins, including identifying similar IPs represented by cookie multisets for proxy detection.
Method
V-SMART-Join classifies partial results and uses two stages: joining partial results, then computing exact similarities for candidate pairs.
Results
Up to 30 times faster than VCL on real small datasets, V-SMART-Join also ran on a realistic dataset where the VCL mapper never succeeded to finish.
Takeaways & Limitations
The framework provides scalable exact similarity joins across sets, multisets, and vectors and can run on Hadoop.
Takeaways & Limitations
The algorithms do not handle similarity measures whose partial results require scanning the union of two entities.
Abstract
from arXiv · showhide
This work proposes V-SMART-Join, a scalable MapReduce-based framework for discovering all pairs of similar entities. The V-SMART-Join framework is applicable to sets, multisets, and vectors. V-SMART-Join is motivated by the observed skew in the underlying distributions of Internet traffic, and is a family of 2-stage algorithms, where the first stage computes and joins the partial results, and the second stage computes the similarity exactly for all candidate pairs. The V-SMART-Join algorithms are very efficient and scalable in the number of entities, as well as their cardinalities. They were up to 30 times faster than the state of the art algorithm, VCL, when compared on a real dataset of a small size. We also established the scalability of the proposed algorithms by running them on a dataset of a realistic size, on which VCL never succeeded to finish. Experiments were run using real datasets of IPs and cookies, where each IP is represented as a multiset of cookies, and the goal is to discover similar IPs to identify Internet proxies.
1. INTRODUCTION
V-SMART-Join addresses scalable all-pair similarity discovery for sets, multisets, and vectors, motivated by Internet-scale data and proxy identification. It combines broad data-model support with a two-stage scalable design and reports substantial gains over VCL.
- Internet-traffic-scale data creates a scalability gap that MapReduce addresses by distributing analysis across multiple machines.
- V-SMART-Join discovers similar IP pairs by representing each IP as a multiset of cookies, with multiplicity recording cookie occurrence counts.Similar IPs can then be clustered into load-balancer groups.
- V-SMART-Join supports vectors, sets, and multisets with a wide variety of similarity measures.
- Its two-stage design scales in entity count and cardinality without loading whole entities into main memory, while handling skewed data distributions.
- The algorithms can run on the publicly available Hadoop version of MapReduce.
- Up to 30 times faster than VCL, V-SMART-Join achieved this result on real datasets.
2. THE MAPREDUCE FRAMEWORK
MapReduce distributes record processing across mappers and reducers while hiding partitioning, scheduling, failure handling, and communication details. Its execution model supports deterministic functions, combining, external data loading, and memory-aware processing.
- MapReduce partitions distributed input among mappers, applies map functions, shuffles outputs by key, and groups values for reducers.
- The framework simplifies distributed processing by handling input partitioning, scheduling, failures, and inter-machine communication.
- Pure and deterministic map and reduce functions improve fault tolerance, while combining reduces network load through partial reduction at mappers.
- Memory requirements depend on the algorithm and input and output tuples, with additional buffering possible during map and reduce stages.
- MapReduce permits external data loading only at the beginning of mapping or reducing stages, preserving function determinism and purity.
- Analyzing MapReduce complexity is difficult because mapper, shuffler, and reducer work overlaps and I/O and communication costs can dominate processing.
3. PROBLEM FORMALIZATION AND INSIGHTS
The paper formalizes thresholded all-pair similarity search over multisets and develops scalable insight by classifying similarity partial results according to the data regions they scan. This classification supports efficient unilateral and conjunctive computation, while disjunctive functions remain outside the framework’s scope.
- 3.1 Formalizing the Problem: Problem Formalization: The task is to find multiset pairs whose commutative similarity exceeds threshold t, with multiplicities defined over an alphabet.
- 3.1 Formalizing the Problem: Problem Formalization: Multisets can be represented as non-negative vectors or expanded sets, and the formalization applies to sets and vectors as well.
- 3.1 Formalizing the Problem: Problem Formalization: The framework considers Nominal Similarity Measures, which are invariant to alphabet-element order and can be aggregated from partial results.
- 3.1 Formalizing the Problem: Problem Formalization: The similarity expression combines aggregated partial results produced by functions over element multiplicities.
- 3.2 Insight for High Scalability: Insight for High Scalability: Unilateral functions scan one multiset, while conjunctive functions scan the intersection of two multisets.
- 3.2 Insight for High Scalability: Insight for High Scalability: Disjunctive functions require scanning the union of two multisets, so the framework leaves them for future work.
- 3.2 Insight for High Scalability: Insight for High Scalability: Unilateral results can be accumulated in one dataset scan, and conjunctive results for candidate pairs in one inverted-index scan.
4. THE V-SMART-JOIN FRAMEWORK
V-SMART-Join separates partial-result joining from exact similarity computation, using an inverted index to process candidate pairs while addressing skew and memory-related bottlenecks.
- V-SMART-Join joins each multiset’s Uni(Mi) partial result to its elements, then uses an inverted index to compute similarities for candidate pairs.The framework’s two phases are joining and similarity computation.
- Similarity1 builds an inverted index augmented with Uni(.) values and generates candidate pairs from multisets sharing elements.MapReduce groups tuples by common elements before candidate pairs are passed onward.
- Similarity2 computes Conj(Mi, Mj) from common-element frequencies and combines it with Uni(Mi) and Uni(Mj) to obtain Sim(Mi, Mj).
- The similarity phase’s efficiency is little affected by changing the similarity measure when the same gl(., .) functions are used.
- Long reduce value lists can make Similarity1 reducers slow and memory-intensive, whereas combiners largely mitigate Similarity2 slowness.Similarity1 I/O is quadratic in the maximum element frequency, and long lists may cause thrashing.
- Stop-word removal or chunking overloaded reduce lists distributes quadratic processing across Similarity2 mappers without discarding highly frequent elements.Chunking divides a long list into T chunks and processes up to T^2 chunk pairs.
5. THE JOINING PHASE ALGORITHMS
The joining phase offers Online-Aggregation, Lookup, and Sharding strategies for attaching Uni(Mi) to multiset elements, with different scalability and implementation trade-offs.
- Online-Aggregation: Online-Aggregation computes Uni(Mi) and emits it with each element using secondary-key ordering and combiners.The reducer processes partial-result inputs before scanning the element tuples.
- Online-Aggregation: Online-Aggregation provides scalability and load balancing, but Hadoop lacks native support for its required secondary-key sorting.The available workarounds are described as unscalable or requiring engine changes.
- Lookup: Lookup computes Uni(Mi) in Lookup1 and loads the resulting per-multiset table into memory during Lookup2 to join it with input tuples.
- Lookup: Lookup has limited scalability because its second step requires a memory-resident entry for each multiset, with insufficient memory causing reducer thrashing.
- Sharding: Sharding separates few, large-cardinality multisets from smaller ones, distributing sharded multisets across machines while keeping unsharded multisets in memory.
- Sharding: The threshold C controls Sharding’s separation: extreme values can eliminate the split, overload reducers, or turn the method into memory-heavy Lookup.
- For all three algorithms, the slowest machine handles the multiset with the largest underlying cardinality, while dedicated combiners reduce network bandwidth.
6. RELATED WORK
Related work spans approximate and exact similarity joins across sets, multisets, and vectors. VCL is the principal exact distributed baseline but has substantial computation, communication, storage, and memory bottlenecks.
- Prior work addresses all-pair similarity joins using varied applications, programming paradigms, and similarity measures for sets, multisets, and vectors.
- LSH-based approaches approximate similarity by making hash collisions proportional to similarity, avoiding exhaustive pairwise comparisons.
- LSH has also been applied to EMD and cosine similarity, but its estimated similarities can have multiplicative bias for large alphabets.
- Exact inverted-index methods use candidate generation and verification phases, with prefix and suffix filtering reducing unnecessary candidate comparisons.
- MapReduce approximations based on vector cosine similarity represent multisets as unit vectors, thereby ignoring cardinalities and limiting their applicability.
- VCL: VCL is an exact, distributed, versatile MapReduce adaptation of PPJoin+ applicable to sets, multisets, and vectors.
- VCL: VCL incurs network and storage costs proportional to |Prefix(Mi)| × |U(Mi)| and repeatedly computes each pair’s similarity for shared prefix elements.
- VCL: Grouping elements into super-elements can create superfluous pairs and overhead; using one element per group leaves VCL unable to handle alphabets that exceed mapper memory.
7. EXPERIMENTAL RESULTS
Experiments on real IP-cookie datasets evaluate V-SMART-Join against VCL across similarity thresholds, machine counts, and a realistic Internet-traffic-scale setting. V-SMART-Join remained efficient and scalable, while VCL was slower and failed to finish on the realistic dataset.
- Datasets and setup: The experiments used real IP-cookie datasets, representing each IP as a cookie multiset and measuring Ruzicka similarity.The smaller dataset contained approximately 133 million unique cookies and 82 million IP multisets; the realistic dataset contained approximately 2.2 billion cookies and 454 million IP multisets.
- Small dataset: On the small dataset, VCL runtime depended strongly on the similarity threshold, whereas V-SMART-Join runtimes were fairly insensitive to it.All algorithms ran on 500 machines with thresholds from 0.1 to 0.9; at least 86% of VCL runtime was consumed by its kernel map phase.
- Small dataset: 30 times faster: Online-Aggregation outperformed VCL at similarity threshold 0.1, while the gap narrowed to 5 times at threshold 0.9.Online-Aggregation was consistently the most efficient algorithm, followed by Lookup and Sharding.
- Realistic dataset: On the realistic dataset, Lookup could not load its lookup table, and VCL never finished within two days.VCL mappers in the kernel step ran for more than 48 hours before being killed by the MapReduce scheduler; Online-Aggregation and Sharding were compared instead.
- Sharding sensitivity: Increasing Sharding’s parameter C reduced Sharding1 I/O time but increased Sharding2 aggregation time, leaving total runtime broadly stable while reducing memory footprint.Total runtime trended slightly downward until C was roughly 1000 and then increased; larger C values were more recommended for their lower memory footprint.
8. DISCUSSION
V-SMART-Join computes exact all-pair similarity through two stages and supports sets, multisets, and vectors. It improves scalability over VCL on realistic data, while its applicability is bounded by the supported similarity-measure structure and skewed, large-scale datasets.
- The framework classifies partial results to split exact similarity joins into partial-result computation and candidate-pair similarity stages.
- V-SMART-Join supports sets, multisets, and vectors for a wide variety of similarity measures.
- Up to 30 times faster than VCL on real small datasets, V-SMART-Join also scaled to realistic data where VCL never finished.
- Prefix filtering was excluded because its MapReduce implementation can require large alphabet lists and complete multisets in memory, creating scalability bottlenecks.
- The algorithms handle NSMs whose partial results scan entity pairs or their intersection, but not measures requiring scans of the union.
- The approach assumes many large entities with skewed sizes and is not applicable to datasets containing many entities with very few elements.