#### DMCA

## Diversified top-k graph pattern matching

Venue: | PVLDB |

Citations: | 6 - 1 self |

### Citations

2796 | Computational Complexity
- Papadimitriou
- 1994
(Show Context)
Citation Context ...aphs makes matching costly: for matching defined by simulation, it takes O(|G||Q|+ |G|2) time to compute M(Q;G) [11]; for subgraph isomorphism, it is NP-complete to decide whether a match exists (cf. =-=[29]-=-). (3) Social queries often need to find matches of a specific pattern (query) node uo as “query focus” [3], i.e., we just want those nodes in a social graph G that are matches of uo in M(Q;G), rather... |

1275 |
Approximation Algorithms
- Vazirani
- 2003
(Show Context)
Citation Context ...ion F (·) with a revised F ′(·), and (2) finding a solution that maximizes F ′(·), which in turn guarantees an approximation ratio for F (·). This technique is commonly used for optimization problems =-=[13,34]-=-. Algorithm. Given Q, G and an integer k, algorithm TopKDiv identifies a set S′ of k matches of uo, such that F (S′) ≥ F (S∗) 2 , where S∗ is an optimal set of k matches that maximizes F (·). That is,... |

985 | Maximizing the spread of influence through a social network
- Kempe, Kleinberg, et al.
- 2003
(Show Context)
Citation Context ...ion favors those matches that can reach more other matches: for a match vo of the output node uo, the more matches vo can reach, the bigger “impact” it may have, as observed in social network studies =-=[20]-=-. Thus, the matches with high r() values are preferred for relevance. Top-k matching problem. We now state the top-k matching problem, denoted by topKP. Given a graph G, a pattern Q with output node ... |

899 | The Link Prediction Problem for Social Networks
- L-Nowell, Kleinberg
- 2003
(Show Context)
Citation Context ...arlier are special cases of ∗r (), ∗ d() and F ∗(), respectively. Moreover, ∗r () and ∗ d() are able to express a variety of ranking functions commonly used in e.g., social/information networks =-=[22,24]-=- and Web search [28], including the following: Ranking functions Types Formulations Preference attachment [24] relevance |R(u)| ∗ |R∗(u; v)| Common neighbors [22] relevance |M(Q;G;R(u)) ∩ R∗(u; v)| Ja... |

713 | Optimal aggregation algorithms for middleware
- Fagin, Lotem, et al.
- 2001
(Show Context)
Citation Context ...tive integer k, it is to find k top-ranked matches of uo based on the relevance function r(). We provide two algorithms for doing so, in O(|G||Q| + |G|2) time yet with the early termination property =-=[10]-=-. That is, they stop as soon as the top-k matches are found, without computing the entire M(Q;G). (4) We also study the diversified top-k graph pattern matching problem (Section 5). It is to find top-... |

417 | Combining Fuzzy Information from Multiple Systems
- Fagin
- 1996
(Show Context)
Citation Context ...ML and graphs. Relational databases. Top-k query answering is to retrieve top-k tuples from query result. Given a monotone scoring function and sorted lists, one for each attribute, Fagin’s algorithm =-=[9]-=- reads attributes from the lists and constructs tuples with the attributes. It stops when k tuples are constructed from the top-ranked attributes that have been seen. It then performs random access to... |

255 | XRANK: ranked keyword search over XML documents
- Guo, Shao, et al.
- 2003
(Show Context)
Citation Context ...ithout computing the entire M(Q;G). XML and graph matching. Top-k queries have also been studied for XML, and for graph queries defined in terms of subgraph isomorphism. (1) XML keyword search (e.g., =-=[15]-=-) is to find top-k subtrees of a document, given a set of keywords. Essentially, the prior work is to find top-ranked trees or connected subgraphs induced from a set of keywords, rather than to find m... |

