Using online data sources to make query suggestions for children

To determine the candidate suggestions for query Q with m ( ⩾ 1 ) words, i.e., terms, CQS examines the frequency of occurrence of words that follow the last word t m in Q in a category c. CQS identifies the frequencies of the top-five most frequently-occurred t m + 1 words following t m , denoted f ( t m , t m + 1 ) , in c. For each one of the top-five words t m + 1 in c, CQS considers the next top-five f ( t m + 1 , t m + 2 ) frequency values and so on to determine candidate suggestions in different categories for Q. Given that suggestions including seldom-occurring words are less likely to make it to the top ranking positions among the suggestions for Q, CQS considers only the top-five most frequent words. In doing so, CQS speeds up its processing time without affecting its accuracy, a fact that has been empirically verified and discussed in [25].

To obtain the frequency distribution of bigrams that are used in generating candidate suggestions, CQS examines the consecutive word occurrences in the 82,000 documents belonged to the 16 categories extracted from children’s websites (see Table 2). Using word occurrences, CQS considers f ( t m , t m + 1 ) and creates phrases as suffixes of Q, which yield candidate suggestions for Q.

3.2. Category likelihood

Given a query Q, CQS computes the likelihood of keyword(s) in Q matching the contents of different categories. To determine the category likelihood of Q, CQS employs the multinomial model, along with the well-known Bayes’ rule,12

CQS treats the likelihood value computed in Equation (1) as one of the measures to determine the significance of CS and computes the category likelihood score of CS with respect to c, denoted CL ( CS , c ) , as (3) CL ( CS , c ) = P ( c | Q ) .

If the probability of keywords in Q belonged to category c is high, then a candidate suggestion originated from c is treated as a more promising suggestion for Q. CQS offers diverse query suggestions by considering various categories to which a given ambiguous query13

CQS relies on frequency distribution of bigrams within categorized documents to provide statistics of consecutive term occurrences in different categories, i.e., categories shown in Table 1. Recall that we define a term as a non-stopword keyword, which can be preceded by a sequence of connection words. For example, if a user enters the query keyword “information,” a suggestion “information about animals” makes more sense than the suggestion “information animals,” since in the latter case the relationship between the two keywords is missing. To obtain the frequency distribution of bigrams, CQS examines the consecutive term occurrences in the aforementioned 82,000 children’s documents (including SimpWiki documents), which are distributed across 16 categories.

We consider bigram frequency distribution of terms so that searching for related terms to a user query becomes more efficient than examining the frequencies of occurrence of sequences of more than two terms which increases the database size [2] for the document collection and significantly impacts the search time for terms related to a given query.

For a given query Q with the only keyword A, CQS generates candidate suggestions for Q by considering phrases, which are N-grams that includes A, such as A B C and A B C D in which A B , B C , and C D are bigrams belonging to documents of the same category c. In generating phrases, CQS first considers all the frequent bigrams with the leading A. Based on the statistical data as to the frequency of occurrence of words B that follow A, and words that follow B, and so on, CQS concatenates the bigrams such that the 2nd word in the preceding bigram is the 1st word in the subsequent bigram to generate candidate suggestions. Thus, candidate suggestions are N-grams generated from across different categories, which are constructed based on the frequencies of word co-occurrences. CQS computes the N-Gram frequency score for each candidate suggestion CS .

Given a CS , which is a sequence of words, t 1 , … , t n ( n > 1 ) extracted from documents in c, CQS computes the average (N-Gram) frequency of the sequence below. (4) f ( t 1 , t 2 , … , t n ) = f ( t 1 , t 2 ) + f ( t 2 , t 3 ) + ⋯ + f ( t n − 1 , t n ) n − 1 where f ( t i − 1 , t i ) , 1 < i ⩽ n , is the frequency of the bigram made up by the word t i − 1 followed by word t i . A high N-gram frequency value of CS indicates that, in general, CS includes highly co-occurring bigrams in c and is treated as a favorable suggestion.

We consider a special case f ( t i − 1 , EOS ) , where EOS stands for “End Of Sentence”. f ( t i − 1 , EOS ) captures the frequency with which term t i − 1 is the last term in a sentence. CQS considers all the terms following t i − 1 , including EOS.14

CQS applies N-gram frequency to determine which candidate suggestions should be considered favorable.

