Quick Search:

uzh logo
Browse by:

Zurich Open Repository and Archive

Permanent URL to this publication: http://dx.doi.org/10.5167/uzh-56143

Mazeika, Arturas; Böhlen, Michael H; Koudas, Nick; Srivastava, Divesh (2007). Estimating the selectivity of approximate string queries. ACM Transactions on Database Systems, 32(2):12.

[img]Published Version
PDF - Registered users only
View at publisher


Approximate queries on string data are important due to the prevalence of such data in databases and various conventions and errors in string data. We present the VSol estimator, a novel technique for estimating the selectivity of approximate string queries. The VSol estimator is based on inverse strings and makes the performance of the selectivity estimator independent of the number of strings. To get inverse strings we decompose all database strings into overlapping substrings of length q (q-grams) and then associate each q-gram with its inverse string: the IDs of all strings that contain the q-gram. We use signatures to compress inverse strings, and clustering to group similar signatures.We study our technique analytically and experimentally. The space complexity of our estimator only depends on the number of neighborhoods in the database and the desired estimation error. The time to estimate the selectivity is independent of the number of database strings and linear with respect to the length of query string. We give a detailed empirical performance evaluation of our solution for synthetic and real-world datasets. We show that VSol is effective for large skewed databases of short strings.


7 citations in Web of Science®
14 citations in Scopus®
Google Scholar™



1 download since deposited on 01 Jun 2012
0 downloads since 12 months

Detailed statistics

Additional indexing

Item Type:Journal Article, refereed, original work
Communities & Collections:03 Faculty of Economics > Department of Informatics
Dewey Decimal Classification:000 Computer science, knowledge & systems
Deposited On:01 Jun 2012 12:57
Last Modified:05 Apr 2016 15:26
Publisher:Association for Computing Machinery
Publisher DOI:10.1145/1242524.1242529
Other Identification Number:merlin-id:2809

Users (please log in): suggest update or correction for this item

Repository Staff Only: item control page