194 | Computing simulations on finite and infinite graphs
- Henzinger, Henzinger, et al.
- 1995
(Show Context)
Citation Context ...sis [5, 32], among other things. A number of algorithms have been developed for graph pattern matching that, given a graph pattern Q and a graph G, compute M(Q;G), the set of matches of Q in G (e.g., =-=[11, 18]-=-). Social data analysis, however, introduces new challenges to graph pattern matching. Social graphs are typically large, Permission to make digital or hard copies of all or part of this work for pers... |

189 | Clustering and preferential attachment in growing networks
- Newman
(Show Context)
Citation Context ...s of ∗r (), ∗ d() and F ∗(), respectively. Moreover, ∗r () and ∗ d() are able to express a variety of ranking functions commonly used in e.g., social/information networks [22,24] and Web search =-=[28]-=-, including the following: Ranking functions Types Formulations Preference attachment [24] relevance |R(u)| ∗ |R∗(u; v)| Common neighbors [22] relevance |M(Q;G;R(u)) ∩ R∗(u; v)| Jaccard Coefficient [2... |

164 | A survey of top-k query processing techniques in relational database systems
- Ilyas, Beskales, et al.
(Show Context)
Citation Context ...for details. 3. RANKING PATTERN MATCHES The result setMu(Q;G; uo) could still be excessively large when G is large, while users are often only interested in the best k matches of the output node of Q =-=[19]-=-. This suggests that we define certain functions to rank the matches, and compute top-k matches for uo based on the functions. In this section we study two sets of ranking functions: relevance functio... |

133 | What do people ask their social networks, and why?: a survey study of status message q&a behavior,
- Morris, Teevan, et al.
- 2010
(Show Context)
Citation Context ...ucted on a big social graph with more than 1 billion users and 140 billion links( http://newsroom.fb.com/). The need for this is also evident in, e.g., egocentric search [6] and expert recommendation =-=[27, 31]-=-. In fact, 15% of social queries are to find matches of specific pattern nodes [27]. These highlight the need for top-k graph pattern matching: given Q, G and a designated pattern node uo, it is to fi... |

104 | An Axiomatic Approach for Result Diversification. In
- Gollapudi, Sharma
- 2009
(Show Context)
Citation Context ...versification, which is not studied in the prior work mentioned above. Result diversification. Result diversification is a bicriteria optimization problem for balancing result relevance and diversity =-=[4,13]-=-, with applications in e.g., social searching [2]. (1) General frameworks for query result diversification are introduced in [4,13,30]. A set of axioms for designing diversification systems is propose... |

99 | Social matching: A framework and research agenda
- Terveen, McDonald
- 2005
(Show Context)
Citation Context ...ersified) top-k matching algorithms are effective, and outperform traditional matching algorithms in efficiency. 1. INTRODUCTION Graph pattern matching is being widely used in social network analysis =-=[5, 32]-=-, among other things. A number of algorithms have been developed for graph pattern matching that, given a graph pattern Q and a graph G, compute M(Q;G), the set of matches of Q in G (e.g., [11, 18]). ... |

83 | Identifying meaningful return information for xml keyword search
- Liu, Chen
- 2007
(Show Context)
Citation Context ...ries with output nodes. Several query languages allow one to specify a designated output node, notably twig queries on XML data [26]. Such nodes can also be specified with a “return” clause in XQuery =-=[25]-=-, or a “select” clause in SPARQL. These languages are typically based on subgraph (tree) isomorphism. To reduce search effort, [33] proposes a “Seed-Finder” that identifies matches for certain pattern... |

62 |
Vertex similarity in networks
- Leicht, Holme, et al.
(Show Context)
Citation Context ...arlier are special cases of ∗r (), ∗ d() and F ∗(), respectively. Moreover, ∗r () and ∗ d() are able to express a variety of ranking functions commonly used in e.g., social/information networks =-=[22,24]-=- and Web search [28], including the following: Ranking functions Types Formulations Preference attachment [24] relevance |R(u)| ∗ |R∗(u; v)| Common neighbors [22] relevance |M(Q;G;R(u)) ∩ R∗(u; v)| Ja... |

53 | Graph pattern matching: From intractable to polynomial time
- Fan, Li, et al.
- 2010
(Show Context)
Citation Context ...sis [5, 32], among other things. A number of algorithms have been developed for graph pattern matching that, given a graph pattern Q and a graph G, compute M(Q;G), the set of matches of Q in G (e.g., =-=[11, 18]-=-). Social data analysis, however, introduces new challenges to graph pattern matching. Social graphs are typically large, Permission to make digital or hard copies of all or part of this work for pers... |

53 | Fast best-effort pattern matching in large attributed graphs
- Tong, Faloutsos, et al.
- 2007
(Show Context)
Citation Context ...]. Such nodes can also be specified with a “return” clause in XQuery [25], or a “select” clause in SPARQL. These languages are typically based on subgraph (tree) isomorphism. To reduce search effort, =-=[33]-=- proposes a “Seed-Finder” that identifies matches for certain pattern nodes. These nodes are, however, not specified by users. This work extends twig queries to graph pattern matching defined in terms... |

