An Adaptive Algorithm for Splitting Large Sets of Strings
and Its Application to Efficient External Sorting
Tatsuya Asai†

Seishi Okamoto†

Hiroki Arimura‡† Knowledge Research Center, Fujitsu Laboratories Ltd.
4–1–1 Kamikodanaka, Nakahara-ku, Kawasaki 211–8588, Japan
Email: asai.tatsuya@jp.fujitsu.com
Email: seishi@labs.fujitsu.com‡ Graduate School of Information Science and Technology, Hokkaido University
Kita 14–jo, Nishi 9–chome, Sapporo 060–0814, Japan
Email: arim@ist.hokudai.ac.jp

STEP2: SplitDietTrie

STEP3: SortBucket

SortedOutput String List T

SortedBucketSortedBucketBucketSortedBucketSynopsis Trie TαS

BucketSTEP1: BuildDietTrie

Internal memory

BucketIn this paper, we study the problem of sorting a large
collection of strings in external memory. Based on
adaptive construction of a summary data structure,
called adaptive synopsis trie, we present a practical string sorting algorithm DistStrSort, which issuitable to sorting string collections of large size inexternal memory, and also suitable for more complex string processing problems in text and semistructured databases such as counting, aggregation,and statistics. Case analyses of the algorithm and experiments on real datasets show the efficiency of ouralgorithm in realistic setting.

GrowthInternal memory
parameter α

Input String List S

Abstract

STEP4: Merge

Figure 1: The architecture of an external sorting algorithm DistStrSort using adaptive constructionof a synopsis trie

Keywords: external string sorting, trie sort, semistructured database, text database, data splitting
1

Introduction

Sorting strings is a fundamental task of string processing, which is not only sorting the objects in associated ordering, but also used as a basis of moresophisticated processing such as grouping, counting, and aggregation. With a recent emergence ofmassive amount of semi-structured data (Abiteboul
et al. 2000), such as plain texts, Web pages, or
XML documents, it is often the case that we would
like to sort a large collection of strings that do not
fit into main memory. Moreover, there are potential demands for flexible methods tailored for semistructured data beyond basic sorting facilities suchas statistics computation, counting, and aggregation
over various objects including texts, data, codes,
and streams (Abiteboul et al. 2005, Stonebraker et
al. 2005).
In this paper, we study efficient methods for sorting strings in external memory. We present a new
approach to sorting a large collection of strings in external memory. The main idea of our method is togeneralize distribution sort algorithms for collectionsof strings by the extensive use of trie data structure.
To implement this idea, we introduce a synopsis data
structure for strings, called a synopsis trie, for approximate distribution, and develop an adaptive con-struction algorithm for synopsis tries for a large collection of strings with the idea of adaptive growth.
Based on this technique, we present an external
string sorting algorithm DistStrSort. In Fig. 1, weshow an architecture of our external sorting. Thisalgorithm first adaptively construct a small synopsis
trie as a model of string distribution by a single scanof the input data, splits input strings into a collection of buckets using the synopsis trie as a splitter,then sort the strings in each bucket in main memory,and finally merge the sorted buckets into an output
collection.
By an analysis, we show that if both of the size ofthe synopsis trie and the maximum size of the buckets
are small enough to fit into main memory of size M ,then our algorithm DistStrSort correctly solves theexternal string sorting problem in O(N ) time withinmain memory M using 3N sequential read, N random write, and N sequential write in the external
memory, where N is the total size of an input string
list S. Thus, this algorithm of O(N ) time complexity is attractive compared with a popular merge sortbased external string sort algorithm of O(N log N )time complexity. Experiments on real datasets show
the effectiveness of our algorithm.
As an advantage, this algorithm is suitable
to implement complex data manipulation operations (Ramakrishnan and Gehrke 2000) such asgroup-by aggregation, statistics calculation, and functional join for texts.
1.1

Related works

