On-the-Fly Token Similarity Joins in Relational Databases

Summary: Introduces tokenize, a relational operator that generates tokens and embeds them in the plan, enabling optimization without precomputed tokens. Key ideas: algebraic rules, cardinality estimates, and replication-free handling of nested tokenize in PostgreSQL. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4963
Venue: SIGMOD
Year: 2014
Pagerank: 5.2447096e-05
Overall Rank: 9,613 | 34.05%
DOI: 10.1145/2588555.2610530

Incoming Non-self Citations Over Time

Authors

1. Nikolaus Augsten (University of Salzburg)
2. Armando Miraglia (Vrije Universiteit Amsterdam)
3. Thomas Neumann (Technical University of Munich)
4. Alfons Kemper (Technical University of Munich)

BibTeX Citation

@inproceedings{augsten_sigmod14,
        title = {{On-the-Fly Token Similarity Joins in Relational Databases}},
        author = {Augsten, Nikolaus and Miraglia, Armando and Neumann, Thomas and Kemper, Alfons},
        series = {{SIGMOD} '14},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2588555.2610530},
        url = {https://dl.acm.org/doi/10.1145/2588555.2610530},
        year = {2014}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,023	Smurf: Self-Service String Matching Using Random Forests	2019	VLDB	6.949387e-05
4,260	Set Similarity Joins on MapReduce: An Experimental Survey	2018	VLDB	6.7984322e-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
107	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00033511706
169	Efficient Exact Set-Similarity Joins	2006	VLDB	0.0002743469
200	Efficient set joins on similarity predicates	2004	SIGMOD	0.00025597287
975	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD	0.00012870645
1,040	VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams	2007	VLDB	0.00012466499
1,115	Comparing Stars: On Approximating Graph Edit Distance	2009	VLDB	0.00012117375
1,592	Efficient Processing of Joins on Set-valued Attributes	2003	SIGMOD	0.00010253457
2,103	Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently	2008	SIGMOD	9.1621686e-05
3,047	Similarity Evaluation on Tree-structured Data	2005	SIGMOD	7.8155543e-05
3,372	Incorporating Computed Relations in Relational Databases	1981	SIGMOD	7.4694279e-05
7,559	An Incrementally Maintainable Index for Approximate Lookups in Hierarchical Data	2006	VLDB	5.5985266e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	509	Supporting Top-k Join Queries in Relational Databases	2003	VLDB
2	5,723	Constructing Queries from Tokens	1986	SIGMOD
3	9,702	Towards a Unified Framework for String Similarity Joins	2019	VLDB
4	3,040	Leveraging Set Relations in Exact Set Similarity Join	2017	VLDB
5	200	Efficient set joins on similarity predicates	2004	SIGMOD
6	107	Approximate String Joins in a Database (Almost) for Free	2001	VLDB
7	2,462	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS
8	9,052	Fast Approximate Similarity Join in Vector Databases	2025	SIGMOD
9	13,672	Exploiting Database Similarity Joins for Metric Spaces	2012	VLDB
10	11,504	TokenJoin: Efficient Filtering for Set Similarity Join with Maximum Weighted Bipartite Matching	2023	VLDB