# Leveraging Transitive Relations for Crowdsourced Joins

arXiv: https://arxiv.org/abs/1408.6916 · HTML: https://mlsanity.com/paper/1408.6916/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Aug 2014.

## Built on by (most cited first, 9 of 9)

- [Revisiting Prompt Engineering via Declarative Crowdsourcing](https://mlsanity.com/paper/2308.03854/) (2023)
- [METAM: Goal-Oriented Data Discovery](https://mlsanity.com/paper/2304.09068/) (2023)
- [Learning to Cluster via Same-Cluster Queries](https://mlsanity.com/paper/2108.07383/) (2021)
- [Active clustering for labeling training data](https://mlsanity.com/paper/2110.14521/) (2021)
- [How to Query An Oracle? Efficient Strategies to Label Data](https://mlsanity.com/paper/2110.02341/) (2021)
- [Crowdsourcing with Meta-Workers: A New Way to Save the Budget](https://mlsanity.com/paper/2111.04068/) (2021)
- [Rank Aggregation in Crowdsourcing for Listwise Annotations](https://mlsanity.com/paper/2410.07538/) (2024)
- [Adaptive Graph Refinement and Label Propagation with LLMs for Cost-Effective Entity Resolution](https://mlsanity.com/paper/2605.25814/) (2026)
- [Randomized Algorithms for Learning Partitions with Near Optimal Query Complexity in Constant Rounds](https://mlsanity.com/paper/2608.02176/) (2026)

## Abstract (arXiv)

The development of crowdsourced query processing systems has recently attracted a significant attention in the database community. A variety of crowdsourced queries have been investigated. In this paper, we focus on the crowdsourced join query which aims to utilize humans to find all pairs of matching objects from two collections. As a human-only solution is expensive, we adopt a hybrid human-machine approach which first uses machines to generate a candidate set of matching pairs, and then asks humans to label the pairs in the candidate set as either matching or non-matching. Given the candidate pairs, existing approaches will publish all pairs for verification to a crowdsourcing platform. However, they neglect the fact that the pairs satisfy transitive relations. As an example, if o1 matches with o2, and o2 matches with o3, then we can deduce that o1 matches with o3 without needing to crowdsource (o1, o3). To this end, we study how to leverage transitive relations for crowdsourced joins. We propose a hybrid transitive-relations and crowdsourcing labeling framework which aims to crowdsource the minimum number of pairs to label all the candidate pairs. We prove the optimal labeling order in an ideal setting and propose a heuristic labeling order in practice. We devise a parallel labeling algorithm to efficiently crowdsource the pairs following the order. We evaluate our approaches in both simulated environment and a real crowdsourcing platform. Experimental results show that our approaches with transitive relations can save much more money and time than existing methods, with a little loss in the result quality.