CQS determines the “children-friendliness” of the vocabulary used in a candidate suggestion by consulting a vocabulary dictionary comprised of words appropriate for children that were downloaded from children’s word lists posted at a number of children’s websites, including, but not limited to Reading Rockets, Big IQ Kids, Game Gal (see Table 2 for details), as well as Library of Congress (Children’s Subheading). If a term in a suggestion is found in the dictionary, it is assigned the value of 1; otherwise, it is given the value of 0. For a candidate suggestion CS with multiple terms, CQS averages the values over all the terms in CS and obtains a single value between 0 and 1, which is called the Vocabulary score for CS . A Vocabulary score of value closer to 1 indicates that the corresponding suggestion is child-friendly.

3.5. Simplicity of phrase keywords

As indicated earlier, one of the design goals of CQS is to offer query suggestions that children can understand, i.e., providing simple query suggestions. To determine the simplicity of a candidate suggestion CS , CQS measures not only whether non-stop words in CS appear in children’s vocabulary (CV), but also how often they are seen in web pages that are written in a simple style. Given that texts consisting of short sentences and simple words are deemed easier to read than those including longer sentences and rare words [1], it is assumed that web pages written using basic English vocabulary and shorter sentences are tailored for children. SimpWiki is such a website that includes these web documents. Hence, we maintain a count of all the words in the entire collection of documents archived at SimpWiki.

A highly-ranked candidate suggestion CS can be partially affected by having keywords of CS in the SimpWiki documents. CQS considers the normalized frequencies for the occurrences of keywords in SimpWiki documents, with values between 0 and 1. A value closer to 1 for a non-stop keyword in a phrase indicates that the word is very often found in SimpWiki, which reflects its degree of simplicity. For example, the term “call” with a value 0.7 indicates that it is very commonly found in simple text documents, i.e., kid’s literature, as compared with “torrent”, which is assigned a value 0.000327, is less-frequently-used in kid’s simple text documents. The values of the keywords in CS are averaged, and the averaged value is referred as the simplicity score of CS .

Simplicity vocabulary SV generated from SimpWiki differs from the children’s vocabulary CV introduced in Section 3.4. First, words in CV are not extracted from a collection of text documents. Instead, they are words that a child is expected to know. Second, a word in SV is simple but may be absent in CV. In SV, we include words, such as “Nintendo” (a video game console), “Transformer” (the name of a toy), or “Anna” (a character in a Disney movie), which are common terms of children’s folk culture, or terms that children are exposed to on a regular basis through mass-media, i.e., pop-culture. (See [22] for a detailed discussion on children’s exposure to terms/concepts addressing children’s folk, mass-media, and commercial cultures.) Terms in SV are simple based on their frequency of exposure to children. However, they are not commonly-occurred words in children’s literature, and hence are not part of, i.e., included in, CV. Quite often to distinguish which one of the two candidate suggestions with all the words included in CV is more appealing to a kid, CQS must rely on their simplicity scores.

3.6. Distribution of phrase keywords in children’s documents

While simplicity of phrase keywords indicates how often keywords in a candidate suggestion CS are used by kids, it does not show whether the words are more likely to be found in documents pertaining to kids than in documents belonging to generic audience. To measure whether the word distribution of CS within kids’ documents is more likely than in a general-audience’s documents, CQS determines its Naïve Bayes (NB) classification score using the NB model. This score captures the probability distribution of keywords in CS that are also in children’s content. We trained a multinomial model as presented in [7] using 10,900 documents randomly chosen from Wikipedia.org for the non-kid’s class and 25,115 documents from children’s websites, such as Dogo News, National Geographic for Kids, Time for Kids, etc. (see Table 2 for further details), for the kid’s class. Although the number of documents in kid’s class is more than the number in non-kid’s class, it does not create an imbalance, since documents in the former are comparatively shorter than the Wikipedia documents, resulting in a vocabulary smaller than the non-kid’s class. Given CS , the NB feature calculates the likelihood of CS using the Naïve Bayes’ rule.

3.7. Locality

