DEIM Forum 2017 G4-4

Eﬃcient Query Autocompletion for Abbreviated Queries
Sheng HU , Chuan XIAO , and Yoshiharu ISHIKAWA Graduate School of Information Science, Nagoya University

Furo-cho, Chikusa-ku, Nagoya, 464–8601 Japan
 Institute for Advanced Research, Nagoya University
Furo-cho, Chikusa-ku, Nagoya, 464–8601 Japan
E-mail: hu@db.ss.is.nagoya-u.ac.jp, chuanx@nagoya-u.ac.jp, ishikawa@is.nagoya-u.ac.jp
Abstract In modern search engines applications, query autocompletion is a useful feature which can save many keystrokes
from inputting the entire query. As the autocompletion features of search engines have become more and more popular,
many variations of query autocompletion appear in various scenarios, e.g. error-tolerant autocompletion and common phrase
autocompletion. In this paper, we propose a novel autocompletion paradigm called Query Autocompletion for AbbreviatedQueries, and propose a prefix-network based index to solve this issue eﬃciently. We conduct some experiments with classicaltrie-based method using a large dataset. Experiments show that our method outperformed the classical method.
Key words Query autocompletion, prefix-network, text database search.

1. Introduction

so that users may input queries like acronyms or abbreviation instead of letter by letter. We give an motivating example in Fig. 1.

Query autocompletion has become a useful feature and been stud-

For example, in IDE, users may type “GNV” to get the function

ied for a long time since the appearance of search engines. As this“GetNextValue()”. We call this kind of problem Abbreviated Queryfeature can save many key strokes from inputting the entire query, it

Autocompletion. This problem is quite challenging because cur-has been considered a standard function of search engines. Besides

rently there’s no approach to solve it very well. The most similar

traditional text search engines, query autocompletion also has wide

approach is to model it using common subsequence techniques, but

application domains including common shells, integrated devel-

we find that common subsequence model cannot solve it eﬃciently

opment environments (IDEs) and special text abbreviation search.

because we will not consider every subsequence like “NV” or “GV”

Also, as query autocompletion usually needs to response the in-can get the function “GetNextValue()”. To model this novel querycoming query in a very short time and suﬀer from heavy query

more suitably, we propose a novel problem definition to define “Ab-throughput, query autocompletion on modern databases need to be

breviated Query Autocompletion”.

more eﬃcient to improve the user’s experience. An autocompletion

Additionally, it is also very hard to answer Abbreviated Query ef-

query often returns all the objects begins with the textual prefix.

ficiently using existing techniques. One approach is to conduct theMore useful scenarios are, users want to search for the most related

search on a prefix trie, but for every character, it needs do the ex-

objects, and then this issue changes into the autocompletion top-k

haustive search throughout current subtree recursively. This method

query, which returns objects after calculating and ranking objects

will result in extremely expensive computation when a query con-according to their textual popularities.

tains too many characters.

Autocompletion has become a standard feature these years. ThisTo deal with this problem, we propose a prefix-network index

important feature can return the search results when user is typing

structure called PNI. It transforms a trie into a prefix-network by

the partial keywords letter by letter and accordingly pop a pull-down

merging trie nodes which share the same special characters. It also

list to show the most intended items. After that user just need choose

attaches a unique bit array as an indicator on each network node

the correct entry to save the tedious inputting time.

to do eﬃcient pruning when traverse the network. In search phase,the given query traverse the prefix-network from the root node andcheck the bit array indicator to decide if stop traversing. We also
devise an eﬃcient result fetching algorithm to fetch the results by
doing interval intersection. Besides that, we also utilize the network’s nodes subsumption properties to speed up the result fetching

Figure 1 A Motivating Example

In this paper, we propose a novel query autocompletion features

time and duplicate-removal time.
In this paper we mainly study the autocompletion of abbreviation

query and then extend our index to support processing top-k query.

