NTCIR-2 Experiments Using Long Gram Based Indices
Takashi SATO Nao HATTA Koji HIRAIWA
Kihei KOBATA Akihiro FURUSHO Koto HAN
Osaka Kyoiku University
4–698–1 Asahigaoka, Kashiwara, Osaka, Japansato@cc.osaka-kyoiku.ac.jp

Abstract
Long gram based indices are experimented at
NTCIR-2. In making gram based indices, no analyses such as morphological ones are required. The
accessing number, titles, abstracts and keywords are
extracted from NTCIR-2 documents. The total index
size is 1.43Gbyte and time to make indices is about
100 minutes. Average retrieval time per topic takes 21
seconds since documents are ranked in a Perl program
which is simple and not fast. Ranking algorithm used
is based on a traditional probabilistic model, and theresult is standard average precision.
Keywords: long gram based index, gram coding, NTCIR.

1

Introduction

The use of Web pages, on-line documents, electronic books, newspapers, and so on, which we canretrieve directly from the internet using computers, isincreasing more and more these days. In order to makethe best use of the potential information which theseon-line texts contain, we need the means to access objective information efficiently. In particular, we shouldbe able to access arbitrary strings in the text at highspeed. Retrievals of fixed keywords, which are prepared in advance, is not sufficient to support retrievalsfrom such diverse sources.
When we retrieve text by uni-string, the output isoften too large. So we have to squeeze the result
by successive retrievals and strings which relate to a
retrieved string may be added. Also, some retrieval
systems can adjust queries interactively based on retrieved results. In this way, many retrieval results haveto be combined organically in order to serve the user’s
purpose. Therefore, string retrieval engines should befast.
To realize fast retrieval from a large text, indices
are indispensable. Indices based on sistring are dedicated to fast string retrieval[1, 2, 3, 4, 5]. Suffix array (orPAT array), which is made from sistrings, is often used

for string search, however, it is very inefficient whentext size exceeds main memory size. Recently, n-grambased indices have drawn attention since they have low
construction cost and do not require intensive processing such as bit operations[6, 7, 8, 9, 10] .
Not only speed but also size is an important element of indices. Since oriental languages, including Japanese, have a large alphabet, it is often remarked that indices tend to become very large in thesecases[6, 10]. Conversely, if we reduce the index size,
many false drops occur. Consequently, an index structure which allows both low space overhead and a low
false drop rate is required.
To meet the above requirements, we have been
studying n-gram based indices which differ from standard n-gram indices in the following ways[11, 12, 13] .
[long gram] Usually, strings shorter than the gramare not retrievable[6, 7, 8, 9, 10] . If we want to use a 3gram index for example, we have to prepare not only
a 3-gram but also a uni and a 2-gram index. Fromthe space cost viewpoint, we can not use a large gramindex. However, by turning the index into a tree structure, we have seen that shorter grams may be retrievedby sequential scan of leaves so that indices for shorter
grams become unnecessary.
[no position] Usually, occurrences of a gram arerecorded in terms of a document number and an offset (called position) and the index manages such pairsof data[6, 7, 8, 9, 10] . If a set of grams, which are madefrom decomposition of a retrieve key, are found in adocument, the result is a false drop if the grams are
not adjacent in the document. So position is necessary
to examine the adjacency of grams. However, we will
not store position. This is because, (1)By using longgrams, the key often fits inside a gram. We are guaranteed no false drop in these cases. (2)Even if the key islong and divided into grams, false drops seldom occur,
because candidate documents are sufficiently limitedby the high selectivity of long grams. (3)If necessary,
one can determine whether or not the result is a false
drop by accessing the original text.
[gram coding] Usually, a gram is made from simple concatenation of characters which compose thegram[7, 10] . Or some hashing is applied to the gramwith some parameters such as frequency[6, 8]. However, hashing causes false drops because of collisions
among hashed values. We will code the gram so as tomake the index compact and a good filter with no false
drop. We avoid intensive processing such as bit operations while searching an index. Once a gram or a setof grams is made from the key, searches of an index
are processed efficiently by word or byte sized units.
We experimented our long gram based indices at
NTCIR-2. Since our indices are based on grams,
no analyses such as morphological ones are required.
However, we used NTCIR-2 segmented topic data inorder to search words and compound words. We madeindices from titles, abstracts and keywords of NTCIR2 documents. The total index size is 1.43Gbyte andtime to make indices is about 100 minutes. Average
retrieval time per topic takes 21 seconds since documents are ranked in a Perl program which is simple
and not fast. Ranking algorithm used is based on a traditional probabilistic model, and the result is standard
average precision.

