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.
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.
1 download since deposited on 01 Jun 2012
0 downloads since 12 months
|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|
|Other Identification Number:||merlin-id:2809|
Users (please log in): suggest update or correction for this item
Repository Staff Only: item control page