2. 1. 1 Trie-based Text SearchEﬃcient string prefix search based on trie index was first proposed in Baeza-Yates et al.’s work [1] in 1996. In his work, he also
proposed a patricia tree approach to save the index space. After that,
community of information retrieval begins to focus on autocompletion using trie index. A large amount of studies [2], [11], [12] havebeen done to improve the autocompletion queries’ qualities in thepast decades. Besides that, some works [8], [9] focus on reducing
the index size by various compression techniques in order to fit theindex into server’s main memory. The basic index structure used inthese works is the classical trie structure showed in Fig. ??. However, these works mainly focus on improving the autocompletion results qualities by ranking and calculate relevances carefully insteadof focusing on search eﬃciency.
2. 1. 2 Error-Tolerant Query Autocompletion
Error-Tolerant Autocompletion (ETA) [6] studied the problem
that when a user issues a partial query which contains some typos,

Figure 2 Merge Uppercase Nodethe search engine can still identify the intended query and give thecorrect answers. META [6] put forward by Deng et al. is consid-

Our main contributions are summarized as follows.
（ 1 ） Propose a novel query autocompletion feature Abbreviation

Query and give the problem definition.

ered the state-of-the-art work currently. In META, they proposed amatching-based framework, which computes the answers based onmatching characters between queries and data eﬃciently. Besides
that, some works [3], [4], [10], [13], [14] also solve the ETA prob-（ 2 ） Propose a novel prefix-network index PNI to deal with theAbbreviation Query eﬃciently.
（ 3 ） Propose an eﬃcient results fetching method which can fetch

the results by intersecting intervals.

lem using various techniques.
2. 2 Tolerant Retrieval and Wildcard Query
Tolerant Retrieval problem [5] comes from information retrieval
community and has been studied for many years. The query modelof this problem called wildcard query. This means a query such as（ 4 ） Devise a method to speedup the result fetching time andn*g*y*, and seeks documents containing any term that includes all

duplicate-removal time based on network nodes subsumption

the three characters in sequence, e.g, nagoya, nergy. The * sym-

relationships.

bol can be replaced by any characters. This kind of query is es-（ 5 ） A simple experiment has be conducted to compare with ex-

isting method and the results show our method outperforms theclassical one.

pecially useful when users are uncertain about how to spell query
term, or want to seek documents containing any of the term. A classical approach to solve this problem eﬃciently is to use a special
index called permuterm index [7]. It attaches a special symbol $The rest of our paper is organized as follows. In section 2., we show

after each string and them calculate variants of each string by rotat-

some related works. In section 3., we will give the formal problem

ing the string by one step. And then index all these variants into a

definition. In section 4., we will give the fundamental index struc-tree-like index to do eﬃcient search.

ture called PNI and show our eﬃcient search and result fetchingalgorithm. In section 5., we use a simple experiment to verify that
our algorithm outperforms the classical method.

2. Related Work

3. Problem Definition
Below we’ll give our data model and query model.
3. 1 Data Model
Suppose D is a textual database, which consists of a lot of ob-

2. 1 Trie-based Autocompletion

jects {O1 , O2 , ..., Oi , ..., On }. Each object is defined as a tuple =In order to obtain the strings with the same prefix eﬃciently, trie-{O.id, O.string, O.staticscore}, where O.id is the object id whichbased index becomes very popular and is adopted as the most eﬃ-

is a unique number, O.string is a single string which represents ob-

cient way to implement autocompletion among the current research

ject’s name, and O.staticscore is the object’s popularity.

works. Figure. 2 shows a standard trie built based on data in Table 1.

In our running example, we use a textual database showed in Table. 1 for easier demonstration.

Table 1 Textual Database D
ObjectID String
Popularity

Note that we consider uppercase and lowercase is non-sensitive in

O1

ApdNextChar

0.4

O2

ApdNextValue

0.9［Example 4］ Given a query Q = gnv. String s = “Gnv Corp.”

O3

ApdNextVector

0.9

O4

GetNextChar

0.7

the third condition that gnv in s has inter-word neighborhood rela-

O5

GetNextValue

1.0

tionship which means g||n, n||v. While string t = “GetMyNvidia”

O6

GetNextVector

0.5

doesn’t match match Q, because although it also satisfies the first

O7

GetPrevValue

0.4

two conditions, the three letters gnv appearing in t doesn’t have any

O8

GetTimeOfDay

0.1

of the two relationships.

O9

GitNextValue

0.1

