Automated Query Reformulation for Efficient Search based on Query Logs From Stack Overflow

Table I shows the top-10 most frequent 1-grams, 2-grams, 3-grams, and 4-gram in the users’ queries. Programming languages such as Python and Java, platforms such as Android, data types such as string, and data structures such as array are the most frequently queried terms. At the same time, “how to” is the most frequently used phrase in the queries. Almost every 3-gram starts with “how to”, next comes “what is” and programming language qualifiers such as “in python” and “in java”. It is worth noting that some Java and Python error logs appear in the top ten 4-grams. The reason is that the developers often paste these error logs directly into the search box to perform queries, and logs like “exception in thread "main"” and “ImportError: No module named” are the most common error types.

Fig. 3 shows the distribution of query length via a box plot. The median, mean, $25^{th}$ percentile, and $75^{th}$ percentile of the length are 3, 3.6, 2, and 4 respectively. The distribution shows that users do intentionally limit the length of their queries to get better search results. However, we can also easily find that the query length span of the outliers is very large, and all values from 8 to 25 correspond to outliers. For these queries, it is difficult for the search engine of Stack Overflow to return satisfactory results. Because most search engines are optimized only to handle common requests, they use exact-match techniques in which all query words must match a web page for web page retrieval [22]. A longer query means lower matching probability and leads to lower-quality search results. After manual analysis, we find that most of these queries contain error messages or code snippets.

The result shows that 8.74% of the queries use the advanced search. The top-10 most frequently used advanced search methods, an illustrative example, and their proportions can be found in Table II. Tag filtering, user filtering, and declaring specific phrases are the top-3 most commonly-used advanced search methods, accounting for 73.53%, 10.35%, and 10.00% respectively.

The users reformulate their queries for many reasons. For example, the queries may not specify the corresponding programming language, or some words in the queries may be misspelled. We use the provided dataset to analyze why the users reformulate their queries. We manually classify 384 randomly collected query reformulation threads⁴⁴ 4 The number is the minimum number to be statistically representative of a large dataset with a confidence level of 95% and error margin of 5% via a commonly-used sampling method [23]. into four categories. The first and second author classified these 384 threads independently. For the cases without an agreement, the final classification result is determined through discussions. For the threads with more than two queries, if multiple query reformulation types are identified, the type of reformulation from the first query to the last query is used as the final classification result. The Kappa inter-rater agreement [24] is 0.83, which shows the high agreement of classification.

Table III shows the manual classification results. In this table, we can see that adding new information to the query is the most common query reformulation operation, which accounts for 40.1% of all threads, then comes modifying the query (33.59%), and deleting information from the query (23.18%). In the category of adding new information [25], we further divide it into two sub-categories: (1) adding information about specific programming languages or platforms, (2) adding new requirements for the question or more detailed content. In the category of modifying, we further divide it into three sub-categories: (1) spelling and syntax checking [26], (2) simplifying and refining the query to reformulate it into the most commonly-used expression, (3) modifying to other content related to the original query. In the category of deleting, we further divide it into three sub-categories: (1) deleting some unnecessary or less informative words, (2) deleting specific information in error messages or code snippets (such as file path, URL, function names, etc.), (3) deleting punctuation and some mistyped symbols.

Based on the classification result, we can observe many different types of query reformulation operations (such as adding information, deleting information, and modifying their expressions). Previous studies [27, 28, 29, 30] mainly use rule-based methods to perform automated query reformulation. However, each of these methods can only target query reformulation for a specific reason. Different rules need to be designed for each situation and then implemented with different methods, which is inefficient and difficult to achieve. For example, for the query reformulation in the category of modifying, the user may completely change the expression of a query (e.g., from “how to cut youtube embedded videos” to “how to make embedded videos that only play certain parts”). It is challenging to implement this type of reformulation by using rule-based methods. Therefore, we find it necessary to propose a general query reformulation approach, which is the motivation of this study.

In Section III-B, we find that when reformulating a query, the users may add, remove, or replace some words in the original query. To understand the scale of changes that query reformulation involves, we measure the similarity between the original query and the reformulated query. For each query reformulation thread, $n-1$ pairs of reformulation samples (original, reformulated) can be extracted, that is $\{(q_{1},q_{n})$, $(q_{2},q_{n})$, $\cdots$, $(q_{n-1},q_{n})\}$. The first query original in the pair is the initial query performed by the user, and the second query reformulated is the user’s manual reformulated query, which meets their requirement. We use a text-matching algorithm with improved dynamic programming [31] to find the character-level Longest Common Subsequence (LCS) between original and reformulated. Then the similarity between original and reformulated can be defined as follows:

