Paolo Cremonesi

Franca Garzotto
email: franca.garzotto]@polimi.itroberto.turrin@contentwise.tv

Roberto Turrin

User-Centric vs. System-Centric Evaluation of Recommender Systems

Keywords: Recommender systems, E-tourism, Evaluation, Decision Making

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Recommender Systems (RSs) aim at helping users search large amounts of digital contents and identify more effectively the items that are likely to be more useful or attractive. For consumers overwhelmed by excessively wide offer of products or services, recommendations reduce information overload, facilitate the discovery of what they need or are interested to, help them to make choices among a vast set of alternatives, and potentially improve their decision making process. From a provider's perspective, RSs are regarded as a means to improve users' satisfaction and ultimately increase business. Most recommender systems operate by predicting the opinion (i.e., the numerical rating) that a user would give to an item (such as a movie, or a hotel), using a statistical model built from the characteristics of the item (content-based approaches) or the opinions of a community of users (collaborative-based approaches).

Some research has explored the effectiveness of RSs as decision support tools in the e-tourism domain, and has investigated how they influence users' decision making processes and outcomes [START_REF] Delgado | Knowledge bases and user profiling in travel and hospitality recommender systems[END_REF][START_REF] Ricci | Supporting travel decision making through personalized recommendation[END_REF][START_REF] Xie | Comprec-trip: A composite recommendation system for travel planning[END_REF][START_REF] Zanker | Evaluating recommender systems in tourism -a case study from austria[END_REF][START_REF] Jannach | Developing a conversational travel advisor with advisor suite[END_REF]28]. Empirical evidence suggests that RSs improve user's decision making and their influence depends on a variety of factors which are related to the quality of the recommender system.

RS quality can be defined either in terms of system-oriented metrics, which are evaluated algorithmically (e.g., precision, recall), or with user-centric experiments. [START_REF] Deshpande | Item-centric top-N recommendation algorithms[END_REF][START_REF] Herlocker | Evaluating collaborative filtering recommender systems[END_REF]28].

─ In user-centric evaluation, users interact with a running recommender system and receive recommendations. Measures are collected by asking the user (e.g., through interviews or surveys), observing her behavior during use, or automatically recording interactions and then subjecting system logs to various analyses (e.g., click through, conversion rate). ─ With system-centric methods, the recommender system is evaluated against a prebuilt ground truth dataset of opinions. Users do not interact with the system under test but the evaluation, in terms of accuracy, is based on the comparison between the opinion of users on items as estimated by the recommender system and the judgments previously collected from real users on the same items.

Although the user-centric approach is the only one able to truly measure the user's satisfaction on recommendations and the quality of the decision making process, conducting empirical tests involving real users is difficult, expensive, and resource demanding. On the contrary, system-centric evaluation has the advantage to be immediate, economical and easy to perform on several domains and with multiple algorithms.

Recently, many researchers have argued that the system-centric evaluation of RSs in e-commerce applications does not always correlate with how the users perceive the value of recommendations [START_REF] Bollen | Understanding choice overload in recommender systems[END_REF][START_REF] Cremonesi | Looking for "good" recommendations: a comparative evaluation of recommender systems[END_REF][START_REF] Cremonesi | Investigating the Persuasion Potential of Recommender Systems from a Quality Perspective: an Empirical Study[END_REF][START_REF] Mahmood | Adaptive recommender systems for travel planning[END_REF][START_REF] Pu | A User-Centric Evaluation Framework for Recommender Systems[END_REF][START_REF] Swearingen | Beyond algorithms: An hci perspective on recommender systems[END_REF]. This may happen because system-centric evaluation cannot reliably measure non-accuracy metrics such as noveltythe extension to which recommendations are perceived as newwhich more reflects the user and business dimensions. These works suggest that RS effectiveness in e-commerce applications should not be evaluated simply in terms of system-oriented accuracy but user-centric metrics should be adopted as well.

These contrasting results between system-centric and user-centric evaluation of RSs do not necessarily hold for e-tourism applications, because of the peculiar nature of the touristic product [START_REF] Hennig-Thurau | Electronic Word-of Mouth via Consumer-Opinion Platforms: What Motivates Consumers to Articulate Themselves on the Internet[END_REF][START_REF] Ricci | Product Reviews in Travel Decision Making[END_REF][START_REF] Senecal | The Influence of Online Product Recommendations on Consumers' Online Choices[END_REF][START_REF] Werthner | E-commerce and tourism[END_REF]: ─ Touristic products lack the feature of "try-before-buy" or "return in case the quality is below expectance". Online tourist service purchasing involves a certain amount of risk taking. ─ A priori comprehensive assessment of the quality of the touristic product is impossible: tourists must leave their daily environment to use it. ─ The touristic product has to do with an overall emotional experience. ─ In many circumstances, novelty is a weak quality attribute of touristic products.

Tourists can "reuse" and buy the same product again and again if they consider the experience emotionally satisfying.

Because of these differences that might impact on users' decision making, the online selling of touristic services cannot be considered as a special case of e-commerce, and the quality characteristic of this process might differ significantly in the two domains. This paper explores the influence of recommendations on decision making in the wide application arena of online tourism services, specifically considering hotel booking. Our research is grounded on a specific case studythe online reservations service provided by Venere.com, a subsidiary company of the Expedia group, one of the worldwide leaders in the hotel booking market, featuring more than 120,000 hotels, bed and breakfasts and vacation rentals in 30,000 destinations worldwide. Our joint work with Expedia addresses the following research question:

Do the algorithms which perform best in terms of system-centric quality generate recommendations that provide the best effects on decision making?

We focus our research on the effects of recommendations on decision making in relationship to a specific design factorthe recommendation algorithm used. We aim at exploring the differences between users who use an online booking system without recommendations and those who use the same booking system extended with personalized recommendations generated by different algorithms.

Our research investigates the effects of recommender algorithms from both a usercentric ("subjective") point of view and a system-centric ("objective") perspective. To explore our general research question and to evaluate if system-oriented metrics are able to correctly capture the quality of the decision making process from a user perspective, we carried on two wide and articulated empirical studies: 1. a system-centric evaluation to measure the objective quality in terms of accuracy (recall and fallout); this involved 210,000 simulated users, characterized by absence or presence of personalized recommendations, the latter being generated by three different algorithms (collaborative, content-centric, and hybrid); 2. a set of user-centric experiments involving 240 users and measuring different decision making attributes in four experimental conditions, characterized by the same four recommenders adopted in system centric evaluation.

The comparison of the evaluation outcomes shows that system-centric and usercentric metrics lead to consistent results, in contrast with past studies in e-commerce [START_REF] Cremonesi | Looking for "good" recommendations: a comparative evaluation of recommender systems[END_REF][START_REF] Cremonesi | Investigating the Persuasion Potential of Recommender Systems from a Quality Perspective: an Empirical Study[END_REF], and suggests that in the online hotel booking domain system-centric accuracy measures are good predictors of the beneficial effect of personalized recommendations on user's decision making. Our findings pinpoints that the relationship between the system-centric and user-centric metrics may depend on the business sector, is more complex that we may expect, and is a challenging issues that deserves further research.

Related Work

Recommender Systems in e-Tourism

The potential benefits of RSs in e-tourism have motivated some domain-specific researches. Ricci et al. in [START_REF] Ricci | Supporting travel decision making through personalized recommendation[END_REF] present NutKing, an online system that helps the user to construct a travel plan by recommending attractive travel products or by proposing complete itineraries. The system collects information about personal and travel characteristics and provides hybrid recommendations. NutKing searches for user-centric similar items and later ranks them based on a content-centric similarity between items and user's requirements. Levi et al. in [START_REF] Lops | Content-centric recommender systems: State of the art and trends[END_REF] describes a recommender system for online hotel booking. The system adopts a recommendation technique symmetric to technique described in [START_REF] Ricci | Supporting travel decision making through personalized recommendation[END_REF] and adopts sentiment-analysis to estimate user's rating from their reviews. Zanker et al. [START_REF] Zanker | Evaluating recommender systems in tourism -a case study from austria[END_REF] present an interactive travel assistant, designed for an Austrian spa-resort, where preference and requirement elicitation is explicitly performed using a sequence of question/answer forms. Delgado et al. in [START_REF] Delgado | Knowledge bases and user profiling in travel and hospitality recommender systems[END_REF] describe the application of a collaborative attribute-centric recommender system to the Ski-Europe.com web site, specialized in winter ski vacations. Recommendations are produce by taking into account both implicit and explicit user feedbacks. Implicit feedback is inferred whenever a user prints, bookmarks, or purchases an item (positive feedback) or does nothing after viewing an item (negative feedback).

Evaluation of recommender systems