By concatenating different bigrams in a category into an N-gram phrase, some undesirable phrases, such as “greek language french cyclist” which consists of frequent bigrams ‘greek language’, ‘language french’, and ‘french cyclist’, can be created and should be avoided. To eliminate their creations, CQS determines the locality score for each candidate suggestion CS . The locality score, as defined below, which is based on the Lennon Similarity measure [19], captures the likelihood of all the bigrams in CS being extracted from the same document(s) within a given category c, such that the smaller the number of documents in c in which all the bigrams in CS occur, the less likely CS is an appealing one. (5) locality ( CS , c ) = S n Min { S l 1 l 2 − S n , … , S l n − 1 l n − S n } + S n where n is the number of terms in CS , l i ( 1 ⩽ i ⩽ n ) is a term in CS , S n is the number of documents in c that include all the bigrams in CS , and S l i l j ( i , j > 0 ) is the number of documents in c that include bigram l i l j . It is easy to see that the more bigrams in CS , the fewer the number of documents that include all the bigrams in CS which yields the lower the locality score. By using the Min function in Equation (5), we normalize the locality score of CS without penalizing CS based on its length.

3.8. Subject headings

It has been shown [11] that searching information on the Web can be facilitated by searching for the topics of the desired information. With that in mind, we have designed CQS to examine the topics of information addressed in candidate suggestions and penalize suggestions that are associated with topics/themes that are not commonly associated with children content. To accomplish this task, CQS relies on Library of Congress Subject Headings (LCSH), which is a de facto universal controlled vocabulary and constitutes the largest general indexing vocabulary in the English language. LCSH, which are keywords or phrases that denote concepts, events, or names, are employed by librarians to categorize and index books according to their themes, i.e., topics. Examples of LCSH include “Fairy tales” and “Fear of the dark-Fiction”.

To identify, among the large number of LCSH, the subject headings that address topics of interest to children, we (i) examined LCSH assigned to 30,000 randomly selected books known to be suitable for children, which are with readability levels between the K-6 grades defined by publishers and (ii) generated a list of 10,749 children’s LCSH, denoted cLCSH , that describe text content in children’s literature using subject keywords.

In examining the topical information of a candidate suggestion CS , CQS employs Equation (6) to determine the degree of closeness of CS and children’s subject headings, denoted SHScore . To compute the SHScore feature score of CS , CQS compares CS against each subject heading SH in cLCSH , and chooses the highest similarity value between CS and the subject headings as the value that quantifies the degree to which CS addresses themes suitable for children. The degree of similarity between CS and SH is computed using the word correlation factor ( wcf )15

The Min function in Equation (6) imposes a constraint on summing up the correlation factors of words in the description of CS and SH . Even if a word in the description of CS (i) matches exactly one of the words in SH and (ii) is similar to some of the remaining words in SH , which yields a value greater than 1.0, CQS limits the sum of their similarity measure to 1.0, which is the word-correlation factor of an exact match. This constraint ensures that if CS contains a dominant word w in its description which is highly similar to a few words in SH , w alone cannot dictate the content resemblance value of CS with respect to SH . Words in SH that are similar to most of the words in CS should yield a greater SHScore value than the SHScore value of words in SH that are similar to only one dominant word in CS . The Max function, on the other hand, ensures that the SHScore of CS reflects the highest similarity of CS among all the subject headings which most effectively captures the topics/theme of CS .

A candidate suggestion CS with a high SHScore illustrates that CS is closely related to contents in children’s literature and hence is treated by CQS as more favorable compared with other suggestions with lower SHScore . Example 1.

Consider a candidate suggestion “british movies”, which is generated by CQS in response to the user query “british.” In comparing against the subject headings digestion, finance person, television, and films using word-correlation factors, the corresponding degrees of resemblance with respect to “british movies” are assigned the SHScore of 0, 0, 2.7 × 10 − 7 , and 3.8 × 10 − 7 , respectively. Based on the aforementioned resemblance scores, films is the closest to the suggestion. By using the subject heading feature, CQS assigns 3.8 × 10 − 7 , which is the similarity score computed with respect to films, as the SHScore value of “british movies”.

Now consider the four subject headings again for another candidate suggestion “british pancakes”, which is assigned the value 0 as its SHScore, indicating that there is no suitable topic description for the suggestion based on the set of subject headings. Furthermore, in considering the two suggestions “british movies” and “british sitcoms” against the subject heading television, CQS assigns higher SHScore to “british sitcoms” than “british movies”, i.e., 1.1 × 10 − 6 versus 2.7 × 10 − 7 , since television is more accurately reflecting the subject area of “british sitcoms” than “british movies.”

