More Web Proxy on the site http://driver.im/

short-paper

Modeling video hyperlinks with hypergraph for web video reranking

Authors:

Hung-Khoon Tan,

Xiao WuAuthors Info & Claims

MM '08: Proceedings of the 16th ACM international conference on Multimedia

Pages 659 - 662

https://doi.org/10.1145/1459359.1459453

Published: 26 October 2008 Publication History

Abstract

In this paper, we investigate a novel approach of exploiting visual-duplicates for web video reranking using hypergraph. Current graph-based reranking approaches consider mainly the pair-wise linking of keyframes and ignore reliability issues that are inherent in such representation. We exploit higher order relation to overcome the issues of missing links in visual-duplicate keyframes and in addition identify the latent relationships among keyframes. Based on hypergraph, we consider two groups of video threads: visual near-duplicate threads and story threads, to hyperlink web videos and describe the higher order information existing in video content. To facilitate reranking using random walk algorithm, the hypergraph is converted to a star-like graph using star expansion algorithm. Experiments on a dataset of 12,790 web videos show that hypergraph reranking can improve web video retrieval up to 45% over the initial ranked result by the video sharing websites and 8.3% over the pair-wise based graph reranking in mean average precision (MAP).

References

[1]

S. Agarwal, K. Branson, and S. Belongie. Higher order learning with graphs. In ICML, 2006.

Digital Library

[2]

S. Agarwal, J. Lim, L. Zelnik-Manor, P. Perona, D. Kriegman, and S. Belongie. Beyond pairwise clustering. In CVPR, 2005.

Digital Library

[3]

T.-S. Chua and et. al. Trecvid 2004 search and feature extraction task by NUS PRIS. In TRECVID Workshop, 2004.

[4]

W. H. Hsu, L. S. Kennedy, and S.--F. Chang. Video search reranking via information bottleneck principle. In ACM Multimedia, 2006.

Digital Library

[5]

W. H. Hsu, L. S. Kennedy, and S.-F. Chang. Video search reranking through random walk over document-level context graph. In ACM Multimedia, 2007.

Digital Library

[6]

L. S. Kennedy and S. F. Chang. A reranking approach for context-based concept fusion in video indexing and retrieval. In CIVR, 2007.

Digital Library

[7]

J. Liu, W. Lai, X. S. Hua, Y. Huang, and S. Li. Video search re-ranking via multi-graph propogation. In ACM Multimedia, 2007.

Digital Library

[8]

L. Page, S. Brin, L. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford Digital Library Technologies Project, 1998.

[9]

A. F. Smeaton, P. Over, and W. Kraaij. Evaluation campaigns and TRECVID. In MIR, 2006.

Digital Library

[10]

Wikipedia. http://en.wikipedia.org/wiki/youtube.

[11]

X. Wu, A. G. Hauptmann, and C.-W. Ngo. Practical elimination of near-duplicates from web video search. In ACM Multimedia, 2007.

Digital Library

[12]

R. Yan and A. G. Hauptmann. Multimedia search with pseudo-relevance feedback. In CIVR, 2003.

Digital Library

[13]

Y. H. Yang and W. H. Hsu. Video search reranking via online ordinal reranking. In ICME, 2008.

[14]

W. L. Zhao, C.-W. Ngo, H.-K. Tan, and X. Wu. Near-duplicate keyframe identification with interest point matching and pattern learning. In IEEE Trans. on Multimedia, volume 9, pages 1037--1048, Aug 2006.

Digital Library

[15]

J. Y. Zien, M. D. F. Schlag, and P. K. Chan. Multi-level spectral hypergraph partitioning with arbitrary vertex sizes. In IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, volume 18, pages 1389--1399, 1999.

Digital Library

Cited By

Preti GDe Francisci Morales GBonchi F(2024)Hyper-distance oracles in hypergraphsThe VLDB Journal10.1007/s00778-024-00851-233:5(1333-1356)Online publication date: 19-Apr-2024
https://doi.org/10.1007/s00778-024-00851-2
Luo QYu DCai ZLin XWang GCheng X(2022)Toward maintenance of hypercores in large-scale dynamic hypergraphsThe VLDB Journal10.1007/s00778-022-00763-z32:3(647-664)Online publication date: 20-Sep-2022
https://doi.org/10.1007/s00778-022-00763-z
Bellaachia AAl-Dhelaan M(2021)Random Walks in HypergraphInternational Journal of Education and Information Technologies10.46300/9109.2021.15.215(13-20)Online publication date: 10-Mar-2021
https://doi.org/10.46300/9109.2021.15.2
Show More Cited By

Index Terms

Modeling video hyperlinks with hypergraph for web video reranking
1. Information systems
  1. Information retrieval
    1. Retrieval models and ranking

Recommendations

