Online HodgeRank on Random Graphs for Crowdsourceable QoE Evaluation

• Published in: IEEE transactions on multimedia 2014-02, Vol.16 (2), p.373-386
• Main Authors: Xu, Qianqian, Xiong, Jiechao, Huang, Qingming, Yao, Yuan
• Format: Article
• Language: English
• Subjects: Algorithm design and analysis; Algorithmics. Computability. Computer arithmetics; Applied sciences; Approximation algorithms; Approximation methods; Asymptotic properties; Computer science; control theory; systems; Computer systems and distributed systems. User interface; Convergence; Crowdsourcing; Data processing. List processing. Character string processing; Exact sciences and technology; Graphs; Hodge theory; Image edge detection; Information retrieval. Graph; Internet; Memory organisation. Data processing; Multimedia; Multimedia communication; On-line systems; Online; online algorithms; paired comparison; persistent homology; quality of experience; random graphs; Ranking; Ratings; Robbins-Monro procedure; Sampling; Software; stochastic approximation; Theoretical computing
• ISSN: 1520-9210; 1941-0077
• DOI: 10.1109/TMM.2013.2292568

HodgeRank on random graphs is proposed recently as an effective framework for multimedia quality assessment problem based on paired comparison methods. With a random design on graphs, it is particularly suitable for large scale crowdsourcing experiments on the Internet. However, there still lacks a systematic study about online schemes to deal with the rising streaming and massive data in crowdsourceable scenarios. To fill in this gap, we propose in this paper an online ranking/rating scheme based on stochastic approximation of HodgeRank on random graphs for Quality of Experience (QoE) evaluation, where assessors and rating pairs enter the system in a sequential or streaming way. The scheme is shown in both theory and experiments to be efficient in obtaining global ranking by exhibiting the same asymptotic performance as batch HodgeRank under a general edge-independent sampling process. Moreover, the proposed framework enables us to monitor topological changement and triangular inconsistency in real time. Among a wide spectrum of choices, two particular types of random graphs are studied in detail, i.e., Erdös-Rényi random graph and preferential attachment random graph. The former is the simplest I.I.D. (independent and identically distributed) sampling and the latter may achieve more efficient performance in ranking the top- k items due to its Rich-get-Richer property. We demonstrate the effectiveness of the proposed framework on LIVE and IVC databases.