Using the individual scores of the features introduced earlier, which are computed for each candidate suggestion CS , CQS ranks the candidate suggestions belonged to multiple categories so that the top-k suggestions17

In training the BP model for CQS, 138,579 training instances were used. Each training instance includes a given noun-phrase, in lieu of a query, and is associated with the seven different feature scores computed for the corresponding noun-phrase and a label, which is either 1 or 0, to designate whether the noun-phrase is a children or generic query, respectively. In gathering the training instances of children queries, noun-phrases from a number of children websites, including spaghettibookclub.org, motherdaughterbookreviews.com, and best-kids-books.com,18

4.1. Dataset and metrics

Due to the lack of benchmark datasets to evaluate the design methodology and performance of QS modules for children, we turned to a number of 7- to 12-year-old children who are 1st- to 6th-grade students at a local school. During the month of April 2014, we asked the students to first create keyword queries that they would like to use to conduct their searches. We collected 127 children queries. Children were then provided with a number of CQS-, Google-, Yahoo!-, and Bing-generated suggestions to evaluate. We selected these popular search engines for baseline purposes, as opposed to search engines specifically targeting children, since it has been reported that children rank Google, Yahoo!, and Bing as their three most favored engines for conducting their daily information discovery tasks [3].

We used eight, five unigram and three bigram, queries randomly chosen out of the (keywords in) 127 unique queries provided by 127 elementary school students, who are 3rd to 6th graders, to evaluate the performance of CQS. (Table 3 shows a few of the 127 queries offered by the children.) Altogether, 25 students in 3rd grade, 36 in 4th grade, 26 in 5th grade, and 40 in 6th grade participated in the empirical study. For each query Q, we applied CQS to generate the top-4 query suggestions, which were mixed with the top-4 suggestions of Q offered by Google, Yahoo!, and Bing. Note that we assessed the performance of CQS against Google, Yahoo!, and Bing, since the latter are widely-used search engines. Furthermore, the top-4 suggestions of CQS were used, since Google offers four suggestions per query, the least number of generated suggestions among the QS modules considered for comparison purpose.

Each child who participated in the study was asked to choose four useful suggestions for each test query. Table 4 shows two of the test queries and their corresponding suggestions used in the evaluation, and the remaining queries are arctic circle, chocolate chip, football, greek, information, and snow. The top-4 most frequently chosen suggestions for each test query Q, among the choices provided by the 43 children who participated in the evaluation, were treated as the gold standard of Q.

We acknowledge that the number of queries considered for the evaluation of CQS by school children is relatively small. However, given that (i) evaluations involving children are difficult to conduct due to privacy constraints [28] and (ii) we only had access to students for a limited amount of time—each student involved in the assessment was given 15 minutes to complete the evaluation, which was imposed by their school administrators—we were forced to limit the number of queries to be assessed to eight which allowed each student to spend an average of at most 2 minutes on evaluating suggestions for a query. Had we been given access to more students at the school and/or more time to conduct our evaluation, we would have compiled the results based on more than eight queries.

We applied a simple counting scheme to evaluate the query suggestions made by CQS. For each CQS-offered query suggestion that was chosen by a child (as a useful suggestion), a point is rewarded for the suggestion. Using this counting strategy, we consider the top-4 counts of suggestions for each one of the eight test queries, which yields the gold standard for our evaluation. A total of 43 children participated in the evaluation.

To determine the effectiveness of CQS and existing QS modules (considered for comparison purpose) in making useful suggestions to children, we have computed the Normalized Discounted Cumulative Gain (nDCG) value [15] on their corresponding top-4 suggestions for each test query. nDCG penalizes relevant suggestions that are ranked lower in the list of suggested queries.

To verify the correctness of the design of CQS we conducted a number of studies using the dataset and metrics introduced in the previous section. We first validated the correctness of selecting Backpropagation as a combination strategy. Thereafter, we evaluated the effectiveness of each individual feature (as discussed in Sections 3.2 through 3.8) in making good query suggestions to children, which validates its usefulness. Lastly, we assessed the overall performance of CQS based on combining individual features as a whole (as defined in Section 3.9), which we compared with the performance of a number of existing QS modules adopted by popular search engines. As previously stated, we also used the nDCG metric to quantify the performance of CQS in making suggestions suitable for children against Google, Yahoo!, and Bing, being used these days.20

