# Real-Time Experimental Demonstration of Multi-band CAP Modulation in a
VLC System with Off-the-Shelf LEDs
††thanks: This work is supported by EPSRC MARVEL (EP/P006280/1).

Paul Anthony Haigh and Izzat Darwazeh
Communications and Information Systems Group, University College London, Gower
Street, WC1E 6BT, United Kingdom
<EMAIL_ADDRESS>
###### Abstract

We demonstrate, for the first time, $m$-CAP modulation using off-the-shelf
LEDs in a VLC in real time experimental setup using field programmable gate
arrays based in universal software radio peripherals (USRPs). We demonstrate
transmission speeds up to $\sim$30 Mb/s can be achieved, which supports high
definition television streaming.

###### Index Terms:

Digital signal processing, field programmable gate array, modulation, real
time, visible light communications

##  I Introduction

Advanced modulation formats are commonly used to increase transmission speeds
in visible light communications (VLC), where modulation bandwidths are
typically limited to several MHz [1, 2, 3, 4]. They allow, in principle,
additional spectral efficiency and hence, higher data rates [3]. One of the
most popular formats is carrier-less amplitude and phase (CAP) modulation,
which, in 2013 [1], was shown to outperform experimentally orthogonal
frequency division multiplexing (OFDM) in terms of bit-error rate (BER). Since
the report in [1], several variations of CAP have been proposed, the most
significant of which is the multi-band system ($m$-CAP) that protects against
chromatic dispersion in fibres [5]. Subsequently, $m$-CAP was adopted in VLC
[2], it was shown that reducing subcarrier bandwidths led to tolerance of out-
of-band attenuation caused by the low LED modulation bandwidths, and thus,
higher spectral efficiencies.

In recent years, there have been only a limited number of studies of real-time
VLC systems, where the two most recent examples are reported in [6, 7]. Both
reports utilise OFDM modulation rather than CAP due to the ease of deploying
an (inverse) fast Fourier transform ((I)FFT) pair. The computational
complexity of the (I)FFT pair increases with $2\log_{2}(N)$, where $N$ is the
number of subcarriers, while $m$-CAP requires finite impulse response (FIR)
pulse-shaping filters whose complexity increases with $4Lm$, where $L$ is the
number of taps and $m$ is the number of subcarriers [8]. Clearly, $m$-CAP has
a higher computational requirement than OFDM, however recent reports have
shown that look-up tables at the transmitter can reduce this by 50%, and when
used together with new receiver architectures and pulse shapes, the
computational load can be reduced by a up to $\sim$90% [9], meaning
straightforward implementation.

Here, we experimentally demonstrate a real-time $m$-CAP system for the first
time over a VLC system using white LEDs. Two field programmable gate arrays
(FPGAs) are used in this real-time demonstration to ensure fair
synchronisation and BER measurement across two independent clocks. We show
that transmission speeds up to $\sim$30 Mb/s can be supported with a 20%
forward error correction (FEC) code, and $\sim$20 Mb/s with a 7% FEC code.
These rates are sufficient to support full high-definition television (HDTV)
transfer, as will be demonstrated, across real VLC links using off-the-shelf
LEDs.

##  II Experimental Real Time Demonstrator Setup

The system block diagram is shown in Fig. 1. Details of the generation of
$m$-CAP signals may be referred to in the literature, due to space
considerations, in [2, 5]. We tested $m$-CAP signals, varying from $m=1$ to
$m=10$, using the 4-, 16- and 64-QAM constellations for each subcarrier, with
a fixed bandwidth of 6.5 MHz and roll-off factor of 0.15 as used in [2]. The
incoming information is modulated into the $m$-CAP signal format inside the
transmitter FPGA, which is a Xilinx Kintex 7 (410T) contained within a
National Instruments universal software radio peripheral reconfigurable
input/output (USRP-RIO) 2953. The FPGA outputs the signal to an Ettus Research
LFTX digital-to-analogue converter (DAC) daughtercard, which has an analogue
bandwidth up to 30 MHz. The signal is then passed through a Texas Instruments
THS3202 amplifier with 4 times gain, before superimposing on a 250 mA bias
current.

The biased signal that intensity modulates the Osram Golden Dragon LED
(optoelectronic characteristics can be referred to in [10]) for transmission
over a 0.5 m link, which is fixed to maintain a compact demonstrator, however
operation can also be supported at 1 m distances. No bulk optics, such as
lenses, are used and a Thorlabs PDA100A2 packaged receiver is used, which
consists of a silicon $p$-$i$-$n$ photodiode and an in-built transimpedance
amplifier. The amplifier output is further amplified ($10\times$) by a Texas
Instruments THS3202 amplifier to maximize symmetrical swing at the receiver
input. The receiver is a National Instruments USRP-RIO 2943 with the same
Xilinx Kintex 7 FPGA on-board, but running independently from the transmitter.
An Ettus Research LFRX analogue-to-digital converter (ADC) daughtercard (0-30
MHz) is used to digitise the data and direct it to the FPGA, for demodulation
and BER measurements. Synchronisation is obtained using the Schmidl and Cox
[11] method while the demodulation of $m$-CAP signals may be referred to in
[2, 5]. A photograph of the experimental setup is shown in Fig. 2.

Figure 1: System block diagram (simplified) Figure 2: Photograph of
demonstrator test setup: (A) transmit USRP-RIO; (B) transmitter amplifier; (C)
transmit driver and LED; (D) photodetector; (E) receiver amplifier and (F)
receiver FPGA

##  III Results

The total accumulated BER is shown in Fig. 3, and $>10^{6}$ symbols were
transmitted. A clear trend is evident; a low order of $m$ indicates a high
BER, which reduces as $m$ increases. The reason for this is due to inter-
symbol interference (ISI) caused by attenuation of high frequencies as
documented in [2]. However, there is another contributor to this, which is the
slight impact of fluorescent light bulbs present in the laboratory. A dark
environment is unrealistic in a real-world scenario, and hence, a 500 kHz
frequency offset was introduced to the signals allow co-existence of
fluorescent bulbs alongside the VLC system, as illustrated in Fig. 4, which
resulted in minor intermodulation. This effect reduces with increasing m as
the aggregated roll-off at the bandwidth edges becomes sharper. The
transmission rate is sufficient to demonstrate HDTV streaming.

Figure 3: Measured real time BER performance of 4-. 16- and 64-QAM.
Transmission can be supported with 4- and 16-QAM with a 7% FEC code at 11.3
Mb/s and 22.61 Mb/s, respectively, and with a 20% FEC code for 16-QAM at 33.91
Mb/s. Figure 4: The received electrical signal spectrum for a 5-CAP system,
and inset, the flourescent component (0-500 kHz).

##  IV About the Demonstrator and Conclusion

This demonstration is a self-contained and flexible test environment that
supports HDTV video streaming in real time. Modulation formats can be adapted
in real-time, albeit with an interruption in service before data recovery.
Attendees will be able to block physically the optical path and observe the
impact of a degradation in BER on the video quality. Wireless internet access
will also be available via the VLC system through the demonstrator, which
reports a real-time $m$-CAP VLC system, for the first time.

