Problem motivation


Download 513 b.
Sana08.12.2017
Hajmi513 b.









Problem motivation

  • Problem motivation

  • Preliminaries

    • Grams
    • Inverted lists
  • Merge algorithms

  • Filtering techniques

  • Conclusion



q-grams

  • q-grams



Convert strings to gram inverted lists

  • Convert strings to gram inverted lists







T = 4

  • T = 4





Problem motivation

  • Problem motivation

  • Preliminaries

  • Merge algorithms

  • Filtering techniques

  • Conclusion







































Problem motivation

  • Problem motivation

  • Preliminaries

  • Merge algorithms

  • Filtering techniques

  • Conclusion and future work











Filters fragment inverts lists



  • Three new merge algorithms

  • Interesting finding:





[Arasu 2006] A. Arasu and V. Ganti and R. Kaushik “Efficient Exact Set-similarity Joins” in VLDB 2006

  • [Arasu 2006] A. Arasu and V. Ganti and R. Kaushik “Efficient Exact Set-similarity Joins” in VLDB 2006

  • [Chaudhuri 2003] S. Chaudhuri ,K Ganjam, V. Ganti and R. Motwani “Robust and Efficient Fuzzy Match for online Data Cleaning” in SIGMOD 2003

  • [Gravano 2001] L. Gravano, P.G. Ipeirotis, H.V. Jagadish, N. Koudas, S. Muthukrishnan and D. Srivastava “Approximate string joins in a database almost for free” in VLDB 2001



4. [Li 2007] C. Li, B Wang and X. Yang “VGRAM:Improving performance of approximate queries on string collections using variable-length grams ” in VLDB 2007

  • 4. [Li 2007] C. Li, B Wang and X. Yang “VGRAM:Improving performance of approximate queries on string collections using variable-length grams ” in VLDB 2007

  • 5. [Navarro 2001] G. Navarro, “A guided tour to approximate string matching” in Computing survey 2001

  • 6. [Sarawagi 2004] S. Sarawagi and A. Kirpal, “Efficient set joins on similarity predicates” in ACM SIGMOD 2004




Do'stlaringiz bilan baham:


Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2017
ma'muriyatiga murojaat qiling