Contextual In-Stream Video Advertising the predefined locations in a video, this advertis- ing paradigm aims to embed more contextually relevant ads at less intrusive positions within the video stream nonlinearly. The remaining of this chapter is organized as follows. Section II reviews related research on video advertising. Section III describes the approach of the proposed in-stream advertising. Section IV presents two exemplary systems in this paradigm, e.g., VideoSense (Mei et al., 2009) (Mei et al., 2007b) and AdOn (Mei et al., 2010). We conclude this chapter in Section V. RELATED WORK Advertising in Text Domain One of the fundamental problems in online ad- vertising is ad relevance which in studies detracts an intermediate taxonomy so that the selected ads are more targeted to the query. Research on ad relevance has proceeded along three directions from the perspective of what the ads are matched against: (1) keyword-targeted ad- vertising (also called "paid search advertising" or "sponsored search") in which the ads are matched against the originating query (Joshi and Motwani, 2006) (Mehta et al., 2007), (2) content-targeted advertising (also called "contextual advertising") in which the ads are associated with the Web page content rather than the keywords (Broder et al., 2007) (Lacerda et al., 2006) (Murdock et al., 2007) (Ribeiro-Neto et al., 2005), and (3) user-targeted advertising (also called "audience intelligence") in which the ads are driven based on user profile and demography (Hu et al., 2007), or behavior (Dai et al., 2006) (Richardson et al., 2007). Although the paid search market develops quicker than contextual advertising, and most