NDLI: State-of-the-art in string similarity search and join

Please wait, while we are loading the content...

State-of-the-art in string similarity search and join

Content Provider	ACM Digital Library
Author	Leser, Ulf Siragusa, Enrico Mitankin, Petar Wang, Wei Patil, Manish Wandelt, Sebastian Deng, Dong Gerdjikov, Stefan Mishra, Shashwat Wang, Jiaying Tiskin, Alexander
Abstract	String similarity search and its variants are fundamental problems with many applications in areas such as data integration, data quality, computational linguistics, or bioinformatics. A plethora of methods have been developed over the last decades. Obtaining an overview of the state-of-the-art in this field is difficult, as results are published in various domains without much cross-talk, papers use different data sets and often study subtle variations of the core problems, and the sheer number of proposed methods exceeds the capacity of a single research group. In this paper, we report on the results of the probably largest benchmark ever performed in this field. To overcome the resource bottleneck, we organized the benchmark as an international competition, a workshop at EDBT/ICDT 2013. Various teams from different fields and from all over the world developed or tuned programs for two crisply defined problems. All algorithms were evaluated by an external group on two machines. Altogether, we compared 14 different programs on two string matching problems (k-approximate search and k-approximate join) using data sets of increasing sizes and with different characteristics from two different domains. We compare programs primarily by wall clock time, but also provide results on memory usage, indexing time, batch query effects and scalability in terms of CPU cores. Results were averaged over several runs and confirmed on a second, different hardware platform. A particularly interesting observation is that disciplines can and should learn more from each other, with the three best teams rooting in computational linguistics, databases, and bioinformatics, respectively.
Starting Page	64
Ending Page	76
Page Count	13
File Format	PDF
ISSN	01635808
DOI	10.1145/2627692.2627706
Journal	ACM SIGMOD Record (SGMD)
Volume Number	43
Issue Number	1
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1999-06-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Scalability String search Comparison String join
Content Type	Text
Resource Type	Article
Subject	Information Systems Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Boosting the Quality of Approximate String Matching by Synonyms

String similarity search and join: a survey

Extending string similarity join to tolerant fuzzy token matching

Epsilon grid order:an algorithm for the similarity join on massive high-dimensional data

A partition-based method for string similarity joins with edit-distance constraints

S3:similarity search in CAD database systems

Fast parallel similarity search in multimedia databases

Super-EGO: fast multi-dimensional similarity join

Set similarity join on massive probabilistic data using MapReduce

State-of-the-art in string similarity search and join

Similar Documents

Boosting the Quality of Approximate String Matching by Synonyms

String similarity search and join: a survey

Extending string similarity join to tolerant fuzzy token matching

Epsilon grid order:an algorithm for the similarity join on massive high-dimensional data

A partition-based method for string similarity joins with edit-distance constraints

S3:similarity search in CAD database systems

Fast parallel similarity search in multimedia databases

Super-EGO: fast multi-dimensional similarity join

Set similarity join on massive probabilistic data using MapReduce

State-of-the-art in string similarity search and join