51 | Learning concept importance using a weighted dependence model
- Bendersky, Metzler, et al.
- 2010
(Show Context)
Citation Context ...;G) [11]; for subgraph isomorphism, it is NP-complete to decide whether a match exists (cf. [29]). (3) Social queries often need to find matches of a specific pattern (query) node uo as “query focus” =-=[3]-=-, i.e., we just want those nodes in a social graph G that are matches of uo in M(Q;G), rather than the entire set M(Q;G) of matches of Q. Indeed, this is how “graph search” (http: //www.facebook.com/a... |

49 | Ecient top-k querying over social-tagging networks
- Schenkel, Crecelius, et al.
- 2008
(Show Context)
Citation Context ...ucted on a big social graph with more than 1 billion users and 140 billion links( http://newsroom.fb.com/). The need for this is also evident in, e.g., egocentric search [6] and expert recommendation =-=[27, 31]-=-. In fact, 15% of social queries are to find matches of specific pattern nodes [27]. These highlight the need for top-k graph pattern matching: given Q, G and a designated pattern node uo, it is to fi... |

45 | Approximation algorithms for maximum dispersion
- Hassin, Rubinstein, et al.
- 1997
(Show Context)
Citation Context ...f uo otherwise. We next show that TopKDiv approximates topKDP with ratio 2. To see this, note that an instance of TopKDiv can be transformed to an instance of the Maximum Dispersion problem (MAXDISP) =-=[16]-=-. The problem MAXDISP is to find a subgraph G′c induced by a k-node set Vc from a weighted complete graph Gc, with the maximum sum of node and edge weights. Given a match set Mu(Q;G; uo), we construct... |

43 | A fast bisimulation algorithm
- Dovier, Piazza, et al.
(Show Context)
Citation Context ...aph pattern matching is defined in terms of subgraph isomorphism [29], no match of Q can be identified in G. Indeed, it is too restrictive to define matches as isomorphic subgraphs [11]. Bisimulation =-=[8]-=- extends subgraph isomorphism with matching relations as equivalence relations, which is still unable to identify some sensible matches, e.g., PM1. Instead, we adopt simulation [18] with a designated ... |

27 |
DivQ: diversification for keyword search over structured databases, in:
- Demidova, Fankhauser, et al.
- 2010
(Show Context)
Citation Context ...strategies. (2) Based on result diversification, Top-k diversity queries are to find k answers that maximize both the relevance and overall diversity, which have been studied for e.g., keyword search =-=[7, 17]-=-. Generally speaking, the approaches to finding top-k diversified results consist of two steps: (1) a ranked list w.r.t. relevance score is computed; and (2) the list is re-ranked by combining diversi... |

23 | Adaptive processing of top-k queries in xml
- Marian, Amer-Yahia, et al.
- 2005
(Show Context)
Citation Context ...of keywords, rather than to find matches for a general graph pattern. (2) Top-k XPath queries are to identify top matches for the nodes in a tree pattern, based on tree pattern matching. For example, =-=[26]-=- finds top-ranked matches for tree patterns in terms of keyword and document frequency. (3) Top-k subgraph matching is to find top-ranked subgraphs that are isomorphic to a graph pattern [14, 37, 38],... |

23 | Efficient search ranking in social networks
- Vieira, Fonseca, et al.
- 2007
(Show Context)
Citation Context ...evance |M(Q;G;R(u)) ∩ R∗(u; v)| Jaccard Coefficient [28] relevance |M(Q;G;R(u))∩R ∗(u;v)| |M(Q;G;R(u))∪R∗(u;v)| Neighborhood diversity [23] distance 1|R∗(u;v1)∩R∗(u;v2)| |V | Distance-based diversity =-=[36]-=- distance 1− 1 d(v1;v2) (d(v1; v2) is the distance between v1 and v2), or 1 if d(v1; v2)=∞. Generalized top-k matching. Given Q with output node uo, graph G and an integer k, the generalized topKP (re... |

22 |
Evolution of an online social aggregation network: An empirical study
- Garg, Gupta, et al.
- 2009
(Show Context)
Citation Context ...synthetic graphs G = (V;E;L), controlled by the number of nodes |V | and edges |E|, where L are assigned from a set of 15 labels. We generated synthetic graphs following the linkage generation models =-=[12]-=-: an edge was attached to the high degree nodes with higher probability (see [1] for details). We use (|V |; |E|) to denote the size of G. (3) Pattern generator. We also implemented a generator for gr... |

22 |
On query result diversification.
- Vieira, Razente, et al.
- 2011
(Show Context)
Citation Context ...wing criteria. (1) Social impact [21]. Observe that PM2 can reach more people than any other PM, i.e., PM2 has collaborated with more people. Thus PM2 has stronger social impact. (2) Social diversity =-=[2,35]-=-. Consider match sets {PM1;PM2} and {PM2;PM3}. While PM2 and PM3 worked with the same people, PM1 and PM2 are quite “dissimilar” since they covered different groups of people. Putting these together, ... |

18 |
Detecting social positions using simulation
- Brynielsson, Högberg, et al.
- 2010
(Show Context)
Citation Context ...ersified) top-k matching algorithms are effective, and outperform traditional matching algorithms in efficiency. 1. INTRODUCTION Graph pattern matching is being widely used in social network analysis =-=[5, 32]-=-, among other things. A number of algorithms have been developed for graph pattern matching that, given a graph pattern Q and a graph G, compute M(Q;G), the set of matches of Q in G (e.g., [11, 18]). ... |

16 | Max-sum diversification, monotone submodular functions and dynamic updates
- Borodin, Lee, et al.
- 2012
(Show Context)
Citation Context ...Process updates DB3.T to ⟨Xdb3 = true, {ST3; ST4;DB2;DB3;PRG2;PRG3}; 6; 6⟩. It then updates vector for each node in VA (line 10). After this, the vectors of the candidates for PMs are as follows (i ∈ =-=[3; 4]-=-): v v:T = ⟨v:bf; v:R; v:l; v:h⟩ PM2 ⟨XPM2 = true; {ST3;ST4;DB2;DB3;PRG2;PRG3}; 6; 7⟩ PMi ⟨XPMi = true; {ST3;ST4;DB2;DB3;PRG2;PRG3}; 6; 6⟩ Observe that after a single propagation, the termination cond... |

15 | Diversifying top-k results
- QIN, YU, et al.
- 2012
(Show Context)
Citation Context ...ia optimization problem for balancing result relevance and diversity [4,13], with applications in e.g., social searching [2]. (1) General frameworks for query result diversification are introduced in =-=[4,13,30]-=-. A set of axioms for designing diversification systems is proposed in [13], to characterize reasonable diversification functions. A general framework for diversified top-k search is proposed in [30],... |

13 | Scalable Diversified Ranking on Large Graphs‖,
- Li, Yu
- 2011
(Show Context)
Citation Context ...ment [24] relevance |R(u)| ∗ |R∗(u; v)| Common neighbors [22] relevance |M(Q;G;R(u)) ∩ R∗(u; v)| Jaccard Coefficient [28] relevance |M(Q;G;R(u))∩R ∗(u;v)| |M(Q;G;R(u))∪R∗(u;v)| Neighborhood diversity =-=[23]-=- distance 1|R∗(u;v1)∩R∗(u;v2)| |V | Distance-based diversity [36] distance 1− 1 d(v1;v2) (d(v1; v2) is the distance between v1 and v2), or 1 if d(v1; v2)=∞. Generalized top-k matching. Given Q with ou... |

11 | Efficient algorithms for exact ranked twig-pattern matching over graphs - Gou, Chirkova - 2008 |

9 | A survey of algorithms and systems for expert location in social networks
- Lappas, Liu, et al.
- 2011
(Show Context)
Citation Context ...graph search query to find PMs who supervised both DBs and PRGs, and moreover, (1) the DB worked under the PRG directly or indirectly, and vice versa; and (2) both the DB and the PRG supervised an ST =-=[21]-=-. The requirements for the PMs are expressed as a graph pattern Q shown in Fig. 1 (a). Here PM is the “focus” of the query, i.e., only the matches of PM are asked for [3]. This is indicated by labelin... |

8 | Top-k subgraph matching query in a large graph,” In
- Zou, Chen, et al.
- 2007
(Show Context)
Citation Context ...example, [26] finds top-ranked matches for tree patterns in terms of keyword and document frequency. (3) Top-k subgraph matching is to find top-ranked subgraphs that are isomorphic to a graph pattern =-=[14, 37, 38]-=-, ranked by, e.g., the total node similarity scores [38]. Our work differs from the prior work in the following. (1) We study top-k queries defined by graph simulation [18], rather than subgraph (tree... |

7 | GenDeR: A Generic Diversified Ranking Algorithm.
- He, Tong, et al.
- 2012
(Show Context)
Citation Context ...strategies. (2) Based on result diversification, Top-k diversity queries are to find k answers that maximize both the relevance and overall diversity, which have been studied for e.g., keyword search =-=[7, 17]-=-. Generally speaking, the approaches to finding top-k diversified results consist of two steps: (1) a ranked list w.r.t. relevance score is computed; and (2) the list is re-ranked by combining diversi... |

7 |
Top-k linked data query processing
- Wagner, Duc, et al.
- 2012
(Show Context)
Citation Context ...example, [26] finds top-ranked matches for tree patterns in terms of keyword and document frequency. (3) Top-k subgraph matching is to find top-ranked subgraphs that are isomorphic to a graph pattern =-=[14, 37, 38]-=-, ranked by, e.g., the total node similarity scores [38]. Our work differs from the prior work in the following. (1) We study top-k queries defined by graph simulation [18], rather than subgraph (tree... |

4 | On principles of egocentric person search in social networks
- Cohen, Kimelfeld, et al.
- 2011
(Show Context)
Citation Context ...aphsearch) of Facebook is conducted on a big social graph with more than 1 billion users and 140 billion links( http://newsroom.fb.com/). The need for this is also evident in, e.g., egocentric search =-=[6]-=- and expert recommendation [27, 31]. In fact, 15% of social queries are to find matches of specific pattern nodes [27]. These highlight the need for top-k graph pattern matching: given Q, G and a desi... |

3 | Diversity and relevance in social search - Alonso, Gamon, et al. - 2012 |