Set Similarity Join on Probabilistic Data

Summary: Models probabilistic set data at set- and element-level uncertainty and defines probabilistic set similarity join (PS2J) under possible worlds semantics. Introduces world condensation and pruning techniques—Jaccard distance, probability upper-bound, and aggregate pruning—with indexing and synopses, validated by extensive experiments. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10304
Venue: VLDB
Year: 2010
Pagerank: 5.5340666e-05
Overall Rank: 7,839 | 46.22%
DOI: 10.14778/1920841.1920924

Incoming Non-self Citations Over Time

Authors

1. Xiang Lian (Hong Kong University of Science and Technology)
2. Lei Chen (Hong Kong University of Science and Technology)

BibTeX Citation

@article{lian_vldb10,
        title = {{Set Similarity Join on Probabilistic Data}},
        author = {Lian, Xiang and Chen, Lei},
        journal = {PVLDB},
        series = {{VLDB} '10},
        volume = {3},
        number = {1},
        pages = {650--661},
        doi = {10.14778/1920841.1920924},
        url = {https://doi.org/10.14778/1920841.1920924},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,186	String Similarity Joins: An Experimental Evaluation	2014	VLDB	9.0001436e-05
12,103	Indexing Metric Uncertain Data for Range Queries	2015	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
56	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00040719947
78	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00036571789
169	Efficient Exact Set-Similarity Joins	2006	VLDB	0.0002743469
200	Efficient set joins on similarity predicates	2004	SIGMOD	0.00025597287
238	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.0002369322
680	Creating Probabilistic Databases from Information Extraction Models	2006	VLDB	0.0001504854
683	MYSTIQ: A system for finding more answers by using probabilities	2005	SIGMOD	0.00015005338
699	Data Integration with Uncertainty	2007	VLDB	0.0001487423
820	BayesStore: Managing Large, Uncertain Data Repositories with Probabilistic Graphical Models	2008	VLDB	0.00013814535
1,638	U-DBMS: A Database System for Managing Constantly-Evolving Data	2005	VLDB	0.00010155338
4,743	Probabilistic String Similarity Joins	2010	SIGMOD	6.5268783e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,648	Consistent Query Answers in Inconsistent Probabilistic Databases	2010	SIGMOD
2	3,724	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD
3	11,504	TokenJoin: Efficient Filtering for Set Similarity Join with Maximum Weighted Bipartite Matching	2023	VLDB
4	3,040	Leveraging Set Relations in Exact Set Similarity Join	2017	VLDB
5	3,474	An Efficient Partition Based Method for Exact Set Similarity Joins	2016	VLDB
6	200	Efficient set joins on similarity predicates	2004	SIGMOD
7	2,501	An Empirical Evaluation of Set Similarity Join Techniques	2016	VLDB
8	4,743	Probabilistic String Similarity Joins	2010	SIGMOD
9	12,177	Similarity Joins for Uncertain Strings	2014	SIGMOD
10	169	Efficient Exact Set-Similarity Joins	2006	VLDB