where $N_{match}$ is the number of characters in the LCS, and $N_{total}$ is the sum of the number of characters in original and reformulated. The similarity score is in the range of 0 to 1. The higher the similarity score, the fewer changes between original and reformulated.

As shown in Fig. 4, among 1,121,185 query reformulation pairs, 58.07% of the pairs are very similar (i.e., the similarity score is larger than 0.7) with an average of 6.73 character level modifications, which corresponds to 1.14 words according to the average length of query words. The analysis result indicates that most of the query reformulations only involve minor changes.

Our empirical study shows that: (1) On Stack Overflow, most of the users’ queries are simple and short with only 2 to 4 words, but there are also very long queries containing error logs, code snippets, and structured queries with advanced search patterns. (2) The users perform query reformulation for various reasons, making it difficult to design a general query reformulation model by only using rule-based methods. (3) Most query reformulations only involve minor changes.

Considering the diversity of query reformulation patterns, it would require significant effort to manually develop a complete set of reformulation patterns, which is both time-consuming and error-prone. Unlike enumerating all the rules, the deep learning method [32] can automatically learn the latent features from the dataset and these latent features are helpful for downstream tasks.

Based on the above findings, we believe it is necessary and feasible to propose an automated query reformulation approach based on deep learning. Our proposed approach would benefit the developers and the Stack Overflow community. In particular, the developers can use our automated query reformulation tool to refine their queries and get better search results, which can alleviate the effort of manual reformulation. The Stack Overflow community can also use the query reformulation model to enhance the users’ search experience.

Our formative study has shown a wide variety of query reformulation behaviors. Since not all reformulation patterns are amenable to automated tool support, we focus on query reformulations that trigger minor changes to the original query to develop our automated query reformulation approach. In this work, we formulate query reformulation as a machine translation problem, in which an original query is “translated” into a reformulated query. We solve the problem using the Transformer model [33].

The overall workflow of SEQUER is shown in Fig. 5. SEQUER first extracts query reformulation threads for sampling original queries and corresponding reformulated ones. Then a large corpus of query reformulation pairs is gathered for training the model, each of which contains the original query and the corresponding reformulated one that triggers only minor changes (in Section IV-B). To model the patterns of query reformulation (such as spelling correction, expression refinement, unnecessary word deletion), SEQUER trains a Transformer-based model with a large parallel corpus of query reformulation pairs (from Section IV-C to Section IV-E). Given the users’ original queries, the trained model can suggest a list of reformulated candidates for selection.

Based on the description in Section II, query reformulation threads can be extracted from the users’ navigation sequences by pattern matching. The most important thing for the pattern is how to ensure that $q_{i}$ and $q_{i+1}$ are issued for the same purpose, rather than two independent queries. Two constraints are applied: (1) The character-level similarity between $q_{i}$ and $q_{i+1}$ must be greater than 0.7 by using Equation (1). (2) The browsing time of the post $p_{1}$ cannot be greater than 30 seconds. The first constraint can limit the change scale since a large-scale change is likely to introduce a new query. The second constraint can guarantee the post $p_{1}$ is not what the user wants, since a previous study [34] shows for an unsatisfactory post, the user would not spend more than 30 seconds on it.

We set the minimum number of query events before the final post visiting event in the thread to 2. After identifying all the query reformulation threads, we perform the following data cleaning steps. For consecutive identical queries in the thread, we only keep one of these identical queries and remove the rest to avoid generating duplicate query reformulation pairs. We also remove threads containing queries with non-English words, since non-English words are not encouraged to be used on Stack Overflow⁵⁵ 5 https://stackoverflow.blog/2009/07/23/non-english-question-policy/. After the above data cleaning, we pair each query between $q_{1}$ to $q_{n-1}$ with $q_{n}$ (i.e., ($q_{1}$, $q_{n}$), ($q_{2}$, $q_{n}$), $\cdots$, ($q_{n-1}$, $q_{n}$)) as the training instances. From the provided dataset, we extract a total of 1,121,185 query reformulation pairs.

