Database Paper Browser

Back to papers

Neighborhood Based Fast Graph Search in Large Networks

Summary: Proposes Ness, a neighborhood-based similarity for top-k approximate subgraph/graph matching in large labeled networks, avoiding isomorphism and edit-distance. An information-propagation model embeds networks into vectors for fast indexing; robust to noise, with subgraph match NP-hard, graph similarity polynomial. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
4441
Venue
SIGMOD
Year
2011
Pagerank
0.00012833377
Overall Rank
1,285 | 91.07%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank Citing Paper Year Venue Pagerank
764 TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases 2013 SIGMOD 0.00017018712
1,635 An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases 2013 VLDB 0.0001105793
1,641 Fast and Exact Top-k Search for Random Walk with Restart 2012 VLDB 0.00011047924
1,958 Exemplar Queries: Give me an Example of What You Need 2014 VLDB 9.9572632e-05
2,117 Efficient SimRank-based Similarity Join Over Large Graphs 2013 VLDB 9.5155578e-05
2,551 NeMa: Fast Graph Search with Label Similarity 2013 VLDB 8.5572574e-05
3,202 VIIQ: Auto-Suggestion Enabled Visual Interface for Interactive Graph Query Formulation 2015 VLDB 7.3911717e-05
7,295 Searching with XQ: the eXemplar Query Search Engine 2014 SIGMOD 4.7728968e-05
8,210 Mining Top-k Pairs of Correlated Subgraphs in a Large Network 2020 VLDB 4.5581054e-05
9,228 Efficiently Counting Triangles in Large Temporal Graphs 2025 SIGMOD 4.3690661e-05
11,565 Simulation-based Approximate Graph Pattern Matching 2020 SIGMOD 4.1945683e-05
11,818 NED: An Inter-Graph Node Metric Based On Edit Distance 2017 VLDB 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
7 Optimal Aggregation Algorithms for Middleware [Extended Abstract] 2001 PODS 0.0015496097
155 Robust and Efficient Fuzzy Match for Online Data Cleaning 2003 SIGMOD 0.00040637896
171 Algorithmics and Applications of Tree and Graph Searching 2002 PODS 0.00038830709
203 Graph Indexing: A Frequent Structure-based Approach 2004 SIGMOD 0.00034889335
350 FG-Index: Towards Verification-Free Query Processing on Graph Databases 2007 SIGMOD 0.00026365067
572 Substructure Similarity Search in Graph Databases 2005 SIGMOD 0.00019887011
612 Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism 2008 VLDB 0.0001920234
869 APEX: An Adaptive Path Index for XML Data 2002 SIGMOD 0.00015788339
900 Graph Indexing: Tree + Delta >= Graph 2007 VLDB 0.00015495155
993 D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data 2003 SIGMOD 0.00014765816
1,414 Graph Pattern Matching: From Intractable to Polynomial Time 2010 VLDB 0.00012118275
1,454 SAPPER: Subgraph Indexing and Approximate Matching in Large Graphs 2010 VLDB 0.00011913289
2,938 Graph Homomorphism Revisited for Graph Matching 2010 VLDB 7.8524059e-05
5,159 Towards Proximity Pattern Mining in Large Graphs 2010 SIGMOD 5.6587631e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
1,844 Effective Community Search over Large Spatial Graphs 2017 VLDB 0.00010341077
1,920 Fast and Unified Local Search for Random Walk Based K-Nearest-Neighbor Query in Large Graphs 2014 SIGMOD 0.00010090791
2,721 Effective and Efficient Relational Community Detection and Search in Large Dynamic Heterogeneous Information Networks 2020 VLDB 8.2345495e-05
2,286 Effective and Efficient Community Search over Large Heterogeneous Information Networks 2020 VLDB 9.0982591e-05
8,505 Top-K Nearest Keyword Search on Large Graphs 2013 VLDB 4.4958064e-05
3,969 Efficient Size-Bounded Community Search over Large Networks 2021 VLDB 6.5787567e-05
10,694 Effective and Efficient Community Search for Complex Network Semantics Capture: From Coarse-Grain to Fine-Grain 2025 VLDB 4.1945683e-05
212 Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph 2019 VLDB 0.00033913475
6,839 Boosting Graph Similarity Search through Pre-Computation 2021 SIGMOD 4.9109527e-05
2,551 NeMa: Fast Graph Search with Label Similarity 2013 VLDB 8.5572574e-05