In what follows, we denote by K = |S| and N = ||S||be the cardinality and the total size of an input string
list S ∈ (Σ∗ )∗ .
A straightforward extension of quick sort algorithm solves the string sorting problem in
O(LK log K) time in main memory, where L is the
maximum length of the input strings and N =O(LK). This algorithm is efficient if L = O(1), butinefficient if L is large.
Arge et al. presented an algorithm that solves
the string sorting problem in O(K log K + N ) timein main memory (Arge et al. 1997). The String Btree is an efficient dynamic indexing data structure
for strings (Ferragina and Grossi 1999). This data
structure also has almost optimal performance for external string sorting in theory, while the performancedegenerates in practice because of many random access to external memory.
Sinha and Zobel presented a trie-based string
sorting algorithm, called the burst sort, and showthat the algorithm outperforms many of previous
string sorting algorithms on real datasets (Sinha andZobel 2003). However, their algorithm is an internal sorting algorithm, and furthermore, the main aimof this paper is proposal of an adaptive strategy forrealizing an efficient external string sorting.
Although there are a number of studies on sorting the suffixes of a single input string (Bentley andSedgewick 1997, Manber and Myers 1993, Manzini
and Ferragina 2002, Sadakane 1999), they are rather
irrelevant to this work since they are mainly incore
algorithms and utilize the repetition structure of suffixes of a string.
The adaptive construction of a trie for a stream ofletters has been studied since 90’s in time-series modeling (Laird, Saul 1994), data compression (Moffat1990), and bioinformatics (Ron, Singer, Tishby 1996).
However, the application of adaptive trie construction
to external sorting seems new and an interesting direction in text and semi-structured data processing.
Recently, (Stonebraker et al. 2005) showed the usefulness of distributed stream processing as a massive
data application of new type.
1.2

Organization

This paper is organized as follows. In Section 2, we
prepare basic notions and definitions on string sorting
and related string processing problems. In Section 3,
we present our external string sorting algorithm basedon adaptive construction of a synopsis trie. In Section
4, we report experiments on real datasets, and finally,
we conclude in Section 5.
2

Preliminaries

In this section, we give basic notions and definitions
on external string sorting.

2.1

Strings

Let Σ = {A, B, A1 , A2 , . . .} be an alphabet of letters,with which a total order ≤Σ on Σ is associated. In
particular, we assume that our alphabet is a set of
integers in a small range, i.e., Σ = {0, . . . , C − 1}for some integer C ≥ 0, which is a constant or at
most O(N ) for the total input size N . This is thecase for ASCII alphabet {0, . . . , 255} or DNA alphabet {A, T, C, G}.
We denote by Σ∗ the set of all finite strings on Σand by ε the empty string. Let s = a1 · · · an ∈ Σ∗
be a string on Σ. For 1 ≤ i ≤ j ≤ n, we denote by|s| = n the length of s, by s[i] = ai the i-th letter ,and by s[i..j] = ai · · · aj the substring from i-th toj-th letters. If s = pq for some p, q ∈ Σ∗ then we saythat p is a prefix of s and denote p v s.
We define the lexicographic order ≤lex on stringsof Σ∗ by extending the total order ≤Σ on letters inthe standard way.
2.2

String sorting problem

