{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T07:52:38Z","timestamp":1792741958095,"version":"4.5.0"},"reference-count":50,"publisher":"SAGE Publications","issue":"5","license":[{"start":{"date-parts":[[2024,10,9]],"date-time":"2024-10-09T00:00:00Z","timestamp":1728432000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SW"],"published-print":{"date-parts":[[2024,10,9]]},"abstract":"<jats:p>The SPARQL standard provides operators to retrieve exact matches on data, such as graph patterns, filters and grouping. This work proposes and evaluates two new algebraic operators for SPARQL 1.1 that return similarity-based results instead of exact results. First, a similarity join operator is presented, which brings together similar mappings from two sets of solution mappings. Second, a clustering solution modifier is introduced, which instead of grouping solution mappings according to exact values, brings them together by using similarity criteria. For both cases, a variety of algorithms are proposed and analysed, and use-case queries that showcase the relevance and usefulness of the novel operators are presented. For similarity joins, experimental results are provided by comparing different physical operators over a set of real world queries, as well as comparing our implementation to the closest work found in the literature, DBSimJoin, a PostgreSQL extension that supports similarity joins. For clustering, synthetic queries are designed in order to measure the performance of the different algorithms implemented.<\/jats:p>","DOI":"10.3233\/sw-243540","type":"journal-article","created":{"date-parts":[[2024,3,8]],"date-time":"2024-03-08T10:20:55Z","timestamp":1709893255000},"page":"1701-1732","source":"Crossref","is-referenced-by-count":2,"title":["Similarity joins and clustering for SPARQL"],"prefix":"10.1177","volume":"15","author":[{"given":"Sebasti\u00e1n","family":"Ferrada","sequence":"first","affiliation":[{"name":"Departament of Computer and Information Science (IDA), Link\u00f6ping University, Link\u00f6ping, Sweden"},{"name":"Millenium Institute for Foundational Research on Data, Department of Computer Science, Universidad de Chile, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Benjamin","family":"Bustos","sequence":"additional","affiliation":[{"name":"Millenium Institute for Foundational Research on Data, Department of Computer Science, Universidad de Chile, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aidan","family":"Hogan","sequence":"additional","affiliation":[{"name":"Millenium Institute for Foundational Research on Data, Department of Computer Science, Universidad de Chile, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"179","reference":[{"issue":"4","key":"10.3233\/SW-243540_ref1","doi-asserted-by":"publisher","first-page":"355","DOI":"10.3233\/SW-2012-0065","article-title":"Enabling the geospatial Semantic Web with Parliament and GeoSPARQL","volume":"3","author":"Battle","year":"2012","journal-title":"Semantic Web"},{"issue":"5","key":"10.3233\/SW-243540_ref2","doi-asserted-by":"publisher","first-page":"706","DOI":"10.1016\/j.jbi.2008.03.004","article-title":"Bio2RDF: Towards a mashup to build bioinformatics knowledge systems","volume":"41","author":"Belleau","year":"2008","journal-title":"Journal of Biomedical Informatics"},{"key":"10.3233\/SW-243540_ref3","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1145\/376284.375714","volume-title":"Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data","author":"B\u00f6hm","year":"2001"},{"key":"10.3233\/SW-243540_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45227-0_50"},{"key":"10.3233\/SW-243540_ref5","doi-asserted-by":"publisher","DOI":"10.1145\/502512.502524"},{"issue":"1","key":"10.3233\/SW-243540_ref6","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1023\/A:1025026030880","article-title":"D-index: Distance searching index for metric data sets","volume":"21","author":"Dohnal","year":"2003","journal-title":"Multimedia Tools and Applications"},{"key":"10.3233\/SW-243540_ref7","unstructured":"M.\u00a0Ester, H.-P.\u00a0Kriegel, J.\u00a0Sander, X.\u00a0Xu et al., A density-based algorithm for discovering clusters in large spatial databases with noise, in: Proceedings of the 2nd ACM International Conference on Knowledge Discovery and Data Mining (KDD), Vol.\u00a096, 1996, pp.\u00a0226\u2013231."},{"key":"10.3233\/SW-243540_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-68204-4_8"},{"key":"10.3233\/SW-243540_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-62419-4_12"},{"key":"10.3233\/SW-243540_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-67162-8_26"},{"key":"10.3233\/SW-243540_ref11","doi-asserted-by":"publisher","DOI":"10.1145\/1282280.1282347"},{"key":"10.3233\/SW-243540_ref12","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00186"},{"issue":"2","key":"10.3233\/SW-243540_ref13","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1145\/276305.276312","article-title":"CURE: An efficient clustering algorithm for large databases","volume":"27","author":"Guha","year":"1998","journal-title":"SIGMOD Rec."},{"key":"10.3233\/SW-243540_ref14","doi-asserted-by":"crossref","unstructured":"A.\u00a0Guttman, R-Trees: A Dynamic Index Structure for Spatial Searching, Vol.\u00a014, ACM, 1984.","DOI":"10.1145\/971697.602266"},{"key":"10.3233\/SW-243540_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30284-8_53"},{"key":"10.3233\/SW-243540_ref17","doi-asserted-by":"publisher","DOI":"10.1145\/1366102.1366104"},{"issue":"8","key":"10.3233\/SW-243540_ref18","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1109\/2.781637","article-title":"Chameleon: Hierarchical clustering using dynamic modeling","volume":"32","author":"Karypis","year":"1999","journal-title":"Computer"},{"key":"10.3233\/SW-243540_ref19","unstructured":"L.\u00a0Kaufman and P.J.\u00a0Rousseeuw, Finding Groups in Data: An Introduction to Cluster Analysis, John Wiley & Sons, 2009."},{"key":"10.3233\/SW-243540_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-76298-0_22"},{"key":"10.3233\/SW-243540_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-05290-3_101"},{"key":"10.3233\/SW-243540_ref22","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247496"},{"key":"10.3233\/SW-243540_ref23","doi-asserted-by":"publisher","DOI":"10.1109\/MINES.2011.85"},{"key":"10.3233\/SW-243540_ref24","unstructured":"J.\u00a0MacQueen et al., Some methods for classification and analysis of multivariate observations, in: Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, Vol.\u00a01, Oakland, CA, USA, 1967, pp.\u00a0281\u2013297."},{"key":"10.3233\/SW-243540_ref25","doi-asserted-by":"publisher","DOI":"10.1109\/CIT.2008.4594646"},{"key":"10.3233\/SW-243540_ref26","unstructured":"M.\u00a0Muja and D.G.\u00a0Lowe, Fast approximate nearest neighbors with automatic algorithm configuration, in: International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications (VISSAPP), INSTICC Press, 2009, pp.\u00a0331\u2013340."},{"key":"10.3233\/SW-243540_ref27","doi-asserted-by":"publisher","DOI":"10.1109\/SISAP.2009.17"},{"key":"10.3233\/SW-243540_ref28","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767868"},{"key":"10.3233\/SW-243540_ref29","unstructured":"A.N.\u00a0Ngomo and S.\u00a0Auer, LIMES\u00a0\u2013 a time-efficient approach for large-scale link discovery on the web of data, in: International Joint Conference on Artificial Intelligence (IJCAI), 2011, pp.\u00a02312\u20132317."},{"key":"10.3233\/SW-243540_ref31","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-72617-0_17"},{"issue":"8","key":"10.3233\/SW-243540_ref32","doi-asserted-by":"publisher","first-page":"909","DOI":"10.1109\/TKDE.2004.25","article-title":"Efficient disk-based k-means clustering for relational databases","volume":"16","author":"Ordonez","year":"2004","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"issue":"1","key":"10.3233\/SW-243540_ref33","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/j.jda.2008.09.012","article-title":"Solving similarity joins and range queries in metric spaces with the list of twin clusters","volume":"7","author":"Paredes","year":"2009","journal-title":"Journal of Discrete Algorithms"},{"issue":"3","key":"10.3233\/SW-243540_ref34","doi-asserted-by":"publisher","first-page":"16:1","DOI":"10.1145\/1567274.1567278","article-title":"Semantics and complexity of SPARQL","volume":"34","author":"P\u00e9rez","year":"2009","journal-title":"ACM TODS"},{"key":"10.3233\/SW-243540_ref35","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-68288-4_31"},{"key":"10.3233\/SW-243540_ref37","doi-asserted-by":"publisher","DOI":"10.1109\/ICDEW.2013.6547456"},{"key":"10.3233\/SW-243540_ref38","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2021.101804"},{"key":"10.3233\/SW-243540_ref39","doi-asserted-by":"publisher","DOI":"10.1145\/3068335"},{"issue":"5","key":"10.3233\/SW-243540_ref40","doi-asserted-by":"publisher","first-page":"589","DOI":"10.3233\/SW-170285","article-title":"A systematic survey of point set distance measures for link discovery","volume":"9","author":"Sherif","year":"2018","journal-title":"Semantic Web"},{"key":"10.3233\/SW-243540_ref41","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1109\/69.979979","volume-title":"High-Dimensional Similarity Joins","author":"Shim","year":"2002"},{"key":"10.3233\/SW-243540_ref42","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.113"},{"key":"10.3233\/SW-243540_ref43","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41062-8_27"},{"key":"10.3233\/SW-243540_ref44","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04930-9_41"},{"key":"10.3233\/SW-243540_ref45","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1145\/2629489","article-title":"Wikidata: A free collaborative knowledgebase","volume":"57","author":"Vrande\u010di\u0107","year":"2014","journal-title":"Communications of the ACM"},{"key":"10.3233\/SW-243540_ref46","unstructured":"W.\u00a0Wang, J.\u00a0Yang, R.\u00a0Muntz et al., STING: A statistical information grid approach to spatial data mining, in: Very Large Data Bases Conference (VLDB), Vol.\u00a097, 1997, pp.\u00a0186\u2013195."},{"key":"10.3233\/SW-243540_ref47","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.1998.655795"},{"key":"10.3233\/SW-243540_ref48","unstructured":"P.N.\u00a0Yianilos, Data structures and algorithms for nearest neighbor search in general metric spaces, in: Symposium on Discrete Algorithms (SODA), Vol.\u00a093, 1993, pp.\u00a0311\u2013321."},{"key":"10.3233\/SW-243540_ref49","doi-asserted-by":"crossref","unstructured":"P.\u00a0Zezula, G.\u00a0Amato, V.\u00a0Dohnal and M.\u00a0Batko, Similarity Search: The Metric Space Approach, Vol.\u00a032, Springer Science & Business Media, 2006.","DOI":"10.1007\/0-387-29151-2"},{"key":"10.3233\/SW-243540_ref50","doi-asserted-by":"publisher","DOI":"10.1109\/GEOINFORMATICS.2010.5567605"},{"key":"10.3233\/SW-243540_ref51","doi-asserted-by":"publisher","DOI":"10.1145\/1341012.1341077"},{"issue":"2","key":"10.3233\/SW-243540_ref52","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1145\/235968.233324","article-title":"BIRCH: An efficient data clustering method for very large databases","volume":"25","author":"Zhang","year":"1996","journal-title":"SIGMOD Rec."},{"issue":"5","key":"10.3233\/SW-243540_ref53","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1002\/sam.11161","article-title":"A survey on unsupervised outlier detection in high-dimensional numerical data","volume":"5","author":"Zimek","year":"2012","journal-title":"Science Journal"}],"container-title":["Semantic Web"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/SW-243540","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T05:27:20Z","timestamp":1777613240000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/SW-243540"}},"subtitle":[],"editor":[{"given":"Marta","family":"Sabou","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Wien (TUWien), Austria"}],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2024,10,9]]},"references-count":50,"journal-issue":{"issue":"5"},"URL":"https:\/\/doi.org\/10.3233\/sw-243540","relation":{},"ISSN":["2210-4968","1570-0844"],"issn-type":[{"value":"2210-4968","type":"electronic"},{"value":"1570-0844","type":"print"}],"subject":[],"published":{"date-parts":[[2024,10,9]]}}}