MA'LUMOTLARNI TAKRORLANISHDAN TOZALASH VA SIFATINI OSHIRISH ALGORITMLARI
Abstract
Tashkilotlar to'playdigan ma'lumotlar hajmi o'sgani sari ularda bir xil obyektga tegishli takroriy va nomuvofiq yozuvlar ko'payadi, bu tahlil natijalarini buzadi va saqlash hamda qayta ishlash xarajatini oshiradi. Maqolada ma'lumotlar sifatini baholash mezonlari, ma'lumotni standartlash (normallashtirish) usullari hamda takrorlanishni aniqlash algoritmlari tizimlashtiriladi: aniq moslik, satr o'xshashligi o'lchovlari (Levenshtein, Jaro–Winkler), Fellegi–Sunter ehtimoliy modeli, blokirovka va saralangan qo'shnilik usuli, MinHash va LSH hamda fayl darajasidagi deduplikatsiya. Usullar 5000 yozuvli sintetik to'plamda (4000 obyekt, 1000 shovqinli takror) sinab ko'rildi: standartlash aniq moslik usulining F1-o'lchovini 0,14 dan 0,58 gacha, noaniq moslik usullarini esa 0,81 dan 0,91 gacha oshirdi, blokirovka esa taqqoslashlar sonini 26–95 marta kamaytirdi. Maqola oxirida amaliy tavsiyalar beriladi.
References
1. Batini, C., & Scannapieco, M. (2016). Data and Information Quality: Dimensions, Principles and Techniques. Springer.
2. Wang, R. Y., & Strong, D. M. (1996). Beyond accuracy: What data quality means to data consumers. Journal of Management Information Systems, 12(4), 5–33.
3. ISO/IEC 25012:2008. Software engineering – Software product Quality Requirements and Evaluation (SQuaRE) – Data quality model.
4. Elmagarmid, A. K., Ipeirotis, P. G., & Verykios, V. S. (2007). Duplicate record detection: A survey. IEEE Transactions on Knowledge and Data Engineering, 19(1), 1–16.
5. Rahm, E., & Do, H. H. (2000). Data cleaning: Problems and current approaches. IEEE Data Engineering Bulletin, 23(4), 3–13.
6. Ilyas, I. F., & Chu, X. (2019). Data Cleaning. ACM Books, Morgan & Claypool.
7. Levenshtein, V. I. (1966). Binary codes capable of correcting deletions, insertions and reversals. Soviet Physics Doklady, 10(8), 707–710.
8. Winkler, W. E. (1990). String comparator metrics and enhanced decision rules in the Fellegi–Sunter model of record linkage. Proceedings of the Section on Survey Research Methods, American Statistical Association, 354–359.
9. Fellegi, I. P., & Sunter, A. B. (1969). A theory for record linkage. Journal of the American Statistical Association, 64(328), 1183–1210.
10. Christen, P. (2012). Data Matching: Concepts and Techniques for Record Linkage, Entity Resolution, and Duplicate Detection. Springer.
11. Hernández, M. A., & Stolfo, S. J. (1995). The merge/purge problem for large databases. Proceedings of ACM SIGMOD, 127–138.
12. Papadakis, G., Skoutas, D., Thanos, E., & Palpanas, T. (2020). Blocking and filtering techniques for entity resolution: A survey. ACM Computing Surveys, 53(2), Article 31.
13. Broder, A. Z. (1997). On the resemblance and containment of documents. Proceedings of Compression and Complexity of Sequences (SEQUENCES '97), IEEE, 21–29.
14. Indyk, P., & Motwani, R. (1998). Approximate nearest neighbors: Towards removing the curse of dimensionality. Proceedings of ACM STOC, 604–613.
15. Leskovec, J., Rajaraman, A., & Ullman, J. D. (2020). Mining of Massive Datasets (3rd ed.). Cambridge University Press.
16. Mudgal, S., Li, H., Rekatsinas, T., et al. (2018). Deep learning for entity matching: A design space exploration. Proceedings of ACM SIGMOD, 19–34.
17. Muthitacharoen, A., Chen, B., & Mazières, D. (2001). A low-bandwidth network file system. Proceedings of ACM SOSP, 174–187.
18. Zhu, B., Li, K., & Patterson, H. (2008). Avoiding the disk bottleneck in the Data Domain deduplication file system. Proceedings of USENIX FAST, 269–282.
19. Harnik, D., Pinkas, B., & Shulman-Peleg, A. (2010). Side channels in cloud services: Deduplication in cloud storage. IEEE Security & Privacy, 8(6), 40–47.
20. Bellare, M., Keelveedhi, S., & Ristenpart, T. (2013). Message-locked encryption and secure deduplication. EUROCRYPT 2013, LNCS 7881, 296–312.
21. Bachmann, M. RapidFuzz: Rapid fuzzy string matching in Python and C++. https://github.com/rapidfuzz/RapidFuzz