## References

  * [1] F. M. Wu, C. T. Lin _et al._ , “Performance comparison of OFDM signal and CAP signal over high capacity RGB-LED-based WDM visible light communication,” _IEEE Photonics Journal_ , vol. 5, no. 4, 2013.
  * [2] P. A. Haigh, A. Burton _et al._ , “A multi-CAP visible-light communications system with 4.85-b/s/Hz spectral efficiency,” _IEEE Journal on Selected Areas in Communications_ , vol. 33, no. 9, pp. 1771–1779, Sept 2015.
  * [3] Y. Wang, L. Tao _et al._ , “8-Gb/s RGBY LED-based WDM VLC system employing high-order CAP modulation and hybrid post equalizer,” _IEEE Photonics Journal_ , vol. 7, no. 6, Dec 2015.
  * [4] H. Li, X. Chen _et al._ , “High bandwidth visible light communications based on a post-equalization circuit,” _IEEE Photonics Technology Letters_ , vol. 26, no. 2, pp. 119–122, Jan 2014.
  * [5] M. I. Olmedo, T. Zuo _et al._ , “Multiband carrierless amplitude phase modulation for high capacity optical data links,” _Journal of Lightwave Technology_ , vol. 32, no. 4, pp. 798–804, Feb 2014.
  * [6] Z. Li, C. Zhang _et al._ , “A real-time high-speed visible light communication system based on RGB-LEDs,” in _2017 IEEE International Symposium on Broadband Multimedia Systems and Broadcasting (BMSB)_ , June 2017\.
  * [7] F. Wang, J. Yin _et al._ , “Real-time bi-directional 800mbs visible light communication system utilizing commercial leds,” in _Asia Communications and Photonics Conference 2016_. OSA, 2016, p. AF3A.5.
  * [8] J. L. Wei, C. Sanchez, and E. Giacoumidis, “Fair comparison of complexity between a multi-band CAP and DMT for data center interconnects,” _Opt. Lett._ , vol. 42, no. 19, pp. 3860–3863, Oct 2017.
  * [9] P. A. Haigh and I. Darwazeh, “Demonstration of reduced complexity multi-band CAP modulation using Xia-pulses in visible light communications,” in _OFC 2018_ , March 2018, pp. 1–3.
  * [10] P. A. Haigh, P. Chvojka _et al._ , “Analysis of nyquist pulse shapes for carrierless amplitude and phase modulation in visible light communications,” _Journal of Lightwave Technology_ , vol. 36, no. 20, Oct 2018.
  * [11] T. M. Schmidl and D. C. Cox, “Robust frequency and timing synchronization for OFDM,” _IEEE Transactions on Communications_ , vol. 45, no. 12, pp. 1613–1621, Dec 1997.


A Farewell to Professor RNDr. Věra Trnková, DrSc.

J. Adámek

When in May 2018 Věra Trnková passed away, the mathematical community lost a
marvellous personality who had substantially influenced the generation in
which she was active as a scientist and teacher. Her lectures were full of her
enthusiasm and love for math. And she led her seminar in a wonderfully
inspiring manner for almost half a century – when her disease started to
prevent her going to the university, it was held in her flat. Her radiant
personality and her great enthusiasm made it a pleasure to collaborate with
her.

Věra Trnková was born in 1934, she studied mathematics at the Charles
University in Prague in 1952-1957 and continued there, at the Faculty of
Mathematics an Physics, with her doctoral studies supervised by Professor
Eduard Čech in 1957-1960. From 1960 until her emeritation she was employed at
that faculty. In 1961 she obtained title CSc (corresponding to PhD). For
political reasons she had to wait for reaching the higher scientific degree
DrSc until 1989 and the Full Professor position until 1991.

Besides research, she had a great love for the forest. Her father was a
forester, and she passionately collected mushrooms and antlers (of which the
walls of her study were full). She dreamed of hunting, but never made any
practical steps in that direction. In her last couple of years she gave up
research and wrote short stories and two volumes of personal memories. Věra
could also make nice drawings, e.g. the above cat symbol for the conference
Categorical Topology held in 1988 in Prague.

Věra had a very wide scope of interests in research, from General Topology
through Category Theory to Theoretical Computer Science. I will try to
indicate some of her best results. But I admit that my choice will be a
substantial reduction of all that Věra achieved in her more than 160 reseach
articles and the two monographs she co-authored.

The first papers of Věra’s were devoted to General Topology and were much
influenced by Profesor Miroslav Katětov. Surprisingly, the most widely cited
topological article of Věra’s is her very first publication (in Russian and
published under her maiden name Šedivá), based on her master thesis, see [11].
General Topology remained her great love all through her scientific career.
For example, a series of her publications applied a very special continuum (a
connected, compact Hausdorff space) constructed by H. Cook in 1967 and
sketched on four pages of his article [3]. When Věra decided ten years later
to unravel all the details of Cook’s construction, she virtually spent several
months doing nothing else. As a result, she presented a detailed proof of
fifty(!) tightly written pages in her joint monograph [7]. Using Cook’s
continuum, Věra proved a number of really astonishing results. For example:
every monoid is isomorphic to the monoid of all non-constant continuous self-
maps of a regular space on which all continuous real functions are constant
[16].

Věra was in the late 1950’s one of the first mathematicians in Czechoslovakia
to recognize the importance of category theory. Her first papers in that realm
were devoted to formal completions of categories. But soon her interest
shifted to embeddings of concrete catgeories (i.e., those with a faithful
functor to $\emph{S}et$). This was influenced by the research reported by
Zdeněk Hedrlín and Aleš Pultr at the Topology Seminar (led by Miroslav
Katětov), see [4]. The question was which concrete category is ’universal’ in
the sense that every concrete category can be fully embedded into it? For
example, the category of topological spaces and local homeomorphisms and that
of unary algebras on two operaions were proved to be universal, assuming
certain set-theoretical assumptions. Later Věra concentrated on embeddings
into the category of topological spaces and continuous maps. Here the fact
that constant maps are always morphisms led her to introducing the _almost
universal_ categories $\mathcal{K}$: this means that every concrete category
has an almost full embedding into $\mathcal{K}$. That is, an embedding $E$
such that $Ef$ is non-constant for every morphism $f$ and, conversely, every
non-constant morphism between objects of $E[\mathcal{K}]$ has the form $Ef$
for a unique $f$. Věra proved in [14] that the category of compact Hausdorff
spaces is, under some set-theoretical assumptions, almost universal. (Without
any set-theoretical assumptions all algebraic categories have an almost full
embedding into the category of paracompact Hausdorff spaces, as one of the
most brilliant doctoral students of Věra’s, Václav Koubek, proved [5].) In
Věra’s joint monograph with Aleš Pultr [7] an impressive theory of embeddings
of concrete categories is presented.