For strings s1 , . . . , sm ∈ Σ∗ , we distinguish an ordered list (s1 , . . . , sm ), an unordered list (or multiset) {{s1 , . . . , sm }}, and a set {s1 , . . . , sm } (of uniquestrings) each other. The notations ∈ and = are defined accordingly. We use the intentional notation( s | P (s) ) or { s | P (s) }. For lists of strings S1 , S2 ,we denote by S1 S2 (S1 ⊕ S2 , resp.) the concatenationof S1 , S2 as ordered lists (as unordered lists, resp.).
An input to our algorithm is a string list of sizeK ≥ 0 that is just an ordered list S = (s1 , . . . , sK ) ∈(Σ∗ )∗ of possibly identical strings, where si ∈ Σ∗ is astrings on Σ for every 1 ≤ i ≤ K. We denote by |S| =PK
K the cardinality of S and ||S|| = N = i=1 |si | thetotal size of S. We denote the set of all unique strings
in S by uniq(S) = { si | i = 1, . . . , K }. A string list
S = (s1 , . . . , sn ) is sorted if si ≤lex si+1 holds forevery i = 1, . . . , n − 1.
Definition 1 The string sorting problem (STRSORT) is, given a string list S = (s1 , . . . , sK ) ∈(Σ∗ )∗ , to compute the sorted list π(S) =(sπ(1) , . . . , sπ(K) ) ∈ (Σ∗ )∗ for some permutation π :{1, . . . , K} → {1, . . . , K} of its indices.
We can extend our framework for more complicated string processing problems as follows.
Definition 2 The string counting problem (STRCOUNT) is, given a string list S = (s1 , . . . , sK ) ∈(Σ∗ )∗ , to compute the histogram h : uniq(S) → N
such that h(s) is the number of occurrences of theunique string s.
Let (∆, ◦) be a pair of a collection ∆ of values anda corresponding associative operation ◦ : ∆2 → ∆.
For example, (N, +) and (R, max) are examples of(∆, ◦). A string database of size K ≥ 0 over dom(D)is a list D = ( (si , vi ) | i = 1, . . . , K ) ∈ (Σ∗ × ∆)∗of pairs of a string and a value. We denote byuniq(D) = {si | (si , vi ) ∈ D } the set of unique strings
in S. For (∆, ◦), the aggregate on s w.r.t. ◦, denoted

Algorithm DistStrSort:
Input: A string list S = (s1 , . . . , sK ) ∈ (Σ∗ )∗ anda maximal bucket size 0 ≤ B ≤ M .
Output: The sorted string list T ∈ (Σ∗ )∗ .
1. Determine a growth parameter α ≥ 0. Build an
adaptive synopsis trie Tα,S for S in main memory
with the growth parameter α and a bucket size B.
(BuildDietTrie in Fig. 4)
2. Split the input list S in external memory into
partition of buckets S1 , . . . , Sd of size at most B(d ≥ 0) by using Tα,S , where Si ¹ Si+1 for every
i = 1, . . . , n − 1. (BuildDietTrie in Fig. 5)
3. For every i = 1, . . . , K, sort the bucket Bi by arbitrary internal sorting algorithm and write backto Bi in external memory. (BuildDietTrie inFig. 6)
4. Return the concatenation T = B1 · · · BK ofsorted buckets.
Figure 2: An outline of the external string sorting
algorithm with adaptive splitting DistStrSort
by aggr◦ (s), is defined as aggr◦ (s) = ◦ ( v | (s, v) ∈D ) = v1 ◦ · · · ◦ vm , where (s1 , v1 ), . . . , (sm , vm ) ∈ D
is the list of all pairs in D with si = s.
Definition 3 The string aggregation problem w.r.t.
operation (∆, ◦) (STR-AGGREGATE(∆, ◦)) is, given
a string database S = ( (si , vi ) | i = 1, . . . , K ) ∈(Σ∗ ×∆)∗ , to compute the pair (s, aggr◦ (s)) for every
unique string s ∈ uniq(D).
The above string counting and string aggregation
problems as well as string sorting problem can be efficiently solved by a modification of trie-based sorter.
In this paper, we extend such a trie-based sorter foran external memory environment.
2.3

Model of computation

In what follows, we denote by K = |S| and N = ||S||the cardinality and the total size of the input string
list S. We assume a naive model of computation suchthat a CPU has random access to a main memoryof size M ≥ 0 and sequential and random access toan external memory of unbounded size, where memory space is measured in the number of integers to
be stored. Though the external memory can be partitioned into blocks of size 0 ≤ B ≤ M , we do notstudy a detailed analysis of I/O complexity. In thispaper, we are particularly interested in the case thatthe input size does not fit into the main memory but
not so large, namely, N = O(M 2 ).
3
3.1