Some of these reformulation pairs are hard-to-predict due to their large-scale modifications. After randomly sampling reformulation pairs with different similarity, we carry out a pilot study to determine the similarity threshold, which can be used to identify large-scale modifications. The results show that reformulation pairs with a similarity score higher than 0.7 are predictable, while the remaining pairs (i.e., reformulating by large-scale modifications) cannot be predicted even by humans. As analyzed in Section III-C, 58.06% of the query reformulations involve minor modifications with a similarity of at least 0.7. Therefore, we only consider these similar-enough query reformulations, which results in 651,036 query reformulation pairs.

Traditional word segmentation methods include whitespace-separated word level and character level segmentation. However, word-level embedding cannot handle the Out-Of-Vocabulary (OOV) problem [35], and the character level is too fine-grained, resulting in the loss of high-level information. Therefore, we adopt the BPE (Byte Pair Encoding) [36], which can effectively interpolate between word-level inputs for frequent symbol sequences and character-level inputs for infrequent symbol sequences.

The BPE algorithm contains multiple iterations. In each iteration, it calculates each consecutive byte pair’s frequency and finds the most frequent one, then merges the two byte pair tokens into one token. This encoding approach can divide words into sub-words like encoding the common words at the word level while encoding the rare words at the character level. Since the form of the users’ queries on Stack Overflow varies, using BPE can better identify the content of the users’ queries. For example, misspelled words can be divided into several correctly spelled sub-words to alleviate the OOV problem’s impact. Words with camel-case style can be separated into several sub-words and then each sub-word can be identified. Besides, using BPE to separate words with their affixes can help the model learn the relationships between them. After applying the BPE algorithm on the corpus, we get a vocabulary composed of sub-words, which is used as the dictionary for our model.

With the introduction of the attention mechanism [37], many neural machine translation approaches integrate the attention mechanism with sequence transduction models like Convolution Neural Network (CNN) and Recurrent Neural Network (RNN) to improve their performance. Even so, the CNN-based network architectures require many layers to capture long-term dependencies, leading to high computational cost, and operations in RNN-based network structures cannot be parallelized, resulting in low efficiency. To address these issues, Transformer [33] is proposed, which is the first transduction model entirely relying on the attention mechanism and has shown competitive performance on various tasks (such as machine translation [33], image captioning [38], document generation [39], and syntactic parsing [40]).

The most significant difference between Transformer and other sequence transduction models like CNNs and RNNs is that it relies entirely on self-attention (called “Scaled Dot-Product Attention”) to obtain global dependencies, and the attention weights are defined by how each word of the sequence is influenced by all the other words in the sequence. The self-attention mechanism creates shortcuts between the current token and all the other context tokens to determine the current token vector for the final input representation. As weights of these shortcuts are customizable, the self-attention mechanism is able to capture global dependencies without using many layers of convolution and pooling in CNN-based models. At the same time, the calculation in self-attention is implemented with highly optimized matrix multiplication, and thus resolves the low efficiency caused by the RNN-based models, which sequentially encode the input tokens. Intuitively, for an input sequence, first, a neural network is employed to map the input into three matrices: query $Q$, key $K$, and value $V$. Then, the dot products of the queries $Q$ with all keys $K$ is divided by $\sqrt{d_{k}}$ ($d_{k}$ is the dimension of the queries), and a softmax function is applied to obtain the weights for the values. Finally, the weighted value is used as the representation of each input.

Instead of performing a single self-attention function, the Transformer employs a multi-head self-attention, which linearly projects the queries $Q$, keys $K$ and values $V$ $h$ times with different, learned linear projections respectively, where $h$ is the number of heads. To obtain the temporal relationship of the words, the Transformer adds positional embedding to the input embedding.