Another passion of Věra’s were set functors. A beautiful theory of their
properties was presented by her in the early 1970’s, see [12, 13], and she
continued studying and applying them throughout the following decades. One of
her results that has been particularly often used recently is that for every
set functor $F$ there exists a functor $G$ preserving finite intersections
that agrees with $F$ on all non-empty sets. Nowadays $G$ is called the
_Trnková hull_ of $F$. Věra and members of her seminar applied her insight to
the theory of algebras and automata for a given set functor (or, more
generally, an endofunctor of a category where the underlying objects ’live’).
Věra’s beautiful proof that a set functor $F$ generates a free monad iff it
has arbitrarily large prefixed points (i.e. sets $X$ of cardinality larger or
equal to that of $FX$) was generalized to arbitrary endofunctors in [20]. An
important, often cited paper [18] of Věra’s concerns the behaviour of
nondeterministic automata. Results obtained in Věra’s seminar on automata and
algebras for endofunctors are collected in our joint monograph [1]. I remember
with pleasure the time we worked on this book; we often had fierce
discussions, but invariably we would find by the next day a solution that we
both found good. Jan Reiterman, another of the brilliant doctoral students of
Věra, devoted his dissertation to iterative constructions of algebras. One of
his results, known these days as the Reiterman Theorem, is widely used in the
Theoretical Computer Science: it characterizes classes of finite algebras that
are pseudovarieties, i.e. closed under subalgebras, regular quotients and
finite products, see [8]. I remember how happy Věra was when Jan presented
this result in her seminar.

A realm in which Věra also achieved astounding results is that of isomorphisms
of products of algebras and spaces. For example in [19] she constructed a
metric space $X$ homeomorphic to its power $X^{2}$ and uniformly homeomorphic
to $X^{4}$ but not to $X^{2}$ and at the same time isometric to $X^{8}$ but
not to $X^{4}$. A famous result of hers is that whenever a countable Boolean
algebra $B$ is isomoprhic to the coproduct $B+B+B$, it is also isomorphic to
$B+B$. Her paper [17] was reprinted in the Handbook of Boolean Algebras [6]
where R.S. Pierce comments: ’It was a major surprise when Trnková showed that
the multiplicative analog of the cube problem has a positive solution in BA’.
She proved with coauthors that every finite abelian group has a representation
by both products and coproducts of boolean algebras. That is, a collection
$B_{x}$ of pairwise non-isomorphic boolean algebras is given, indexed by
elements $x$ of the group, with $B_{x+y}$ always isomorphic to $B_{x}\times
B_{y}$ (see [2]) or to $B_{x}+B_{y}$ (see [21]), respectively. For _all_
commutative semigroups Věra proved such a representation by products of metric
spaces in [19]. There was in fact much much more Věra proved about such
representations, including a series of articles on clones represented by
products in various categories. A number of these results were obtained in
collaboration with Jiří Sichler, see e.g. [9,10].

Věra had at least eight ’doctoral children’ (I do not use the expression PhD
students since the title was called CSc, a candidate of sciences, until the
1990s). In the current issue they are represented by Libor Barto and myself.
Two names that are sorely missing are those of Koubek and Reiterman: they
passed away before Věra. It seems impossible to find out even a good
approximation of the number of her doctoral descendants; her ’doctoral
grandchildern’ are represented in the present issue by my PhD students Lurdes
Sousa and Stefan Milius, and her ’great-grandchildern’ by Thorsten Wißmann, a
PhD student of Milius. Věra had close contacts with the group of General
Topology in Moscow, represented here by Alexander Vladimirovich
Archangel’skii, and with a number of groups all over the world. I am happy
about the number of colleagues and friends who have contributed to this
volume.

I was entrusted to organize the refereeing process for the articles in the
present volume. The article I co-author followed the standard submission
procedure of the journal. I am grateful to the Executive Editor Zdenka
Crkalová for her very pleasant cooperation.

REFERENCES

[1] J. Adámek and V. Trnková, Automata and algebras in a category, Kluwer
Academic Publ., Dordrecht 1989

[2] J. Adámek, V. Koubek and V. Trnková, Sums of boolean spaces represent
every group, Pacific J. Mathem. 61 (1975), 1-6

[3] H. Cook, Continua which admit only the identity mapping onto non-
degenerate subcontinua, Fund. Math. 69 (1967), 241-249

[4] Z. Hedrlín, A. Pultr and V. Trnková, Concerning a categorical approach to
topological and algebraic theories, Proceedings of the Second Prague
Topological Symposium, Prague 1966, 176-181

[5] V. Koubek, Each concrete category has a representation by
$T_{2}$-paracomact spaces, Comment. Math. Univ. Carolinae 15 (1974), 655-663

[6] J. D. Monk and R. Bonnet (ed.), Handbook of Boolean algebras, North
Holland 1988

[7] A. Pultr and V. Trnková, Cominatorial, algebraic and topological
representations of groups, semigroups and categories, Academia Praha 1980

[8] J. Reiterman, The Birkhoff theorem for finite algebras, Algebra Univeralis
14 (1982), 1-10

[9] J. Sichler and V. Trnková, Disciplined spaces and centralizer clone
segments, Canad. J. Math 48 (1996), 1296-1323

[10] J. Sichler and V. Trnková, Continuous maps of products of metrizable
spaces, Houston J. Math. 26 (2000), 417-450

[11] V. Šedivá, On collectionwise normal and hypercompact spaces (in Russian),
Czechoslovak Math. J. 9 (1959), 50-62

[12] V. Tnková, Some properties of set functors, Comment. Math. Univ.
Carolinae 10 (1969), 323-352

[13] V. Tnková, Descriptive classification of set functors I, II, Comment.
Math. Univ. Carolinae 12 (1971), 143-175 and 345-357

[14] V. Trnková, Non-constant continuous mappings of metric or compact
Hausdorff spaces, Comment. Math. Univ. Carolinae 13 (1972), 283-295

[15] V. Trnková, Representation of semigroups by products in a category, J. of
Algebra 34 (1975), 191-204

[16] V. Trnková, Categorical aspects are useful in topology, Lecture Notes
Mathem. 609, Springer Verlag 1977, 211-225

[17] V. Trnková, Isomorphisms of sums of countable Boolean algebras, Proc.
Amer. Math. Soc. 80 (1980) 389-392

[18] V. Trnková, General theory of relational automata, Fund. Informaticae 3
(1980) 189-233

[19] V. Trnková, Products of metric, uniform and topological spaces, Comment.
Math. Univ. Carolinae 31 (1990), 167-180

[20] V. Trnková, J. Adámek, V. Koubek and J. Reiterman, Free algebras, input
processes and free monads, Comment. Math. Univ. Carolinae 16 (1975), 339-351

[21] V. Trnková and V. Koubek, Isomorphisms of sums of Boolean algebras, Proc.
Amer. Math. Soc. 66 (1977), 231-236


acmcopyright

# QUICKAR: Automatic Query Reformulation for Concept Location using
Crowdsourced Knowledge

