article · 1999

Substring selectivity estimation

Hongrae Lee, Raymond T. Ng, Kyuseok Shim

Cited by 0Abstract and details only

Abstract

We study the problem of estimating selectivity of approximate substring queries. Its importance in databases is ever increasing as more and more data are input by users and are integrated with many typographical errors and different spelling conventions. To begin with, we consider edit distance for the similarity between a pair of strings. Based on information stored in an extended N-gram table, we propose two estimation algorithms, MOF and LBS for the task. The latter extends the former with ideas from set hashing signatures. The experimental results show that MOF is a light-weight algorithm that gives fairly accurate estimations. However, if more space is available, LBS can give better accuracy than MOF and other baseline methods. Next, we extend the proposed solution to other similarity predicates, SQL LIKE operator and Jaccard similarity. 1.

Cite this paper

APA 7

Lee, H., Ng, R. T., & Shim, K. (1999). Substring selectivity estimation.

MLA 9

Lee, Hongrae, et al. “Substring selectivity estimation.” 1999.

Chicago

Lee, Hongrae, Raymond T. Ng, and Kyuseok Shim. 1999. “Substring selectivity estimation.”

Harvard

Lee, H., Ng, R.T. and Shim, K. (1999) ‘Substring selectivity estimation’.

BibTeX

@article{lee1999substring,
  title = {{Substring selectivity estimation}},
  author = {Lee, Hongrae and Ng, Raymond T. and Shim, Kyuseok},
  year = {1999}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.