DEIM Forum 2016 D4-1

Efficient Autocompletion with Error tolerance
Sheng HU†

Chuan XIAO‡

andYoshiharu ISHIKAWA††Graduate School of Information Science, Nagoya University, Furo-cho, Chikusa-ku, Nagoya, 466-8601 Japan‡Institute for Advanced Research, Nagoya University, Furo-cho, Chikusa-ku, Nagoya, 466-8601 Japan
E-mail: †hu@db.ss.is.nagoya-u.ac.jp,‡{chuanx, y-ishikawa}@nagoya-u.ac.jp

Abstract Most popular search engines have provided query autocompletion features in their systems. When a user issues aquery, without inputting complete keywords, the search engine will prompt several options which complete the remaining partof the query automatically. This research will focus on investigating novel techniques for error-tolerant query autocompletionby addressing several key issues of this feature, and eventually improve the efficiency and the accuracy of the query processing.
In our work, we proposed an improve expansion algorithm based on current state-of-the-art work. Moreover, we also improve
the index reduction method to reduce the index size as much as possible. Experiment results show that our new method canimprove the algorithm efficiency and reduce the index size very well.
Keyword Query Autocompletion，Query Processing，Textual Database

1. Introduction
Recently, the user experience of search engine becomes

2. Related Work
There are various ways to implement the autocomple-

more and more important. Most popular search enginestion technique[1][6]. Currently, trie index[2] becomes

have provided query autocompletion features in their sys-

very popular and is adopted as the most efficient way

tems. When a user issues a query, without inputting com-among the current research works. The ICPAN algorithm

plete keywords, the search engine will prompt several op-

put forward by Guoliang Li[3] is considered the most re-tions which complete the remaining part of the query au-

liable trie traversal algorithm while IncNGTrie which istomatically.

put forward by Chuan Xiao[4] is considered the most ef-

Moreover, search engines like Google, hav e equipped

ficient trie traversal algorithm. The ICPAN [3] gives atheir system with an advanced autocompletion technique,definition about the Pivotal Active Node which is seemedwhich is called autocompletion with error tolerance. Evenas the basic composition unit of the trie index and cana user issues an uncompleted query which may containsupport 2-length characters error tolerance which means

typos, the search engine can still identify the intended

the search system can give the correct answer despite ofquery and give the correct answers. As more and more

two characters typos. The IncNGTrie[4] uses the Neighborusers are using smartphones as search engine interface,

Generation method[5] so as to include the possibility ofthis feature is considered of great importance and pro-typos in advance. In the experiment, it can support

spective.

3-length characters error and achieves up to two orders ofThis research will focus on investigating novel tech-magnitude speedup over Li’s ICPAN method. However,niques for error-tolerant query autocompletion by ad-

IncNGTrie achieves the efficiency at the price of sacri-dressing several key issues of this feature, e.g., improving

ficing large memory space, and under the special circum-

the efficiency and the accuracy of query processing. Fig-

stances the overhead of the space may be unaffordable.

ure.1 shows an example of the result of autocompletion
with inputting “coff”.

Figure 2. An example of IncNGTrie with keyword
Figure 1. An example of autocompletion of “coff”{test, text} with τ=1

Example 2 Figure 2. shows a simple example of IncNTrie

prune all the path which contain ‘#’ in the subtree from

Index Structure which consists of two strings t1 and t2. T1

current node.

represents “test” and t2 represents “text”. Single path from

Example 3 Figure 3, Figure 4, Figure 5 give an example

the root to one leaf represent s one string. For example,of the trie variation under the condition when we increase

from left side, we have Φ-t-e-s-t path, which represents

BRC from 1 to 3 consecutively. If we set the BRC param-string “test”. Meanwhile we use ‘#’ as the placeholder toeter to 1, the leaf nodes’ parent node will be merged whenrepresent the deletion conducted on the data string side.

the descendant identical data string number less equal s

Below we give the definition of ‘#’.