Self-attention can be regarded as a basic calculation in Transformer. The Transformer model comprises an encoder and a decoder, which are actually multiple identical encoder and decoder blocks stacked on top of each other with the same number of units. Each encoder block has one layer of multi-head self-attention followed by another layer of Feed Forward Network (FFN). On the other hand, each decoder has an extra masked multi-head self-attention, which prevents the model from seeing the generated words during parallel training. On the encoder side, the multi-head self-attention layer’s input is the input embedding with temporal information, and the layer output is normalized and sent into an FFN, which consists of two linear transformations with a ReLU activation. The output of the encoder on the top of the stack is a set of attention vectors $K$ and $V$, which are used by the decoder to determine the token it should pay attention to. On the decoder side, the previous output is used as the input to the masked multi-head self-attention layer. After that, another multi-head self-attention layer with subsequent FFN generates decoder output $h_{t}$ by getting the query matrix $Q$ from the masked multi-head self-attention layer, the key $K$ and value $V$ matrices from the output of the encoder stack. Finally, the output of the decoder stack $h_{t}$ is sent to a fully connected neural network to get the logits vectors, and then a softmax layer to predict the probabilities of the next token.

where $h_{t}$ is the output of the decoder stack.

During decoding, for each time step $t$, the Transformer model will output the word with the highest conditional probability $y_{t}=\operatornamewithlimits{argmax}_{y\in\mathcal{D}}P\left(y|y_{1},\cdots,y_{t-1}\right)$ via greedy search from $|\mathcal{D}|$ number of words, where $\mathcal{D}$ represents all the words in the word dictionary. Since we calculate the conditional probability of generating an output sequence based on the input sequence $\prod_{t=1}^{T}P\left(y_{t}|y_{1},\cdots,y_{t-1}\right)$, where $T$ is the maximum length of the output sequence, the main problem with greedy search is that there is no guarantee that the optimal sequence will be obtained. The reason is that although the greedy strategy ensures that the output candidate with the highest probability is picked up for each time step, it cannot ensure that the conditional probability of the entire output sequence obtained is the highest.

Beam search [41] is an improved algorithm of greedy search, and beam size $k$ is its hyper-parameter. The decoding process using beam search is as follows: At time step 1, $k$ words with the highest probability are selected as the first word of $k$ candidate output sequences $cs_{1}$. Then, at time step $i$, $k$ output sequences with the highest conditional probability $cs_{i}$ will be selected from $k|\mathcal{D}|$ possible output sequences based on $cs_{i-1}$. After $T$ iterations, $k$ sequences with the highest score will be selected from $CS$ as the beam search result, where $T$ is the maximum number of tokens of the output sequence, and $CS$ is the collection from $cs_{1}$ to $cs_{i}$. Note, for each sequence, portions including and after special end-of-sequence tokens are discarded. The score is calculated as follows:

where $L$ is the length of the sequence in $CS$ and $\alpha$ is the length normalization parameter.

In our implementation, the maximum vocabulary size for BPE [36] is set to 10,000. For the Transformer, we use the tensor2tensor library [42] developed by the Google Brain team. The Transformer model contains four attention heads with four encoder and decoder layers, with $\textit{hidden\_size}=512$. During the model training, the parameters are learned by back propagation [43] with Adam optimizer [44] to minimize the error rate. We train our model with $\textit{batch\_size}=256$, $\textit{learning\_rate}=0.0001$ for 147 epochs on 4 Nvidia V100 GPU (32G memory) for about 8 hours. During decoding, the hyper-parameter $k$ of beam search is set to 10 to ensure the probability of finding the optimal solution. The length normalization parameter $\alpha$ is set to 0.6, which is a common practice in neural machine translation [45].

To make our work more practical, we develop a browser plugin⁶⁶ 6 https://github.com/kbcao/sequer based on Tampermonkey, which is a popular user-script manager. The browser plugin will automatically analyze the query content and recommend the top-10 query reformulation candidates to the users for selection (a screenshot can be found in Fig. 6). Although the plugin is designed to only work on Stack Overflow now, it can be easily extended to other software-specific Q&A sites.

From the 651,036 query reformulation pairs, we randomly take 520,830 (80%) of these query pairs as the training set to train the model, 65,103 (10%) as the validation set to tune model hyper-parameters, and 65,103 (10%) as the testing set to evaluate the quality of recommended reformulations.

As analyzed in Section III-B, many queries are reformulated to fix grammatical errors. Therefore, we first adopt a popular grammatical error correction (GEC) tool as the baseline. LanguageTool⁷⁷ 7 https://languagetool.org is an open-source proof-reading tool for more than 20 languages. This tool’s style and grammar checker is rule-based and has been developed for over ten years.