Several studies have investigated how to measure the effectiveness of recommenders. A systematic review of system-centric evaluation techniques is reported by Herlocker et al. in [START_REF] Herlocker | Evaluating collaborative filtering recommender systems[END_REF]. More recently, some researchers [START_REF] Burke | Hybrid web recommender systems[END_REF][START_REF] Mahmood | Adaptive recommender systems for travel planning[END_REF][START_REF] Mcnee | Being accurate is not enough: how accuracy metrics have hurt recommender systems[END_REF][START_REF] Pu | A User-Centric Evaluation Framework for Recommender Systems[END_REF][START_REF] Swearingen | Beyond algorithms: An hci perspective on recommender systems[END_REF] have argued that RS effectiveness should not be evaluated simply in terms of system-centric metrics and have investigated user-centric evaluation methods, which focus on the human/computer interaction process (or User eXperience, UX) [START_REF] Lops | Content-centric recommender systems: State of the art and trends[END_REF][START_REF] Pu | A User-Centric Evaluation Framework for Recommender Systems[END_REF][START_REF] Tintarev | Explanations of recommendations[END_REF].

Swearingen and Sinha [START_REF] Swearingen | Beyond algorithms: An hci perspective on recommender systems[END_REF] were among the first studies to point out that subjective quality of a RS depends on factors that go beyond the quality of the algorithm itself. Without diminishing the importance of the recommendation algorithm, these authors claim that RS effectiveness should not be evaluated simply in terms of system-centric accuracy metrics. Other design aspects, ignored by these metrics, should be measured, and in particular those related to the acceptance of the recommender system and of its recommendations.

Along the same vein, other researchers have investigated the so called user-centric methods, which focus on how user characteristics are elicited and recommended items are presented, compared, or explained. They explore "subjective" quality of RSs and attempt to correlate it to different UX factors. They highlight that, from a user's perspective, an effective recommender system should inspire credibility and trust towards the system [START_REF] Pu | A User-Centric Evaluation Framework for Recommender Systems[END_REF] and it should point users towards new, not-yet-experienced items [START_REF] Lops | Content-centric recommender systems: State of the art and trends[END_REF].

Due to the intrinsic difficulty of performing user studies in the RS domain, empirical results in this field are tentative and preliminary. Celma and Herrera [START_REF] Celma | A new approach to evaluating novel recommendations[END_REF] report an experiment that studied how users judged novel recommendations provided by a CF and a CBF algorithm in the music recommendation context. Ziegler et al. [START_REF] Ziegler | Improving recommendation lists through topic diversification[END_REF] and Zhang et al. [START_REF] Zhang | Novelty and redundancy detection in adaptive filtering[END_REF] propose diversity as a quality attribute: recommender algorithms should seek to provide optimal coverage of the entire range of user's interests. This work is an example of a combined use of automatic and user-centric quality assessment techniques. Pu et al. [START_REF] Pu | A User-Centric Evaluation Framework for Recommender Systems[END_REF] developed a framework called ResQue, which defines a wide set of user-centric quality metrics to evaluate the perceived qualities of RSs and to predict users' behavioral intentions as a result of these qualities.

The Design of the Studies

The research question presented in the Introduction has been explored with two studiesa system-centric simulation and a user-centric experimentsummarized in Table 1. In both the studies, the effects of recommendations have been explored under 4 different experimental conditions defined by one manipulated variable: the recommendation algorithm. Our study considers one non-personalized algorithm and three personalized RSs representatives of three different classes of algorithms: collaborative, content and hybrid.

─ HotelAvg is a non-personalized algorithm and presents hotels in decreasing order of average user rating [START_REF] Konstan | Recommender systems: from algorithms to user experience[END_REF]. This is the default ranking option adopted in our study when the user does not receive personalized recommendations. The same ranking strategy is adopted by most online hotel booking systems such as TripAdvisor, Expedia, and Venere. ─ PureSVD is a collaborative algorithm based on matrix-factorization; previous research shows that its accuracy is one of the best in the movie domain [START_REF] Cremonesi | Investigating the Persuasion Potential of Recommender Systems from a Quality Perspective: an Empirical Study[END_REF]. ─ DirectContent recommends hotels whose content is similar to the content of hotels the user has rated [START_REF] Lops | Content-centric recommender systems: State of the art and trends[END_REF]. Content analysis takes into account the 481 features (e.g., category, price-range, facilities), the free text of the hotel description, and the free text of the hotel reviews. DirectContent is a simplified version of the LSA algorithm described in [START_REF] Bambini | A Recommender System for an IPTV Service Provider: a Real Large-Scale Production Environment[END_REF]. ─ Interleave is a hybrid algorithm that generates a list of recommended hotels alternating the results from PureSVD and DirectContent. Interleave has been proposed in [START_REF] Burke | Hybrid web recommender systems[END_REF] with the name "mixed hybridization" and, although trivial in its formulation, has been shown to improve diversity of recommendations.

Study 1: System-centric evaluation

The first study analyzes the accuracy of recommendations as a function of the recommender algorithm. For the evaluation, Venere.com made us available a catalog of more than 3,000 hotels and 72,000 related users' reviews. Each accommodation is provided with a set of 481 features concerning, among the others: accommodation type (e.g., residence, hotel, hostel, B&B) and service level (number of stars), location (country, region, city, and city area), booking methods, average single-room price, amenities (e.g., spa), and added values (e.g., in-room dining). User's reviews associated to each accommodation consist of numeric ratings and free-text.

We have enriched the dataset with additional reviews extracted from the TripAdvisor.com web site using a web crawling tool.

Dependent Variables.

System-centric quality can be measured by using either accuracy metrics (e.g., precision, recall and fallout) or error metrics (e.g., RMSE and MAE). The hybrid algorithm tested in this study cannot be evaluated with error metrics since it does not compute actual ratings [START_REF] Konstan | Recommender systems: from algorithms to user experience[END_REF]. Hence we have considered only accuracy metrics. In particular we focused our attention on recall (the conditional probability of suggesting a hotel given it is relevant for the user) and fallout (the conditional probability of suggesting a hotel given it is irrelevant for the user) as the dependent variables. A good algorithm should have large recall (i.e., it should be able to recommend hotels of interest to the user) and low fall-out (i.e., it should avoid to recommend hotels of no interest to the user).

The methodology adopted to measure the two variables is the same used in many works on recommender systeme.g., [START_REF] Cremonesi | Investigating the Persuasion Potential of Recommender Systems from a Quality Perspective: an Empirical Study[END_REF][START_REF] Koren | Factorization meets the neighborhood: a multifaceted collaborative filtering model[END_REF]. Ratings in the dataset were randomly split into two subsets: training set (90% of the ratings) and test set (10% of the ratings). In order to measure recall, we first trained the algorithms using the ratings in the training set. Then, for each user in the test set and for each hotel in the test set that was rated 10-stars or 9-stars by the user (we assumed these hotels to be relevant for the users) we followed these steps: ─ We randomly selected 1,000 additional hotels that were not rated by the user. We assumed that the user was not interested in most of them. ─ We predicted the ratings for the relevant hotel and for the additional 1,000 hotels. ─ We formed a recommendation list by picking the N hotels with the largest predicted ratings (top-N recommendation).

For each recommendation we have a hit (e.g., a successful recommendation) if the relevant hotel is in the list. Therefore, the overall recall was computed by counting the number of hits (i.e., the number of successful recommendations) over the total number of recommendations A similar approach was used to measure fallout, with the only difference being that we selected non-relevant hotelsdefined as the hotels rated lower than 2 out of 10 stars. The fallout was computed as



Recall and fallout range from 0% to 100%. An ideal algorithm should be able to recommend all of the interesting hotels (i.e., recall equals to 100%) and to discard all of the uninteresting hotels (i.e., fallout equals to 0%).

Study 2: User-centric evaluation

The second study analyzes opinions and behavior of 240 users interacting with an online hotel booking service.

Dependent Variables.

We model the effects on decision making that can be associated to the introduction of personalized recommendations using some subjective attributes resulting from the user's perception and judgment of the decision activity (subjective variables) as well as some objectively measurable attributes of the decision processes (objective variables). The variables, listed in Table 1, have been defined according to the model described in [START_REF] Werthner | E-commerce and tourism[END_REF]: ─ Choice satisfaction: the subjective evaluation of the reserved hotel in terms of quality/value for the user; ─ Choice risk: the user's perception of uncertainty and potentially adverse consequences of booking the chosen hotel, measured in terms of the perceived degree of mismatching between the characteristics of the chosen hotel emerging from the use of the system and the real characteristic of the accommodation; ─ Perceived time: the user's judgment on the length of the decision making process; ─ Elapsed time: the time taken for the user to search for hotel information and make a reservation decision; ─ Extent of hotel search: the number of hotels that have been searched, for which detailed information has been acquired; ─ Number of sorting changes: the number of times the user changed the ordering of hotels in the list view: the default ordering is (i) descending order of average user ratings, when there are no recommendations, and (ii) descending order of estimated user relevance, when there are recommendations. Ordering change is a measure of the efficacy of RSs in situations where the conversion rate, i.e., the percentage of recommended items that are actually purchased by users [START_REF] Zanker | Evaluating recommender systems in tourism -a case study from austria[END_REF] cannot be assessed. This happens, for example, when a system does not present a separate list of recommended items, but recommendations are rendered by sorting items in descending order of relevance as estimated by the recommender algorithm, which represents the "de facto" recommendation list.