The Ramsey number for hypergraph cycles I

Let C_n denote the 3-uniform hypergraph loose cycle, that is the hypergraph with vertices v₁.....,v_n and edges v₁v₂v₃, v₃v₄v₅, v₅v₆v₇,.....,v_n-1v_nv₁. We prove that every red-blue colouring of the edges of the complete 3-uniform hypergraph with N vertices ...
Covering Non-uniform Hypergraphs

A subset of the vertices in a hypergraph is a cover if it intersects every edge. Let (H) denote the cardinality of a minimum cover in the hypergraph H, and let us denote by g(n) the maximum of (H) taken over all hypergraphs H with n vertices and with no ...
Anti-Ramsey number of matchings in a hypergraph
Abstract
Given an edge-coloring of a hypergraph G, G is said to be rainbow if any two edges of G receive different colors. The anti-Ramsey number A R ( G , H ) of a hypergraph H in a hypergraph G is defined to be the maximum ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MM '08: Proceedings of the 16th ACM international conference on Multimedia

October 2008

1206 pages

ISBN:9781605583037

DOI:10.1145/1459359

General Chairs:
Abdulmotaleb EL Saddik
University of Ottawa
,
Son Vuong
University of British Colombia
,
Program Chairs:
Carsten Griwodz
University of Oslo
,
Alberto Del Bimbo
University degli Studi di Firenze
,
K. Selcuk Candan
Arizona State University
,
Alejandro Jaimes
Telefonica R&D, Madrid, Spain

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 October 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Short-paper

Conference

MM08

Sponsor:

MM08: ACM Multimedia Conference 2008

October 26 - 31, 2008

British Columbia, Vancouver, Canada

Acceptance Rates

Overall Acceptance Rate 2,145 of 8,556 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
253
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Preti GDe Francisci Morales GBonchi F(2024)Hyper-distance oracles in hypergraphsThe VLDB Journal10.1007/s00778-024-00851-233:5(1333-1356)Online publication date: 19-Apr-2024
https://doi.org/10.1007/s00778-024-00851-2
Luo QYu DCai ZLin XWang GCheng X(2022)Toward maintenance of hypercores in large-scale dynamic hypergraphsThe VLDB Journal10.1007/s00778-022-00763-z32:3(647-664)Online publication date: 20-Sep-2022
https://doi.org/10.1007/s00778-022-00763-z
Bellaachia AAl-Dhelaan M(2021)Random Walks in HypergraphInternational Journal of Education and Information Technologies10.46300/9109.2021.15.215(13-20)Online publication date: 10-Mar-2021
https://doi.org/10.46300/9109.2021.15.2
Jiang WQi JYu JHuang JZhang R(2019)HyperX: A Scalable Hypergraph FrameworkIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2018.284825731:5(909-922)Online publication date: 1-May-2019
https://doi.org/10.1109/TKDE.2018.2848257
Kim SHa JKim HZhang B(2019)Bayesian evolutionary hypernetworks for interpretable learning from high-dimensional dataApplied Soft Computing10.1016/j.asoc.2019.05.00481:COnline publication date: 1-Aug-2019
https://dl.acm.org/doi/10.1016/j.asoc.2019.05.004
Li JHe JZhu YGuo YFarooq F(2018)E-tail Product Return Prediction via Hypergraph-based Local Graph CutProceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining10.1145/3219819.3219829(519-527)Online publication date: 19-Jul-2018
https://dl.acm.org/doi/10.1145/3219819.3219829
Zhang BQu YPeng JFan J(2017)An automatic image-text alignment method for large-scale web image retrievalMultimedia Tools and Applications10.1007/s11042-016-4059-x76:20(21401-21421)Online publication date: 1-Oct-2017
https://dl.acm.org/doi/10.1007/s11042-016-4059-x
Li XYe YNg M(2016)MultiVCRank With Applications to Image RetrievalIEEE Transactions on Image Processing10.1109/TIP.2016.252229825:3(1396-1409)Online publication date: 1-Mar-2016
https://dl.acm.org/doi/10.1109/TIP.2016.2522298
Ordelman REskevich MAly RHuet BJones GGangemi ALeonardi SPanconesi A(2015)Defining and Evaluating Video Hyperlinking for Navigating Multimedia ArchivesProceedings of the 24th International Conference on World Wide Web10.1145/2740908.2742915(727-732)Online publication date: 18-May-2015
https://dl.acm.org/doi/10.1145/2740908.2742915
Huang JZhang RYu J(2015)Scalable Hypergraph Learning and ProcessingProceedings of the 2015 IEEE International Conference on Data Mining (ICDM)10.1109/ICDM.2015.33(775-780)Online publication date: 14-Nov-2015
https://dl.acm.org/doi/10.1109/ICDM.2015.33
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents