File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Evaluating multi-way joins over discounted hitting time

TitleEvaluating multi-way joins over discounted hitting time
Authors
Issue Date2014
PublisherIEEE Computer Society. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/conhome.jsp?punumber=1000178
Citation
The 30th IEEE International Conference on Data Engineering (ICDE 2014), Chicago, IL., 31 March-4 April 2014. In International Conference on Data Engineering Proceedings, 2014, p. 724-735 How to Cite?
AbstractThe discounted hitting time (DHT), which is a random-walk similarity measure for graph node pairs, is useful in various applications, including link prediction, collaborative recommendation, and reputation ranking. We examine a novel query, called the multi-way join (or n-way join), on DHT scores. Given a graph and n sets of nodes, the n-way join retrieves a set of n-tuples with the k highest scores, according to some aggregation function of DHT values. This query enables analysis and prediction of complex relationship among n sets of nodes. Since an n-way join is expensive to compute, we develop the Partial Join algorithm (or PJ). This solution decomposes an n-way join into a number of top-m 2-way joins, and combines their results to construct the answer of the n-way join. Since PJ may necessitate the computation of top-(m+ 1) 2-way joins, we study an incremental solution, which allows the top-(m+ 1) 2-way join to be derived quickly from the top-m 2-way join results earlier computed. We further examine fast processing and pruning algorithms for 2-way joins. An extensive evaluation on three real datasets shows that PJ accurately evaluates n-way joins, and is four orders of magnitude faster than basic solutions. © 2014 IEEE.
Persistent Identifierhttp://hdl.handle.net/10722/203650
ISBN
ISSN

 

DC FieldValueLanguage
dc.contributor.authorZhang, Wen_US
dc.contributor.authorCheng, Ren_US
dc.contributor.authorKao, Ben_US
dc.date.accessioned2014-09-19T15:49:10Z-
dc.date.available2014-09-19T15:49:10Z-
dc.date.issued2014en_US
dc.identifier.citationThe 30th IEEE International Conference on Data Engineering (ICDE 2014), Chicago, IL., 31 March-4 April 2014. In International Conference on Data Engineering Proceedings, 2014, p. 724-735en_US
dc.identifier.isbn978-1-4799-2555-1-
dc.identifier.issn1084-4627-
dc.identifier.urihttp://hdl.handle.net/10722/203650-
dc.description.abstractThe discounted hitting time (DHT), which is a random-walk similarity measure for graph node pairs, is useful in various applications, including link prediction, collaborative recommendation, and reputation ranking. We examine a novel query, called the multi-way join (or n-way join), on DHT scores. Given a graph and n sets of nodes, the n-way join retrieves a set of n-tuples with the k highest scores, according to some aggregation function of DHT values. This query enables analysis and prediction of complex relationship among n sets of nodes. Since an n-way join is expensive to compute, we develop the Partial Join algorithm (or PJ). This solution decomposes an n-way join into a number of top-m 2-way joins, and combines their results to construct the answer of the n-way join. Since PJ may necessitate the computation of top-(m+ 1) 2-way joins, we study an incremental solution, which allows the top-(m+ 1) 2-way join to be derived quickly from the top-m 2-way join results earlier computed. We further examine fast processing and pruning algorithms for 2-way joins. An extensive evaluation on three real datasets shows that PJ accurately evaluates n-way joins, and is four orders of magnitude faster than basic solutions. © 2014 IEEE.-
dc.languageengen_US
dc.publisherIEEE Computer Society. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/conhome.jsp?punumber=1000178-
dc.relation.ispartofInternational Conference on Data Engineering Proceedingsen_US
dc.rightsInternational Conference on Data Engineering Proceedings. Copyright © IEEE Computer Society.-
dc.rights©2014 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.-
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.titleEvaluating multi-way joins over discounted hitting timeen_US
dc.typeConference_Paperen_US
dc.identifier.emailCheng, R: ckcheng@cs.hku.hken_US
dc.identifier.emailKao, B: kao@cs.hku.hken_US
dc.identifier.authorityCheng, R=rp00074en_US
dc.identifier.authorityKao, B=rp00123en_US
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.1109/ICDE.2014.6816695-
dc.identifier.scopuseid_2-s2.0-84901755684-
dc.identifier.hkuros239391en_US
dc.identifier.spage724-
dc.identifier.epage735-
dc.publisher.placeUnited States-
dc.customcontrol.immutablesml 141021-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats