Distance-Join: Pattern Match Query In a Large Graph Database

Summary: Distance-Join transforms graph vertices into vectors, turning pattern-match queries on large graphs into a distance-based multi-way join in vector space. It introduces pruning strategies and join-order optimization, with experiments showing orders-of-magnitude speedups over existing methods. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h8f0624a61a3c2387
Venue: VLDB
Year: 2009
Pagerank: 0.00014021799
Overall Rank: 783 | 94.74%
DOI: 10.14778/1687627.1687727

Incoming Non-self Citations Over Time

Authors

1. Lei Zou (Huazhong University of Science and Technology)
2. Lei Chen (Hong Kong University of Science and Technology)
3. M. Tamer Özsu (University of Waterloo)

BibTeX Citation

@article{zou_vldb09,
        title = {{Distance-Join: Pattern Match Query In a Large Graph Database}},
        author = {Zou, Lei and Chen, Lei and Özsu, M. Tamer},
        journal = {PVLDB},
        series = {{VLDB} '09},
        doi = {10.14778/1687627.1687727},
        url = {https://doi.org/10.14778/1687627.1687727},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 25 of 25 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
355	On Graph Query Optimization in Large Networks	2010	VLDB	0.00020124083
443	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018197688
511	Scalable SPARQL Querying of Large RDF Graphs	2011	VLDB	0.00017061883
1,027	GraMI: Frequent Subgraph and Pattern Mining in a Single Large Graph	2014	VLDB	0.00012422544
1,148	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.00011809728
1,249	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB	0.00011340141
1,410	A Distributed Graph Engine for Web Scale RDF Data	2013	VLDB	0.00010742208
1,864	Efficient SimRank-based Similarity Join Over Large Graphs	2013	VLDB	9.4824224e-05
2,773	Graph Homomorphism Revisited for Graph Matching	2010	VLDB	8.0351713e-05
4,583	Event Pattern Matching over Graph Streams	2015	VLDB	6.5187824e-05
5,017	Privacy Preserving Subgraph Matching on Large Graphs in Cloud	2016	SIGMOD	6.3125608e-05
5,309	On Link-based Similarity Join	2011	VLDB	6.1865348e-05
5,581	Neighborhood-Privacy Protected Shortest Distance Computing in Cloud	2011	SIGMOD	6.076839e-05
5,605	Capturing Topology in Graph Pattern Matching	2012	VLDB	6.0695806e-05
6,027	Answering Top-k Representative Queries on Graph Databases	2014	SIGMOD	5.9112117e-05
6,811	BOOMER: Blending Visual Formulation and Processing of P-Homomorphic Queries on Large Networks	2018	SIGMOD	5.6744946e-05
7,573	A Framework for Privacy Preserving Localized Graph Pattern Query Processing	2023	SIGMOD	5.4934674e-05
7,752	Optimal Enumeration: Efficient Top-k Tree Matching	2015	VLDB	5.4595236e-05
7,768	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB	5.4558207e-05
8,042	Adaptive Optimizations of Recursive Queries in Teradata	2012	SIGMOD	5.4014499e-05
9,278	Ontological Pathfinding: Mining First-Order Knowledge from Large Knowledge Bases	2016	SIGMOD	5.203976e-05
10,056	Finding Logic Bugs in Graph-processing Systems via Graph-cutting	2025	SIGMOD	5.0875952e-05
10,782	Testing Graph Databases via Transformations Between Fixed-Length and Variable-Length Queries	2026	VLDB	4.9793485e-05
11,358	GraphCSR: A Degree-Equalized CSR Format for Large-scale Graph Processing	2025	VLDB	4.9793485e-05
11,539	Connectivity-Oriented Property Graph Partitioning for Distributed Graph Pattern Query Processing	2024	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029061754
176	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00026700508
192	Algorithmics and Applications of Tree and Graph Searching	2002	PODS	0.00025659453
330	Fast and Practical Indexing and Querying of Very Large Graphs	2007	SIGMOD	0.00020838159
332	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00020765078
736	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00014363536
1,996	Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data	2001	SIGMOD	9.216723e-05
4,291	Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs	2008	SIGMOD	6.6827339e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	288	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD
2	1,181	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB
3	2,014	RapidMatch: A Holistic Approach to Subgraph Query Processing	2021	VLDB
4	12,450	Leveraging Graph Dimensions in Online Graph Search	2015	VLDB
5	1,148	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB
6	9,361	Subgraph Matching: A New Decomposition Based Approach	2025	VLDB
7	657	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD
8	12,065	Simulation-based Approximate Graph Pattern Matching	2020	SIGMOD
9	443	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB
10	12,059	Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees	2020	SIGMOD