2

Definitions

The alphabet is denoted by . (= jj) denotes
the size of the alphabet. Although any set of symbols
can be an alphabet, we used Japanese EUC two bytecharacters ( = 8836) in our experiments. A text retrieved is a collection of m documents. The number ofcharacters in the i-th document is ni (1  i  m). Themsize of the whole text is n(= i=1 ni ), which is considered too large to be put in main memory. Instead it
is put in secondary memory.
We extract strings called grams which start at every character from all documents, code and sort them,and then make an index. The index is also put in secondary memory. Although the number of characterswhich constitute a gram is not constant, coded grams(called gram values) are fixed length wg [byte] in order to make retrieval fast. Since the index is put insecondary memory, pointers in it are offsets from thehead of the file. The size of the pointers is wp[byte].
The result of retrieval is a set of document numbers.
Document numbers can be represented in wd [byte].
A string sought is a key k. A key is composed ofcharacters in  and coded in the same method as gramsare. The size of a coded key is lk [bit].
Since the text and index are put in secondary memory, we have to transfer data between main and secondary memory while processing. Data are transferredin blocks of size B [byte].

P

3

Gram Based Index with Tree Structure

We propose an index which consists of a root, a leaf
and a locator(see Fig.1). The elements of a leaf areslots. Slots contain a pair consisting of a gram value
and a pointer. The pointer points to a bucket in the locator. Each bucket has document numbers in it. The
bucket, which is pointed to by a slot, stores the document numbers where the string corresponding to thegram value in the slot is found.
root

in main memory

tree structure
gram code

leaf
pointerbuckets

locator

.....

text

.....

....

Figure 1. Gram Based Index Structure
As a leaf of a B–tree[14] stores not only keys but also
pointers, we can fill a leaf with not only gram values
but also document numbers.
However, we separate them to avoid unnecessary
reading of document numbers when we are searchingfor a gram value in the leaf. We can also avoid uncompressing unnecessary document numbers in the case of
a compressed index.
The root stores the gram values of regularly spaced
slots of the leaf in order to guarantee only one block
access to any required slot. The root is compact andcan be put into the work space of the main memory
provided the retrieved text is smaller than a few dozens
of gigabytes. If we can not fit the whole root in main
memory, we can make it into a multi-leveled structure,i.e. a tree.
3.1

Space Cost

The size of a slot in the leaf is wg + wp [byte]. The
number of grams made is n, since we make grams
starting at every character of all documents. However,
we do not save the same gram values repeatedly into
the leaf. We call this removal of redundancies unification with associated ratio us(0 < us  1). The
gram values in slots of the leaf are arranged in ascending order. The pointers in slots are also in ascending order since buckets of the locator are concatenated in the order of the corresponding gram values. We can compress ordered number sequences
by run-length encoding[16] with a compression ratios . Therefore, we estimate the size of the leaf to bes usn(wg + wp )[byte].
As for the locator, since we do not repeatedly savethe document number when a gram value occurs morethan once in a document, the locator is unified in theratio of ud . Since the occurrence of gram values ina document is less frequent than in the whole text,
0 < us  ud  1. Again, since the document numbers are in ascending order in a bucket, we can compress the leaf in the ratio of d using run-length encoding. Thus we estimate the size of the locator to bed ud nwd [byte].
Although we can compress the root by run-length
encoding, we ignore its space cost because the root is
far smaller than the leaf.
From the above, we estimate the total space cost tobenf sus (wg + wp ) + d ud wd g [byte]:
3.2

(1)

X

X M w =Be:d (wg + wP )=B e + d
i

i d

i

(5)

Pi means summation over all grams which have the

key as prefix. Mi is the number of matches for the i-thmatching gram.
[C] lk is coded longer than wg