4.2.1. Validating CQS’s combination strategy

CQS considers the BP model, a supervised learning-to-rank approach as presented in Section 3.9. To demonstrate the correctness of selecting such a strategy to combine the seven different scores generated by CQS for each candidate suggestion into a single ranking score, we compared the use of BP with two other combination strategies: (i) CombMNZ [18], which is a linear combination measure frequently used in fusion experiments [6] and (ii) Reciprocal Rank Fusion (RRF) [6]. C̱ombMNZ, as defined in Equation (7), is applied to consider multiple existing lists of rankings on CS in CQS to determine a joint ranking of CS , a task known as rank aggregation or data fusion. (7) CombMNZ CS = ∑ f = 1 N CS f × | CS f > 0 | where N is the number of (ranked lists of) features to be fused, which is seven in our case, CS f is the normalized score of CS on the ranked list of feature f, and | CS f > 0 | is the number of non-zero, normalized scores of CS in the ranked lists to be fused.

Prior to computing the ranking score of CS , it is necessary to transform the original scores in each individual ranked list of CS into a common range, which can be accomplished by applying Equation (8) to each score in each ranked list so that it is within the range [ 0 , 1 ] , a commonly-used. (8) CS f = S CS − CS min f CS max f − CS min f where S CS is the score of the feature f of CS prior to be normalized, CS max f ( CS min f , respectively) is the maximum and (minimum, respectively) score in the ranked list of f, and CS f is the normalized score for CS in the ranked list of f.

Ṟeciprocal Rank Fusion (RRF) [6] first sorts the score list of each feature of all the candidate suggestions, which yields a ranked list of candidate suggestions corresponding to every feature in descending order. Given a list of M candidate suggestions, RRF in Equation (9) is applied to generate a single rank score for CS . (9) RRF score ( CS ∈ M ) = ∑ f ∈ N 1 rank ( CS f ) where N is a set of features such that their scores for a particular CS are to be combined and rank ( CS f ) is the ranking position of CS in the ranked list of feature f.

It has been empirically verified that BP is significantly better than CombMNZ and RRF in terms of combining different features of a candidate suggestion as shown in Fig. 2. The figure shows the performance of using different combination strategies on the eight queries that were evaluated by CQS. While the unsupervised combination strategies of CombMNZ and RRF are simple, their overall nDCG values are significantly lower than the overall nDCG value achieved by BP. Although BP requires training to learn the feature weights, the training process is one-time.

OPEN IN VIEWER

Fig. 2.

Performance evaluation of three feature combination strategies in generating query suggestions for children based on the eight test queries.

OPEN IN VIEWER

Fig. 3.

Performance evaluation of (each of the features of) CQS.

4.2.3. CQS versus QS modules

We compared CQS with the QS modules employed by Google, Yahoo!, and Bing in terms of nDCG, which is an evaluation framework similar to the one adopted by the authors of [28,29]. One of the strengths of our evaluation strategy lies on the fact that we rely on children’s assessments, and there is no room for adult-based bias. This is because we use keyword queries initiated by children as test queries and the top-4 suggestions selected as the gold standard are the ones chosen by children.

OPEN IN VIEWER

Fig. 4.

The nDCG scores for Google, Yahoo!, Bing, and CQS respectively determined using their top-4 suggestions against the gold standards.

OPEN IN VIEWER

Fig. 5.

Per-query distribution of nDCG scores for CQS, Google, Yahoo!, and Bing, respectively.

In seven out of eight queries, CQS provides a suggestion that made it either to the first or second position in the gold standard, whereas Google achieves only six out of the eight queries. Figure 4 shows the performance of Google, Yahoo!, Bing, and CQS using the nDCG measure. The results have verified that suggestions made by CQS are more appealing to children than the ones offered by Google, Yahoo!, and Bing. Although the results of CQS are not statistically significant ( p ⩽ 0.05 ) compared with Google, they are statistically significant ( p ⩽ 0.01 ) compared with Yahoo! and Bing based on the Wilcoxon signed-ranked test.

