The week's pick
Random Articles
Reseach Article
Identification of Similar Strings in a Dataset using Scalable Join
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 120 - Number 18 |
| Year of Publication: 2015 |
| Authors: Khalid F. Alfatmi, Archana S. Vaidya |
10.5120/21329-4295
|
Khalid F. Alfatmi, Archana S. Vaidya . Identification of Similar Strings in a Dataset using Scalable Join. International Journal of Computer Applications. 120, 18 ( June 2015), 25-28. DOI=10.5120/21329-4295
Abstract
Similarity Join plays an important role in data integration and cleansing, record linkage and data de-duplication. It finds similar sting pairs from collections of strings. If two strings are similar they share a common token. Number of approaches has been proposed for in-memory string similarity joins. But due to the rising era of big data, demands for scalable algorithms to support large scale string similarity joins arises. The proposed architecture uses the MapReduce concept and is based on inverted index and multiple prefix filtering methods. The prefix filtering is made of different global ordering which reduces the number of candidate pairs significantly, thus improving the pruning power as compared to other approach.
References
- C. Rong, Wei Lu, Xiaoli Wang, Xiaoyong Du and Anthony K. H. Tung, "Efficient and Scalabe Processing of String Similarity Join," IEEE Transactions on Knowledge and Data Engineering, VOL. 25, 2013, pages 2217-2230.
- R. Vernica, M. J. Carey, and C. Li, "Efficient Parallel Set Similarity Joins using MapReduce," In SIGMOD, 2010, pages 495-502.
- J. Dean and S. Ghemawat, "Mapreduce: Simplified data processing on large clusters," In OSDI, pages 137- 150, 2014.
- NikolausAugsten, Michael H Bohlen, "Similarity Joins in Relational Database Systems," Morgan & Claypool publishers.
- Younghoon Kim, Kyuseok Shim, "Parallel Top-K Similarity Join Algorithms using MapReduce," IEEE 28th International Conference on Data Engineering, 2012.
- A. Arasu, V. Ganti, and R. Kaushik, "Efficient Exact Set-Similarity Joins," Proc. 32nd International Conf. Very Large Data Bases, pp. 918-929, 2009.
- Yu Jiang, Guoliang Li, JinhuaFeng, Wen-Syan Li, "String Similarity Joins: An Experimental evaluation", International Conference on Very LargeDataBases, Vol. 7, No. 8. , 2014.
- Wang, J. Feng, and G. Li, "Trie-Join: Efficient Trie-Based String Similarity Joins with Edit-Distance Constraints," Proc. VLDB Endowment, vol. 3, nos. 1/2, pp. 1219-1230, 2010.
- C. Xiao, W. Wang, X. Lin, and J. Yu, "Efficient Similarity Joins for Near Duplicate Detection," Proc. International Conf. World Wide Web, pp. 131-140, 2008.
- A. Elmagarmid, P. Ipeirotis, and V. Verykios, "Duplicate Record Detection: A Survey," IEEE Trans. Knowledge and Data Eng. , vol. 19, no. 1, pp. 1-16, Jan. 2007.
- Z. Zhang, M. Hadjieleftheriou, B. Ooi, and D. Srivastava, "Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance," Proc. ACM SIGMOD International Conf. Management of Data, pp. 915-926, 2010.
- Dataset https://www. informatik. uni-trier. de/~ley/db
- D. Deng, G. Li, S. Hao,"MassJoin: A MapReduce-based Method for Scalable String Similarity Joins", IEEE 30th International Conference on Data Engineering, pp. 340-351, 2014.
Index Terms
Keywords