X 1 + XdM w =Be:
j

j

j d

(6)

P means summation over all grams which are subj
strings of the key. Mj is the number of matches forj -th component gram.

Construction Cost

We estimate the construction cost as the number ofblock accesses required to make an index. First we
make batches, which are pairs of a gram value and adocument number, and put these in the work space ofthe main memory. Then we merge these batches tomake an index[15]. Each batch is also sorted, unified
and coded by run-length encoding.
We first estimate the cost to make the batches.
2n=B blocks are accessed in order to read the whole
text assuming 1 character is 2 bytes. After each batchis made in main memory, it is stored in secondary
memory batch by batch. Although a batch has no root
since it is not used for retrieval, the leaf and locator
have the same structure as in the index. We estimate
the cost to make the index as

nf 0su0s (wg + wp ) + d ud wd g=B;(2)
where 0s and u0s (0 < s  0s  1, 0 < us  u0s 1) are respectively the batch’s unification ratio and its
compression ratio due to run-length encoding.
The cost to merge batches is the sum of the costto read batches (equation (1)/B) and to write an index(equation (2)).
From the above, we estimate the total construction
cost to benf2+( sus +2 0su0s )(wg +wp )+3 d ud wd g=B:(3)3.3[B] lk is coded shorter than wg

Retrieval Cost

The retrieval algorithm and space cost for a tree
structured index are described in detail in [12]. We
rewrite the equations for retrieval cost found in that
paper using the symbols defined in Section 2.
[A] lk just fits in wg

1 + dMwd =B e;(4)where M is the number of matches for the retrieval
key.

4

Gram Coding
wg
Ci

Ci+1

Ci+2

Ci+1

Ci+2

Ci+3 Ci+4

Ci+2

Ci+3 Ci+4

Ci+3 Ci+4

Ci+4 Ci+5

Ci+3

Ci+5

Ci+5

Ci+5

Ci+6

Figure 2. Example of Gram Coding. (Shadowed portions are filled with bit 0)

A character which appears very often is not effective as a filter. Therefore, we will give it a short length
for gram coding in order to put more characters in agram. Conversely, since a rare character is a very effective filter, we give it a longer length. Since we codegrams of a fixed length for fast retrieval, the numberof characters in a gram is variable. For an equal lengthof gram value wg , the proposed method will lower the
chance of false drops compared with earlier methods.
Conversely, if we allow the same false drop rate, we
can choose a smaller wg . That is, we expect that we
can make a more compact index with no false drop retrieval in practice. Figure 2 shows an example of gramcoding for a string of ci ci+1 ci+2 ci+3ci+4 ci+5 ci+6 .
The space, construction and retrieval cost is thesame as in Section 3. However, notice that us ; ud; sand d change depending on the coding.

5Models and Analysis

In order to estimate the false drop rate of retrievalswith an index whose grams are coded in the manner ofSection 4, we analyze selectivity using a model.
5.1

Models for Characters and Strings

We assume no correlations among characters in the
text and in the key. We make a coding table for eachcharacter in the alphabet. The Huffman code[17] isused to code characters with reference to their frequency of appearance in the text. We assume this coding can be done nearly optimally, i.e. we can code acharacter ci , whose appearance ratio is p(ci )( 1), in
log2 p(ci)[bit].
The average code length of all the characters in the
text is represented by lc = log2 p(ci )[bit]. Then the
average selectivity per character becomes 1=2lc which
is nearly equal to 1= by assumption, i.e. lc ' log2 .
5.2

Using the index, we get document numbers as retrieval results. Since we do not store the starting positions of grams in a document, those documents whichcontain not only (0)c1c2 c3c4 c5 but also (1-1)c1c2c3+ c2 c3c4 c5 , (1-2)c1c2 c3 c4 + c3c4 c5 or (2)c1c2 c3 +c2 c3 c4 + c3 c4c5 are retrieved2. Needless to say, thecases (1-1),(1-2) and (2) are false drops. (1-1) and(1-2) are strings which we can make from the key
by dividing at one point. Similarly case (2) is madeby dividing the key at two points. The selectivities
are (0)1=25lc , (1-1)(1-2)1=2 7lc , and (2)1=29lc respectively.
In general, the selectivity when the key really is in
the text is (0)1=2nklc . The selectivity when the key
is divided at one point is (1)1=2nklc  1=2(ng 1)lc
and there are nk ng C1 such cases. The selectivity
when the key is divided at i( nkng ) points is(i)1=2nklc  1=2i(ng 1)lc and there are nk ng Ci cases.
Consequently, the total selectivity is the sum of theabove.

