An Efficient Elastic-Degenerate Text Index? Not Likely
| العنوان: | An Efficient Elastic-Degenerate Text Index? Not Likely |
|---|---|
| المؤلفون: | Daniel Gibney |
| المصدر: | String Processing and Information Retrieval ISBN: 9783030592110 SPIRE |
| بيانات النشر: | Springer International Publishing, 2020. |
| سنة النشر: | 2020 |
| مصطلحات موضوعية: | 050101 languages & linguistics, Polynomial, Exponential time hypothesis, Matching (graph theory), Computer Science::Information Retrieval, 05 social sciences, Degenerate energy levels, Window (computing), 02 engineering and technology, Image (mathematics), Alpha (programming language), 0202 electrical engineering, electronic engineering, information engineering, Preprocessor, 020201 artificial intelligence & image processing, 0501 psychology and cognitive sciences, Algorithm, ComputingMethodologies_COMPUTERGRAPHICS, Mathematics |
| الوصف: | Elastic-degenerate text provides a novel and effective method for modeling collections of text that have local variations. Due to its applicability in pan-genomics, an index for an elastic-degenerate text which can efficiently report the occurrences of a given query pattern is desirable. This paper attempts to dash our hopes for such an index, one that is deterministic and has good worst-case query time. We do so by providing conditional lower bounds based on the Orthogonal Vectors Hypothesis (OVH) (and hence the Strong Exponential Time Hypothesis). We show that, even with arbitrary polynomial preprocessing time, an index for an elastic-degenerate text with n degenerate letters that can perform queries on a pattern of length m in time Open image in new window for constants \(\alpha \) and \(\beta \) where Open image in new window or Open image in new window would violate OVH. Additionally, we provide an elastic-degenerate text index with query time Open image in new window, which is independent of the size N (distinct from its length) of the elastic-degenerate text. Finally, we investigate the hardness of matching elastic-degenerate text to elastic-degenerate text. |
| ردمك: | 978-3-030-59211-0 |
| DOI: | 10.1007/978-3-030-59212-7_6 |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_________::e2ea5b38170ce50bd2f120b8b0df47ca https://doi.org/10.1007/978-3-030-59212-7_6 |
| Rights: | CLOSED |
| رقم الانضمام: | edsair.doi...........e2ea5b38170ce50bd2f120b8b0df47ca |
| قاعدة البيانات: | OpenAIRE |
| ردمك: | 9783030592110 |
|---|---|
| DOI: | 10.1007/978-3-030-59212-7_6 |