Our Algorithm
Outline of the main algorithm

In Fig. 2, we show the outline of our external string
sorting algorithm DistStrSort using an adaptive

Figure 3: A trie
construction of synopsis trie for splitting, which is avariant of distribution sort for integer lists. In Fig. 1
shows the architecture of DistStrSort.
The key of the algorithm is Step 2 that splits the
input list S into buckets S1 , . . . , Sd of at most B bycomputing an ordered partition defined as follows.
For string lists S1 , S2 ∈ (Σ∗ )∗ , S1 precedes S2 , denoted by S1 ≺ S2 , if s1 <lex s2 for every combinationof s1 in S1 and s2 in S2 .
Then, an ordered partition of a string list S is asequence of string lists S1 , . . . , Sd such that(i) the sequence is a partition of S as unordered list,
i.e., S = S1 ⊕ · · · ⊕ Sd ,(ii) Si precedes Si+1 , i.e., Si ¹ Si+1 , for every i =1, . . . , n − 1, andFurthermore, an ordered partition of a string list S
satisfies maximum bucket size B if(iii) |Si | ≤ B holds for every i = 1, . . . , n.
It is easy to see that if we can compute an ordered partition of an input string list S of maximum
size B ≤ M in main memory of size M and if we
can sort bucket of size B in O(B) main memory thenthe algorithm DistStrSort in Fig. 2 correctly solves
the string sorting problem in main memory M (Theorem 7).
However, it is not easy to compute a good partition with maximum block size B using only a limited
main memory for a large input data S that does not
fit into main memory. Hence, we take an approachof computing an approximate answer using adaptive
computation in the following sections.
3.2

A Synopsis Trie