A questionnaire has been used to measure choice satisfaction, choice risk and perceive time. Measures of effort and efficacy (execution time, extent of hotel search, number of sorting changes) have been obtained by analyzing the interaction data collected from the system logs.

Instruments.

For the purpose of our study, we have developed PoliVenus, a web-centric testing framework for the hotel booking field, which can be easily configured to facilitate the execution of controlled empirical studies in e-tourism services (Figure 1). PoliVenus implements the same layout as Venere.com online portal and simulates all its functionality with the exception of payment functions. PoliVenus contains the same catalog of hotels and reviews used in the first study. The Polivenus framework is based on a modular architecture and can be easily customized to different datasets and types of recommendation algorithms. Its current library of algorithms comprises 20 algorithms, developed in cooperation with ContentWise2 . PoliVenus can operate in two different configurations:

─ Baseline configuration: it corresponds to the existing Venere.com portal. Users can filter the hotel catalogue according to hotel characteristics (e.g., budget range, stars, accommodation type, city area), and retrieve non-personalized results. They can sort the list by popularity, service level, price, or user average rating (the default sorting option). The default sorting option corresponds to the HotelAvg nonpersonalized recommender algorithm. ─ Personalized configuration: it is almost identical to the baseline configuration, the only difference being the personalized recommendations. When watching a list of hotels previously filtered according to accommodation characteristics, the user is offered an additional option to sort hotels on the basis of the personalized recommendations (this is the default sorting option).

The user profile required by the algorithms to generate recommendations is based on the user's current interaction with the system (implicit elicitation). This choice is motivated by three specific reasons: (i) we want to support users who have no rating history or who are not interested in logging into the system; (ii) we are interested in exploring a smooth integration of personalized recommendations in existing online booking systems; to enable explicit elicitation would require the introduction of an intrusive add-on; (iii) according to a large number of works, the lower effort of implicit elicitation (as compared to explicit elicitation) is related to higher perceived effectiveness of recommendations [START_REF] Drenner | Crafting the initial user experience to achieve community goals[END_REF][START_REF] Golbandi | On bootstrapping recommender systems[END_REF][START_REF] Jones | User technology adoption issues in recommender systems[END_REF][START_REF] Rashid | Learning preferences of new users in recommender systems: an information theoretic approach[END_REF]. The implicit elicitation mechanism adopted in PoliVenus is the following: whenever a user interacts with an object on the interface, the system assigns a score to the hotel related to that object (e.g. link, button, map, picure, etc.). With all these signals, PoliVenus builds the user profile for the current user session: the user profile contains implicit hotel ratings, where each rating is computed as the maximum of all the signals generated for that hotel. The user profile is continuously updated with every new signal and the list of recommended hotels is updated accordingly.

Following the definition of Ricci and Del Missier in [START_REF] Ricci | Supporting travel decision making through personalized recommendation[END_REF] we considered short-term and long-term signals. In our implementation the short-term signal is the last interac-tion of the user with the system. All previous interactions with the system are considered long-term signals. In order to give more importance to the most recent interaction, we have employed an exponential decay function to the ratings. Whenever a new signal enters in the user profile, all previous ratings are divided by a dumping factor. The magnitude of the damping factor controls the decay rate. In our experiments we have used a damping factor of 2.

Participants and procedure.

Our main research audience is represented by users aged between 20 and 40 who have some familiarity with the use of the web and had never used Venere.com before the study (to control for the potentially confounding factor of biases or misconceptions derived from previous uses of the system). The total number of recruited subjects who completed the task and filled the questionnaire by the deadline was 240. They were equally distributed in the four experimental conditions. We recruited participants from current students and ex-alumni from the School of Engineering and the School of Industrial Design of our university. They were contacted by e-mail, using university mailing lists. The invitation included the description of the activities to be performed and the reward for taking part in the study. Users were not aware of the true goal of the experiment.

To encourage participation, and to induce participants to play for real and to take decisions as they would actually do when planning a vacation, we used a lottery incentive [START_REF] Porter | The Impact of Lottery Incentives on Survey Response Rates[END_REF]. Participants had the chance of winning a prize, offered to a randomly selected person who completed the assigned decision making task and filled the final questionnaire by a given deadline. The prize consisted of a coupon of the value of 150€ to be used to stay in the hotel fictitiously reserved using PoliVenus.

All participants were given the following instructions: "Imagine that you are planning a vacation in Rome and are looking for an accommodation during Christmas season; choose a hotel and make a reservation; dates and accommodation characteristics (stars, room type, services, and location) are at your discretion. After confirming the reservation (simulated), please complete the final questionnaire" . After accessing PoliVenus, reading the instructions, and agreeing on the study conditions (lottery participation and privacy rules), each participant was automatically moved to the homepage of the PoliVenus hotel reservation system and randomly as-signed to one of the four experimental conditions. After committing the reservation, the user was directed to the questionnaire page containing 11 questions, a subset of which is reported in Table 3.

Results

Study 1: System-centric evaluation

Figure 2 presents a plot of recall versus fallout, where each point on the curve corresponds to a value of the number N of recommended hotels. A perfect recommendation algorithm will generate a curve that goes straight to the upper left corner of the figure, until 100% of relevant hotels and 0% of non-relevant hotels have been recommended.

The figure shows that the hybrid Interleaved algorithm is the most accurate. The accuracy of the content and collaborative algorithms (DirectContent and pureSVD) is not significantly better than the accuracy of the non-personalized baseline HotelAvg.

Study 2: User-centric evaluation

We first polished the collected data by removing the ones referring to subjects who showed apparent evidences of gaming with the testing system (e.g., those who interacted with the system for less than 2 minutes) or left too many questions unanswered.

In the end, we considered the data referring to 229 participants. They were almost equally distributed in the four experimental conditions, each one involving a number of subjects between 54 and 58.

Subjective metrics.

We used ANOVA to test the effects of the algorithm on the dependent variables. The tests suggest that the algorithm has a significant impact (p<0.05) on all of the subjective variables (Choice Satisfaction, Perceived Risk, Perceived Time). We ran multiple pair-wise comparison post-hoc tests using Tukey's method on subjective variables. The results are shown in Figures 345, where the mean is represented by a circle and the 95% confidence interval as a line.

The results show that the adoption of the hybrid Interleaved algorithm significantly increases user satisfaction and decreases both perceived risk and effort with respect to the non-personalized HotelAvg configuration. On the contrary, content and collaborative algorithms (DirectContent and pureSVD) do not affect user satisfaction and perceived effort with respect to the baseline scenario, although DirectContent reduces the perceived risk.

Objective metrics.

Behavioral data emerging from the tracking of users' interaction provides some interesting results. PoliVenus does not us enable to directly measure the efficacy of the RS using conversion rate metrics, because it does not explicitly present a separate list of recommended items. The hotel list view, where hotels are sorted in descending order of relevance as estimated by the recommender algorithm, is the actual recommendation list. As mentioned in the previous section, we have estimated the efficacy of the RS by measuring how many users changed the default sorting options (recommended hotels first) by setting other parameters (e.g., price, popularity, stars). The results show that only 37% of the users with personalized recommendations changed the sorting of hotels compared to 54% of the users in the baseline scenario (e.g., with non-personalized recommendations).

Surprisingly, the value of the two objective effort variables (elapsed time and number of explored hotels) is not affected by the recommender systems. Regardless the presence of personalized recommendations, the number of explored hotels is between 5 and 8 for almost all of the users. In other words, customers wish to compare in details at least 5 and no more than 8 alternative choices before committing to a final decision. Moreover, the time required to complete the task is between 10 and 22 minutes for 95% of the users and is not affected by the presence of personalized recommendations.

Discussion and conclusions

This section discusses the validity of our empirical study, analyses the findings in relationship to our research question, and provides some possible interpretation of results, also in light of the current state of the art.

Validity of our study

The internal validity of our study is supported by the accuracy of our research design and by the quality of study execution. We have carefully implemented a mechanism to randomly assign participants to the different experimental conditions. We have adopted a lottery incentive to improve the accuracy of the task's execution and offered a shared motivation to all participants. Obviously, the individuals' intrinsic characteristics and actual behavior always bring to an experiment a myriad of factors that can be hardly controlled. In terms of external validity, the results of our study are limited to those participants and conditions used in our study. The applicability of our results might not be confined to the specific online booking system used. Most services available in the market provide a user experience very similar to Venere.com, in terms of filtering criteria and information/navigation structures, and it is likely that replications of our study on other systems may lead to results consistent with our findings. Finally, the high overall number of testers (240) and the relatively high number of subjects involved in each experimental condition (between 54 and 58) may allow us to generalize our results to a wider population of users aged 20-40.

In the "with-RS" experimental conditions, there might be a potentially confounding factor which might affect the results. The list of presented hotels for a user in the "with-RS" condition changes after each interaction, as the user profile is updated with each new "signal". On the contrary, the user in the "without-RS" condition sees no updates to the list of presented hotels, unless she explicitly changes the search criteria. This phenomenon could explain why users not receiving personalized recommendations take more initiative in changing the sorting of hotels in the list. However, as the different "with-RS" conditions provided exactly the same results, we may argue that the effect of recommender systems on the users' behavior is genuine and not affected by the different "dynamics" of the list of hotels "with" and "without recommendations". To further validate this assumption, in future tests it may be worth considering changing the list of hotels in the menu entry of presented hotels after each signal also for the no-RS subjects (in some random re-sort).

Research question

Overall, our findings answer our research question: system-centric evaluation can be used to compare the effects of different recommender algorithms on the decisionmaking process in online hotel booking. A finer grained analysis of the statistically relevant relationships among all the different variables offers a much more articulated picture of the results, which are apparently in contrast with previous findings and suggest a number of interesting considerations for e-tourism applications:

─ system-centric accuracy metrics (e.g., recall and fallout) are a good approximation of the quality perceived by the use; ─ personalized recommendations do not reduce the decision-making effort; moreover, there is a mismatch between objective and perceived effort.

System-centric vs. user-centric evaluation.

The comparison between Figures 2 and3 shows a strong consistency between system-centric accuracy (e.g., recall and fallout) and the users' perceived quality. We can claim that, in the e-tourism domain, system-centric quality attributes are good predictors of how the users perceive the quality of a recommender algorithm. This result is apparently in contrast with previous works [START_REF] Cremonesi | Investigating the Persuasion Potential of Recommender Systems from a Quality Perspective: an Empirical Study[END_REF][START_REF] Mahmood | Adaptive recommender systems for travel planning[END_REF][START_REF] Pu | A User-Centric Evaluation Framework for Recommender Systems[END_REF][START_REF] Swearingen | Beyond algorithms: An hci perspective on recommender systems[END_REF] which state that user satisfaction is not correlated with accuracy of algorithms.

A possible interpretation of this result is to consider that, in traditional e-commerce applications, non-accuracy attributes such as novelty have an important role in shaping the user satisfaction. This is not necessarily the case with touristic services as they have a number of peculiar aspects that call for a rethinking of the decision making process normally assumed in traditional e-commerce and affect which RSs attributes impact on the user final choices [START_REF] Hennig-Thurau | Electronic Word-of Mouth via Consumer-Opinion Platforms: What Motivates Consumers to Articulate Themselves on the Internet[END_REF][START_REF] Ricci | Product Reviews in Travel Decision Making[END_REF][START_REF] Senecal | The Influence of Online Product Recommendations on Consumers' Online Choices[END_REF][START_REF] Werthner | E-commerce and tourism[END_REF]: ─ The touristic product is complex and emotional. Booking hotel rooms requires a considerable decision effort, as the user might lack background knowledge of the characteristic of the possible accommodations. A priori comprehensive assessment of hotel accommodations is impossible. Touristic products lack the feature of "trybefore-buy" or "return-if-not-satisfied". In case the quality of the accommodation is below expectance, the whole travel experience will be negatively affected and the memory of it will be persistent over time. The opportunity to fill that particular period of the user life with a positive experience will be lost. ─ The touristic product is volatile. Hotel rooms are limited in number and, especially in high-seasons, the best-value accommodations are sold-out months in advance.

Even optimizers (i.e., users who would choose the "best" possible hotel) could be urged to take sub-optimal decisions. These aspects imply that (i) online hotel booking involves a certain amount of risk taking, and (ii) the user needs to minimize such risk by searching for an accommodation perfectly matching his/her largely unexpressed requirements. Accuracy, e.g., the perfect matching between user needs and solutions proposed, may become the most important attribute of recommendations as it reduces the perceived risk.

Decision effort.

There is no significant variation among personalized algorithms with respect to objective effort: none of them statistically differ from the baseline in terms of execution time and extent of product search, i.e., number of explored hotel pages. Our results show a mismatch between satisfaction and effort: users exposed to hybrid and content recommendations perceived the decision activity process as more satisfying than those without personalized recommendations, although they spent the same time in the process. Moreover, there is a mismatch between objective and perceived effort: users exposed to hybrid recommendations perceived the decision activity process as shorter (Figure 5), and more trustworthy (Figure 4), than the others, although they spent the same time and explored the same number of hotels. This result is partially in line with some previous studies which explored subjective vs. objective effort under different conditions of RS design [START_REF] Ricci | Supporting travel decision making through personalized recommendation[END_REF]. Works on preferences elicitation pinpoint for example that more effort-intensive sign up activities do not necessarily imply higher perceived effort [START_REF] Swearingen | Beyond algorithms: An hci perspective on recommender systems[END_REF], as if the effort perception were mitigated by the benefits of a more satisfying decision process. Other works hypothesize that, thanks to RSs, users spend less time in searching for items and more time in the more satisfactory activity of exploring information related to the choice processes [START_REF] Ricci | Supporting travel decision making through personalized recommendation[END_REF].

Conclusions

In spite of some limitations, our work represents a contribution to the research and practice in RS design and evaluation, for the specific domain of online booking and from a more general perspective. Our research differs from previous work in this domain for a number of aspects:

─ We smoothly extend a true online booking system (Venere.com) with personalized recommendations without creating major modifications to the "standard" interaction flow and overall user experience. Our userboth in the control group and in the treatment groupsis always in control of all information and functionality of conventional online booking services. In contrast, most previous works either are based on prototype RSs or create ad hoc user experiences for the subjects exposed to recommendations. ─ We compare three different personalized algorithms against the baseline scenario (non-personalized) and against each other. Previous works limit their analysis to a single recommendation algorithm evaluated against a non personalized baseline. In addition, we consider recommenders involving implicit elicitation, while most of existing studies in the e-tourism domain address recommenders with (more intrusive) explicit elicitation ─ Our results on the comparison between system-centric and user-centric evaluation are totally new for the e-tourism domain. They show that the peculiarity of the touristic products may exploit different aspects of recommender systems, and suggest the possibility to adopt system-centric evaluation techniques as a good approximation of the user experience.

In relationship to other studies in e-tourism and in other domains, the research design of our empirical study is per se a strength of our work, for a number of reasons: the large number of variables that have been measured, the sophisticated technological instrument used (the PoliVenus framework), the vast size of the involved subjects (240), and the lottery based incentive mechanisms adopted to motivate users and commit them to realistic and sound task execution. Overall, our findings extend our understanding of the potential of introducing recommendations to improve decision making processes. At the same time, our results help us to identify potential weakness of current state of the art approaches in RSs and can orient future investigations in the field.

SortingFig. 1 .

 1 Fig. 1. Screenshot of the PoliVenus page showing a list of hotels

Fig. 2 .

 2 Fig. 2. System-centric evaluation: Recall vs.Fallout

Fig. 3 .Fig. 4 .

 34 Fig. 3. Choice Satisfaction: how much are you satisfied with your final choice? (1: not too much -5: very much)

Fig. 5 .

 5 Fig. 5. Perceived Effort: the time required to book the hotel is … (1: short -5: overmuch)

Table 1 .

 1 Experimental conditions used in the two studies

	Study	Type	Independent variables (algorithms)	Dependent variables	Users
	1	System-centric simulation		Accuracy (recall and fallout)	210,000 (simulated)
			HotelAvg PureSVD	Choice satisfaction	Satisfaction
			DirectContent	Choice risk	Trust	subjective
	2	User-centric experiment	Interleave	Perceived time Elapsed time	Effort	240 (total)
				Extent of hotel search		objective
				Menu interactions	Efficacy

Table 2

 2 reports the detailed statistics of the dataset used in our experiments.1

Table 2 .

 2 Dataset used in the two studies.

		Total	Venere TripAdvisor
		(Venere+TripAdvisor)		(crawled)
	Hotels	3,100	3,100	
	Users (reviewers)	210,000	72,000	138,000
	Reviews and ratings	246,000	81,000	165,000
	Hotel features	481	481	

Table 3 .

 3 Excerpt from the questionnaire

	Question	Range	Dependent Variable
	How much are you satisfied with your final choice?	1:not too much 5:very much	Choice Satisfaction
	The time required to book the hotel is:	1:short 5:overmuch	Perceived Time
	How much will the characteristics of the reserved hotel correspond to those of the real accommodation?	1:not much, 5:very much	Choice Risk

The dataset is available by contacting the authors.

www.contentwise.tv


Abir Al-Hajri
email: abira@ece.ubc.ca

Gregor Miller
email: gregor@ece.ubc.ca

Sidney Fels
email: ssfels@ece.ubc.ca

Matthew Fong
email: mfong@ece.ubc.ca

Video Navigation with a Personal Viewing History

Keywords: Video Navigation, Navigation History, Video Summarization

We describe a new video interface based on a recorded personal navigation history which provides simple mechanisms to quickly find and watch previously viewed intervals, highlight segments of video the user found interesting and support other video tasks such as crowd-sourced video popularity measures and consumer-level video editing. Our novel history interface lets users find previously viewed intervals more quickly and provides a more enjoyable video navigation experience, as demonstrated by the study we performed. The user study tasked participants with viewing a pre-defined history of a subset of the video and answering questions about the video content: 83.9% of questions (average) were answered correctly using the personal navigation history, while 65.5% were answered using the state-of-art method; they took significantly less time to answer a question using our method. The full video navigation interface received an 82% average QUIS rating. The results show that our history interface can be an effective part of video players and browsers.