O10

GotNextValue

0.1

O11

RmvNextChar

1.0

O12

RmvNextValue

0.3

sues a query, with every single stroke of the query string, the string

O13

RmvNextVector 0.3

typed in so far will be sent as the input of the index. After that, our

3. 1. 1 Token-based Data Preprocessing
We’ll use a tokenizer to do the data preprocessing in order to build
our index more conveniently during subsequent steps. We use thetokenizer to process every single string and identify every single
word in this string and change every word’s first letter into uppercase and then concatenate them together again.
［Example 1］ For a string “getnextvalue”, we first identify ev-

ery single word “get”, “next”, “value”, transform them into “Get”,“Next”, “Value” and at last concatenate them as “GetNextValue”.
3. 1. 2 Intra-word Neighborhood Relationship［Definition 1］（Intra-word Neighborhood Relationship） In a sin-

gle word from a string, every adjacent character has the intra-wordneighborhood relationship. When two characters a and b has theintra-word neighborhood relationship, we denote it as a|b.
［Example 2］ In a string “GetNextValue”, we take the word Get

and we have G|e, e|t. Similarly, in Next we have N|e, e|x, x|t, in
Value, we have V|a, a|l, l|u, u|e.
3. 1. 3 Inter-word Neighborhood Relationship［Definition 2］（Inter-word neighborhood Relationship） In two ad-

jacent single words from a string, previous word’s every characterhas the intra-word neighborhood relationship with the last word’s
uppercase letter. When two characters a and b has the intra-wordneighborhood relationship, we denote it as a||b.

the match between Q and s.
matches Q because it satisfies first two conditions and also satisfies

3. 3 Abbreviated Query
Autocompletion abbreviated query runs as follows: When user is-index return objects that match the query.
3. 4 Top-k Abbreviated Query
Top-k query runs as follows: When user issues a query, with every single stroke of the query string, the string typed in so far will
be sent as the input of the index. And then, our index will returnthe most relevant k objects that match the query according to textual
popularity.
3. 5 Problem Statement
3. 5. 1 Abbreviated Query
Based on above specification, we give the abbreviated query autocompletion problem formulation.
［Definition 3］（abbreviated query autocompletion） Given a query

Q, a textual database D = {O1 , O2 , ..., On },each object consists of
one part O.str, it returns all the objects R ⊂= D such that each object

in R satisfies Q ⪯ O.str .

3. 5. 2 Top-k Abbreviated QueryWe also give the definition of Top-k Query.
［Definition 4］（top-k abbreviated query autocompletion） Given aquery Q, a textual database D = {O1 , O2 , ..., On }, each object consists of two parts O.str and O.staticscore, it returns the top-k objects
R⊂= D such that each object O ∈ R satisfied Q ⪯ O.str, sorted by
the textual static score.

4. Prefix-network Index［Example 3］ In a string “GetNextValue”, we take the word Get

and Next, so we have G||N, e||N, t||N. Similarly, in Next and Value
we have N||V, e||V, x||V, t||V.
3. 2 Match an Abbreviated Query
Given a abbreviated query Q, and a data string s, when Q ands satisfy the following three conditions, s matches Q. When smatches Q, we denote it as Q ⪯ s.

4. 1 Index Structure
We introduce our index structure from the classical trie index
showed in Fig. 2. Considering fetching the object results conveniently, we attach an object id interval [a, b] on each trie node. If
we traverse the trie and find a trie node, we can directly use the object id range [a, b] to collect the results by random access instead of
traversing the subtree recursively.

（ 1 ） Q is a subsequence of s.
（ 2 ） Q’s first character is identical with s’s first character.

4. 1. 1 Merge Uppercase Node
Although the query match is non-sensitive to uppercase character,we can deem uppercase character as a beginning of a single word

（ 3 ） Every two adjacent characters in Q has intra-word neighbor-and do the search eﬃciently. Here, for convenience, we call thehood relationship or inter-word neighborhood relationship in

node attached with uppercase character Uppercase Node. As wes.

have highlighted using the red circle in Fig. 2, we decide to merge

the uppercase nodes if they share the same uppercase lowest common ancestor. For example, in Fig. 2, the upside red circle high-Algorithm 1: BuildPrefixNetworkIndex(T, D)