A synopsis trie for a string list S = (s1 , . . . , sK ) ∈(Σ∗ )∗ is the trie data structure T for a subset of prefixes of strings in uniq(S) defined as follows.
A trie for a set S of strings on Σ (Fredkin 1960) isa rooted tree T whose edges are labeled with a letterin Σ. In Fig. 3, we show an example of a trie fora set S = {AN, ART, BAG, BAT, BEAT, BEE, CAT, CAP, CUP}
of strings.
We denote by T the set of vertices of T and byL(T ) ⊆ T the set of its leaves. Each vertex v ∈ T
represents the string str(`) ∈ Σ∗ , called the pathstring, obtained by concatenating the labels on theunique path from the root root to v in T . Let
Str(T ) = { str(`) | ` ∈ L(T ) } be the set of strings
represented by the leaves of T . The vertices of a trie
T are often labeled with some additional information.

Algorithm: BuildDietTrie
Input: A string list S = (s1 , . . . , sK ), a maximum
bucket size M ≥ B ≥ 0, and a growth parameterα > 0.
Output: A synopsis trie Tα,S for S.
1. T := {root};
2. For each i := 1, . . . , K, do the following:(a) Read the next string s = si from the external disk;(b) For each j := 1, . . . , |s|, do:• y := goto(x, s[j]); (Trace the edge cj .)• If y = ⊥ holds, then:− If count(x) ≥ α holds, then:Create a new state y; T := T ∪ {y};count(y) := 1; goto(x, cj ) := y;− Else:break the inner for-loop and goto
the step 2(a);• Else, x := y andcount(y) := count(y) + 1;
3. Return T ;Figure 4: An algorithm for constructing a synopsis
trie
If a trie T satisfies that Str(T ) = S then T is said
to be a trie for S. The trie T for a string list S can beconstructed in O(N ) time and O(N ) space in the total
input size N = ||S|| for constant Σ (Fredkin 1960).
Then, a synopsis trie for S is a trie T for S which
satisfies that for every string s ∈ uniq(S), some leaf
` ∈ T represents a prefix of s, i.e., str(`) v s. Notethat a synopsis trie for S is not unique and the empty
trie T = {root} is a trivial one for any set S.
Given a string list S, a synopsis trie T can store
strings in S. For every leaf ` ∈ L(T ), we define thesublist of strings in S belongs to ` by list(`, S) =( s ∈ S | str(`) v s ) and the count of the vertex bycount(`, S) = |list(`, S)|. The total space required
to implement a trie for S is O(||S||) even if we include
the information on count and list. On the incore
computation by a trie, we have the following lemma.
Lemma 1 We can solve the string sorting, the string
counting, and the string aggregation problems for an
input string list S in O(N ) time using main memoryof size O(N ), where N = ||S||.
We will extensively use this trie data structure in
the following subsections in order to implement thecomputation at Step 1, Step 2, and Step 3 of themain sorting algorithm in Fig. 2.
3.3

STEP1: Adaptive Construction of a Synopsis TrieIn Fig. 4, we show the algorithm BuildDietTrie forconstructing an adaptive synopsis trie.

Although the empty trie T = {root} obviously
satisfies the above condition, it is useless for computing a good ordered partition. Instead, the goalis adaptive construction of a synopsis trie T for S
satisfying the following conditions:(i) T fits into the main memory of size M , i.e.,size(T ) ≤ M .
(ii) For an input string list S, count(`, S) ≤ B for aparameter B ≤ M
The adaptive construction is done as follows.
For an alphabet Σ = {c0 , . . . , cs−1 }, each statev of the automaton is implemented as the list
(goto(v, 0), . . . , goto(v, s − 1)) of s pointers. For analphabet of constant size, this is implemented as anarray of pointers. At the creation of a new statev, these pointers are set to N U LL and a countercount(v) is set to 1.
When we construct a synopsis trie T , the algorithm uses a positive integer α > 0, called the threshold for growing. This threshold represents a minimum
frequency for extending a new state to the current
edge.
The algorithm firstly initializes a trie T as the trie
T = {root} consisting of the root node only. Whenthe algorithm inserts a string s ∈ S into T , it traces
the corresponding edge to w starting from root by
goto pointers. Each state v in the synopsis trie T
has an integer count(v) incremented when a string w
reaches to v. These counters represent approximate
occurrences of suffixes of input strings.
When there are no states the current state v transfers to, the synopsis trie tries to generate a new state.
However, the algorithm does not permit the trie toextend a new edge unless the counter count(v) of v ismore than the given threshold α. If count(v) exceeds
α, the trie generates a new state, and attach it to thecurrent state with a new edge.
Lemma 2 Let S be an input string list of total size
N . The algorithm BuildDietTrie in Fig. 4 computes a synopsis trie for S in O(N ) time and O(|T |)space.
At present, we have no theoretical upper bounds
of |T | and the maximum value of count(`) according
to the value of growth parameter α ≥ 0. Tentatively,
setting α = cB for some constant 0 ≤ c ≤ 1 works
well in practice.
3.4

STEP2: Splitting a String List into Buckets

Let BID = {1, . . . , b} be a set of bucket-id ’s for someb ≥ 0. Then, a bucket-id assignment for T is a mapping β : L(T ) → BID that assigns bucket id’s tothe leaves. Let (T , BID) be a synopsis trie T whose
leaves are labeled with the bucket-id assignment β.
A bucket-id assignment β for T is said to be orderpreserving if it satisfies the following condition: forevery leaves `1 , `2 , if str(`1 ) ≤lex str(`2 ) then β(`1 ) ≤β(`2 ).

Algorithm SplitDietTrie:

Algorithm SortBucket:

Input: A string list S = (s1 , . . . , sK ) (in external
memory), a synopsis trie Tα,S for S (in internal
memory), and a positive integer M ≥ B ≥ 0.

Input: A bucket B ∈ (Σ∗ )∗ .

Output: An ordered partition B1 ⊕ · · · ⊕ Bb for S.

1. Build a trie TB for the bucket B in main memory;

1. //Compute a bucket-id assignment βP0• Let N 0 =`∈L(Tα,S ) count(`); B
0
BN /N ; k = 1; A = 0;

2. Traverse all vertices v of TB in the lexicographic
order of path strings str(v) and output str(v).

=• For each leaf ` ∈ L(Tα,S ) in the lexicographic order of str(`), do:− If (A+count(`) ≤ B 0 ), then bucket(`) :=k and A := A + count(`);− Else, k := k + 1 and A := 0;• b = k;2. //Distribute all strings in S into the corresponding buckets.
• For each k = 1, . . . , b, do: Bi := ∅;• For each string s ∈ S, do:− Find the leaf ` = vertex(s, Tα,S ) reachable from the root by s;− Put s to the k-th bucket Bk in external
memory for k = β(`).
Figure 5: An algorithm SplitDietTrie for splitting
an input string list
By the definition of a synopsis trie above, we knowthat for every string s ∈ uniq(S), there is the uniqueleaf ` ∈ L(T ) such that str(`) v s. We denote
this leaf by vertex(s, T ) = `. Then, the bucketid assigned to s is defined by bucket(T , β, s) =β(vertex(s, T )). Given an input string list S ∈(Σ∗ )∗ , (T , β) defines the partition
P ART (S, T , β) = S1 ⊕ . . . ⊕ Sb
where Sk = ( s ∈ S | bid(T , β, s) = k ) holds forevery bid k ∈ BID. Then, the maximum bucket sizeof (T , BID) on input S is defined by max{ Sk | k =1, . . . , b }. Clearly, S1 ⊕ . . . ⊕ Sb = S holds.
Lemma 3 Ifβisorder-preserving
P ART (S, T , β) is an ordered partition.

then

In Fig. 5, we show an algorithm SplitDietTrie for splitting an input string list S into buckets
P ART (S, T , β) = B1 ⊕ . . . ⊕ Bb . We can easily seethat the bucket-id assignment computed by algorithm
SplitDietTrie is always order-preserving. Furthermore, we have the following lemma.
Lemma 4 Let S be an input list and T be a synopsis
trie with bucket-id assignment for S. Suppose that
|T | ≤ M . Then, the algorithm SplitDietTrie of in
Fig. 5, given S and T , computes an ordered partitionof S in O(N ) time and O(|T |) space in main memory,where N = ||S||.
We have the following lemma on the accuracy of
the approximation.

Output: A bucket Ci ∈ (Σ∗ )∗ obtained from B by
sorted in ≤lex .

Figure 6: An algorithm SortBucket for sorting
each bucket
Lemma 5 Let B 0 ≥ 0 (0 ≤ B 0 ≤ M ) and k ≥ 1 beany integers. Let T be the synopsis trie for S. If thetrie T on S satisfies 0 ≤ count(v) ≤ k1 B 0 for any
vertex ` ∈ L(T ), then the resulting ordered partition
S = B1 ⊕ · · · ⊕ Bb (b ≥ 0) satisfies that k−1
k B ≤ Bi ≤B holds for any bucket Bi (1 ≤ i ≤ m).
3.5

