File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1109/ICDE.2014.6816695
- Scopus: eid_2-s2.0-84901755684
- Find via
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Evaluating multi-way joins over discounted hitting time
Title | Evaluating multi-way joins over discounted hitting time |
---|---|
Authors | |
Issue Date | 2014 |
Publisher | IEEE 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? |
Abstract | The 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 Identifier | http://hdl.handle.net/10722/203650 |
ISBN | |
ISSN | 2023 SCImago Journal Rankings: 1.306 |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Zhang, W | en_US |
dc.contributor.author | Cheng, R | en_US |
dc.contributor.author | Kao, B | en_US |
dc.date.accessioned | 2014-09-19T15:49:10Z | - |
dc.date.available | 2014-09-19T15:49:10Z | - |
dc.date.issued | 2014 | en_US |
dc.identifier.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 | en_US |
dc.identifier.isbn | 978-1-4799-2555-1 | - |
dc.identifier.issn | 1084-4627 | - |
dc.identifier.uri | http://hdl.handle.net/10722/203650 | - |
dc.description.abstract | The 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.language | eng | en_US |
dc.publisher | IEEE Computer Society. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/conhome.jsp?punumber=1000178 | - |
dc.relation.ispartof | International Conference on Data Engineering Proceedings | en_US |
dc.title | Evaluating multi-way joins over discounted hitting time | en_US |
dc.type | Conference_Paper | en_US |
dc.identifier.email | Cheng, R: ckcheng@cs.hku.hk | en_US |
dc.identifier.email | Kao, B: kao@cs.hku.hk | en_US |
dc.identifier.authority | Cheng, R=rp00074 | en_US |
dc.identifier.authority | Kao, B=rp00123 | en_US |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1109/ICDE.2014.6816695 | - |
dc.identifier.scopus | eid_2-s2.0-84901755684 | - |
dc.identifier.hkuros | 239391 | en_US |
dc.identifier.spage | 724 | - |
dc.identifier.epage | 735 | - |
dc.publisher.place | United States | - |
dc.customcontrol.immutable | sml 141021 | - |
dc.identifier.issnl | 1084-4627 | - |