Burst tries: a fast, efficient data structure for string keys Export

@article{citeulike:747171, abstract = {Many applications depend on efficient management of large sets of distinct strings in memory. For example, during index construction for text databases a record is held for each distinct word in the text, containing the word itself and information such as counters. We propose a new data structure, the burst trie, that has significant advantages over existing options for such applications: it uses about the same memory as a binary search tree; it is as fast as a trie; and, while not as fast as a hash table, a burst trie maintains the strings in sorted or near-sorted order. In this paper we describe burst tries and explore the parameters that govern their performance. We experimentally determine good choices of parameters, and compare burst tries to other structures used for the same task, with a variety of data sets. These experiments show that the burst trie is particularly effective for the skewed frequency distributions common in text collections, and dramatically outperforms all other data structures for the task of managing strings while maintaining sort order.}, address = {New York, NY, USA}, author = {Heinz, Steffen and Zobel, Justin and Williams, Hugh E.}, citeulike-article-id = {747171}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=506312}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/506309.506312}, doi = {10.1145/506309.506312}, issn = {1046-8188}, journal = {ACM Trans. Inf. Syst.}, keywords = {2002, data-structure, tois, trie}, month = {April}, number = {2}, pages = {192--223}, posted-at = {2009-09-30 14:07:49}, priority = {4}, publisher = {ACM}, title = {Burst tries: a fast, efficient data structure for string keys}, url = {http://dx.doi.org/10.1145/506309.506312}, volume = {20}, year = {2002} }

TY - JOUR ID - citeulike:747171 L3 - citeulike-article-id:747171 N2 - Many applications depend on efficient management of large sets of distinct strings in memory. For example, during index construction for text databases a record is held for each distinct word in the text, containing the word itself and information such as counters. We propose a new data structure, the burst trie, that has significant advantages over existing options for such applications: it uses about the same memory as a binary search tree; it is as fast as a trie; and, while not as fast as a hash table, a burst trie maintains the strings in sorted or near-sorted order. In this paper we describe burst tries and explore the parameters that govern their performance. We experimentally determine good choices of parameters, and compare burst tries to other structures used for the same task, with a variety of data sets. These experiments show that the burst trie is particularly effective for the skewed frequency distributions common in text collections, and dramatically outperforms all other data structures for the task of managing strings while maintaining sort order. IS - 2 JF - ACM Trans. Inf. Syst. SN - 1046-8188 AD - New York, NY, USA EP - 223 TI - Burst tries: a fast, efficient data structure for string keys PB - ACM VL - 20 SP - 192 KW - 2002 KW - data-structure KW - tois KW - trie AU - Heinz, Steffen AU - Zobel, Justin AU - Williams, Hugh PY - 2002/04// UR - http://dx.doi.org/10.1145/506309.506312 ER -