Besides analyzing the overall performance of CQS, Google, Yahoo!, and Bing using nDCG, we also examined their performance at the query level. As shown in Fig. 5, CQS outperforms Google in making suggestions in four out of the 8 test queries based on the gold standard. More importantly, CQS-offered suggestions are placed at higher ranking positions compared to Google. In fact, among all the test queries, while CQS and Google both have equal number of suggestions posted at rank position 1, the former has more suggestions placed at positions 2 and 3. Similar to the overall performance, CQS and Google distance themselves from Yahoo! and Bing in terms of achieving higher nDCG values at the query level.

We attempted to compare CQS against other children QS modules [10,28,29]. Unfortunately, implementing these modules requires setting up different parameters which are not explicitly articulated in [10,28,29]. For example, the authors of [28,29] create the random walk graphs, which include a foreground and background model, based on tags and URLs. Given that the (i) specific URLs considered for creating such graphs were not made available, and (ii) authors’ cleaned tags and URLs to a large extent using tag normalization and tag filtering are not described in details in the respective paper, it is not possible to regenerate the foreground and the background model for comparison purpose. Furthermore, datasets presented in [10,28,29] are not available to the research community. For this reason, fair comparisons between CQS and these children QS modules are not possible.

As previously stated, there are no benchmark datasets that can be used to assess the performance of QS modules for children. For this reason, we turned to Mechanical Turk21

OPEN IN VIEWER

Fig. 6.

An evaluation conducted by Mechanical Turk appraisers who assessed the relevance of the suggestions generated by CQS.

4.3.1. Relevance of CQS-generated suggestions

We conducted a survey on Mechanical Turk in which we asked appraisers to examine a set of ten test queries and their corresponding suggestions created by CQS. For each query Q, appraisers were required to identify, among a provided set of four suggestions generated by CQS for Q, the ones (if any) that were suitable and relevant for children.22

²²

Note that the responses identified as relevant provided by an appraiser are treated as the gold standard for accuracy and reciprocal rank assessment, and the reported overall accuracy and MRR are based on the average of the corresponding accuracy and MRR calculated according to each appraiser’s response. In other words, the suggested queries treated as “suitable and relevant” by each appraiser were not combined into a single gold standard for evaluation purpose, since we would like to preserve varied opinions on relevance in evaluating the performance of CQS.

(A sample evaluation form is shown in Fig. 6.)

While the ten test queries (with five queries in each evaluation form) included in the survey, which are “Disney”, “Lego”, “Pet”, “Transformers”, “National football”, “Art”, “Dog”, “Minecraft”, “Video”, and “Basketball player”, were selected among the query set introduced in Section 4.1 that address varied topics of interests for children at diverse school grade levels, the corresponding suggestions were generated using CQS. The goal of this survey is to quantify the degree to which queries suggested by CQS are appealing to children (from the adults’ points of view). We collected 90 responses during the month of July 2014. Based on the feedback collected through Mechanical Turk, we have observed that, on the average, (close to) 50% of the recommendations generated by CQS were deemed suitable for children. (For the evaluation of the performance of CQS on each test query, see Fig. 7.)

OPEN IN VIEWER

Fig. 7.

Performance evaluation of CQS based on the responses of Mechanical Turk appraisers.

We are aware that each Mechanical Turk appraiser must be over 18 years old. We solicited appraisers of all walks of life and assessed the performance of CQS by separating the opinions of appraisers known to be educators or parents of young children,23

²³

Mechanical Turk appraisers were asked to voluntarily answer a question which inquired whether they were parents/educators. Overall, 57% of the 90 appraisers who assessed the performance of CQS were parents/educators.

who have a more direct knowledge on the interests/preferences of children in terms of selecting suitable query suggestions, from the opinions of general appraisers. As shown in Fig. 7, the accuracy ratios computed based on parents/educators’ responses yield not only a statistically significant improvement ( p < 0.05 ) over the ones based on the responses of the general appraisers, which is determined using the Wilcoxon signed-ranked test, but also confirm the appropriateness of the design methodology of CQS, i.e., offering useful query suggestions to children, since in general parents/educators are in better position to judge the usefulness of queries suggested to children than the general public.

4.3.2. Evaluations on QS modules