lights five uppercase nodes N, P, T, N, N, and then merge the three

Input: T is a network node, D is a textual dataset

N node into one node. This will disorganize the original trie order1

T ← RootNodeand regenerate a new subtree. Then we can find that downside red

2for each string s ∈ D docircle highlights 6 uppercase nodes C, V, V, O, V, V, but the second

3

InsertString(T, s)

V node doesn’t share the same uppercase lowest common ancestor

4

TraverseBitIndicatorShortcut(T )with the others so we just merge the other 3 V nodes. Note that5

TraverseSubsumeIndicatorShortcut(T )we also merge the object id intervals to keep the intervals updated.
After merge all the qualified uppercase nodes, we obtain a prefixnetwork described in Fig. 3.
4. 1. 2 Bit Array Indicator

Algorithm 2: InsertString(s, T )To deal with string matched by satisfying inter-word neighbor-

Input: s is a single string with a unique integer id, T is a network node

hood relationship, we attach a bit array indicator on each network1

node ← T

node to judge if any uppercase nodes appear under the current net-

2

UpdateNodeIntervalAndScore(node,s.id,s.score)

work node and help us to locate such uppercase nodes eﬃciently. In

3for each character char in s do

Fig. 3, we use a character list in orange to represent what uppercase

4

if char is UpperCase thennodes will appear under current network node, but use bit array inimplementation to save space. In Fig. 3, when we locate on node
G in the first layer, the character list N, P, T shows that there are
3 uppercase nodes under current G node. Then we locate on G’s

5node.BitIndicator.add(char)

6

FoundOrNot ← node.shortcut. f ind(char)7

if FoundOrNot = NotFound then

10

GitNextValue in this dataset.

node ← node.shortcut[char]

9

child node i, the character list N shows that there’s only one upper case node N under this i node because we only have one string

node.shortcut[char] ← NewNode

8

else

11

FoundOrNot ← node.children. f ind(char)12

if FoundOrNot = NotFound then

13

NewNode.shortcut ← node.shortcut

14

node.children[char] ← NewNodenode ← node.children[char]

15
16

UpdateNodeIntervalAndScore(node,s.id,s.score)

Algorithm 3: UpdateNodeIntervalAndScore(T, s.id, s.score)
Input: T is a network node, s.id is a string integer id

Figure 3 Prefix-network Index with Bit Array Indicator

node ← T2

if node.minid = -1 then3

node.minid ← s.id4

if node.maxid = -1 then5node.maxid ← s.id

6node.interval.pushback(IntervalT riplet < s.id, s.id, s.score >)4. 1. 3 Build the Index

7

Below we give the algorithm of building the prefix-network in-8

if s.id > maxid thenif sid = maxid+1 then9node.interval.lastPair.upperbound++10

if s.score > node.interval.lastPair.score then

Algorithm 1 shows a whole procedure of building the prefix-

11

node.interval.lastPair.score ← s.score

network index. Line 2–3 shows that we insert the whole dataset

12

iteratively, but note that we have sorted the dataset strings in13alphabetical order in advance to make it convenient for the in-14

terval update. In line 4 we complete calculating the bit array

15

dex.
•

1

indicator recursively.

else
node.interval.pushback(IntervalT riplet < s.id, s.id, s.score >)maxid ← s.id
node.maxscore ← MAX(node.maxscore, s.score)•

Algorithm 2 shows how to insert a string object into our index.

Algorithm 5: TraverseBitIndicatorChildren(T )In line 2 we first update the root node interval. As uppercase

Input: T is a network nodecharacter is special so when a uppercase character comes in,

1

node ← T

we begins to build the bit array indicator on each parent node2

if node.children = NULL thenof uppercase node in line 5. In line 6, we first create a map

3called shortcut only on uppercase node as an implicit “short-

4cut” to directly link to the below uppercase node for eﬃcient5

TraverseBitIndicatorChildren(subnode)search. Note that lowercase node only store a pointer as a copy

6

node.BitIndicator | = subnode.BitIndicator

