AS-Index: A Structure for String Search Using n-Grams and Algebraic Signatures
Rigaux, Philippe; Litwin, Witold; du Mouza, Cédric; Schwarz, Thomas (2009), AS-Index: A Structure for String Search Using n-Grams and Algebraic Signatures, CIKM 2009 18th ACM Conference on Information and Knowledge Management, 2009-11, Hong-Kong, Chine
TypeCommunication / Conférence
Conference titleCIKM 2009 18th ACM Conference on Information and Knowledge Management
MetadataShow full item record
Abstract (EN)AS-Index is a new index structure for exact string search in disk resident databases. It uses hashing, unlike known alternatives, whether baesd on trees or tries. It typically indexes every n-gram in the database, though non-dense indexing is possible. The hash function uses the algebraic signatures of n-grams. Use of hashing provides for constant index access time for arbitrarily long patterns, unlike other structures whose search cost is at best logarithmic. The storage overhead of AS-Index is basically 500 - 600%, similar to that of alternatives or smaller. We show the index structure, our use of algebraic signatures and the search algorithm. We present the theoretical and experimental performance analysis. We compare the AS-Index to main alternatives. We conclude that AS-Index is an attractive structure and we indicate directions for future work.
Subjects / KeywordsDatabases
Showing items related by title and author.
Constantin, Camelia; du Mouza, Cedric; Litwin, Witold; Rigaux, Philippe; Schwarz, Thomas (2016) Article accepté pour publication ou publié
Cumulative Algebraic Signatures for Fast String Search, Protection Against Incidental Viewing and Corruption of Data in an SDDS Litwin, Witold; Mokadem, Riad; Schwarz, Thomas (2007) Communication / Conférence