Mohammad Masudur Rahman Chanchal K. Roy Department of Computer Science,
University of Saskatchewan, Canada  {masud.rahman<EMAIL_ADDRESS>
###### Abstract

During maintenance, software developers deal with numerous change requests
made by the users of a software system. Studies show that the developers find
it challenging to select appropriate search terms from a change request during
concept location. In this paper, we propose a novel technique–QUICKAR–that
automatically suggests helpful reformulations for a given query by leveraging
the crowdsourced knowledge from Stack Overflow. It determines semantic
similarity or relevance between any two terms by analyzing their adjacent word
lists from the programming questions of Stack Overflow, and then suggests
semantically relevant queries for concept location. Experiments using 510
queries from two software systems suggest that our technique can improve or
preserve the quality of 76% of the initial queries on average which is
promising. Comparison with one baseline technique validates our preliminary
findings, and also demonstrates the potential of our technique.

###### keywords:

Query reformulation, crowdsourced knowledge, semantic relevance, word co-
occurrence, adjacency list, Stack Overflow

††conference: ASE ’2016 Singapore

[500]Software and its engineering Software maintenance tools [500]Software and
its engineering Requirements analysis [300]Software and its engineering
Traceability [300]Software and its engineering Maintaining software

##  1 Introduction

Studies show that about 85%–90% of the total effort is spent in software
maintenance and evolution [3, 4]. During maintenance, software developers deal
with numerous change requests made by the users of a software system. Although
the users might be familiar with the application domain of the software, they
generally lack the idea of how a particular software feature is implemented in
the source code. Hence, the requests from them generally involve domain
related concepts (e.g., application features), and they are written in an
unstructured fashion using natural language texts. The developers need to
prepare appropriate search query from those concepts, and then identify the
relevant location(s) in the code to implement the requested change(s).
Unfortunately, preparing such a query is highly challenging and error-prone
for the developers [13, 5]. Based on a user study, Kevic and Fritz [13] report
that developers were able to suggest good quality search terms for only 12.2%
of the change tasks. Furnas et al. [5] suggest that there is a little chance
(i.e., 10%–15%) that developers guess the exact words used in the source code.
One way to assist the developers in this regard is to automatically suggest
helpful reformulations for the initially executed query.

Existing studies use relevance feedback from developers [6] or information
retrieval techniques [10], query quality [9, 8] and the context of query terms
within the source code [12, 23] in suggesting reformulated queries. Gay et al.
[6] make use of explicit feedback on document relevance from the software
developers, and then suggest reformulated queries using Rocchio’s expansion.
Haiduc et al. and colleagues [10, 7, 8, 11, 9] take quality of the query into
consideration, and suggest the best reformulation strategy for a given query
using machine learning. Howard et al. [12] analyze leading comments and method
signatures from the source code for mining semantically similar word pairs,
and then suggest reformulated query using those word pairs. While these above
techniques are reported to be novel or effective, they are also limited in
certain aspects. First, collecting explicit feedback from the developers could
be highly expensive, and such study [6] could also be hard to replicate.
Second, machine learning model of Haiduc et al. is reported to be performing
well in the case of _within-project_ training, and only 51–72 queries are
considered from each of the five projects for training and testing [10]. Given
such small dataset, the reported performance possibly could not be generalized
for large systems. Third, Howard et al. require the source code to be well
documented for the mining of word pairs, and hence, might not perform well if
the code is poorly documented [12]. Thus, we need a technique that is neither
subject to the training data nor the availability of comments in the source
code. One way to possibly overcome those concerns is to apply _crowd generated
knowledge_ in the reformulation of queries for concept location.

In this paper, we propose a novel technique–QUICKAR–that automatically
identifies semantically similar words to an initial query not only from
project source code but also from crowdsourced content of Stack Overflow Q & A
site, and then suggests a reformulated query. The technique collects adjacent
word lists from the programming questions of Stack Overflow for any two terms,
and determines their semantic similarity by comparing their corresponding
adjacency lists [24]. In short, QUICKAR not only follows the essence of a
_nearest neighbour classifier_ [16] in the context of natural language texts
but also harnesses the technical corpus developed by a large crowd over the
years in estimating _semantic similarity_ or _relevance_. Such simple but
intuitive estimation of semantic relationship could be highly useful for
suggesting an alternative version of a given query. QUICKAR also addresses the
overarching _vocabulary mismatch problem_ [5]. First, Stack Overflow is
curated by a large crowd of four million technical users, and the millions of
questions and answers posted by them are a great source for technical
vocabulary (e.g., API names) [21]. Thus, QUICKAR mines semantically similar
words not only from a larger corpus (i.e., compared to a single project [23])
but also from a more appropriate vocabulary (i.e., compared to WordNet [22,
23]). Second, Rahman et al. [20] reported a significant overlap (i.e., 73%)
between the vocabulary of real life code search queries and that of question
titles from Stack Overflow. QUICKAR mines 500K programming related questions
from Stack Overflow carefully, and reaps the benefit through meaningful
vocabulary extension. To the best of our knowledge, no existing studies apply
crowdsourced knowledge yet in the reformulation of queries for concept
location which makes our technique novel.

Experiments using 510 concept location queries from two subject systems–ecf
and eclipse.pde.ui–suggest that our technique can improve or preserve the
quality of 76% (i.e., improves 66% and preserves 10%) of the initial queries
through reformulation which is promising according to relevant literature [10,
6]. Comparison with one baseline technique–Rocchio’s expansion [10,
1]–validates our preliminary findings, and also demonstrates the potential of
our technique for query reformulation. While the preliminary findings are
promising, they must be validated using further experiments. In this paper, we
make the following contributions:

  * •

Construction of a word adjacency list database by mining 500K questions from
Stack Overflow for the estimation of semantic similarity or relevance between
words.

  * •

A novel technique that suggests helpful reformulations for a given query for
concept location by leveraging crowdsourced knowledge from Stack Overflow.

##  2 Motivating Example

Software change requests and project source code are often written by
different people, and they use different vocabularies to describe the same
technical concept. Concept location community has termed it as _vocabulary
mismatch problem_ [5, 10]. Table 1 shows three different questions from Stack
Overflow that are marked as _duplicates_ or _linked_ by the users of the site.
These questions use three different verbs– _‘create’, ‘cause’_ and _‘track’_ –
to describe the same programming issue– _locating memory leaks_ , and this can
be considered as a real life parallel for vocabulary mismatch issue. Although,
these verbs have different semantics in English literature, they share the
same or almost similar semantic in this technical literature– programming
questions [23]. More interestingly, their semantic similarities can also be
approximated from their adjacent word lists. In graph theory, two nodes are
considered to be _connected_ if they share the same neighbour nodes [16]. We
adapt that idea for natural language texts, and apply to the estimation of
semantic connectivity between words. The co-occurred word lists (i.e.,
sentence as a context unit) of _‘create’, ‘cause’_ and _‘track’_ –{_memory,
leak, Java_}, {_easiest, way, memory, leak, Java_} and {_down, memory, leak,
garbage, collection, issues, Java_}–respectively share multiple words among
themselves. Thus, comparison between any two such lists can potentially
approximate the semantic similarity or relevance of their corresponding words
[24]. In this research, we apply the above methodology in semantic similarity
estimation, and then use the similar terms for the reformulation of an initial
query.

Figure 1: Proposed technique for query reformulation–(a) Construction of word
adjacency list database from Stack Overflow questions, and (b) Reformulation
of an initial query for concept location Table 1: Duplicate Questions from
Stack Overflow

ID | Title of Question
---|---
6470651 | Creating a memory leak with Java
4948529 | Easiest way to cause memory leak in Java?
1071631 | Tracking down a memory leak/garbage-collection issue in Java

##  3 QUICKAR: Query Reformulation using Crowdsourced Knowledge

Programming questions and answers from Stack Overflow were previously mined
for API elements [21, 20], Q & A dynamics [17, 14] or post suggestions [18,
19]. In this research, we make a novel use of such questions in query
reformulation for concept location. Since these questions contain unstructured
information, relevant items (i.e., potential alternative query term) should be
carefully extracted and then applied to query reformulation. We first
construct a database containing adjacent word list for each of the individual
words taken from the title of the questions, and then leverage that
information in suggesting reformulated queries. Fig. 1 shows the schematic
diagram of our proposed technique–QUICKAR–for query reformulation. Thus, our
technique can be divided into two major parts–(a) Construction of an adjacency
list database from Stack Overflow questions, and (b) Reformulation of an
initial query–as follows:

###  3.1 Construction of Adjacency List Database

Word co-occurrence is often considered as a proxy for semantic relevance
between words in natural language texts [15]. Yuan et al. [24] first propose
to use contextual words (i.e., word co-occurrence) from the programming
questions and answers of Stack Overflow in identifying semantically similar
software-specific word pairs. While they introduce the idea, we adapt that
idea for a specific software maintenance task–search query reformulation for
concept location. Given the significant overlap (i.e., 73%) between real life
code search queries and titles of Stack Overflow questions [20], we collect
the titles of 500K Java related questions from Stack Overflow using Stack
Exchange Data Explorer111http://data.stackexchange.com/stackoverflow. We check
for <java> tag in the tag list for identifying the Java related questions. We
perform standard natural language preprocessing (i.e., word splitting, stop
word removal), and turn each of those titles into a sequence of words (Step 3,
4, Fig. 1-(a)). We decompose each camel case word (e.g.,
GenericContainerInstantiator) into separate tokens (e.g., Generic, Container,
Instantiator), and apply a standard list222https://code.google.com/p/stop-
words/ for stop word removal. It should be noted that we avoid stemming to
ensure a meaningful reformulation of the query. After preprocessing step, we
found a large set of 81,394 individual words (i.e., 2,660,257 words in total)
from our collected titles. Given that source code of a software project is
often authored by a small group of developers, such a large set could possibly
_extend_ the vocabulary of the code. We then use a _sliding window_ of window
size = 2 to capture co-occurred words from the titles [15], and construct an
adjacency list for each of the individual words. For example, based on Table
1, the adjacency list for the word _‘memory’_ would be–{_creating, leak,
cause, down_}. We collect adjacency list for each of the 81,394 words where
each list contains 21 co-occurred words on average (Step 5, 6, Fig. 1-(a)).
These lists comprise our database which is later accessed frequently for query
reformulation.

###  3.2 Reformulation of an Initial Query

Fig. 1-(b) shows the schematic diagram and Algorithm 1 shows the pseudo code
for our query reformulation technique–QUICKAR. We collect semantically similar
words (i.e., with initial query) from two different but relevant
sources–project source code and Stack Overflow questions, and then reformulate
a given query for concept location. We discuss different intermediate steps
involved in such reformulation as follows:

Collection of Candidate Terms: Existing literature mostly relies on the source
code of a software system [10, 12, 23] or WordNet [22] for reformulated query
suggestion. Unfortunately, source code often might not contain a rich
vocabulary [12] and WordNet might also not be appropriate for technical words
[22, 24]. We thus collect candidate terms for possible query expansion not
only from the source code but also from another technical
literature–programming questions of Stack Overflow (Line 6–Line 8, Algorithm
1). In the case of project source, we perform code search using the reduced
keywords ($K$) from the initial query ($Q$). We use _Apache Lucene_ [18], a
popular implementation of Vector Space Model (VSM), for code search, and then
collect the Top-5 (i.e., cut off) retrieved documents as the source for
candidate terms. The cut-off value is chosen based on iterative experiments.
We perform standard natural language preprocessing on those documents, and
extract each of the terms as the reformulation candidates ($T_{p}$) (Step 3–5,
Fig. 1-(b)). Relevant literature [10] also follows the same procedure for
candidate term selection. In the case of questions from Stack Overflow, we
collect such words as candidates ($T_{so}$) that frequently co-occurred in
those questions with the keywords from the initial query. The underlying idea
is that if two words frequently co-occur in various technical contexts, they
share their semantics and thus, are possibly semantically relevant [15, 24].
We use our adjacency list database (Section 3.1) for identifying the second
set of candidates.

Algorithm 1 Query Reformulation using Crowd Knowledge

1:procedure QUICKAR($Q$)$\triangleright$ $Q$: initial search query

2: $Q^{\prime}\leftarrow$ {}$\triangleright$ reformulated search query

3: $\triangleright$ collecting keywords from the initial search query

4: $K\leftarrow$ collectKeywords($Q$)

5: $K\leftarrow$ reduceKeywords($K$)

6: $\triangleright$ collecting candidate terms

7: $T_{p}\leftarrow$ getCandidateTermsFromProject($K$)

8: $T_{so}\leftarrow$ getCandidateTermsFromSO($K$)

9: $\triangleright$ estimating semantic similarity of the candidates

10: for Candidate $T_{i}$ $\in$ $T_{p}$ do

11: $Adj_{T_{i}}\leftarrow$ getAdjacencyListFromDB($T_{i}$)

12: for Keyword $K_{j}\in K$ do

13: $Adj_{K_{j}}\leftarrow$ getAdjacencyListFromDB($K_{j}$)

14: $\triangleright$ contextual similarity between words

15: $S_{cos}\leftarrow$ getCosineSimilarity($Adj_{T_{i}},Adj_{K_{j}}$)

16: $R_{p}[T_{i}].score\leftarrow R_{p}[T_{i}].score+S_{cos}$

17: end for

18: end for

19: for Candidate $T_{i}$ $\in$ $T_{so}$ do

20: for Keyword $K_{j}\in K$ do

21: $\triangleright$ co-occurrence between words

22: $S_{cof}\leftarrow$ getCo-occurrenceFreq($T_{i},K_{j}$)

23: $R_{so}[T_{i}].score\leftarrow R_{so}[T_{i}].score+S_{cof}$

24: end for

25: end for

26: $\triangleright$ ranking and selection of candidates

27: $SR_{Top_{p}}\leftarrow$ selectTopK(sortByScore($R_{p}$))

28: $SR_{Top_{so}}\leftarrow$ selectTopK(sortByScore($R_{so}$))

29: $R\leftarrow$ selectiveCombine($SR_{Top_{p}},SR_{Top_{so}}$)

30: $\triangleright$ reformulate the initial query

31: $Q^{\prime}\leftarrow$ selectiveReformulate($Q,K,R$)

32: return $Q^{\prime}$

33:end procedure

Estimation of Semantic Similarity or Relevance: Since we target to reformulate
a query using meaningful alternatives, we need to choose such terms from the
candidates that are either semantically similar or highly relevant to the
initial query. Yuan et al. use contextual words (i.e., based on co-occurrence)
from Stack Overflow for automatically identifying similar software-specific
words. In the context of query reformulation for software maintenance, we
similarly apply adjacency list to the estimation of semantic relevance between
two terms. We collect adjacency list (i.e., from the adjacency list database)
for each of the candidate terms and the keywords of the initial query, and
estimate their similarities using _cosine similarity_ measure ($S_{cos}$).
Cosine similarity is frequently used in information retrieval for determining
textual similarity between two given documents. It returns a value between
zero (i.e., completely dissimilar) and one (i.e., completely similar). Thus, a
candidate term achieves score only if it shares its context (i.e., adjacent
word list, $Adj_{T_{i}}$) with that (i.e., $Adj_{K_{j}}$) of the keywords
across various questions from Stack Overflow. QUICKAR iterates this process
for each of the candidates ($T_{p}$), and accumulates their similarity scores
against the keywords (Line 9–Line 18, Algorithm 1, Step 6, Fig. 1-(b)). We
also determine co-occurrence frequency ($S_{cof}$) between each candidate term
and each keyword in the titles of Stack Overflow questions [20], and derive
another set of scores for the candidates ($T_{so}$) (Line 19–Line 25,
Algorithm 1, Step 6, Fig. 1-(b)). Finally, we end up with two sets of
candidates (i.e., collected from two different sources), and QUICKAR
determined their relevance to the initial query in terms of their context or
direct co-occurrences in the Stack Overflow questions.

Table 2: Experimental Dataset

Subject System | Release ID | #Files | #Methods | #Queries
---|---|---|---|---
ecf | 170_170 | 5,781 | 21,447 | 222
eclipse.pde.ui | I20151110-0800 | 7,579 | 31,468 | 288
Total | – | 13,360 | 52,915 | 510

Candidate Term Ranking & Top-K Selection : Once relevance estimates for both
candidate sets–$R_{p}$ and $R_{so}$–are collected, they are ranked based on
their estimates. We then collect the Top-$K=5$ candidates from each ranked
list, selectively choose the top candidates ($R$) from both lists, and then
treat them as similar or relevant to the initial query ($Q$) (Line 26–Line 29,
Algorithm 1). In particular, the _nominal terms_ (i.e., nouns) from both lists
are chosen [20]. Thus, we select such terms for reformulation that co-occur
with the initial query keywords not only in the project source but also in the
titles of the questions from Stack Overflow.

Query Reduction & Expansion: We apply both reformulation strategies–
_reduction_ and _expansion_ –to the initial query [1]. In the case of
_reduction_ , we apply a conservative strategy as was also applied by Haiduc
et al.. We discard the keywords from initial query that either are _non-
nominal_ [20] or occurred in more than 25% of the documents of the project
corpus. Such keywords are not specific enough and thus, are not useful for
document retrieval [10]. In the case of _expansion_ , we apply the
semantically similar or relevant terms ($R$) returned by QUICKAR to the query.
If there exist $M$ terms after the reduction step (i.e., Line 5), we append
$(10-M)$ relevant terms from $R$ to the query, and prepare an alternative
query ($Q^{\prime}$) (Line 29–Line 32, Algorithm 1, Step 7, 8, Fig. 1-(b)). We
also decompose each camel case term into separate tokens, and preserve both
the separate and the camel case terms into the reformulated query [10]. It
should be noted that if our reduction step already improves the initial query,
we conveniently avoid its expansion.

Working Example: Let us consider a change request (ID: 408030) from ecf
project. We select title of the request– _“RestClientService ignores content
encoding"_ –as the initial search query for the request, as was also used by
the existing literature [10]. The query returns the first relevant document
(i.e., Java class) at 44th position when tested using _Apache Lucene_. On the
other hand, QUICKAR returns the reformulated query– _“Rest Client Service
RestClientService content Web Java Executor WebService Http"_ –that returns
the same relevant document at 1st position in the search result. Please note
that our technique expands the initial query using several relevant terms such
as _“WebService", “Executor"_ and _“Http"_ and also discards some terms such
as “ _encoding_ " or “ _ignore_ ", which improved the query. We also expand
the query simply using terms from project source– _“RestClientService ignores
content encoding call container service http test"_ –that returns the document
at 11th position. This clearly demonstrates that candidates from the source
code of a project might always not be sufficient, and crowd generated
vocabulary from Stack Overflow can complement them, and thus, can assist in
effective query reformulation.

Table 3: Performance of QUICKAR

System | #Queries | Improvement | Worsening | Preserving
---|---|---|---|---
#Improved | Mean | Q1 | Q2 | Q3 | Min. | Max. | #Worsened | Mean | Q1 | Q2 | Q3 | Min. | Max. | #Preserved
ecf | 222 | 159 (71.62%) | 194 | 10 | 27 | 156 | 1 | 2335 | 41 (18.47%) | 764 | 67 | 245 | 1173 | 18 | 4330 | 22 (9.90%)
pde.ui | 288 | 177 (61.46%) | 219 | 17 | 51 | 171 | 1 | 4766 | 83 (28.82%) | 558 | 93 | 244 | 630 | 17 | 2996 | 28 (9.72%)
| Total=510 | Avg=66.54% |  |  |  |  |  |  | Avg=23.65% |  |  |  |  |  |  | Avg=9.81%

pde.ui=eclipse.pde.ui, Mean=Mean rank of first relevant document in the search
result, Qi= Rank value for $i^{th}$ quartile of all result ranks

##  4 Experiment

One of the most effective ways to evaluate a query reformulation technique is
to check whether the reformulated query improves the search results or not. We
define improvement of search results as the bubbling up of the first relevant
document to the top positions of the result list [10]. That is, a good
reformulation of query provides a better rank than a baseline query for the
first relevant document. We conduct experiments using 510 change requests from
two Java subject systems of _Eclipse_ –ecf and eclipse.pde.ui– and a well
known search engine– _Apache Lucene_ [18, 10]. We also compare with a baseline
technique for query reformulation to validate our findings. In particular, we
attempt to answer the following research questions using our experiments:

  * •

RQ1: How does QUICKAR perform in the reformulation of a query for concept
location?

  * •

RQ2: Can crowdsourced knowledge from Stack Overflow improve a given query
significantly?

  * •

RQ3: How does QUICKAR perform compared to the baseline technique for query
reformulation?

###  4.1 Experimental Dataset & Corpus

Dataset Collection: Table 2 shows details of our selected subject systems. We
first collect the _RESOLVED_ change requests (i.e., bug reports) from
_BugZilla_ for each of the selected systems. Then we identify such commits
that implemented those requests in their corresponding _GitHub_ repositories.
We consider a commit as _eligible_ only if its title contains a specific
request identifier (e.g., Bug: 408030). This practice is common for relevant
literature for evaluation [2]. The step provides 495 and 542 requests from ecf
and eclipse.pde.ui respectively. We also collect _change set_ from each of the
identified commits which are later used as the _solutions_ for the
corresponding change requests. We then consider title of each request as the
baseline query, and identify such queries that return their first relevant
results with poor rank (i.e., $rank$>10). That is, the baseline query needs
reformulation for returning a better rank. This filtration step left us with
222 and 288 baseline queries from ecf and eclipse.pde.ui respectively for the
experiments.

Corpus Preparation: Unlike an unstructured natural language document, a source
code document contains items beyond regular texts such as _classes,
interfaces, methods_ and _constructors_. One should consider such structures
for effective retrieval of the source documents from a project. We thus
decompose each Java document into methods, and consider each of those methods
as a single document of the corpus. This step provides 21,447 and 31,468 Java
methods from ecf and eclipse.pde.ui respectively. We collect these methods
using Javaparser333https://github.com/javaparser/javaparser, and apply natural
language preprocessing to them. In particular, we remove all punctuation
marks, Java programming keywords and English stop words from the body and
signature of the method, and also decompose each camel case token into
individual tokens.

###  4.2 Evaluation of QUICKAR

We execute each of our reformulated queries and baseline queries from each
subject system with _Apache Lucene_ , and compare their topmost ranks for
evaluation. We identify the queries that were improved, worsened or preserved
based on those ranks. Table 3 reports the outcome of our preliminary
investigation. On average, QUICKAR was able to improve 66% of the baseline
queries while preserving the quality of 10% which are highly promising
according to relevant literature [10, 6, 12]. We see that QUICKAR can return
the top results within the 10th position for 25% of 159 requests from ecf
system. It also performs similarly for eclipse.pde.ui, and returns the top
results within the 17th position. One might argue about the verbatim use of
the title of a change request as the baseline query. However, we also
experimented with preprocessed version (i.e., stop word removal, camel case
decomposition) of the title. We found that the preprocessing step discarded
important information, and did not provide much improvement in the query
quality, which possibly justifies our choice about baseline query. Thus, to
answer RQ1, our proposed technique for query reformulation–QUICKAR–improves or
preserves 76% of the 510 baseline queries which is promising.

Table 4: Role of Crowdsourced Knowledge from SO

Technique | Improved | Worsened | Preserved
---|---|---|---
Baseline query (preprocessed) | 17.84% | 9.90% |  72.27%
QUICKARP | 49.15% | 48.41% | 2.44%
QUICKARSO | 47.83% | 49.91% | 2.27%
QUICKARred | 55.55% | 24.46% | 19.99%
QUICKARALL |  66.54% | 23.65% |  9.81%

We investigate how different reformulation decisions influence the end
performance of our technique, and Table 4 reports our findings. We first
experimented using a preprocessed version of the baseline queries, and found
that the preprocessing step did not improve the queries much (i.e., only 18%
improvement). Since candidate terms for reformulation are extracted from both
project source code and Stack Overflow questions, we need to examine their
impact in the reformulated queries. When we rely solely on source code,
QUICKARP can improve 49% of the queries but degrades the quality of 48%.
Although the candidate terms from Stack Overflow questions alone might not be
sufficient (i.e., QUICKARSO improves 48% and degrades 50%), they definitely
can complement the candidate terms from the project source which leads to
overall query quality improvement (i.e., QUICKARALL improves 66%). We also
performed _Mann Whitney U (MWU)_ -test on the provided ranks by QUICKARP and
QUICKARALL, and found that QUICKARALL returns the results at significantly
higher ranks (i.e.,  _p-values_ 0.007<0.05 and 0.001<0.05 for ecf and
eclipse.pde.ui respectively, Table 6) in the result list. The negative _mean
rank difference_ (MRD) in Table 6 suggests that QUICKARALL returns the results
at relatively closer to the top of the list than the counterpart, i.e.,
_extent of result rank improvement_. Thus, to answer RQ2, crowdsourced
knowledge from Stack Overflow questions can significantly improve the quality
of a baseline query during reformulation.

Since QUICKAR involves two steps during query reformulation – _reduction_ and
_expansion_ , an investigation is warranted on how these two steps impact the
end performance. According to our preliminary investigation, the reduction
step (i.e., QUICKARred) dominates over expansion step especially with ecf
system. One possible explanation could be that we used a smaller version of
the adjacency list database constructed from 50,000 (i.e., 10%) questions from
the dataset. Since accessing a large database is time-consuming, we made this
feasible choice during experiment. However, further investigation and
experiments are essential to mitigate such concern which we consider as a
future work. In short, the potential of crowdsourced knowledge is yet to be
explored.

Table 5: Comparison with Baseline Technique

Technique | System | Improved | Worsened | Preserved
---|---|---|---|---
Rocchio’s | ecf | 39.64% | 59.46% | <1.00%
Expansion [1] | pde.ui | 40.63% | 59.38% | 0.00%
QUICKARP | ecf | 53.15% | 43.69% | 3.15%
pde.ui | 45.14% | 53.13% | 1.74%
QUICKARALL | ecf |  71.62% | 18.47% |  9.90%
pde.ui |  61.46% | 28.82% |  9.72%

pde.ui=eclipse.pde.ui

Table 6: Result of Mann Whitney U-Tests

Technique pair | ecf | eclipse.pde.ui
---|---|---
p-value | MRD | p-value | MRD
QUICKARALL vs. QUICKARP |  0.007<0.05 | -248 | <0.001 | -369
QUICKARALL vs. QUICKARSO | 0.115>0.05 | -109 | <0.001 | -253
QUICKARALL vs. Rocchio [1] | <0.001 | -388 | <0.001 | -332

MRD= Mean Rank Difference

###  4.3 Comparison with Baseline Technique

Although the conducted evaluation demonstrates the potential of our proposed
technique–QUICKAR, we still investigate to at least partially validate our
performance. We compare with a baseline technique–Rocchio’s expansion [1,
10]–that is reported to be effective for query reformulation. Rocchio’s method
first collects candidate terms from the Top-K (i.e., $K=5$) source code
documents returned by a baseline query. Then, it selects the most important
candidate terms ($t$) for reformulation by calculating their _TF-IDF_ in each
of those Top-K documents ($D$) as follows:

$Rocchio(t)=\sum_{d\in R}TFIDF(t,d)$

We implemented Rocchio’s method in our working environment, experimented on
the same corpus and applied similar natural language preprocessing. Table 5
reports the comparative analysis between our technique and Rocchio’s method.
We see that our technique can improve 60%–70% of the baseline queries from
each of the subject systems whereas such measure for Rocchio’s method is close
to 40%. More importantly, QUICKAR degrades less number of queries compared to
its counterpart. While Rocchio’s method worsened the quality of 60% of the
baseline queries during reformulation, such measure for QUICKAR is between 18%
to 29%. We also performed _Mann Whitney U_ -test on the returned result ranks
from both techniques, and found that QUICKAR provides significantly better
ranks (i.e.,  _p-values_ <0.001 and <0.001 for ecf and eclipse.pde.ui
respectively, Table 6) than Rocchio’s expansion. We also compared using a
equivalent variant of our technique–QUICKARP, and found that the variant still
performed better than Rocchio’s method for both subject systems. All these
above preliminary findings clearly demonstrate the potential of our proposed
technique. Thus, to answer RQ3, our technique–QUICKAR–performs significantly
better than the baseline technique [1] in query reformulation for concept
location.

##  5 Related Work

Existing studies from the literature use relevance feedback from developers
[6] or information retrieval techniques [10], query quality [9, 8] or the
context of a query in the source code [12, 23] for suggesting query
reformulations. Gay et al. [6] capture explicit feedback on document relevance
from the software developers, and then suggest reformulated queries using
Rocchio’s expansion. Although their adopted methodology is meaningful,
capturing feedback from the developers could be expensive, and such study is
often difficult to replicate. Haiduc et al. and colleagues [10, 7, 8, 11, 9]
analyze quality of the query, and suggest the best reformulation strategy for
any given query using machine learning. Although their reported performance is
significantly higher, such performance might not be generalized for large
systems given their use of small dataset (i.e., only 51–72 queries from each
system). Howard et al. [12] analyze leading comments and method signatures
from the source code, and suggest reformulated queries by extracting
semantically similar word pairs. However, their technique requires the source
code to be well documented, and thus, might not perform well with poorly
documented code. On the other hand, our technique–QUICKAR–complements the
source code vocabulary by capturing appropriate candidate terms from the
programming questions of Stack Overflow. Carpineto and Romano [1] conduct a
survey on the automatic query expansion (AQE) mechanisms applied to
information retrieval. Rocchio’s expansion is one of such mechanisms which was
adapted by earlier studies [6, 10] in the context of software engineering. We
consider this mechanism as the baseline reformulation technique, and compared
with it using experiments (Section 4.3). Yuan et al. [24] first apply
contextual words from Stack Overflow questions and answers for identifying
semantically similar software-specific words. While they introduce the idea,
we successfully adapt that idea for a software maintenance task, i.e., query
reformulation for concept location. From a technical point of view, we collect
candidate query terms opportunistically not only from project source code but
also from questions of Stack Overflow, and determine their relevance to the
initial query using crowdsourced knowledge (i.e., adjacency list database). We
then apply the most relevant terms from both source code and Stack Overflow to
query reformulation, and such methodology was not applied yet by any existing
studies.

##  6 Conclusion and Future Work

Studies show that software developers face difficulties in preparing an
appropriate search query from a change request during concept location. In
this paper, we propose a novel technique–QUICKAR–that automatically suggests
effective reformulations for an initial query by leveraging the crowd
generated knowledge from Stack Overflow. The technique collects candidate
query terms from both project source and questions of Stack Overflow, and then
determines their applicability for the reformulated query by applying the
crowdsourced knowledge. Experiments using 510 change requests from two
software systems suggest that our technique can improve or preserve the
quality of 76% of the baseline queries which is promising. Comparison with one
baseline technique also validates our preliminary findings. While the
preliminary findings are promising, further experiments and investigations are
warranted.

## REFERENCES

  * Carpineto and Romano [2012] C. Carpineto and G. Romano.  A Survey of Automatic Query Expansion in Information Retrieval.  _ACM Comput. Surv._ , 44(1):1:1–1:50, 2012.
  * Dit et al. [2013] B. Dit, M. Revelle, M. Gethers, and D. Poshyvanyk.  Feature Location in Source Code: a Taxonomy and Survey.  _Journal of Software: Evolution and Process_ , 25(1):53–95, 2013.
  * Erlikh [2000] L. Erlikh.  Leveraging Legacy System Dollars for E-Business.  _IT Professional_ , 2(3):17–23, 2000.
  * Favre [2008] L. Favre.  Modernizing Software & System Engineering Processes.  In _Proc. ICSENG_ , pages 442–447, 2008.
  * Furnas et al. [1987] G. W. Furnas, T. K. Landauer, L. M. Gomez, and S. T. Dumais.  The Vocabulary Problem in Human-system Communication.  _Commun. ACM_ , 30(11):964–971, 1987.
  * Gay et al. [2009] G. Gay, S. Haiduc, A. Marcus, and T. Menzies.  On the Use of Relevance Feedback in IR-based Concept Location.  In _Proc. ICSM_ , pages 351–360, 2009.
  * Haiduc and Marcus [2011] S. Haiduc and A. Marcus.  On the Effect of the Query in IR-based Concept Location.  In _Proc. ICPC_ , pages 234–237, June 2011.
  * Haiduc et al. [2012a] S. Haiduc, G. Bavota, R. Oliveto, A. De Lucia, and A. Marcus.  Automatic Query Performance Assessment during the Retrieval of Software Artifacts.  In _Proc. ASE_ , pages 90–99, 2012a.
  * Haiduc et al. [2012b] S. Haiduc, G. Bavota, R. Oliveto, A. Marcus, and A. De Lucia.  Evaluating the Specificity of Text Retrieval Queries to Support Software Engineering Tasks.  In _Proc. ICSE_ , pages 1273–1276, 2012b.
  * Haiduc et al. [2013a] S. Haiduc, G. Bavota, A. Marcus, R. Oliveto, A. De Lucia, and T. Menzies.  Automatic Query Reformulations for Text Retrieval in Software Engineering.  In _Proc. ICSE_ , pages 842–851, 2013a.
  * Haiduc et al. [2013b] S. Haiduc, G. De Rosa, G. Bavota, R. Oliveto, A. De Lucia, and A. Marcus.  Query Quality Prediction and Reformulation for Source Code Search: The Refoqus Tool.  In _Proc. ICSE_ , pages 1307–1310, 2013b.
  * Howard et al. [2013] M.J. Howard, S. Gupta, L. Pollock, and K. Vijay-Shanker.  Automatically Mining Software-based, Semantically-Similar Words from Comment-Code Mappings.  In _Proc. MSR_ , pages 377–386, 2013.
  * Kevic and Fritz [2014] K. Kevic and T. Fritz.  Automatic Search Term Identification for Change Tasks.  In _Proc. ICSE_ , pages 468–471, 2014.
  * Mamykina et al. [2011] L. Mamykina, B. Manoim, M. Mittal, G. Hripcsak, and B. Hartmann.  Design Lessons from the Fastest Q & A Site in the West.  In _Proc. CHI_ , pages 2857–2866, 2011.
  * Mihalcea and Tarau [2004] R. Mihalcea and P. Tarau.  TextRank: Bringing Order into Texts.  In _Proc. EMNLP_ , pages 404–411, 2004.
  * Moreno-Seco et al. [2004] F. Moreno-Seco, L. Mico, and J. Oncina.  A New Classification Rule based on Nearest Neighbour Search.  In _Proc. ICPR_ , pages 408–411, 2004.
  * Nasehi et al. [2012] S. M. Nasehi, J. Sillito, F. Maurer, and C. Burns.  What Makes a Good Code Example?: A Study of Programming Q & A in Stack Overflow.  In _Proc. ICSM_ , pages 25–34, 2012.
  * Ponzanelli et al. [2013] L. Ponzanelli, A. Bacchelli, and M. Lanza.  Seahawk: Stack Overflow in the IDE.  In _Proc. ICSE_ , pages 1295–1298, 2013.
  * Rahman et al. [2014] M. M. Rahman, S. Yeasmin, and C. K. Roy.  Towards a Context-Aware IDE-Based Meta Search Engine for Recommendation about Programming Errors and Exceptions.  In _Proc. CSMR-WCRE_ , pages 194–203, 2014.
  * Rahman et al. [2016] M. M. Rahman, C. K. Roy, and D. Lo.  RACK: Automatic API Recommendation using Crowdsourced Knowledge.  In _Proc. SANER_ , pages 349–359, 2016.
  * Rigby and Robillard [2013] P. C. Rigby and M.P. Robillard.  Discovering Essential Code Elements in Informal Documentation.  In _Proc. ICSE_ , pages 832–841, 2013.
  * Sridhara et al. [2008] G. Sridhara, E. Hill, L. Pollock, and K. Vijay-Shanker.  Identifying Word Relations in Software: A Comparative Study of Semantic Similarity Tools.  In _Proc. ICPC_ , pages 123–132, 2008.
  * Yang and Tan [2012] J. Yang and L. Tan.  Inferring Semantically Related Words from Software Context.  In _Proc. MSR_ , pages 161–170, 2012.
  * Yuan et al. [2014] T. Yuan, D. Lo, and J. Lawall.  Automated Construction of a Software-specific Word Similarity Database.  In _Proc. CSMR-WCRE_ , pages 44–53, 2014.