1=2nklc Analysis

Selectivity of Grams

A gram is 8wg [bit] long. However, the effective bits
are reduced to 8wg lc =2 because lc =2 is a fraction
when we pad characters coded with length lc . Letlg [bit] denote this effective gram length. Since we assume there are no correlations among characters, theselectivity of a gram becomes
1=2lg :
(7)
5.2.2

Selectivity of the Key[A] lk  lg
Since the coded key can fit inside a gram, the selectivity does not depend on lg . It is estimated directlyfrom lk .
1=2lk :
(8)
There are no false drops in this case.
[B] lk > lg
nk = lk =lc characters are coded in a key, andng = lg =lc characters are coded in a gram on average.
Therefore, a key is divided into nk ng + 1 grams
on average. We retrieve all grams and compute the set
product of all the document number sets so obtained.
For example, we will explain the case when nk = 5
and ng = 31 . If k = c1c2 c3c4 c5 , a set of grams becomes fc1 c2c3 ; c2c3c4 ; c3c4 c5g. To simplify the analysis, we assume c1 ; c2; c3; c4; and c5 are different fromone another.
1 We intentionally use a small

ng to simplify the analysis.

nk ng Ci=2i(ng 1)lc

i=0n= 1=2 klc  f1 + 1=2(ng 1)lc gnk ng : (9)To simplify the analysis, we use an average code
length of lc for coded characters.
5.2.1

X

nk ng

We have applied the binomial theorem to the summation. Except for the case (0), these are false drops, andtheir probability is

1=2nklc  f(1 + 1=2(ng 1)lc )nk ng 1g: (10)Therefore, if the above equation ni is far smaller
than 1 for 1  i  m, false drops are negligible inpractice in our model.
5.3

Limitations of Models

In Section 5.1, in order to simplify the analysis,
we assumed that there was no correlation between thecharacters in the text and those in the key. However,in practice there is correlation among these characters. Therefore, the analytical results do not necessarily reflect real key searches quantitatively. However, based on the analysis we know qualitatively how
key and gram length influence the selectivity and thefalse drop rate. As mentioned before, the code given
to each character is determined by its frequency of appearance. The higher the frequency, the shorter thelength of the code assigned. Since punctuation characters such as space, period, comma etc. have weakcorrelation with the strings which precede and follow
them, we know that longer codes are appropriate forthese characters.
2 Strings connected by ‘+’ are found separately in the same document.

6

Experimental Results

References

The computer used is COMPAQ DS-20(CPU: Alpha 21264 500MHz, Main Memory: 4Gbyte andHard Disks: 8msec average seek time, and 3 msec
average latency time). We got a target text by
concatenating the files named ntc2-j0g and ntc2-j0k
of NACSIS Test Collection 2(NTCIR-2). We extracted Accessing Number(ACCN), Title(TTL), Abstract(ABST) and Keywards(KYWD) from a target
text. We made two n-gram based indices, one from
TTL and the other is from ABST and KYWD. The sizeof indices are 95Mbyte and 1,329Mbyte respectively.
The time to make indices are 266sec and 4,811sec respectively, 85min in total. We set wg = 6. Table 1
shows the distributions of the number of characters inevery gram for two indices. ACCN was put on a sepTable 1. Distributin of the number of characters in every gram (106)
TTL
ABST & KYWD

2
1.0
1.5

3
1.2
14.0

4
6.8
121

5
10.6
205

6
0.47
17.8

