@inproceedings{94a992b944f847e6a563bce983bf3f1a,
title = "Efficient subsequence search in databases",
abstract = "Finding tuples in a database that match a particular subsequence (with gaps) is an important problem for a range of applications. Subsequence search is equivalent to searching for regular expressions of the type.*q 1.*q 2.*.*q l .*, where the subsequence is q 1 q 2.q l . For efficient execution of these queries, there is a need for appropriate index structures that are both efficient and can scale to large problem sizes. This paper presents two index structures for such queries based on trie and bitmap. These indices are disk-resident, hence can be easily used by large databases with limited memory availability. Our indices are applicable to dynamic databases, where tuples can be added or deleted. Both indices are implemented and validated against a naive approach. The results show that the proposed indices are efficient, having low I/O and time overhead.",
author = "Rohit Jain and Mohania, \{Mukesh K.\} and Sunil Prabhakar",
year = "2013",
doi = "10.1007/978-3-642-38562-9\_45",
language = "English",
isbn = "9783642385612",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "440--452",
booktitle = "Web-Age Information Management - 14th International Conference, WAIM 2013, Proceedings",
address = "Germany",
note = "14th International Conference on Web-Age Information Management, WAIM 2013 ; Conference date: 14-06-2013 Through 16-06-2013",
}