2015 IEEE International Symposium on Multimedia

ExploratoryVideoSearch: A Music Video Search System
Based on Coordinate Terms and Diversiﬁcation
Kosetsu Tsukuda

Masataka Goto

National Institute of Advanced Industrial
Science and Technology (AIST), Japank.tsukuda@aist.go.jp

National Institute of Advanced Industrial
Science and Technology (AIST), Japanm.goto@aist.go.jp

Abstract—Many people search and watch music videos onvideo sharing websites. Although a vast variety of videos are
uploaded, current search systems on video sharing websites
allow users to search a limited range of music videos for an
input query. Especially when a user does not have enoughknowledge of a query, the problem gets worse because the user
cannot customize the range by changing the query or adding
some keywords to the original query. In this paper, we proposea music video search system, called ExploratoryVideoSearch,that is coordinate term aware and diversity aware. Our system
focuses on artist name queries to search videos on YouTube andhas two novel functions: (1) given an artist name query, thesystem shows a search result for the artist as well as thosefor its coordinate terms; and (2) the system diversiﬁes search
results for the query and its coordinate terms, and allows users
to interactively change the diversity level. Coordinate terms are
obtained by utilizing the Million Song Dataset and Wikipedia,
while search results are diversiﬁed based on tags attached toYouTube music videos. ExploratoryVideoSearch enables users
to search a wide variety of music videos without requiring deep
knowledge about a query.

User’s intent
I want to know arsts
similar to Beyonce andwatch their various kinds ofmusic videos.

Arsts similar to Beyonce(Coordinate terms)
Madonna

Britney Spears

Various kinds of music videos(Diversicaon)

Celine Dion
Britney Spears

pop

3
dance

…
live

Graph analysis

Greedy selecon

Wikipedia
Million Song Dataset

YouTubeFigure 1. An overview of ExploratoryVideoSearch. Given user’s intent
as shown in the ﬁgure, the system ﬁrst obtains artists similar to Beyonce(they are called coordinate terms) from Wikipedia and the Million Song
Dataset by using graph analysis. Then the system searches for their various
kinds of videos using YouTube data based on a greedy selection algorithm(diversiﬁcation). Finally, the system outputs aggregated search results.

I. I NTRODUCTION
It has become common in recent years to watch music
videos on video sharing websites such as YouTube 1 . Formerly, most of music videos were uploaded by professional
creators; but now ordinary people can also easily upload
music videos in which they dance to or cover an artist’s
music [1]. As a result, there are various kinds of music
videos on video sharing websites. However, despite thevast variety of uploaded videos, the current user interface
for video searching allows users to browse only a limited
range of videos, especially when they do not have enoughknowledge about the query. Let us consider two examples.
EXAMPLE 1. A user becomes interested in Celine Dionand inputs her name as a query on YouTube. The user
watches videos related to Celine Dion and now wants toknow other artists like her. If the user has enough knowledge,
the user can input queries such as Mariah Carey or Beyonce
and then watch their videos. If the user does not, however,
it is not always easy to ﬁnd such keywords, and thus, theuser misses a chance to watch their videos.

EXAMPLE 2. A user becomes interested in Michael Jackson and searches for videos by his name on YouTube. Almost all the top-ranked videos are original Michael Jacksonsongs and the user watches some of them and leaves the site.
If the user has enough knowledge about Michael Jackson,
the user can watch videos in which Michael Jackson isinterviewed or a user dances to or covers his song by adding
keywords such as “interview” or “cover.” However, if theuser does not have enough knowledge, it is difﬁcult to thinkof such keywords. The user may be able to ﬁnd such videos
by scrolling through the search results, but most users arelikely to look at only the top of the search results [2]. Thus,
the user misses a chance to watch such videos.
In light of the above observations, we propose a newvideo search system called ExploratoryVideoSearch, whichis coordinate term aware and diversity aware. Figure 1
shows an overview of ExploratoryVideoSearch. ExploratoryVideoSearch enables users to search a wide varietyof videos without requiring a deep knowledge about a