Introduction

The dramatic increase in the quantity of video now available, either in the online form of services such as YouTube TM , Vimeo TM or the more personal form of home video, provides new challenges such as finding specific videos (or intervals within video), authoring new videos from existing content (e.g. video summarization or home movie editing), sharing video playlists (or even intervals) of online video and annotating dynamic content. The increased volume and shrinking average duration of online video has led to new use cases: users are generally free to skip ahead to find intervals which interest them; users may re-watch part of the video they enjoyed; users may employ temporal video links to provide instant access to a specific time within a video, skipping irrelevant sections; playlists and temporal links provide opportunities for customization and sharing of video consumption among users. In short, users can and want to view personally interesting intervals easily and without viewing the entire video. These use cases are supported within current interfaces, however there are no existing mechanisms to support new use cases which arise as a natural consequence, such as navigation of previously viewed intervals. Additionally, users often re-watch segments of video as part of the contemporary browsing and navigation experience [START_REF] Shamma | Watch what I watch: using community activity to understand content[END_REF][START_REF] Syeda-Mahmood | Learning video browsing behavior and its application in the generation of video previews[END_REF][START_REF] Yu | Video summarization based on user log enhanced link analysis[END_REF], and may wish to share these intervals with others. A historical record of video viewing would allow users to quickly find popular intervals, comment on and share them. We introduce our novel video interface, which captures the user's viewing history (analogous to a web browser history) and allows them to reuse it as a navigation tool, through a user-time visualization with supporting interactions. The history supports actions such as faster access to previously viewed intervals, visualization of popular intervals within the video based on a user's temporal view count, simpler authoring via selection of viewed intervals and provides the user with the ability to create a personalized map of the video (e.g. deciding on their own separation of the video into chapters, or highlighting interesting intervals). This type of history interface is not currently supported in commercial products, thus, we are studying interfaces for managing personal viewing history to evaluate effectiveness for inclusion in future video interfaces.

Our research focuses on the utility of video history, examining use cases and establishing which are significantly affected given a user-based timeline of video viewing. The interface we designed (shown in Figure 1) includes a filmstrip visualization below the main video player representing the entire video, and a history to the right of the player with a sequence of intervals ordered top-down by user-time. We discovered through pilot studies that the filmstrip and history are equivalent in navigation speed to find a previously viewed event in the case where the entire video is viewed, although the history interface was preferred since users were able to customize which intervals were visualized. Our study shows that when a subset of the video is viewed, the history significantly outperforms the state-of-art, and 75% of participants preferred the history in this use case. The study found that our history-based authoring interface was useful, easy to use and enjoyable, and participants were keen to see this functionality in YouTube.

We begin with a discussion of the related work, followed by a description of the video navigation interface (including all widgets and interactions used). The evaluation of the use of a history and the interfaces we designed to support it is presented, looking at users' impressions of using a personal video history and the power of using history for fast video navigation.

Motivation

Consider the following scenario with Robert and Elisa: Robert received a YouTube link from his friend Tom about his family vacation to Rome last summer. Robert and his wife Elisa watched the video along with other videos about Italy to enjoy a sense of Tom's holiday. Robert enjoyed some segments of the videos and wanted to share them with his kids when they came home. When they arrive, he browses his history view and jumps to the good bits to show them. After seeing how nicely the Italy videos looked, Elisa suggests creating a video of their last vacation to Vancouver using various videos and photos they captured. Robert had watched these videos many times and he was excited about including particular events from the 12 hours of video he had obsessively taken during their 4-day holiday. He goes to his history view and grabs the shots of the parade and fire works of Canada day, the suspension bridge and swimming at Lynn Canyon Park, along with another 10 segments that he had watched at various times with Elisa and the kids before. He then drags them into the authoring window and creates a new video that he shares with his friends. . This scenario emphasizes the major contributions of our work: (1) a novel video navigation interface for video viewing that captures and visualizes a user's personal history; (2) an experiment that confirms using personal video navigation history is faster in finding previously seen events within videos in contrast to the state-of-art method, filmstrip; (3) a simple video mash-up tool that can be used to summarize videos by using intervals from history or simply watching the corresponding intervals, in comparison to other video editing software where users need to add a video clip, watch it, and then trim it.

Related Work

Retrieving and reusing information from the past is a common activity for users [START_REF] Cockburn | What do web users do? an empirical analysis of web use[END_REF].

In the domain of web browsers, researchers have introduced and developed different tools that keep records of user's browsing experiences for later use. However, keeping and reusing navigation experiences in a video space has not received similar attention. Web browsing history is useful for various domains, thus, we expect our research on effective mechanisms for video watching history management will also benefit various fields where video plays an increasingly important role e.g. education, entertainment, etc. History of user actions has been widely investigated for multiple purposes in different domains including web [START_REF] Card | Information scent as a driver of web behavior graphs: results of a protocol analysis method for web usability[END_REF][START_REF] Li | Here's what I did: sharing and reusing web activity with actionshot[END_REF][START_REF] Hupp | Smart bookmarks: automatic retroactive macro recording on the web[END_REF], workflow [START_REF] Grossman | Chronicle: capture, exploration, and playback of document workflow histories[END_REF][START_REF] Nakamura | An application-independent system for visualizing user operation history[END_REF], tutorial generation [START_REF] Bergman | Docwizards: a system for authoring follow-me documentation wizards[END_REF] and information visualizations [START_REF] Heer | Graphical histories for visualization: Supporting analysis, communication, and evaluation[END_REF][START_REF] Guimbretiere | Experiscope: an analysis tool for interaction data[END_REF]. These are based on mostly static media and so do not directly apply to video: unlike static media, two timelines exist when capturing user history: video timeline and user (or history) timeline. Recording a user's actions, therefore, requires more sophisticated representations, visualization layouts and interaction techniques. In our interface to eliminate the confusion between different timelines, we used a vertical layout to indicate a user's timeline while a horizontal layout indicates a video timeline consistent with usual video players.

The relatively high interest in the social web, sharing and the use of videos online has motivated researchers to investigate the use of video navigation history. Users unintentionally leave footprints during their video-browsing process, which can add value to the content. Yu et al. [START_REF] Yu | Video summarization based on user log enhanced link analysis[END_REF] and Syeda et al. [START_REF] Syeda-Mahmood | Learning video browsing behavior and its application in the generation of video previews[END_REF] investigated how users' video browsing footprints can be utilized in video summarization and to facilitate future viewers. They used video browsing footprints to rank different scenes within a video, which can later be used to extract clips when generating video summaries or previews. However, these systems [START_REF] Syeda-Mahmood | Learning video browsing behavior and its application in the generation of video previews[END_REF][START_REF] Yu | Video summarization based on user log enhanced link analysis[END_REF] have not given the users any control over their personal history during the viewing process (i.e. users cannot access their history). They recorded the users' actions, which were later used by the researchers to generate previews or evaluate the ranking of interesting parts within videos. In our interface we offer the users the ability to utilize their personal history for navigation and authoring as well as summarization.

Video navigation history can play an important role in user-based information retrieval from videos on the web. Shamma et al. [START_REF] Shamma | Watch what I watch: using community activity to understand content[END_REF] and Yew et al. [START_REF] Yew | Knowing funny: genre perception and categorization in social video sharing[END_REF] have proposed a shift from content-based techniques to user-based analysis because it provides a more promising basis for indexing media content in ways that satisfy user needs. Leftheriotis et al. [START_REF] Leftheriotis | Efficient video indexing on the web: A system that leverages user interactions with a video player[END_REF] proposed a video indexing tool on the web based on user interactions to rank different videos. They generated a thumbnail to represent each video based on the frame that has been mostly viewed by users. Gkonela et al. [START_REF] Gkonela | Videoskip: event detection in social web videos with an implicit user heuristic[END_REF] also indicated that this simple user heuristic while navigating videos can be used as effectively to detect video-events as when content-based techniques are applied. In our interface, we applied a flexible thumbnail visualization of each history segment: initially, each segment is visualized using a thumbnail that indicate the beginning of that segment which then changes while the user navigates this segment.