We also turned to Mechanical Turk to validate our claim that queries suggested by CQS for children are more favorable than the ones generated by Google, Yahoo!, and Bing. To verify this claim, we conducted another survey on Mechanical Turk (see a sample evaluation form designed for this empirical study in Fig. 8). The survey requested the appraisers to identify for each test query the two suggestions that, to the best of their knowledge, were most suitable for children. The test queries in this survey are the same queries as presented in Section 4.3.1, and the corresponding suggestions are the top-2 suggestions generated by CQS, Bing, Google, and Yahoo!. (Note that due to overlapped suggestions offered by the four QS modules, there are less than eight suggestions for each of the test queries.) We treated the two suggestions chosen for each test query Q by each appraiser as the gold standard for Q. Based on the chosen suggestions, we computed the accuracy ratio and Mean Reciprocal Rank (MRR). While the former quantifies the proportion of relevant suggestions generated by a QS module, the latter computes the average ranking position of the first relevant suggestion provided by the corresponding QS module.

OPEN IN VIEWER

Fig. 8.

The Mechanical Turk evaluation form for performance comparison of CQS and other QS modules.

OPEN IN VIEWER

Fig. 9.

Evaluations of CQS and other QS modules based on Mechanical Turk appraisers’ responses.

The accuracy and MRR scores computed according to the 90 responses collected during the month of July of 2014 are shown in Fig. 9. The results, which are statistically significant with p < 0.05 , show that appraisers often preferred children query suggestions provided by CQS over the suggestions created by Google, Yahoo!, or Bing. These findings are consistent among the 57% of appraisers who were either educators or parents of young children.

To further validate the performance of CQS, Google, Yahoo!, and Bing, in terms of their ability to generate suggestions appealing to younger audiences, we conducted another survey to gather feedback through Mechanical Turk. Using the same experimental framework described earlier in this section, we created new HITs using 28 new queries (see the new queries, along with the 10 test queries used in the July 2014 survey, in Table 5), which are selected among the ones described in Section 4.1, and vary in terms of length.

OPEN IN VIEWER

Table 5

Children queries and their top suggestions provided by CQS and other web search engines

Children Query	Top Suggestions Provided by Different Search Engines
	CQS	Google	Yahoo!	Bing
Art	Art and crafts	Art of manliness	Art van furniture	Art Institute of Chicago
Animal migration route	Animal migration route every time	Animal migration routes	Animal migration route of the monarch	Animal migration routes in washington state
Basketball player	Basketball player team	Basketball player with clothing line	Basketball player clipart	Basketball player with broken leg
Biggest	Biggest book fair	Biggest looser 2017	Biggest loser 2017	Biggest loser
Central train station	Central train station slackened pace	Central train station amsterdam	Central train station milan italy	Central train station amsterdam
Cheese	Cheese boxes	Cheese sauce	Cheese ball recipes	Cheese ball recipes
Cheese cake	Cheese cake sweet	Cheese cake factory	Cheese cake factory	Cheese cake recipes scratch
Chocolate chip cookie	Chocolate chip cookie dough	Chocolate chip cookie recipe	Chocolate chip cookie recipe	Chocolate chip cookie recipe
Cookie recipes	Cookie recipes in book	Cookie recipes without butter	Cookie recipes from scratch	Cookie recipes from scratch
Disney	Disney movie	Disney store	Disney character	Disney cruise
Dog	Dog pet	Dog breeds	Dog breeds	Dog breeds
Ice cream	Ice cream cake	Ice cream boise	Ice cream alley	Ice cream maker
India	India trading company	India news	India map	India news
Japan	Japan animation	Japan time	Japan airlines	Japan crate
Famous piano concert	Famous piano concert composers	Famous piano composers of all time	Famous piano composers of classical music	Famous piano composers list
Lego	Lego movie	Lego dimensions	Lego city	Lego games
Lego dinosours	Lego dinosaurs robots	Lego dinosaurs movie	Lego dinosaurs video	Lego dinosaurs games
Map	Map expert	Map of idaho	Yahoo maps	Mapquest
Meme	Meme in july	Meme maker	Meme generator	Meme generator
Minecraft	Minecraft	Minecraft skins	Minecraft skins	Minecraft servers
Music	Music books	Music notes	Music videos	Music notes
National football	National football coach	National football league	National football league	National football league
Migration routes	Migration routes enable people	Migration routes definition	Migration routes in the united states	Migration routes of birds
Most popular sport	Most popular sport music	Most popular sport in the world	Most popular sport in the world	Most popular sport in the world
Nike	Nike shoes	Nike shoes	Nike outlet	Nike inc.
Pet	Pet dog	Petsmart	Pet supplies	Pet supplies plus
Piano	Piano teacher	Piano guys	Piano guys	Piano guys
Popular book	Popular book contains municipality of the district	Popular book series	Popular book series	Popular book club
Soccer	Soccer ball	Soccer ball		Soccer games
Sport shoes	Sport shoes fashionist	Sport shoes for women	Sport shoes for women	Sport shoes for men
Star wars	Star wars characters	Star wars 8	Star wars rogue one	Star wars rebels
Star wars clones	Star wars clones episode	Star wars clones wars	Star wars clones vs droids	Star wars clones ebay
Tallest person	Tallest person of the year	Tallest person in the world	Tallest person in the world	Tallest person in the world
Tiger	Tiger Woods	Tiger Woods	Tiger Woods	Tiger Woods
Transformer	Transformers movies	Transformers toys	Transformers toys	Transformers calculator
Video	Video games	Video games	Video converter	Video editor
Water	Water bottles	Water cycle	Water softener systems	Water softeners
Youtube	Youtube celebrity	Youtube to mp3	Youtube music	Youtube music

