INSTRUCT: Space-Efficient Structure for Indexing and Complete Query Management of String Databases by Sourav Dutta and Arnab Bhattacharya.
Abstract:
The tremendous expanse of search engines, dictionary and thesaurus storage, and other text mining applications, combined with the popularity of readily available scanning devices and optical character recognition tools, has necessitated efficient storage, retrieval and management of massive text databases for various modern applications. For such applications, we propose a novel data structure, INSTRUCT, for efficient storage and management of sequence databases. Our structure uses bit vectors for reusing the storage space for common triplets, and hence, has a very low memory requirement. INSTRUCT efficiently handles prefix and suffix search queries in addition to the exact string search operation by iteratively checking the presence of triplets. We also propose an extension of the structure to handle substring search efficiently, albeit with an increase in the space requirements. This extension is important in the context of trie-based solutions which are unable to handle such queries efficiently. We perform several experiments portraying that INSTRUCT outperforms the existing structures by nearly a factor of two in terms of space requirements, while the query times are better. The ability to handle insertion and deletion of strings in addition to supporting all kinds of queries including exact search, prefix/suffix search and substring search makes INSTRUCT a complete data structure.
From the introduction:
As all strings are composed of a defined set of characters, reusing the storage space for common characters promises to provide the most compressed form of representation. This redundancy linked with the need for extreme space-efficient index structures motivated us to develop INSTRUCT (INdexing STrings by Re-Using Common Triplets).
By the time of a presentation (below) on the technique, the authors apparently rethought the name, settling on:
“SPACE-EFFICIENT MANAGEMENT OF TEXT USING INDEXED KEYS” (SEManTIKs)“
Neither one really “rolls off the tongue,” but I suspect searching for the second may be somewhat easier.
I say that, but “semantiks” turns out to be a women’s clothing line and at least one popular search engine offers to correct to “semantics.” I am sure a “gathered scoop neck” and a “flattering boot-cut silhouette” are all quite interesting but not really on point.
The slide presentation lists some fourteen (14) other approaches that can be compared to the one developed by the authors. (I am assuming the master’s thesis by Dutta has the details on the comparisons with the other techniques. I haven’t found it online but have written to request a copy.)
This work demonstrates that we are no where near the end of improvements for indexing and search.
See also the presentation: SPACE-EFFICIENT MANAGEMENT OF STRING DATABASES BY REUSING COMMON CHARACTERS by Sourav Dutta.