Generalized substring selectivity estimation

Zhiyuan Chen; Flip Korn; Nick Koudas; S. Muthukrishnan

doi:10.1016/S0022-0000(02)00031-4

Generalized substring selectivity estimation

Zhiyuan Chen, Flip Korn, Nick Koudas, S. Muthukrishnan

Research output: Contribution to journal › Article › peer-review

Abstract

An approach to selectivity estimation of generalized Boolean substring queries with a focus on conjunctive multidimensional and Boolean queries was presented. The set hashing, a Monte Carlo technique, was used to succinctly represent the set of tuples containing a given substring as a signature vector of hash values. The analysis showed that using only linear storage, a large number of cross-counts were generated including those for complex co-occurrences of substrings.

Original language	English (US)
Pages (from-to)	98-132
Number of pages	35
Journal	Journal of Computer and System Sciences
Volume	66
Issue number	1
DOIs	https://doi.org/10.1016/S0022-0000(02)00031-4
State	Published - 2003

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science
Applied Mathematics
Computer Networks and Communications
Computational Theory and Mathematics

Access to Document

10.1016/S0022-0000(02)00031-4

Cite this

@article{d4022283661f47418c27938efacb4b3e,

title = "Generalized substring selectivity estimation",

abstract = "An approach to selectivity estimation of generalized Boolean substring queries with a focus on conjunctive multidimensional and Boolean queries was presented. The set hashing, a Monte Carlo technique, was used to succinctly represent the set of tuples containing a given substring as a signature vector of hash values. The analysis showed that using only linear storage, a large number of cross-counts were generated including those for complex co-occurrences of substrings.",

author = "Zhiyuan Chen and Flip Korn and Nick Koudas and S. Muthukrishnan",

year = "2003",

doi = "10.1016/S0022-0000(02)00031-4",

language = "English (US)",

volume = "66",

pages = "98--132",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - Generalized substring selectivity estimation

AU - Chen, Zhiyuan

AU - Korn, Flip

AU - Koudas, Nick

AU - Muthukrishnan, S.

PY - 2003

Y1 - 2003

N2 - An approach to selectivity estimation of generalized Boolean substring queries with a focus on conjunctive multidimensional and Boolean queries was presented. The set hashing, a Monte Carlo technique, was used to succinctly represent the set of tuples containing a given substring as a signature vector of hash values. The analysis showed that using only linear storage, a large number of cross-counts were generated including those for complex co-occurrences of substrings.

AB - An approach to selectivity estimation of generalized Boolean substring queries with a focus on conjunctive multidimensional and Boolean queries was presented. The set hashing, a Monte Carlo technique, was used to succinctly represent the set of tuples containing a given substring as a signature vector of hash values. The analysis showed that using only linear storage, a large number of cross-counts were generated including those for complex co-occurrences of substrings.

UR - http://www.scopus.com/inward/record.url?scp=0038605881&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0038605881&partnerID=8YFLogxK

U2 - 10.1016/S0022-0000(02)00031-4

DO - 10.1016/S0022-0000(02)00031-4

M3 - Article

AN - SCOPUS:0038605881

SN - 0022-0000

VL - 66

SP - 98

EP - 132

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 1

ER -

Generalized substring selectivity estimation

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this