arated file and used as a translation table from document numbers which are counted from the top of atarget text. Its size is 7Mbyte. Then the total size for
retrieval is 1,431Mbyte. Including extraction step, thetotal time to make indices is about 100min.
We made queries from given topic files (topic-j101150 and topic-w101-150). Keys for indices search
are words in Description and Concept field of theabove files. Using topic-w101-150 in which compound words are segmented in words, every possiblecombinations of words are made of a compound word.
We search keys from Description by using TTL
index, and keys from Concept by ABST-KYWD index. Then we ranked documents, which are retrievedby search keys for each topic, using probabilistic
model[18] written in a Perl program. Processing timeto search keys and to rank documents for all 49 topics
is 1,034sec, then the average is 21sec.

7

Conclusions

We experimented our long gram based indices at
NTCIR-2. Since our indices are based on grams,
no analyses such as morphological ones are required.
However, we used NTCIR-2 segmented topic data inorder to search words and compound words. We madeindices from titles, abstracts and keywords of NTCIR2 documents. The total index size is 1.43Gbyte andtime to make indices is about 100 minutes. Average retrieval time per topic takes 21 seconds. Ranking algorithm used is based on a traditional probability model,
and the result is standard average precision.

[1] Gonnet, G., Baeza-Yates, R. and Snider, T., New Indices for Text: Pat Trees, in Information Retrieval:
Data Structure & Algorithms chapter 5, Frakes, W. andBaeza-Yates, R. Ed., pp. 66–82 (1992).
[2] Shang, H. and Merrett T., Trees for approximate string
matching, IEEE Trans. Knowledge and Data Eng.,
Vol. 8, No. 4, pp. 540–547 (1996).
[3] Itoh, M., An Efficient Method for Constructing Suffix
Arrays of Large Texts, IPS Japan SIG Notes, 99-NL129-5 (1999).
[4] Yamashita, T., Fujio M. and Matsumoto Y., Language
Independent Tools for Natural Language, Proc. 18th
ICCPOL, pp.237–240 (1999).
[5] Ferragina, P. and Grossi, R., Fast string searchingin secondary storage: Theoretical developments andexperimental results, Proc. ACM-SIAM Symposia on
Discrete Algorithms, Vol. 7, pp. 373–382 (1996).
[6] Ogawa, Y. and Iwasaki, M., A new character-based indexing method using frequency data for Japanese documents, In Proc. 18th ACM SIGIR Conf., pp. 121–129(1995).
[7] Sugaya, N. et al., A full-text search system for large
Japanese text bases using n-gram indexing method,
Proc. 53th Annual Convention IPS Japan, 5T–2,3(1996).
[8] Akamine, S. and Fukushima, T., Flexible string inversion method for high-speed full-text search, Proc. Advanced Database Symposium ’96 (1996).
[9] Matsui K., Namba, I. and Igata, N., Full-text searchingengine for large-scale data, Proc. 1997 IEICE General
Conference, D–4–6 (1997).
[10] Kikuchi, C., A fast full-text search method forJapanese test database, Trans. IEICE, Vol. J75-D-1,
No. 9, pp. 836–846 (1992).
[11] Sato, T., Fast full test search with free word using TS–
file, Proc. 19th ACM SIGIR Conf., p. 342 (1996).
[12] Sato, T., Fast full test retrieval using gram based tree
structure, Proc. ICCPOL ’97, Vol. 2, pp. 572–577(1997).
[13] Sato, T. et al., Gram based full test search system
and its application, IPSJ SIG Notes, 98–DBS–114–2(1998).
[14] Knuth, D.: The Art of Computer Programming: Vol.3
Sorting and Searching, 2nd Ed., Addison-Wesley,
Reading, Mass., pp. 481–489 (1998).
[15] Noda, J., Endoh, A. and Sato, T., Creation and updateof indices for a n-gram based fill text retrieval system,
Proc. IEICE DEWS’98 (1998).
[16] Zobel, J., Moffat, A. and Sacks-Davis, R., An efficientindexing technique for full-text database, Proc. 18th
Int. Conf. on VLDB, 1992, pp. 352–362.
[17] Huffman, D.A., A method for the construction ofminimum-redundancy codes, Proc. IRE, Vol. 40, pp.
1098–1101 (1952).
[18] Robertson, S.E. and Walker, S., Some simple effective
approximations to the 2-Poisson model for probabilistic weighted retrieval, Proc. 17th Int. Conf. Researchand Development in Information Retrieval, pp. 232–
241 (1994).