returnfor each subnode in node.children doof its nearest or lowest ancestor uppercase node. Line 8 showsthat if we fail to find an existing node, we will insert a node.
Then, in line 9 we update current node to keep the loop going.
In line 11 we begin to insert the non-special lowercase nodeusing a map called “children”. In line 14 if we fail to find an
existing child node, we will insert a new one. And in line 15
we update the node to keep the loop going. Finally, in line 16
we update the interval for every node we have accessed.

shortcut. If it successfully matches, we call this kind of node Active
Node. When the search traverses the network and access a node, itwill see the bit array indicator to judge if the short cut really has thequery character. If the short cut really has the query character, we
can use the short cut to eﬃciently set the corresponding node active.
The active nodes in our prefix-network index will continue expanding until a query ends or the query fails to find at least one match••

Algorithm 3 shows how to update each node’s string id interval

character in its children or short cut nodes. After the query ends,

when inserting strings. In line 2 and line 4 we set the interval

if there are nodes remaining active, we will fetch the string results

minimum and maximum value to both -1 to represent the in-using these active nodes. As each active node has a path from theterval is empty. In line 6 shows that if we encounter an empty

root and every nodes it had accessed to current node, we can uti-interval we can insert the string id into the interval immedi-

lize the intervals store in these nodes to obtain the results. Note that

ately. Line 7–13 shows that if current string id is adjacent with

we only need some of these intervals, more precisely, we only needcurrent maximum id, we can simply plus 1 in the last the inter-

those nodes who is the most far from its lowest ancestors. Thenval’s upper bound, otherwise we will insert a new standalone

we can intersect these nodes’ intervals to obtain the final intervals.

interval into the interval vector. Last, we update the maximum

We give detailed algorithm in Algo 6. We also devise a merge-sort-

id in line 14.

like algorithm IntersectInterval to eﬃciently intersect the interval

Algorithm 4 and algorithm 5 show how to complete calculating each node’s bit array indicator recursively. In algorithm 5line 6, we do union operation between a parent node and its
each child to finish the bit array calculation.

•

segments, we omit the details of IntersectInterval due to the paper
space limit. After that, we can simply fetch those results strings byrandom access. Figure. 4 gives an example of abbreviated querysearch.

Algorithm TraverseSubsumeIndicatorShortcut in algo 1 issimilar with Algo 4, we omit it in details due to the paper space
limit.

Algorithm 4: TraverseBitIndicatorShortcut(T )Input: T is a network node1

node ← T2

if node.shortcut = NULL then3
4

returnfor each subnode in node.shortcut do

5

TraverseBitIndicatorShortCut(subnode)

6

TraverseBitIndicatorChildren(subnode)
Figure 4 Search with Abbreviation Query［Example 5］ See Fig. 4, given a abbreviation query “geneve”. So

4. 2 Search with Abbreviation Queryafter we traverse the prefix-network index, we can obtain an ac-

Given an abbreviation query, we will traverse the prefix-network

tive node e3 under the node V. We use color purple to repre-

index from the root node first. We try to match each character in thesent those node it has gone through. The path it goes through isquery with each character in current network node’s children and

G − e1 − N − e2 − V − e3. Their intervals are:

•G : [4, 10]•e1 : [4, 8]•

N : [4, 6][9, 10]•e2 : [4, 6][9, 10]

1

NodeS et ← NULL•

V : [5, 6][9, 10]2

bNodeS et ← NULL•

e3 : [6, 6], respectively. As node e1 is absolutely subsumed by its parent G,

Algorithm 6: SearchwithAbbreviationQuery(s, T )Input: s is an abbreviation query, T is the root network node
Output: NodeS et is the final active nodeset

3

NodeS et.push(T )4for each character char in s do

5

we don’t need to intersect node G’s interval. Similarly, we only

for each node in NodeS et do

6ChildrenFoundOrNot ← node.children. f ind(char)need to intersect nodes e1, e2, e3’s 3 intervals which the result is

7

S hortcutFoundOrNot ← node.shortcut. f ind(char)[4, 8] ∩ [4, 6][9, 10] ∩ [6, 6] = [6, 6]. [6,6] only contains O6 which is

8

BitIndicatorFoundOrNot ← node.bitIndicator. f ind(char)

