City Research Online

Abstract

One common way to speed up the find operation within a set of text files involves a trigram index. This structure is merely a map from a trigram (sequence consisting of three characters) to a set of files which contain it. When searching for a pattern, potential file locations are identified by intersecting the sets related to the trigrams in the pattern. Then, the search proceeds only in these files.

However, in a code repository, the trigram index evolves across different versions. Upon checking out a new version, this index is typically built from scratch, which is a time-consuming task, while we want our index to have almost zero-time startup.

Thus, we explore the persistent version of a trigram index for full-text and key word patterns search. Our approach just uses the current version of the trigram index and applies only the changes between versions during checkout, significantly enhancing performance. Furthermore, we extend our data structure to accommodate CamelHump search for class and function names.

Publication Type:	Conference or Workshop Item (Paper)
Additional Information:	Copyright © 2024 by the Association for Computing Machinery,Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page
Publisher Keywords:	search index, trigrams, persistency
Subjects:	Q Science > QA Mathematics > QA76 Computer software Z Bibliography. Library Science. Information Resources > ZA Information resources Z Bibliography. Library Science. Information Resources > ZA Information resources > ZA4050 Electronic information resources
Departments:	School of Science & Technology School of Science & Technology > Department of Computer Science
SWORD Depositor:	Symplectic Administrator

Export

Downloads