As our task is query reformulation, and Google is the most popular search engine in the world, we choose Google Prediction Service (GooglePS) [19] as a baseline. Google uses a prediction service to help complete searches in the search box or address bar within Chrome. These suggestions are based on the real searches that happen on Google. Common and trending queries relevant to the strings entered by the users are shown in the drop-down bar for the users to choose⁸⁸ 8 https://www.blog.google/products/search/how-google-autocomplete-works-search. Since Google has accumulated a large-scale dataset of the users’ queries, GooglePS can efficiently and accurately reformulate users’ queries, such as correcting misspelled words, completing words that the users are typing, and appending the next possible word.

The query reformulation task can also be regarded as a translation task (i.e., translating the original query into the reformulated query). Therefore, we take the most classical neural machine translation model seq2seq [17] as our baseline. It contains one Long Short-Term Memory (LSTM) model [46] as the encoder, which can encode the original query to an embedding vector, and another LSTM model, which can decode that embedding vector to the reformulated query. We also add the seq2seq model with the attention mechanism as another baseline.

Besides, there are many studies in information retrieval [47, 48, 49, 50] about query suggestion. We select HRED-qs [18] as one of our baselines, which is a representative hierarchical and session-based query suggestion model with full source code release. HRED-qs is trained with our dataset. In particular, given a query in the session, HRED-qs first encodes the information seen up to the position by a query-level RNN encoder and a session-level RNN encoder. Then it uses the following decoder to predict the next query. To keep the setting of all baselines consistent, we only feed the last query before the reformulated one in the session to HRED-qs.

To make a fair comparison, we employ the same data preprocessing method and Byte Pair Encoding for seq2seq and HRED-qs as SEQUER, and we perform hyper-parameter optimization with grid search [51].

Query reformulation is similar to the grammar error correction task (i.e., revising some words in the original sentence for generating the target sentence). Therefore, we evaluate the query reformulation with the metrics used in the GEC task (i.e., $\mathit{GLEU}$, $\mathit{M^{2}}$ and $\mathit{ExactMatch}$).

$\mathit{GLEU}$ (General Language Evaluation Understanding) [52, 53] is a customized metric from $\mathit{BLEU}$ (BiLingual Evaluation Understudy) [54], which is a widely used metric to measure the performance of machine translation approaches. Since only part of the source sentence will be changed in the GEC task, which is different from the machine translation task, this motivates a small change to $\mathit{BLEU}$ that computes $n$-gram precision over the reference but assigns more weight to $n$-grams that have been correctly changed from the source. Therefore, compared with $\mathit{BLEU}$, $\mathit{GLEU}$ is more suitable for evaluating query reformulation in our study.

$\mathit{MaxMatch}$ (or $\mathit{M^{2}}$) [55] is another widely used GEC evaluation metric that computes the sequence of phrase-level edits between a source sentence and a system hypothesis that achieves the highest overlap with the gold-standard annotation. These edits are scored by $\mathit{precision}$, $\mathit{recall}$, and $\mathit{F1}$. Specifically, in the scenario of query reformulation, $\mathit{M^{2}@P}$ represents the proportion of edits of the original query given by an approach that appears in the user’s manual reformulation. $\mathit{M^{2}@R}$ represents the proportion of edits of the original query by users that are correctly predicted by an approach. $\mathit{M^{2}@F1}$ is the harmonic mean of $\mathit{M^{2}@P}$ and $\mathit{M^{2}@R}$.

$\mathit{ExactMatch}$ ($\mathit{EM}$) evaluates the probability of a perfect match between the query provided by a specific approach and the user’s manually reformulated one. Since SEQUER uses beam search during decoding, it can suggest multiple reformulations for an original query, for the decoding results of SEQUER with different beam size, we can calculate $\mathit{EM@1}$, $\mathit{EM@5}$, and $\mathit{EM@10}$, where $\mathit{EM@n}$ means one case will be considered positive as long as one of $n$ reformulation results returned by beam search matches the ground truth.

We report our evaluation results by answering the following two research questions.

In Section V-D, we evaluate the quality of reformulations from different approaches by comparing them with users’ manual ones with the metrics used in the GEC task. However, none of these metrics consider the model effectiveness (i.e., the ability of the reformulated query to retrieve the desired post). Therefore, we further evaluate the retrieval effectiveness of SEQUER in this section.