GetNextVector and it’s the only match of abbreviation query “gen-9

S ubIndicatorFoundOrNot ←node.subsumeIndicator. f ind(char)eve”.
4. 2. 1 Subsumption Relationship-based Intersection Optimiza-

if ChildrenFoundOrNot = NotFound AND

10

BitIndicatorFoundOrNot = NotFound thention

continue11

We propose a technique which optimizes the intersection cost by
utilizing the subsumption relationship in this prefix-work. We show

else

12

if ChildrenFoundOrNot = Found then13

the algorithm below. We also show the basic idea with an illustrative
example.
［Example 6］ Consider the path G − e1 − N − e2 − V − e3 in exam-

14

Found.history ← node.history

15

bNodeS et.push(node.children[char])16

if BitIndicatorFoundOrNot = S CFound AND

ple 5. Notice that the node e2’s in this path interval is [4,6][9,10],

S hortcutFoundOrNot = Found thenand the interval of node V is [5,6][9,10], and the interval of node17

S CFound.history ← node.history

e3 is [6,6]. As the node e3 has parent-child relationship with node18

if S ubIndicatorFoundOrNot = NotS ubsume thenV, naturally the interval of node e3 ⊂= V. However we observe that

19

midIntersect ← node.IntersectIntervals⊂
there’s also node V ⊂= e2. So we can deduce that the node e3 = e2.
This means when we calculate the intersection of e1 e2 e3 in exam-

20(node.interval, S CFound.history)

21

if midIntersect is EMPTY thennode.history.clear()22

ple 5, it is not necessary to intersect node e2’s interval anymore. As
a result, we only need to calculate [4, 8] ∩ [6, 6].

else

23

S CFound.history ← midIntersect

24

For any uppercase node whose interval is completely subsumed
by its ancestor node, we mark “subsumed” on that ancestor node’s

25link to this uppercase node. Actually, we only need to mark those26

uppercase nodes who appear in the bit array indicator because only

bNodeS et.push(node.shortcut[char])node.history.clear()

27

NodeS et ← NULL

those who show up in the array indicator can be searched and be-

28

for each node in bNodeS et docome active. We do this by invoking TraverseSubsumeIndicator

29

NodeS et.push(node)30

for each acnode in nodeSet doshowed in Algo. 1.
4. 2. 2 Subsumption Relationship-based Duplicate-removal Op-

31

f inalIntersect ←We can also utilize the subsumption relationship to help to re-32

acnode.history ← f inaIntersect

move those possible duplicates. We also show the basic idea with33

timization

activenode.IntersectInterval(ac.interval, acnode.history)

return nodeS et

an illustrative example.
［Example 7］ See Fig. 3, given an abbreviation query “get”. After

we traverse the prefix-network index, we can obtain an active node

expands into two active nodes, in this example, we will check thet from path G − e − t and an active node T from path G − e − T . The

node t and T subsumption relationship when active node e “splits”

second active node is obtained because when search goes throughinto these two active nodes. We can find that node T ⊂= node t, and if

G − e, node e’s bit array indicator shows that there’s a T below soquery ends here, we will abandon active node T to do the duplicate

the node T also become active. We observe that these active nodes’

removal.

intervals are [4,8] and [8,8] respectively. As we need to fetch all

About the “active node split”, we give the definition below.

these active nodes results, we do [4, 8] ∪ [8, 8] = [4, 8]. As node［Definition 5］（Active Node Split） Given an active node n, whenT ⊂= node t, the interval of node T becomes completely duplicate

query’s next character s comes in, n finds the character s matchedin this Union operation. To solve this problem, we need to check

both in its children and shortcut map, we call this active node n split

the subsumption relationship especially when a single active nodes

into two active nodes.

Whenever an active node split into two active nodes, we begin
to trace these two nodes and check if they have subsumption relationship, if they have and query ends here, we can abandon the subsumed node to remove the duplicate. If they have subsumption relationship but the query doesn’t end, we will trace these two nodes’

can easily prune this node or remaining interval segments to avoid
unnecessary operations.
Algorithm 7 shows the details of top-k abbreviation query search.

5. Experiment

