Efficient Processing of Joins on Set-valued Attributes

Summary: Investigates joins on set-valued attributes in object-relational DBMS, focusing on set containment, set equality, and set overlap predicates. Proposes inverted-file based join algorithms and benchmarks them against signature-based methods across these predicates. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3491
Venue: SIGMOD
Year: 2003
Pagerank: 0.00010253457
Overall Rank: 1,592 | 89.08%
DOI: 10.1145/872757.872778

Incoming Non-self Citations Over Time

Authors

1. Nikos Mamoulis (University of Hong Kong)

BibTeX Citation

@inproceedings{mamoulis_sigmod03,
        title = {{Efficient Processing of Joins on Set-valued Attributes}},
        author = {Mamoulis, Nikos},
        series = {{SIGMOD} '03},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/872757.872778},
        url = {https://dl.acm.org/doi/10.1145/872757.872778},
        year = {2003}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
169	Efficient Exact Set-Similarity Joins	2006	VLDB	0.0002743469
200	Efficient set joins on similarity predicates	2004	SIGMOD	0.00025597287
911	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013283031
3,726	Parallelizing Query Optimization	2008	VLDB	7.1697834e-05
5,306	On Indexing Error-Tolerant Set Containment	2010	SIGMOD	6.2731936e-05
5,996	The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication	2015	PODS	6.0150613e-05
7,732	On the complexity of division and set joins in the relational algebra	2005	PODS	5.5564984e-05
9,613	On-the-Fly Token Similarity Joins in Relational Databases	2014	SIGMOD	5.2447096e-05
12,289	Efficient Implementation of Generalized Quantification in Relational Query Languages	2013	VLDB	5.093636e-05
12,727	A Nested Relational Approach to Processing SQL Subqueries	2005	SIGMOD	5.093636e-05
12,796	Symmetric Relations and Cardinality-Bounded Multisets in Database Systems	2004	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0020210012
1,151	Set Containment Joins: The Good, The Bad and The Ugly	2000	VLDB	0.00011938186
1,568	Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates	1997	VLDB	0.0001034191
1,587	An Efficient Indexing Technique for Full-Text Database Systems	1992	VLDB	0.00010269584
1,685	Closest Pair Queries in Spatial Databases	2000	SIGMOD	0.00010017073
3,098	Evaluation of Signature Files as Set Access Facilities in OODBs	1993	SIGMOD	7.7612856e-05
3,897	Searching Large Lexicons for Partially Specified Terms using Compressed Inverted Files	1993	VLDB	7.0403273e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,757	Efficiently Processing Queries on Interval-and-Value Tuples in Relational Databases	2005	VLDB
2	7,732	On the complexity of division and set joins in the relational algebra	2005	PODS
3	4,042	Join Index Hierarchies for Supporting Efficient Navigations in Object-Oriented Databases	1994	VLDB
4	12,934	Evaluating Functional Joins Along Nested Reference Sets in Object-Relational and Object-Oriented Databases	1998	VLDB
5	6,072	Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited	1989	SIGMOD
6	3,040	Leveraging Set Relations in Exact Set Similarity Join	2017	VLDB
7	1,151	Set Containment Joins: The Good, The Bad and The Ugly	2000	VLDB
8	200	Efficient set joins on similarity predicates	2004	SIGMOD
9	1,568	Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates	1997	VLDB
10	1,479	Computing Joins Of Relations	1975	SIGMOD