than 1. Numbers in the bracket represent the amount of theDefinition 1 (Placeholder ‘#’) We use ‘#’ to create moredescendant identical data string under each node. As

deletion-marked variant[7,8], that is, ‘#’ means at thisshowed in Figure 3, note that in the left subtree under theposition one character is deleted from a data string. E.g.,

node “a”, as all the descendants under “a” only represent“ts”, a 2-variant of “test”, will be represented as “t#s#”.

the same string “t3”, all the paths start from “a” and con-Meanwhile, we will generate all the 1-variant of “test”,

tain “#” will be removed from the index. In Figure 3, we

which is {#est, t#st, te#t, tes#}. And finally use thesechange the nodes’ color into grey i f they are removed. Invariants to construct the trie as Figure 2. shows. Moreover,Figure 4 and Figure 5, we increase BRC to 2 and 3, as thewe use τ as the threshold to limit the error -tolerant ability

nodes satisfying our reduction condition increase quite aof this index.

lot, we can find the index size will be reduced incrementally. Especially when BRC=3, we successfully prune al-3. Index reduction
As IncNGTrie has the shortcoming of space cost, I began my work from reducing the space of IncNGTrie, I also
propose a new expansion algorithm of the trie traversal
algorithm to improve the traversal efficiency. After that,I’m doing the work of result ranking to improve the quality of results as much as possible.
In IncNGTrie research, they used two techniques to reduce the index size as much as possible, so as to make itmost a half part in our example. In our experiment, thischange will reduce the size of our tree drastically when τis larger than 1 and decrease a little bit on the search timeside because this is an inevitable tradeoff between thestorage and efficiency. Moreover, I change the underlying
data storage to make all the identical data point to just one
copy instead of store a copy for every redundant record.
The parameter we introduce could be adjusted accordin gto the requirement of the real environment.

fit the computer memory. One is Common Data String
Merge, the other is Common Subtree Merge. After myexperiments, I found some disadvantages of these twotechniques. For the former one, this work simply does thereduction exhaustedly without any consideration of the
reduction extent parameterization. Thus I come up with
the idea that I can introduce the parameter p to control thereduction extent. In the original work, this parameter is set
to 1, that is, only when the parent node share completely

Figure 3. Index of {test, text, taxi} when BRC=1

the identical data strings, it’l l be merge into 1 string,which drastically limits the benefit of the reduction. Andafter I introduce this parameter BRC, we can generally
control the benefit and gain from the common data string
merge technique. Here we give the definition of Branch
Reduction Control.
Definition 2 BRC (Branch Reduction Control)
We use BRC as the parameter to control how much we will
reduce the index size. First we will traverse the whole trie
in a Depth-First order, and check every nodes to see if its
descendants amount is lower than BRC, if so, we will

Figure 4. Index of {test, text, taxi} when BRC=2

Figure 5. Index of {test, text, taxi} when BRC=3

4. Expansion algorithm improvement
To support the active node model proposed in Li’s paper,Xiao’s work used a triplet <node, cursor, incoordination >as the representation of the active node states . This makes
the expansion algorithm much more tedious and it generate too many active nodes states which consume quite a lot
resources of the memory. To fix this problem, I change theactive node representation to <node, incoordination, difference in trailing’#’>, which simplifies the model drastically and generate much less active node states dur ing
the expansion procedure. Our experiment shows thatcompared with the original work, the intermediate active
nodes number is reduced by over 50%. Moreover, I alsochange the BST method to remove the second duplicate
data because the original lemma suppo rting the old method
is not reliable.
To search an index constructed like Figure 2, we needtraverse the trie with the single stroke of query input. In
Li’s work, <node, incoordination> is used to represent the2.

We delete ‘q[v]’ in the query’s variant and mark it
as ‘#’. So we’ll see if current node is still active bychecking incoordination and difference, and then go
through ‘#’ in the trie.

After processing all the query strokes, the final set A isreturned and used to fetch the results.

5. Experimentactive node state because the index constructed is a direct

The experiments were implemented using a PC withtrie. In Xiao’s work, <node, cursor, incoordination> isIntel Core i5 CPU (2.60GHz), 4GB memory, and Windows

used instead because its new index structure IncNGTrie.

7 OS. The dataset was made by extracting the string ofNow we adjust it into <node, incoordination, difference>

POI of the GNIS dataset. This dataset consists of 200400

and give the explanation based on Xiao’s work.

strings and average string length is 11.

In line 1 of Algorithm1, we use ExpandActiveImproved
to initialize the original active states. At this moment,

5.1 Effect of index reduction

there’s no query stroke is input. τ represents the threshold

We first evaluated the effect of our index reductionof error ’s upper bound, we first go through the trie frommethod. Figure 6, Figure 7, Figure 8 corresponds to theroot to most τ #’s and set the corresponding node to active.

situation when τ=1, 2 and 3. The value of τ represents theAnd then from line 2, we can see user will input a query

error-length, that is, how many errors the query can con-stroke q[v], with the new stroke, algorithm will expand

tain at most. Y-axis represents the amount of data strings

new active states based on original ones. Line 4 to line 9and index nodes. Here, we use data size to represent theshows the method. When a query stroke q[v] comes, fordata strings amount. Because we merge the subtree’s nodeeach active state <node, incoordination, difference>, weand its leaf nodes, some identical data strings we store in

do two steps:

the memory will be merged into one. Then, we use index

1.

We keep ‘q[v]’ in the query’s variant, so we’ll gosize to represent the index nodes amount. From the ex-through ‘q[v]’, and then go through ‘#’ in the trie.

periments, we can see that when BRC variates from 0 to 1,
both data size and index size is reduced by almost 30%,

and the larger tau is, the more the total size is reduced.

creases, the improved expansion algorithm has much less

When BRC is increased to 9999999, the whole IncNGTrieactive states, which can remarkably save the memory andis degenerated to a direct trie, which has a very small size.

improve the time efficiency compared with the old algo-3000000

data size

2000000

index size

rithm. When query length equals 8, the improved algorithm’s active nodes states number is almost a half of theold one, which means our method reduce over 50% active
node states when quer y is long enough.

1000000

old0

improved

300

BRC

200

Figure 6. Data size and index size reduction effect100

when τ=10
data size

10000000

index size

5000000
Figure 10. Returned active nodes amount when τ=20

BRC
Figure 7. Data size and index size reduction effectwhen τ=225000000

oldimproved

data size

20000000

index size

15000000
10000000

Figure 11. Returned active nodes amount when τ=35000000

References

0BRC
Figure 8. Data size and index size reduction effectwhen τ=35.2 Effect of expansion improvement
3020001500
1000
5000oldimproved

20100Figure 9. Returned active nodes amount when τ=1
The three figures Figure 9, Figure 10, Figure 11 show
the expansion improvement effect under the condition τ=1,2 and 3 . X-axis represents the query length and Y-axis
represents the active node states amount. The common
point of the three is that, as the length of query word in-[1] L. Boytsov. Indexing methods for approximate dictionary searching: Comparative analysis. ACM Journal of Experimental Algorithmics, 16(1), 2011.
[2] D. Deng, G. Li, and J. Feng. An efficient trie -based
method for approximate entity extraction with edit-distance constraints. In ICDE, pages 762 -773,2012.
[3] G. Li, S. Ji, C. Li, J. Feng. Efficient Fuzzy Full -text
Type-ahead Search. VLDB Journal, 2011.
[4] C. Xiao, J. Qin, W. Wang, Y. Ishikawa, K. Tsuda, K.
Sadakane. Efficient Error-tolerant Query Autocompletion. Proceedings of the VLDB Endowment, Vol. 6,No. 6, 2013.
[5] T. Bocek, E. Hunt, and B. Stiller. Fast Similarity
Search in Large Dictionaries. Technical Reportifi-2007.02, Department of Informatics, University ofZurich, April 2007.
[6] Inci Cetindil, Jamshid Esmaelnezhad, Taewoo Kim,and Chen Li. Efficient instantfuzzy search withproximity ranking. In Data Engineering (ICDE), 2014
IEEE 30 t h International Conference on, pages 328 –339. IEEE, 2014.
[7] Thomas Bocek, Ela Hunt, Burkhard Stiller, and FabioHecht. Fast similarity search in large dictionaries.
University of Zurich, 2007.
[8] Moshe Mor and Aviezri S. Fraenkel. A hash code
method for detecting and correcting spelling errors.
Communications of the ACM, 25(12):935 –938, 1982.