Navigating a video space or even long videos can be demanding and time consuming. There have been many interaction techniques proposed in the literature to address this problem in order to quickly navigate and search video content; here, we will only mention a few. Typical navigation tools used in most video systems are the VCR-like controls (play, pause, seek, fast forward, and rewind). DVD systems provided users with a higher level of video access using a random access to video segments based on scene indices and chapter boundaries via a table of contents index. Some researchers [START_REF] Yeung | Video visualization for compact presentation and fast browsing of pictorial content[END_REF][START_REF] Sawhney | Authoring and navigating video in space and time[END_REF][START_REF] Christel | Finding the right shots: assessing usability and performance of a digital video library interface[END_REF][START_REF] Drucker | Smartskip: consumer level browsing and skipping of digital video content[END_REF] allowed video navigation using their abstraction thumbnails or keyframes (e.g. filmstrip), where clicking on a thumbnail directly positions the video at a particular point in time corresponding to that thumbnail. Others [START_REF] Cheng | Smartplayer: user-centric video fast-forwarding[END_REF][START_REF] Foote | An intelligent media browser using automatic multimodal analysis[END_REF] proposed new playback mechanisms to help users rapidly skim through uninteresting content while slowing down to watch interesting parts of the video. Since the video content changes as time passes, the separation between the video content and the controls used to manipulate the video introduces a target acquisition problem. Thus, some researchers have focused in introducing new techniques to manipulate the video timeline rather than using the traditional VCR controls. They allow users to navigate the video by directly manipulating the video content along its natural movement path rather than using the timeline slider [START_REF] Kimber | Trailblazing: Video playback control by direct object manipulation[END_REF][START_REF] Karrer | Dragon: a direct manipulation interface for frame-accurate in-scene video navigation[END_REF][START_REF] Dragicevic | Video browsing by direct manipulation[END_REF][START_REF] Goldman | Video object annotation, navigation, and composition[END_REF]. Pongnumkul et al. [START_REF] Pongnumkul | Creating map-based storyboards for browsing tour videos[END_REF] developed a new navigation tool that uses a map-based storyboard where different locations of video segments are directly visualized on the map.

Video navigation history provides a potential interaction technique that can be used to facilitate fast navigation and event search. According to Shamma et al. [START_REF] Shamma | Watch what I watch: using community activity to understand content[END_REF], the more affective a scene is, the more the corresponding interval of the video is viewed or consumed. Thus, the cumulative seamless user interaction history could be leveraged for the benefit of future viewers (i.e. social navigation). For example in You-Tube, when enough user data is available, user behavior will exhibit similar patterns which can then be used by new viewers to quickly navigate to the interesting part of that video. Yu et al. [START_REF] Yu | Video summarization based on user log enhanced link analysis[END_REF] used low-level feature extraction along with user's footprints (i.e. view count) to rank each scene and offer users other scenes that have some correlation with what they are watching. This provides users with a quick navigation method to similar scenes. Mertens et al. [START_REF] Mertens | Social navigation in web lectures[END_REF] visualized users' footprints on the video timeline, which allowed users to quickly navigate to the corresponding scenes in the video. In our interface, we used VCR like controls along with thumbnails of the previously viewed video segments that allow simple navigation to these intervals. Our study revealed that using this method speeds up searching for previously seen events within the video.

Video Navigation Interface

Given the volume of available video data, methods to effectively navigate this space are needed to provide users with more enjoyable video viewing experiences. The principle goal of our interface is to provide efficient access to previously viewed video: in particular, intervals within video. We accomplish this by recording a continuous video history for the user as they consume video content. This paper considers only the history of a single video as a starting point, and demonstrates that further research is warranted for multiple-video history based on our success. Internally, the user's video watching history is represented by a very simple data structure organized by linear user time. Whenever a video begins playback the video ID and current user time are recorded; these are noted again when the video stops playing, to produce interval start and end timestamps. An accumulated view count is maintained for every instant of time in the video: the structure stores intervals of view count derived from the intersection of all viewed intervals.

We designed our interface in a way that allows users to play, view and navigate videos similar to any video player as we envision our history management to be used to augment it. Since our interface records the user's navigation history, we propose new components that offer the users the flexibility of using this history for fast navigation, summarization (or authoring) and sharing. Thus, our interface is based on five separate components: a Player which provides the user with a familiar video setting, a Filmstrip which provides a navigation tool for the entire video content, a History Timeline which visualizes the personal viewing history, a Video Mash-up and a Preview Window which help users creating and previewing their own edit list for video summaries or previews. The main interface components are: the Player and the History Timeline. Player. A familiar video player (similar to YouTube, QuickTime, etc.), shown in Figure 2, contains: play/pause, applied via a button (bottom left) or by clicking directly on the video; seeking via playhead (white circle on timeline) or mouse click on the timeline (red/grey bar); a frame preview triggered by the mouse over the timeline (including when seeking interactively i.e. with mouse button held down over time slider); and a current playhead time label (white text, bottom right). This component is used for direct control of the selected video. To watch a specific video from disk, users click on the "Open" button and choose their video file. Filmstrip. The Filmstrip component, shown in Figure 3, is the state-of-art video navigation tool. It provides a visualization aid to different parts of a video for faster navigation and supports access to the entire video content. The Filmstrip simply consists of a fixed number of Video Segments (n) from the playing video. The entire video is divided into n equal length intervals, where each interval is represented by a small seek-able Video Segment described below. These intervals are created systematically based on the length of the video and the number of segments to be visualized.

User Viewing History Timeline (History Timeline)

. This is the central component for visualizing the personal viewing history of the user. We use a filmstrip metaphor for visualization: the History Timeline consists of thumbnails (similar to interactive storyboards) as shown in Figure 1. These thumbnails represent Video Segments that the user watched. We represent this as a Video Segment component as discussed in the next section. Every time the user seeks to a new temporal location, a new Video Segment is added to the end of the user's history list and represents the interval a user watches in the main video player. The History Timeline is a scrollable box, to provide navigation of the entire viewing history and allows the user to find a specific interval.

The video history is similar conceptually to webpage bookmarks that are used to refer back to visited pages, however, it is more complicated as each Video Segment in the history view is a video interval and also includes a representation of the time the user watched it. Thus representing both of these quantities requires additional mechanisms for visualization and interaction. Moreover, there may be confusion with the currently viewed timeline and with the history views since there exist two timelines: when/what the user watched and the video's timeline. We address this by visualizing the history timeline vertically, while the video timeline remains horizontal, consistent with user's mental model of video. The history is unique in that it records in piecewise linear user-time, not video time (we only display the history of intervals watched and do not represent the complete video from where it came from in the History view.). Each Video Segment is a small interactive video widget described next.

Video Segment. Each interval a user watches is represented as a small video widget that contains the viewed interval only, visualized by the starting frame of that interval. The location of the interval within the entire video is visualized as a red portion underneath the widget to help users spatially contextualize the temporal location of intervals within the complete video where it came from. The video widget, shown in Figure 1, is seek-able and playable to allow users to easily search within the intervals and minimize the time needed to search for a previously viewed scene. On mouse over, a play/pause overlay is displayed over the widget. Clicking on the overlay plays the corresponding video interval within this small widget only. (Note, while technically, this is a rewatching of video, we do not add this activity in the History View.) Moving the cursor over the bottom third portion of the widget pops up a zoom-in visualization of the interval timeline, which can be used to seek within the video interval using mouse motion as a cue. The seeking point is visualized by a yellow line and the thumbnail updates to reflect the current seek position. To play a Video Segment in the main video player, users can drag the entire widget (or the seek location in the widget) to the main video player: dragging the entire widget plays the corresponding interval from the beginning, while dragging the seek bar location plays from that specific time. Video Mash-up. The video mash-up is used for short video composition such as summaries, previews, or trailers (analogous to video editing software e.g. iMovie, Movie Maker, etc). We included this component in our prototype to evaluate one of the use cases we idenitified that takes advantage of potential strength of having personal viewing history. The video mash-up, shown in Figure 4, represents a video edit list that shows the videos, and intervals within each video, that a user may combine into a summary. In summary creation mode, when the user subsequently plays a video (either through opening a new video, a segment from history or seeking within the current video) a new record is added to the edit list. If the video already exists in the edit list, a new interval is added (unless there is an existing identical interval). Otherwise if the video does not exist, a new video record with the interval is added to the edit list. Thus, adding segments or intervals to the edit list is simply done by watching these intervals, in comparison to other video editing software where users need to add a video clip, watch it, and then trim it. Using this component makes video editing simpler for novice users as we discovered upon evaluation.

The video mash-up component allows the user to preview a specific interval by using the play button for that interval. Users can also modify their edit list by directly updating interval start or end times, delete an interval, delete an entire video record, or reorder video records. Previewing the entire summary is provided by clicking on the "Preview" button. Summary Preview. After creating a video mash-up, the user can preview it using the summary preview mode, where a new video player window pops up, and the rest of the interface is disabled and darkened. The summary preview takes the user's edit list as input and plays the intervals in order using this content. It allows users to replay, modify (back to the main interface to modify the edit list), or export it if they wish to save it -the edit list is exported as an XML file that can be shared or modified later.