For each query reformulation thread (mentioned in Section II), we collect pairs of users’ original query and finally-visited post, which is assumed to be the target post. These query-post pairs can be used to demonstrate the retrieval effectiveness of the model. For each pair, we adopt both our approach and baselines in Section V-B to reformulate the query and check the ranking of the target post in all candidate posts on Stack Overflow. All the 65,103 queries in the testing set are paired with their corresponding finally-visited post as the evaluation data.

We use $\mathit{MRR}$ (Mean Reciprocal Rank) as the metric for retrieval effectiveness evaluation. $\mathit{MRR}$ is the average of the reciprocal ranks (i.e., the multiplicative inverse of the target post’s rank in the search result) of the search results for all the queries. For example, given a query, if the target post ranks fifth in the search result, the reciprocal rank is 1/5=0.2. A higher $\mathit{MRR}$ value indicates a better search result.

The comparison results between SEQUER and baselines in terms of $\mathit{MRR}$ can be found in Table VI. SEQUER achieves the best performance (i.e., 129.33% boost in terms of $\mathit{MRR}$ to the original query). Even compared with the best baseline seq2seq+Attn., SEQUER still achieves a 23.7% boost. This result shows that the reformulated query given by SEQUER is not only the closest to manual reformulation, but also has the best retrieval effectiveness among all the baselines. Therefore, SEQUER can effectively help users obtain better search results via high-quality query reformulation.

To help users better refine their queries, there are many studies on query expansion [67, 68], query reformulation [69, 70] and query suggestion [47, 48, 49, 50] in information retrieval. In detail, Jiang et al. [48] tried to provide query suggestions based on previous queries in the session by introducing a binary classifier and an RNN-based decoder as the query discriminator and the query generator. Chen et al. [49] proposed an attention-based hierarchical neural query suggestion model that combines a session-level neural network and a user-level neural network to model the users’ short and long term search history.

However, most of these studies are session-based or user profile-based and apply to general text search. Different from general text search, search in the software engineering domain is very specific, with domain-specific terms and code snippets, which make general approaches not applicable in this scenario. Therefore, we carry out this study based on domain-specific dataset for providing a software-specific automated query reformulator.

The performance of document search in software engineering relies on the domain-specific query reformulation. Haiduc et al. proposed several metrics to measure query difficulty [71], query specificity [72], and query quality [73] for concept location. Based on these metrics, they [74, 75] further developed a machine learning model to adopt one of four strategies to recommend revised queries. Rahman et al. [76] proposed a word-embedding based method to extract semantically similar terms from questions on Stack Overflow, hence suggesting semantically relevant queries. Li et al. [77] shared a similar idea by building a software-specific domain lexical database based on tags on Stack Overflow and optimized the input queries to help search software-related documents. Chen et al. [78] reformulated the Chinese queries to English ones for searching related posts on Stack Overflow.

Most of these previous studies generate query reformulation based on heuristic rules or lexical databases, which depends greatly on the quality and size of the rules or the database. In contrast, SEQUER is fully data-driven, which is based on large-scale real-world developers’ queries on Stack Overflow. We believe that SEQUER can automatically learn reformulation patterns, and generate better reformulation result.

Code search plays an important role in software engineering, many previous studies focused on query reformulation for code search. Sisman et al. [30] proposed a query reformulation framework by enriching the users’ queries with certain specific terms drawn from the highest-ranked retrieved artifacts. Howard et al. [79] leveraged similar word pairs in comments and method signatures, which are semantically similar in software engineering to reformulate users’ queries. Lu et al. [68] took a similar method, i.e., identifying each term in the original query and extends with synonyms generated from WordNet. Nie et al. [67] identified software-specific expansion words from high-quality pseudo relevance feedback question and answer pairs on Stack Overflow. Rahman et al. [80] identified terms from the source code using a novel term weight-CodeRank, and then suggested effective reformulation of the original query by exploiting the source document structures, query quality analysis, and machine learning. They further proposed a query reformulation technique that suggests a list of relevant API classes for a natural language query by exploiting keyword-API associations from the questions and answers on Stack Overflow [70]. Similarly, Sirres et al. [81] augmented the original query with structural code entities by mining questions and answers from Stack Overflow.

Different from code search, our study mainly focuses on software-specific document search. Moreover, SEQUER can complement these code search approaches to reformulate the users’ queries better.