1 http://www.youtube.com/

978-1-5090-0379-2/15 $31.00 © 2015 IEEE
DOI 10.1109/ISM.2015.99

Beyonce

Madonna
Beyonce12Kylie Minogue

Keywords-music video search; coordinate term; diversiﬁcation

Output

221

A

B

HITS
BeyonceC

Beyonce’s coordinate terms

Tag cloudGrammywinnerFrom
the U.S.
Woman

K. Minogue

K. Minogue

C. DionWoman

C. Dion

V. Reid

Human
being

Madonna

…

…

…

…
Human
being

Beyonce
GrammywinnerFrom
the U.S.

Madonna

V. Reid19

V. JaraSALSA

V. JaraFigure 3. An example of calculating coordinate term scores for “Beyonce.”

cloud, the system adds the tag to the original query andits coordinate terms, and shows their search results. For
example, if a user clicks “dance” in the search result of“Beyonce,” the system shows search results not only for“Beyonce dance” but also for “Madonna dance,” “Kylie
Minogue dance,” etc. The user can also change diversity
level for the results. These functions enable the user toexpand the user’s interest from the initial query artist.

Figure 2.
Search results for “Beyonce” with diversity level 1 (nondiversiﬁed search results).

query. More speciﬁcally, the main advantages of ExploratoryVideoSearch are twofold: (1) a user can ﬁnd information
about artists who are similar to an input query artist andbrowse their video search results at the same time; and (2)a user can view a wide variety of artist’s videos that are
related to not only the artist’s popular subtopics but also theartist’s minor or rare subtopics.

III. A LGORITHM
A. Coordinate Terms Collection
In this study, we collect the coordinate terms for a given
query using the method proposed by Tsukuda et al. [3]. We
ﬁrst describe the dataset, and then introduce the algorithm
in the following paragraphs.
This algorithm requires a dictionary containing hypernymhyponym pairs. In this paper, we developed a dictionary
containing only artists’ names as its hypernyms. The ﬁrst
step to develop the dictionary obtains artists’ names from
the Million Song Dataset [4]. We use 7,576 artists who haveJapanese Wikipedia articles from among the 44,745 artists inthe dataset so that we can make effective use of the tool usedin the second step. The second step obtains the hypernymsof each artist. We use an open source “hypernym/hyponym
extraction tool” to obtain these hypernyms [5]. This tool uses
machine learning to extract the hypernym-hyponym pairs
from Japanese Wikipedia. We applied this tool to the 201411-04 version of the Wiki-JP dump data, and this gave us
71,780 hypernym-hyponym pairs for the 7,576 artists. For
instance, “Beyonce” has 34 hypernyms such as “artist” and“winner of Grammy Awards.”
Given a query q, we create a bipartite graph G = ({q} ∪Cq ∪ Hq , E), where Cq and Hq are the set of coordinate
terms and the set of hypernyms of q, respectively, and E
is a set of edges between Hq and {q} ∪ Cq . An edge
exists between hi ∈ Hq and cj ∈ {q} ∪ Cq when hi isa hypernym of cj . Figure 3 shows the bipartite graph whenq is “Beyonce.” In the ﬁgure, the edge width and the heightof a rectangle represent the edge weight and the coordinate
term score, respectively. Only “Beyonce” has an initial value
before applying the algorithm as shown in the left graph. By
applying the method proposed by Tsukuda et al. [3], whichcalculates the appropriateness of each coordinate term in Cq
using the HITS [6] and SALSA [7] algorithms, the scores ofvertices that are connected to many vertices with bold edges