Personal Navigation Footprints. The recorded video history offers additional benefits, such as within-video history and crowd-sourced user histories (neither of these were included in our study). The personal history or footprints offers users a visualization of the view count of every point of time in the video: the blue bar in Figure 5 becomes brighter for the most-viewed intervals, and each one can be selected to play. It provides the user with information on the most-viewed intervals of each video (a temporally tracked frequency). As mentioned previously, a view count is maintained for all points of time for each viewed video. As the user views a video the view count will dynamically change, thus the count is continuously updated and the information propagated backwards through the history. The view counts are then summed and normalized within each video. Crowd-Sourced Navigation Footprints. The personal history from multiple users are combined to form the most popular intervals for a video (i.e. social navigation similar to these are shown in the red bar in Figure 5. This provides users who are watching a video for the first time with a mechanism to watch what others have found to be most interesting. This is an efficient navigation technique, predicated on trusting the crowd to be "correct" on interesting video content.

Evaluation

An extensive set of pilot studies were performed (12 participants total) to investigate a user's preferred scenario for history, and to triangulate the use cases in which a history is beneficial for video viewing. Throughout this triangulation process it became more apparent to the authors how complex and intricate the video-viewing task can be. For tasks such as seeking to a specific time or finding a particular event from a previously watched video, using a history was found to be as good as using a filmstrip methodology. Under more modern viewing patterns (e.g. nonlinear viewing behavior) where users view only parts of the video (e.g. trailers, summaries, playlists or direct temporal links) using a history to find events and seek to them was found to be more efficient.

Using this result from the pilot studies, a full comparative user study was performed to evaluate the design and performance of our interface and to demonstrate the utility of personal video navigation histories. We developed an evaluation protocol which satisfies the use cases previously defined (without biasing our design or the control) and provides the user with sufficient viewing history while keeping the ex-periment relatively short. For fair comparison we ensured our interface mimics currently adopted approaches with logical extensions.

Using our protocol, we investigated whether visualizing and using a video navigation history would make searching for previously seen events more efficient. We conducted a comparative between-subjects user study, comparing the performance of users employing a personal navigation history against those with the state-of-the-art navigation method (Filmstrip) to find events within a previously seen video (i.e. finding answers to questions similar to [START_REF] Yu | Video summarization based on user log enhanced link analysis[END_REF][START_REF] Gkonela | Videoskip: event detection in social web videos with an implicit user heuristic[END_REF]).

Both methods have similar layouts and functionality, differing on the process of segment creation described in section 4. In Filmstrip the intervals are created systematically, while in the History Timeline segments are constructed based on a personal navigation history; each participant tried both methods, on different videos. In Filmstrip tasks the participants were presented with the main Video Player and a horizontal Filmstrip components only. They only used these components and their features to find the answer to each question. In History Timeline tasks the participants were presented with the main Video Player and a vertical History Timeline components.

Our experiment was divided into two phases: phase 1 was conducted to compare the two methods (Filmstrip and History), and phase 2 was performed to qualitatively analyze the entire proposed interface, described in section 4. In phase 1, participants experimented 3 components (Video Player, Filmstrip, and History Timeline) of the interface described in section 4, while in the second phase they were exposed to all components and features.

Apparatus

The experiment application was developed in Flash CS4 and ActionScript 3.0. The experiment ran on an Intel dual-processor dual-core 3 GHz Mac Pro desktop with 8GB RAM and equipped with a 24" Dell LCD monitor with a resolution of 1920 x 1200 pixels at a refresh rate 0f 60Hz. A Microsoft optical wheel mouse was used as the input pointing device with default settings and the Adobe Air environment was set to 1920 x 900 pixels while running the Flash program.

Participants

Twelve paid university students (different from those in the pilot studies), 6 female and 6 male, participated in the experiment. Participants ranged in age from 20 to 30, all were experienced computer users and have either normal or corrected-to-normal vision. Participants reported watching videos either on a daily basis (10 participants) or 3-5 times a week (2 participants). Each participant worked on the task individually. This project targets heavy video users, and according to Purcel1 , video is a growing trend especially amongst those aged 18 to 29. Thus, students are a primary target audience as they are representative of the current/near-future heavy users of video interfaces. We used students across the University to capture this demographic.

Design

To evaluate the efficiency of using navigation history as an aid for efficient search within a previously seen video, we gave participants a pre-defined history, which they had to watch and subsequently answer questions based on the content. We followed this procedure rather than allowing participants to create their own history: this decision was made based on the pilot studies where participants found creating a history based on an unknown list of questions was confusing. Some participants said, "What interests me might not be what you are looking for". Thus, they tried to create many history segments at each point they thought there was potential for a question. The result was a long list of short segments which required significant scrolling when searching. In short, the uncertainty of what should be included on the list led to a large number of segments and created some confusion that affected the performance while using the method.

In order to tackle this problem, the participants could be allowed to create their own history based on their interest after which they can be asked questions that exist within these segments. However, the variation between participants interest would make the comparison difficult. Thus, instead of asking participants to create their own history we decided to give them all the same history from which to answer the list of questions (analogous to watching a playlist created by a friend or a video summary). All participants watched the same clips from the video and were asked questions from these clips only. Thus, we ensured they had experienced the same clips and eliminated the personalization factor within the history. Our method was compared with the state-of-the-art method (Filmstrip). The History Timeline contained the segments of the predefined history only while Filmstrip contained seven evenly divided intervals over the entire video.

In this experiment, we used five different short videos (V1-5). V1 was used to explain the interface's components and features and demonstrate how to use them. The other four videos were used for the actual experiment where each participant used a single method for each video. Each participant experienced each method in a different video to eliminate the learning effect. The number of questions per video were: V1: 20; V2: 38; V3: 25; V4: 38; and V5: 32.

The participants were divided into two groups, A and B. Both groups experienced the videos in the same sequence but with different method sequences. They both started the familiarity phase where they tried a hybrid of the two methods to answer example questions and to become familiar with both methods. Group A was given Filmstrip for V2 and V4 and History Timeline for V3 and V5, while group B used the opposite. Thus, the results were compared between the two groups for each video.

To quantitatively compare the results of the two methods, we measured five variables for each video: (1) The percentage of questions answered for each video within a specified time range. The total time given is 15 seconds multiplied by the total number of questions (chosen based on the pilot studies); [START_REF] Card | Information scent as a driver of web behavior graphs: results of a protocol analysis method for web usability[END_REF] The time needed to answer each question -this is the time measured between two subsequent correct submission clicks; (3) The number of wrong submissions (errors) for each question, which is measured by counting the number of submission clicks that did not result in a correct answer; (4) The number of seeks within a video for each question; and [START_REF] Christel | Finding the right shots: assessing usability and performance of a digital video library interface[END_REF] The number of previews performed in a video for each question, which is measured by counting the number of seeks and playbacks within the small Video Segments. These counts were tracked to analyze the user's behaviour and to investigate the difference between the two methods.

The participants were also asked to fill out questionnaires and give their comments on the entire interface, and suggestions for improvement. This was conducted to qualitatively compare the two methods and to provide an indication of the importance of correcting each particular aspect of the proposed interface. Participants rated different interface features and tools using a 7-point Likert scale. The experiment lasted approximately two hours per participant.

Procedure

Participants were given a description of the procedures to be employed in the study, informed of the goals and purposes of the study, and informed consent was requested to participate in the study. Two methods were evaluated in the study: Filmstrip and History Timeline. The researcher started by showing the interface (shown in Figure 6), describing its components, explaining the functionality of the tools within the interface and how to answer a question in order to complete each task. Participants were then asked to try the same interface with the first video and task. They were given the freedom to play with the interface and ask any questions. This familiarity stage was intended to allow the participant to try all the interface components and become familiar with the available functionality. The participants started watching the video provided without knowing the questions they will be asked.

For each video, the task started by playing the segments from the pre-defined history in the main video player. Participants were asked to watch the playback and pay attention to the video content in order to answer questions later. Once all segments from the history were viewed, the video paused and a list of questions (compiled by researchers) was displayed to the left of the main video player, as shown in Figure 5.

Participants were asked to read these questions before clicking on the "Start" button, when the timer starts and they could begin providing answers. After clicking on the "Start" button, the method's corresponding components were only shown and participants were advised to answer as many questions as they can within the given time by watching the clip which contains the answer.

The questions were randomly ordered (i.e. they were not temporally ordered according to their occurrence in the video). Each participant had the freedom to choose the order they would like to follow to answer these questions (e.g. temporally, linearly, difficulty, memorability, etc.). The participants started answering these questions by clicking on a "Start" button after reading the list of questions. In the familiarity phase, the participant could use either the Filmstrip or History Timeline to navigate the video in an attempt to find an answer. To answer a question the participant needed to re-watch the clip that contains the answer in the main video player. They navigated Video Segments in the provided component (Filmstrip or History Timeline) to find a clip or a video frame that contains the answer. Once they found the frame, they dragged the Video Segment of a specific video frame using the seek thumb of the Video Segment to the main video player to start playing that clip. After watching the interval that contains an answer for a single question they clicked on a submit button beside the corresponding question to proceed to the next question.

Each submitted clip was automatically evaluated: it was considered correct if it contains at least one frame from the ground truth answer. If the answer was correct, the question was faded out from the list and a message was displayed to participants (e.g. "Great. You have 2:14 to answer the rest. Hurry up.") to encourage them and maintain time pressure. However, if the answer was wrong, a message is shown which asks the participant to try again "Sorry. Try again". Participants repeated the same actions till they answered all questions or the time elapsed. A new list of questions was displayed and the participants continued applying the same procedure to answer these questions. The questions for each video were divided into two lists to avoid overloading participants with so many questions. A short break was provided between question sets.

After completing the second list of questions, the familiarity stage ended and the participants were advanced to the phase 1 of the experiment where they watched a new video in similar settings to the watching phase of the familiarity stage. Upon the completion of the watching phase, a new list of questions was given based on the content of this video. In this stage the user was provided with only one method (Filmstrip or History Timeline) to be used in finding the answers. Once all questions were answered or the time elapsed, the participants proceeded to the next video where they repeated the previous stage but with a different video and using a different method than the one used for the previous video. Participants continued tasks until they completed all four videos.

During the experiment, participants were asked to fill out three questionnaires. These questionnaires were designed using the standard Questionnaire for User Interface Satisfaction (QUIS version 6.0 [START_REF] Chin | Development of an instrument measuring user satisfaction of the human-computer interface[END_REF]), modified to reflect the functionality and tools applied and the usability of our interface. Some sections were removed (e.g. Terminology and system information, and System capabilities), some questions were modified, and others were added. The first questionnaire was after V4 in which participants evaluated the method they used for that video. The second questionnaire was after V5 where participants rated the usability of the second method they used. After completing the second questionnaire, participants were advanced to the second phase of the experiment. They were given the full interface, described in section 4, where they have the freedom to create their own history and explore use cases which might be applicable to them. Every performed seek within the video or any watched interval in the main video player was recorded and visualized as a Video Segment in the History Timeline. This helped the participants to understand how history is created for later usage. Once they were satisfied playing with the interface, they were asked to fill out the last QUIS questionnaire, which evaluates the entire interface. Note. M = Mean. SD = Standard Deviation. ns = not significant. Average time per question is measured in seconds.

Results and Discussions

The study showed positive and promising results on the features of the interface. Most participants commented that they enjoyed their time using the interface and they can imagine seeing its features applied, especially in social networking websites (e.g. YouTube). They were impressed with the ease of learning and using the features within the interface. T-test analysis results, illustrated in Table 1, showed that our novel method (History Timeline) was significantly faster than the state-of-the-art (Filmstrip) which allowed participants to answer more questions within the same time. However, both methods demonestrated similar behaviour in terms of average number of seeks, previews and errors.

Each participant answered two identical questionnaires, one for each method, to compare the overall reaction, the time it takes to learn and general impressions. Each questionnaire contains thirty-seven 7-point Likert scale questions. The data collected for the two methods were analyzed and compared in terms of these 37 questions. The results showed a significant difference taking the overall average rating of each method (Filmstrip (M = 5.45, SD = 1.35), History Timeline (M = 5.55, SD = 1.06), t(886) = 2.08, p < 0.04). The History Timeline showed no significant difference from the Filmstrip in all questions except for the question "Learning to use the method features" where (1: Difficult, 7:Easy) History Timeline (M = 5.4, SD = 1.07), and Filmstrip (M = 4.7, SD = 1.16), t(22) = 2.27, p < 0.04. This also coincided with participants preference where 9 participants out of 12 stated that the History Timeline was faster and easier in finding the answers for the questions. Participants reported that History Timeline was faster because it is based on a personal mental context map created for the video. It was easier for them to refer back to the corresponding segments when needed which is not the case for Filmstrip. Since Filmstrip segments was created systematically, participants needed at least to navigate one segment. If the answer was within that segment they submitted it, otherwise they needed to navigate the preceding or subsequent segment. This was also demonstrated by the participants' quantitative results where they were able to answer more questions using History Timeline. All questions for both methods were rated above 5 out of 7 except for four questions: "Satisfaction with the method", "Learning to use the method features", "Number of steps per task", and "Using the method is effortless".

After acquiring some familiarity with the overall interface in phase 2, participants were asked to complete a third questionnaire to rate the entire interface, described in section 4. Responses were compiled for each of the 12 participants in the study, along with any written comments that the participants had. The overall mean rating of all sections of the QUIS was 5.73, on a 7-point scale, and all questions were rated above 5. For the "Overall Reaction" section, "Satisfaction" overall rating was the only factor that was rated significantly lower than the mean response (M = 5.2, SD = 0.57), indicating that this area may need additional consideration. The "Ease of use" overall rating (M = 6, SD = 0.53) was significantly more than the mean response, indicating that users can easily learn and use the interface. From these "Overall Reactions" to the interface, we can conclude that users found our interface easy to use, helpful, useful, and flexible. In the "General Impressions" section, the overall ratings for "Screens are aesthetically pleasing", "Screen designs and layout are attractive", "Interface is impressive", "Interface can do a great deal", and "Interface is fun to use", were rated significantly better than the mean response. This indicates that users found our interface aesthetically pleasing and fun to use. The remaining items of this section were not significantly different from the mean response.

In addition to the QUIS item findings, participants were also asked to list three most negative and positive aspects of the interface. Some participants reported that "I found it weird to have a vertical list of video pieces", "Not being able to delete segments from history", and "Not being able to favorite some segments from history". The comment about the vertical scrolling coincided with their responses to the location of the component where the mean rating for the layout of History Timeline was significantly lower than that of the Filmstrip. We designed the component in this layout to eliminate the confusion between the History Timeline and the video timeline; this may need additional investigation. Participants found the interface helpful and impressive in being able to dynamically create points or bookmarks, which would allow them to skip to a favorite clip. Most participants stated that the interface is fun to use once you get the hang of it.

In order to explore whether users foresee some potentials for the interface we asked them "Where and how do they think video navigation history can be useful". Participants provided us with valuable responses that gave us some insights of how this interface can be further modified and tested. They foresee that it would be useful in educational environment as well for home usage. There were some overwhelming comments made by the participants about the interface. One participant commented "I definitely see how this would be really helpful for long videos because I will not have to waste my time watching the whole video again to get to the important stuff. I could directly use my previous history to navigate to these intervals". Others said, "I would love to see this implemented within social websites. I could see how I would use it and definitely I will have more fun"; "I need to have this. Could we have it in You-Tube?"; and finally "I really do like this interface and I would love to have it to create wonderful clips from my home videos".

Based on the participants' valuable comments and suggestions, we believe using personal navigation history is helpful in navigating a video space. This could work for different applications such as highlights or summary of videos, a movie using home videos, sharing interesting clips, quickly navigating and skimming previously watched videos, and finally watching new videos' interesting parts using crowdsourced viewing histories. Receiving these positive feedbacks from the participants and how they welcomed the idea of using their personal navigation history motivate us to investigate how our interface would work if integrated with social websites (e.g. YouTube, Vimeo) and explore how this could change the way users consume and navigate video.

Conclusion and Future Work

The work we have presented describes a new way to navigate and view video media using a personal video history. We introduced a novel interface for video navigation through the creation and subsequent use of a user's personal viewing history. The interface is based on observations of new use cases involving re-watching of withinvideo intervals and the increasingly temporal nature of video navigation. We performed a study that found positive results and highly positive affect and comments from participants. A comparative study based on a use case of fast navigation found significant results in favor of our method. To our knowledge, this is the first paper on using history navigation through video browsing, and as such, not enough work has been done in this area to evaluate the effectiveness on a larger scale. So we intend to investigate scalability, filtering mechanisms, interactions required when using a multiple-video history to allow users with large history to accurately navigate through them. Once these mechanisms have been tested, we aim to deploy a field study to check the validity and the scalability of history in action.

Figure 1 .

 1 Figure 1. Our video navigation interface: the majority of space is devoted to the currently playing video (top left) with a seek-bar preview; below is a horizontal array of Video Segments arranged by video-time (the Filmstrip), and a vertical array of Video Segments to the right (the History Timeline) ordered top-down by user-time i.e. the order the intervals were viewed. These components described in more details in section 4.

Figure 2 .

 2 Figure 2. The video player component contains play/pause button, video seek-bar, and a popup thumbnail shown when the pointer is over the time bar.

Figure 3 .

 3 Figure 3. The Filmstrip component visualizes the entire video into n equal length segments.

Figure 4 .

 4 Figure 4. The Video Mash-up component illustrates a user edit list which consists of a user defined Video Segments with the options of delete , reorder , play (on click), navigate (on cursor move shown as a yellow line), and modify segment's start and end times.

Figure 5 .

 5 Figure 5. A Video Timeline is combined with navigation footprints visualization, where the more an interval within a video is watched the brighter that region becomes. Blue: a single user history (Personal Navigation Footprints), Red: a combined multiple users histories (Crowd-Sourced Navigation Footprints).

Figure 6 .

 6 Figure 6. The Experiment Interface 2 illustrates the familiarity phase.

Table 1 .

 1 Methods Descriptives Using t-test for Equality of Means

		Filmstrip	History Timeline
		M	SD	M	SD	t-test
	Mean % of answered questions	65.53	14.69	83.93	14.87	4.53 **
	Average time per question	24.11	5.85	18.52	3.85	4.13 **
	Average no. of seeks	1.59	0.45	1.50	0.48	ns
	Average no. of previews	14.37	5.14	12.74	4.91	ns
	Average no. of errors	0.15	0.09	0.14	0.11	ns
	** p < .01.

http://www.pewinternet.org/ /media//Files/Reports/2010/PIP-The-State-of-Online-Video.

The video images are for illustration purpose only as different stimulus was used in the experiment (i.e. Toy Story

3, Alma, Geri's Game, and For the Birds.).