OPEN IN VIEWER

Fig. 10.

Evaluations of CQS and other QS modules based on Mechanical Turk appraisers’ responses collected during 2017.

We collected 657 responses on the new HITs during the months of January and February of 2017. Based on these responses, we computed the accuracy ratio and MRR of CQS, Google, Yahoo!, and Bing, respectively. As shown in Fig. 10, query suggestions generated by CQS continued to be favored by appraisers over those generated by Google, Yahoo!, or Bing, and CQS performs significantly better than Google, Yahoo!, and Bing (with p < 0.05 ) based on the Wilcoxon signed-ranked test. The results, which remain comparable among the 46% Mechanical Turk appraisers who reported being parents of young children or educators, further demonstrate the validity of the experimental results reported earlier in this section.

Note that Table 5 shows the child-formulated queries used in all of the Mechanical Turk experiments discussed in this section. For each test query, we also include the top suggestion generated by CQS and each of the web search engines considered for comparison purpose.

4.3.3. The need for suggestions tailored to children

As we previously stated in Section 4.1, the objective of our empirical assessment is to demonstrate the need for query suggestion modules, alike to CQS, that can be used to complement search engines favored by children, such as Google. In order to further illustrate the suitability of CQS in generating query suggestions to meet the information needs of younger audiences, we conducted another experiment. In the new online study, we examined the performance of CQS and Kidzsearch, a leading kids search engine as discussed earlier.

Following the framework discussed Section 4.3, we created HITs in which we included suggestions generated by both Kidzsearch and CQS for diverse sets of unigram, brigram, and trigram queries, with a total of 28 queries (see the queries in Table 5). We asked Mechanical Turk appraisers to select, according to their interpreted intent of each query Q, the top-2 suggestions most relevant to Q. We collected 687 responses, out of which 344 were provided by appraisers who reported being either parents of young children or educators.

Based on the responses collected on Mechanical Turk, we computed the MRR and accuracy ratios. As shown in Fig. 11, Kidzsearch and CQS achieve comparable performance in terms of MRR, i.e., the difference between their MRR ratios are not significant. The reported results are also consistent among appraisers that are parents or educators. Even though the overall differences in the accuracy ratios between Kidzsearch and CQS are statistically significant ( p < 0.001 ) for general appraisers (as depicted in Fig. 12), CQS and Kidzsearch perform almost identically according to the responses collected among appraisers who are parents/educators. Moreover, the overall accuracy ratios achieved by CQS and Kidzsearch are not statistically significant.

OPEN IN VIEWER

Fig. 11.

Performance assessment in terms of MRR for CQS and Kidzsearch, based on Mechanical Turk appraisers’ responses.

OPEN IN VIEWER

Fig. 12.

Accuracy ratios for CQS and Kidzsearch based on Mechanical Turk appraisers’ responses.