2012/07/02 by Sourav Dutta, Arnab Bhattacharya, Dutta, Sourav +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #Databases (cs.DB) #FOS: Computer and information sciences #H.2.4 #Network Packet Processing and Optimization #Web Data Mining and Analysis
paper · pdf · doi:10.48550/arxiv.1207.0361
openalex publication_date 2012/07/02 · openalex created_date 2022/09/02 · openalex updated_date 2026/07/28
The tremendous expanse of search engines, dictionary and thesaurus storage,\nand other text mining applications, combined with the popularity of readily\navailable scanning devices and optical character recognition tools, has\nnecessitated efficient storage, retrieval and management of massive text\ndatabases for various modern applications. For such applications, we propose a\nnovel data structure, INSTRUCT, for efficient storage and management of\nsequence databases. Our structure uses bit vectors for reusing the storage\nspace for common triplets, and hence, has a very low memory requirement.\nINSTRUCT efficiently handles prefix and suffix search queries in addition to\nthe exact string search operation by iteratively checking the presence of\ntriplets. We also propose an extension of the structure to handle substring\nsearch efficiently, albeit with an increase in the space requirements. This\nextension is important in the context of trie-based solutions which are unable\nto handle such queries efficiently. We perform several experiments portraying\nthat INSTRUCT outperforms the existing structures by nearly a factor of two in\nterms of space requirements, while the query times are better. The ability to\nhandle insertion and deletion of strings in addition to supporting all kinds of\nqueries including exact search, prefix/suffix search and substring search makes\nINSTRUCT a complete data structure.\n