STEP3: Internal Sorting of Buckets

Once an input string list S of total size N has been
split into an ordered partition S1 ⊕ . . . ⊕ Sb = S
of maximum bucket size B ≤ M , we can sort eachbucket Bi in main memory by using any internal
memory sorting algorithm. For this purpose, we use
a internal trie sort which is described in Fig. 6.
Lemma 6 The algorithm SortBucket of Fig. 6
sorts a bucket B of strings in O(N ) time using main
memory of size O(N ), where N = ||B|| and Σ is aconstant alphabet.
3.6

STEP4: Final concatenation

Step 4 is just a concatenation of already sorted buckets B1 , . . . , Bb . Therefore, this step requires no extra
cost.
3.7

Analysis of the algorithm

In this subsection, we give a case analysis of a practical performance of the proposed external sorting algorithm assuming a practical situations for such analgorithm. For the purpose, we suppose the following
condition:
Condition 1 the synopsis trie computed by BuildDietTrie and SplitDietTrie on the input string
list S and the choice of a growth parameter α satisfies the following conditions:• The synopsis trie fits into main memory, that is,size(T ) ≤ M .
• The maximum bucket size of the ordered partition
computed by SplitDietTrie at Step 2 does notexceed M .
For the above condition to hold, we know that atleast the input S satisfies that N = O(M 2 ). Notethat at this time, we only have a heuristic algorithmTable 1: Parameters of the datasets