expansion as query’s next character comes in, if these two nodes

5. 1 Experimental Setting

keep active until query ends and:In this section, we will give our experimental results to show the•

These two nodes only expand through children map.

•

Upside node always subsumes the downside node’s lowest up-（ 1 ） Classical trie. Classical trie is used in text retrieval and eﬃ-

percase ancestor.
We can remove the downside node safely when query ends.
We give our search algorithm and a running example below.
4. 3 Search with Top-k Abbreviation Query

cient autocompletion these years. We donote it as CT for simplicity.
（ 2 ） PNI. With the novel index structure and fetching method we

proposed, we will give the comparison between the other work,
and we denote it as PNI for simplicity in our experiment.

Algorithm 7: FetchTopkResultswithActiveNodeSet(NodeS et)

The experiments were implemented using a PC with Intel Xeon

Input: NodeS et is an active node set

CPU E5620 (2.40GHz), 32GB memory, Ubuntu14. All the algo-

Output: Results is the final topk results

rithm are implemented in C++ and are run as the in-memory index.

1

i←0

2

T opkPriorityQueue ← NULL

3for each active node node in NodeS et do

4

TopkPriorityQueue.push(node)5

performance and compare it with other works showed below.

5. 1. 1 Datasets
We use a large dataset and show the statistics below. Dataset
Table 2 Statistics of the Dataset
Dataset
DBLP

while i < k AND TopkPriorityQueue is not empty do

6

topElem ← T opkPriorityQueue.pop()

number of objects

7

if topElem is a node thenDataset Size

135MB
12

9316195

8

Expand topElem into the interval segments

Max Text Length9for each interval segment seg in topElem do

Average Text Length 9.40

10TopkPriorityQueue.push(seg)11

if topElem is a interval segment then12

for each stringob ject locate in topElem do

13

TopkPriorityQueue.push(stringob ject)

14

if topElem is a stringobject then

DBLP contains bibliography records in Computer Science, and we
extract 9.3 million worldwide author names from the records.
5. 1. 2 Queryset
We generate queries by randomly selecting 1000 strings and gen-

15

Results.push(topElem)erate the abbreviation query for each string. We ignore all the spaces

16

i++

in multikeyword and contecate them into one single string. We re-17

return Results

move meaningless symbols and only remain the alphabetic letters.
In our experiment, we mainly measure:Top-k query processing is quite diﬀerent from the non-top-kquery and eﬃciently fetch the top-k is even an challenging work.
To fetch the most relevant top-k data string, we need to rank the（ 1 ） Abbreviation Query Response Time. It represents the wholetime to execute a abbreviation query and fetch all the qualified
results.

results by their static score. In our index, we store a upper bound（ 2 ） Top-k Abbreviation Query Response Time. It represents thestatic score for every node’s every interval segment (e.g. [4,6]:1.0

whole time to execute a top-k abbreviation query and fetch the;[9,10]:0.1.) in the prefix-network and use the early termination

most relevant k qualified results.

technique to fetch the results eﬃciently. Also, as showed in alg. 3,
we store an overall upper bound score on each node (e.g. for nodeN, we store a maximum score 1.0).That means, we will fetch theresults from the highest static score node’s highest interval segment
which is considered the most relevant. We use a priority queue torank the top-k results and if any node’s upper bound score, or any
node’s any interval segment score is lower than the k-th score, we

5. 2 Abbreviated Query Response TimeIn Fig. 5 we show the abbreviated query response time using
dataset DBLP. We vary the query string prefix length from 1 to 8
to see the runtime. When prefix length is longer, CT method becomes much slower while our PNI method becomes faster. This isbecause CT method costs too much on iteratively search the wholetrie while our PNI almost has no time cost on search of index but

mainly on fetch results phase. When prefix length becomes longer,
qualified strings will reduce drastically and our PNI method will become faster. We also observe that in the most common case, whenprefix length equals 2 or 3, our PNI method is 100 times and 1000

Acknowledgments
This research is partly supported by the Grant-in-Aid for Scientific Research, Japan (16H01722, 26540043).

times faster than the CT method respectively.
PNI-response
CT-response

Time (ms)

1

0.1

0.01

0

1

2

3

4

