2020/02/04 by Mehmet Aytimur, Aytimur, Mehmet, Ali Cakmak +1 · 2 citations
Computer Science · #Advanced Database Systems and Queries #Data Management and Algorithms #Data Mining Algorithms and Applications #Data Structures and Algorithms (cs.DS) #Databases (cs.DB) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2002.01164
openalex publication_date 2020/02/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
With the dramatic increase in the amount of the text-based data which\ncommonly contains misspellings and other errors, querying such data with\nflexible search patterns becomes more and more commonplace. Relational\ndatabases support the LIKE operator to allow searching with a particular\nwildcard predicate (e.g., LIKE 'Sub%', which matches all strings starting with\n'Sub'). Due to the large size of text data, executing such queries in the most\noptimal way is quite critical for database performance. While building the most\nefficient execution plan for a LIKE query, the query optimizer requires the\nselectivity estimate for the flexible pattern-based query predicate. Recently,\nSPH algorithm is proposed which employs a sequence pattern-based histogram\nstructure to estimate the selectivity of LIKE queries. A drawback of the SPH\napproach is that it often overestimates the selectivity of queries. In order to\nalleviate the overestimation problem, in this paper, we propose a novel\nsequence pattern type, called positional sequence patterns. The proposed\npatterns differentiate between sequence item pairs that appear next to each\nother in all pattern occurrences from those that may have other items between\nthem. Besides, we employ redundant pattern elimination based on pattern\ninformation content during histogram construction. Finally, we propose a\npartitioning-based matching scheme during the selectivity estimation. The\nexperimental results on a real dataset from DBLP show that the proposed\napproach outperforms the state of the art by around 20% improvement in error\nrates.\n