30

for computing a good synopsis trie without any theoretical guarantee for its performance. Finally, we
have the following result.

25
20
15
10
5

From Theorem 7 and Lemma 1, we can show thefollowing corollary using modified version of DistStrSort algorithm.

0,
10

00
,1

00
00 ]
,10
0
[1
0. ]
10
[5 00]
0,
1[1 000
00
]
,10
0
[2
00 0]
,1
[1 0000,
10 ][5 0000,
1 ][1 00000
0,1 ][2 000
00
0
,10 ]
00
0]
[2

0]

0

[1

Theorem 7 Suppose that the algorithms BuildDietTrie and SplitDietTrie satisfy Condition 1 on
the input S and α ≥ 0. The algorithm DistStrSort
correctly solves the external string sorting problem inO(N ) time within main memory M using 3N sequential read (Step 1–Step 3), N random write (Step 2),
and N sequential write (Step 3) in the external memory.

SplitDietTrie
BuildDietTrie

35

0]

1.1GB
2290×104
109×104
44.9
19.7
58
15

0,
10

data B

67MB
140×104
22×104
45.0
45.1
58
15

[5

data A[1

File size
Number of records (with duplications)
Number of records (no duplications)Average of record length
Variance of record length
Maximum record length
Minimum record length

Runtime (sec)

DatasetTable 2: Sizes of the constructed synopsis tries
Growth parameter α
100
1,000 10,000
Number of states
426,209 92,768
5,030[Number of buckets, Threshold for growing]

Figure 7: Running time of BuildDietTrie andSplitDietTrie

4.2

Running Time

4.2.1

BuildDietTrie and SplitDietTrie

Corollary 8 Let (∆, ◦) be any associative binary operator, where operation ◦ can be computed in O(1)time. Suppose that the algorithms BuildDietTrie
and SplitDietTrie satisfy Condition 1 on the input
S and α ≥ 0. There exists an algorithm that solves
the string counting (STR-COUNT), and the string
aggregation problems (STR-AGGREGATE(∆, ◦)) for
an input string list S in O(N ) time using main memory of size M in external memory.

Next, we measured the running times of the subprocedures BuildDietTrie and SplitDietTrie on thedata A, by varying the number of buckets and thegrowth parameter. Fig. 7 show the results. The horizontal axis in the figure represents pairs of the numberof buckets and the growth parameter. The verticalaxis represents the running time.
The results indicate that the running time isshorter for larger growth parameters. Thus, a smallersynopsis trie can be constructed in a reasonable computational time.

4

4.2.2

Experimental Results

DistStrSort

In this section, we present experimental results onreal datasets to evaluate the performance of our algorithms. We implemented our algorithms in C. The
experiments were run on a PC (Xeon 3.6GHz, Windows XP) with 3.25 gigabytes of main memory.
We prepared two datasets data A and data B consisting of cookie values from Web access logs. The
parameters of the datasets are shown in Table 1.

Finally, we studied the running time of the algorithm
DistStrSort. Fig. 8 shows the running times on thedata B of DistStrSort and the GNU sort 5.97. The
running time of our algorithm scales linearly with thesize of data and is faster than the GNU sort for larger
data sizes.

4.1

In this paper, we presented a new algorithm for sorting large collections of strings in external memory.
The main idea of our method is first splitting a set of
strings to some buckets by adaptive construction ofa synopsis trie for input strings, then sort the stringsin each bucket, and finally merge the sorted buckets into an output collection. Experiments on real
datasets show the effectiveness of our algorithm.
In this paper, we only made empirical studies on
the performance of adaptive strategy for constructionof a synopsis trie for data splitting. The probabilistic
analysis of the upper bounds of |T | and the maximum

Size of Synopsis TrieFirst, we studied sizes of synopsis tries constructed by
the algorithm BuildDietTrie by varying the growthparameter α = 100, 1000, or 10000. Table 2 shows thenumber of states of the constructed synopsis trie foreach α on the data A. We can see that the bigger α is,the smaller the size of the constructed synopsis trie
becomes.

5

Conclusion

rithm, Proc. the 10th European Symposium on
Algorithms (ESA’02), 698-710, 2002.
A. Moffat, Implementing the PPM data compression
scheme, IEEE Trans Communications COM38(11): 1917–1921, 1990.

900

データを1GB（約2270万レコード）に増やして、前と同様のDistStrSort
実験環境で、GNU sort と計算時間を比較した。

800

Runtime（sec）

700

GNU sort

R. Ramakrishnan, J. Gehrke, Database Management
Systems, McGraw-Hill Professional, 2000.

600
500
400

D. Ron, Y. Singer, and N. Tishby, The power of amnesia: learning probabilistic automata with variable memory length, Machine Learning, 25(2-3):
117– 149, 1996.

300
200
100
0
0

5000000

10000000

15000000

20000000

25000000
15

Number of strings

Figure 8: Running times of DistStrSort and GNU
sortvalue of count(`) concerning to the value of growthparameter α ≥ 0 is an interesting future research.
We considered only the case that the input size
is at most the square of the memory size, and thenpresented a two-level external sorting algorithm. It isa future research to develop a hierarchical version of
our algorithm for inputs of unbounded size. A streambased distributed version of distribution string sortalgorithms is another possible direction.
References
S.

Abiteboul, R. Agrawal, P. A. Bernstein,
M. J. Carey, S. Ceri, W. B. Croft, D. J. DeWitt, et al., The Lowell database research selfassessment, C. ACM, 48(5), 111–118, 2005.

S. Abiteboul, P. Buneman, D. Suciu, Data on theWeb, Morgan Kaufmann, 2000.
L. Arge, P. Ferragina, R. Grossi, and J. S. Vitter, On
Sorting Strings in External Memory, Proc. the29th Annual ACM Symposium on Theory ofComputing (STOC’97), 540–548, 1997.
J. Bentley, R. Sedgewick, Fast Algorithms for Sorting and Searching Strings, Proc. the 8th Annual
ACM-SIAM Symposium on Discrete Algorithms(SODA’97), 360–369, 1997.
P. Ferragina, R. Grossi, The String B-tree: A New
Data Structure for String Search in External
Memory and Its Applications, J. ACM, 46(2),236–280, 1999.
E. Fredkin, Trie Memory, C. ACM, 3(9), 490–499,
1960.
P. Laird and R. Saul, Discrete sequence prediction
and its applications, Machine Learning, 15(1):43–68, 1994.
U. Manber, E. W. Myers, Suffix Arrays: A New
Method for On-Line String Searches, SIAM J.
Comput., 22(5), 935–948, 1993.
G. Manzini and P. Ferragina,
Engineering a
Lightweight Suffix Array Construction Algo-

K. Sadakane A Fast Algorithms for Making Suffix Arrays and for Burrows-Wheeler Transformation, Proc. the 8th Data Compression Conference (DCC’98), 129–138, 1999.
R. Sinha, J. Zobel,
Efficient Trie-Based Sorting of Large Sets of Strings,
Proc. the26th Australasian Computer Science Conference(ACSC’03), 2003.
M. Stonebraker, U. Cetintemel, ”One Size Fits All”:
An Idea Whose Time Has Come and Gone,
Proc. the IEEE 21st International Conferenceon Data Engineering (ICDE’05), keynote, 2–11,
2005.