5

6

7

8

9

Prefix Length

Figure 5 DBLP, Query Response Time5. 3 Top-k Abbreviated Query Response TimeIn Fig. 6 we show the top-k abbreviated query response time. We
set k = 5 and vary the query string prefix length from 1 to 8 to see
the results. Similarly, when prefix length is longer, CT method becomes much slower while our PNI method becomes faster after awave when prefix length equals 2. CT method still costs too muchon trie traversal search while our PNI is fast at index search and also
has decent performance of top-k results pruning. Additionally, we
also record the index size of both methods. CT costs 5.3Gb while
PNI costs 2.27 Gb when k = 5. CT also doesn’t support a dynamic
k value become it needs to materialize a top-k rank list on each nodeof the trie which will introduce prohibitive memory cost under alarge k value. Compared with that, our PNI supports a dynamic k
and the index size will keep constant when k changes.
PNI-topk
CT-topk

Time (ms)

1

0.1

0.01

0.001
0

1

2

3

4

5

6

7

8

9

Prefix Length

Figure 6 DBLP, Top-k Query Response Time

6. Conclusion
In this paper, we propose the definition of abbreviation query autocompletion. Then we design an eﬃcient index structure alongwith a search algorithm and a top-k fetch algorithm. After that wegive a simple evaluation using a large dataset.

References[1] R. A. Baeza-Yates and G. H. Gonnet. Fast text searching for regular expressions or automaton searching on tries. Journal of the ACM(JACM), 43(6):915–936, 1996.
[2] Z. Bar-Yossef and N. Kraus.
Context-sensitive query autocompletion. In Proceedings of the 20th International Conference on
World Wide Web, pages 107–116. ACM, 2011.
[3] I. Cetindil, J. Esmaelnezhad, T. Kim, and C. Li. Eﬃcient instantfuzzy search with proximity ranking. In 2014 IEEE 30th International Conference on Data Engineering, pages 328–339. IEEE, 2014.
[4] S. Chaudhuri and R. Kaushik. Extending autocompletion to tolerate errors. In Proceedings of the 2009 ACM SIGMOD International
Conference on Management of data, pages 707–718. ACM, 2009.
[5] P. R. Christopher D. Manning and H. Schutze. Introduction to Information Retrieval. Cambridge University Press, 2009.
[6] D. Deng, G. Li, H. Wen, H. Jagadish, and J. Feng. Meta: An eﬃcientmatching-based method for error-tolerant autocompletion. Proceedings of the VLDB Endowment, 9(10), 2016.
[7] P. Ferragina and R. Venturini. The compressed permuterm index.
ACM Transactions on Algorithms (TALG), 7(1):10, 2010.
[8] R. Grossi and G. Ottaviano. Fast compressed tries through path decompositions. Journal of Experimental Algorithmics (JEA), 19:3–4,
2015.
[9] B.-J. P. Hsu and G. Ottaviano. Space-eﬃcient data structures for topk completion. In Proceedings of the 22nd International Conferenceon World Wide Web, pages 583–594. ACM, 2013.
[10] G. Li, S. Ji, C. Li, and J. Feng. Eﬃcient fuzzy full-text type-ahead
search. The VLDB Journal, 20(4):617–640, 2011.
[11] M. Shokouhi and K. Radinsky.
Time-sensitive query autocompletion. In Proceedings of the 35th International ACM SIGIR
Conference on Research and Development in Information Retrieval,
pages 601–610. ACM, 2012.
[12] S. Whiting and J. M. Jose. Recent and robust query auto-completion.
In Proceedings of the 23rd International Conference on World Wide
Web, pages 971–982. ACM, 2014.
[13] C. Xiao, J. Qin, W. Wang, Y. Ishikawa, K. Tsuda, and K. Sadakane.
Eﬃcient error-tolerant query autocompletion. Proceedings of the
VLDB Endowment, 6(6):373–384, 2013.
[14] X. Zhou, J. Qin, C. Xiao, W. Wang, X. Lin, and Y. Ishikawa. Beva:
An eﬃcient query processing algorithm for error-tolerant autocompletion. ACM Transactions on Database Systems (TODS), 41(1):5,
2016.