II. F UNCTIONSThis section describes the functions of ExploratoryVideoSearch.
When a user thinks “I want to know artists similar to
Beyonce and watch their various kinds of music videos,”Athe user inputs an artist name “Beyonce” in the textbox (in Figure 2) and chooses the diversity level of the video
B in Figure 2). Here,search results by clicking a button (the diversity level ranges from one to four. The higher thediversity level is, the more diversiﬁed search results the user
can see. In Figure 2, the user selects level 1, and then,ExploratoryVideoSearch generates search results for each of
the input artist and its top four coordinate terms: Madonna,
Kylie Minogue, Celine Dion, and Britney Spears (note thatlevel 1 generates non-diversiﬁed search results). This enables
the user to browse videos of artists that are similar to the
input artist. Although ExploratoryVideoSearch shows only
the top 15 search results for each artist, a user can examine
C inlower ranked videos by clicking the scroll button (Figure 2) and browsing a maximum of 200 videos for eachartist. It also allows the user to change the diversity level byclicking another diversity level button.
In addition, ExploratoryVideoSearch displays a tag cloudunder each video thumbnail so that the user can see tags
that are related to each video. This tag cloud shows tags thatappear equal to or more than ﬁve times in the artist’s search
results. The tags are displayed in random order and theirfont size represents its appearance frequency: 31pt, 24pt,
17pt, and 10pt for the frequencies of 50 ≥, 25 ≥, 15 ≥, and15 <. Even if a user does not know much about an artist,
they can understand the popular and rare tags for the artist
from the tag cloud, and watch the corresponding videos.
ExploratoryVideoSearch also allows a user to click on an
artist’s name to see its coordinate terms and their search
results. In addition, when a user clicks a tag in a tag

222

Original search result (OSR)

YouTube search result
1

pop
music

Tags aachedto this video.
2

…
200

Subtopic
pop

57

music

43

entertainment

26

parody

5

child

5

pop
music

dance
parodypop

Subtopic importance
Subtopic

Score

pop

0.33

music

0.22

lyrics

0.22

dance

0.11

parody0.11

lyricsmusic

Diversied search result (DSR)
danceparodyFigure 4.

poplyrics

5

4

3

dance
parodylyricsmusic

pop
lyrics

2

1

5

4

3

pop

pop
music

#

…

pop
ladieslyricsCollected subtopics…

KeywordBeyonce2

1

Figure 5.

An example of search result diversiﬁcation.

subtopics (“dance” and “parody”), even though its original
rank is low. Then the second ranked video in OSR is ranked
fourth because its original rank is high. Finally, the fourthranked video in OSR is ranked ﬁfth in DSR due to its
redundant subtopics and the low rank in OSR.
We slightly modiﬁed the algorithm by Dou et al. [8] todiversify a music video search result based on the viewcounts and attached tags of the videos. We describe themodiﬁed algorithm below. Let C denote the set of subtopics
and c be a member of C. Using the YouTube API, we
ﬁrst generate the top N non-diversiﬁed search results for a
keyword q. Here, N videos are ranked in descending orderof their view count. R denotes the results. Let rank(q, v)
denote the rank of video v in R. According to Dou et al.,the relevance score of video v with respect to keyword. When we computeq is given by rel (q, v) = √ 1

Subtopics mining from a YouTube search result.

become high as shown in the right graph. More details canbe found in Tsukuda et al. [3].
B. Subtopic Mining
We obtain the subtopics for q in order to diversify thevideo search results retrieved using a keyword q. Dou etal. treated related and suggested queries scraped from the
Web search engines as subtopics, while we treat a set oftags attached to the videos retrieved using a keyword as
subtopics. We ﬁrst generate the top N non-diversiﬁed search
results for q using YouTube API 2 to obtain a set of tags. The
videos are ranked in descending order by their view count.
Then, we pool the tags whose appearance frequencies areequal to or higher than θ, and treat them as subtopics. In
this paper, we use N = 200 and θ = 5. Figure 4 shows theprocess example for the keyword “Beyonce.”

rank (q,v)

rel (c, v), which is the relevance score of v with respect to a
subtopic c, we ﬁrst obtain the videos that are tagged with c,and rank them in descending order by their view count. We
denote the ranked list as Rc . Then, rel (c, v) is √ 1

C. Search Result Diversiﬁcation

rank (c,v)

if v ∈ Rc , and 0 otherwise.
Dou et al. [8] uses a greedy algorithm that iteratively
selects documents and generates a diversiﬁed ranking list.
Let Sn denote the top n videos selected so far. The n + 1-th
video is given by

We utilize the diversiﬁcation framework proposed by Dou
et al. [8]. In the following paragraphs, we ﬁrst intuitively
explain their algorithm and then describe the detail.
In their algorithm, videos that are relevant to more important subtopics and ranked higher in the original search
result (OSR) are ranked higher than those which are relevant
to less important subtopics and ranked lower in OSR. The
algorithm also tries to cover as many subtopics as possible
in the diversiﬁed search result (DSR), by minimizing theredundant retrieved videos for each subtopic. Figure 5 shows
an example of search result diversiﬁcation. For simplicity,
we consider top ﬁve videos in OSR and ﬁve subtopics in thisexample. The importance score of each subtopic is given in
the table. First, the ﬁrst ranked music video in OSR is alsoranked ﬁrst in DSR because it covers important subtopics.
Next, the second ranked video in OSR has a subtopic “pop,”
but it is already included in DSR. Although the third ranked
video in OSR also has the subtopic “pop,” the video has a
new subtopic “lyrics.” Therefore, the third ranked video in
OSR is ranked second in DSR. Similarly, the ﬁfth ranked
video in OSR is ranked third in DSR because it has two new

vn+1 = argmax[ρ · rel (q, v) + (1 − ρ) · Φ(v, Sn , C)]. (1)v∈R\SnIn ExploratoryVideoSearch, the diversity levels 1, 2, 3, and
4 correspond to ρ =1, 0.5, 0.1, and 0.001 in this equation.
Φ(v, Sn , C) represents a subtopic richness score of v given
the set Sn of videos already selected. In their algorithm, it isrequired to compute the importance of subtopic c, denotedby wc . In this paper, wc is given by wc =  freq(c,R),
freq(c ,R)
ci ∈C

i

where freq(c, R) is the number of videos that are taggedwith c in R. More details can be found in Dou et al. [8].
IV. E XPERIMENT
We discuss the actual performance of our system in thissection. Figure 2 and Figure 6 are the original non-diversiﬁed
search results with a diversity level of 1 and the diversiﬁed
search results with a diversity level of 3 for “Beyonce.” In
terms of the coordinate terms, the results are reasonable:

2 https://developers.google.com/youtube/2.0/developers guide protocol
audience?hl=en223

Level 1

Level 2

Level 3

Level 4# of unique tags

50

20

40
30
20
10
0
Top 5

Top 10

Top 15

Top 2020

Figure 7. The average number of unique tags covered in the top 5, 10,15, and 20 retrieved music videos with diversity level 1, 2, 3, and 4.

Figure 6.

results, diversiﬁcation has a positive effect: 10.88 tags arecovered with diversity level 1, while 28.17 tags are covered
with diversity level 4. These results indicate that users canwatch wide variety of music videos for many queries interms of covered subtopics by changing the diversity level.

Search results for “Beyonce” with diversity level 3.

Madonna, Kylie Minogue, Celine Dion, and Britney Spears
are among the top four coordinate terms for “Beyonce.”
Kylie Minogue, for example, shares nine hypernyms such as“artist,” “winner of Grammy Awards,” and “artist inﬂuenced
by Donna Summer” with “Beyonce,” and that resulted in thehigh coordinate score. By examining the results, a user cangain more information on artists like “Beyonce” and browse
their video search results at the same time.
As for the video search results with diversity level of
3, ExploratoryVideoSearch generates well diversiﬁed search
results that cover not only popular subtopics but also rare
subtopics. For example, videos in the top 15 search results
for “Beyonce” in Figure 2 are related to a subtopic “pop.”
Although the top 15 search results for “Beyonce” in Figure 6
allocate more space for videos that are related to “pop”
because it is an important subtopic for “Beyonce,” a video
that focuses on “lyrics” is ranked at six, and a video
related to “parody” and “dance” is ranked at 10: the former
and latter are originally at ranks of 85 and 55, but arepromoted by diversiﬁcation. Similarly, in the search results
for “Britney Spears” with diversity level of 3, a user can ﬁnd
a parody video ranked at 5 and a video in which computer
graphic characters are dancing to her music at 8: they were
promoted from ranks of 25 and 42 in the original search
results. Figure 6 also covers more tags than Figure 2. For
example, the top 15 search results for “Beyonce” in Figure 2
include 19 unique tags, while those in Figure 6 include 37
unique tags. Similarly, in Figure 2, there are 20 unique tags
for “Madonna,” 39 for “Kylie Minogue,” 34 for “Celine
Dion,” and 19 for “Britney Spears,” while in Figure 6, there
are 29 for “Madonna,” 50 for “Kylie Minogue,” 46 for“Celine Dion,” and 45 for “Britney Spears.”
Finally, we evaluated how many subtopics were coveredin the search results. 7,426 artists who had 50 ≥ retrieved
YouTube videos were selected from 7,576 artists in ourdataset for the evaluation. We counted the number of uniquetags covered in the top k search results with diversity level lfor each artist. Then the number of unique tags was averaged
over the 7,426 artists. k was set to 5, 10, 15, and 20; l was
set to 1, 2, 3, and 4. Figure 7 shows the results. Error bars
indicate the standard error of the mean. It can be observedthat the number of unique tags increases with the increaseof diversity level at any rank. Even in the top ﬁve search

V. C ONCLUSION
In this paper we presented a novel music video searchsystem called ExploratoryVideoSearch that enables users
to search for music videos on YouTube in an exploratory
way. Given an artist name query, ExploratoryVideoSearch
generates diversiﬁed search results for the query and thosefor its coordinate terms. It also allowed users to interactively
change the diversity level.
Our future work includes a user study that requires users
to perform video search tasks and quantitatively discuss theusefulness of ExploratoryVideoSearch. Another future workis the exploration of more sophisticated diversiﬁcation methods. Currently, we use only the tags attached by uploaders,
but we could also use comments posted on videos by theirviewers. Comment data could enable us to diversify thesearch results from the viewpoint of the viewers. Appropriate
keywords must be extracted from the comments in orderto realize this and a new diversiﬁcation method needs tobe proposed that balances between tags generated by the
uploaders and comments generated by the viewers.
ACKNOWLEDGEMENTS
This work was supported in part by CREST, JST.

R EFERENCES[1] M. Hamasaki, H. Takeda, and T. Nishimura, “Network analysis of
massively collaborative creation of multimedia contents: Case studyof hatsune miku videos on nico nico douga,” in UXTV, 2008, pp. 165–
168.
[2] T. Joachims et al., “Accurately interpreting clickthrough data as implicit
feedback,” in SIGIR, 2005, pp. 154–161.
[3] K. Tsukuda, H. Ohshima, and K. Tanaka, “Ranking of coordinate terms
and hypernyms using a hypernym-hyponym dictionary,” in WI-IAT,
2014, pp. 15–21.
[4] T. Bertin-Mahieux et al., “The million song dataset,” in ISMIR, 2011,
pp. 591–596.
[5] I. Yamada et al., “Generating information-rich taxonomy fromwikipedia,” in IUCS, 2010, pp. 96–103.
[6] J. M. Kleinberg, “Authoritative sources in a hyperlinked environment,”
J. ACM, vol. 46, pp. 604–632, 1999.
[7] R. Lempel and S. Moran, “SALSA: the stochastic approach for linkstructure analysis,” ACM Trans. Inf. Syst., vol. 19, pp. 131–160, 2001.
[8] Z. Dou et al., “Multi-dimensional search result diversiﬁcation,” in
WSDM, 2011, pp. 475–484.

224