One-dimensional and multi-dimensional substring selectivity estimation
type: Item
instance of: scholarly article
title: One-dimensional and multi-dimensional substring selectivity estimation
zbMATH Open document ID: 0991.68690
author: H. V. Jagadish
author: Olga Kapitskaia
author: Raymond T. Ng
author: Divesh Srivastava
published in: The VLDB Journal
publication date: 2002-07-25T00:00:00Z
full work available at URL: http://hdl.handle.net/2027.42/42330
review text: With the increasing importance of XML, LDAP directories, and text-based information sources on the Internet, there is an ever-greater need to evaluate queries involving (sub)string matching. In many cases, matches need to be on multiple attributes/dimensions, with correlations between the multiple dimensions. Effective query optimization in this context requires good selectivity estimates. In this paper, we use pruned count-suffix trees (PSTs) as the basic data structure for substring selectivity estimation. For the 1-D problem, we present a novel technique called MO (Maximal Overlap). We then develop and analyze two 1-D estimation algorithms, MOC and MOLC, based on MO and a constraint-based characterization of all possible completions of a given PST. For the \(k\)-D problem, we first generalize PSTs to multiple dimensions and develop a space- and time-efficient probabilistic algorithm to construct \(k\)-D PSTs directly. We then show how to extend MO to multiple dimensions. Finally, we demonstrate, both analytically and experimentally, that MO is both practical and substantially superior to competing algorithms.
Mathematics Subject Classification ID: 68U99
Mathematics Subject Classification ID: 68P15
zbMATH DE Number: 1771594
MaRDI profile type: Publication
OpenAlex ID: W2147440220
DOI: 10.1007/S007780000029
description: scientific article; zbMATH DE number 1771594