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: 10149
Venue: VLDB
Year: 2009
Pagerank: 0.00014110016
Overall Rank: 776 | 94.68%
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 24 of 24 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
352	On Graph Query Optimization in Large Networks	2010	VLDB	0.00020375193
442	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018398144
500	Scalable SPARQL Querying of Large RDF Graphs	2011	VLDB	0.00017413839
1,085	GraMI: Frequent Subgraph and Pattern Mining in a Single Large Graph	2014	VLDB	0.0001225302
1,128	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.0001206219
1,246	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB	0.00011504088
1,387	A Distributed Graph Engine for Web Scale RDF Data	2013	VLDB	0.00010949523
1,812	Efficient SimRank-based Similarity Join Over Large Graphs	2013	VLDB	9.6948178e-05
2,718	Graph Homomorphism Revisited for Graph Matching	2010	VLDB	8.209788e-05
4,503	Event Pattern Matching over Graph Streams	2015	VLDB	6.6597953e-05
5,186	On Link-based Similarity Join	2011	VLDB	6.3279474e-05
5,384	Privacy Preserving Subgraph Matching on Large Graphs in Cloud	2016	SIGMOD	6.2370509e-05
5,484	Capturing Topology in Graph Pattern Matching	2012	VLDB	6.2018052e-05
5,507	Neighborhood-Privacy Protected Shortest Distance Computing in Cloud	2011	SIGMOD	6.1924452e-05
5,965	Answering Top-k Representative Queries on Graph Databases	2014	SIGMOD	6.0256454e-05
6,728	BOOMER: Blending Visual Formulation and Processing of P-Homomorphic Queries on Large Networks	2018	SIGMOD	5.7898807e-05
7,622	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB	5.5806644e-05
7,664	Optimal Enumeration: Efficient Top-k Tree Matching	2015	VLDB	5.5720259e-05
7,891	Adaptive Optimizations of Recursive Queries in Teradata	2012	SIGMOD	5.5211516e-05
8,586	A Framework for Privacy Preserving Localized Graph Pattern Query Processing	2023	SIGMOD	5.4073203e-05
9,124	Ontological Pathfinding: Mining First-Order Knowledge from Large Knowledge Bases	2016	SIGMOD	5.319248e-05
9,866	Finding Logic Bugs in Graph-processing Systems via Graph-cutting	2025	SIGMOD	5.2043672e-05
10,972	GraphCSR: A Degree-Equalized CSR Format for Large-scale Graph Processing	2025	VLDB	5.093636e-05
11,197	Connectivity-Oriented Property Graph Partitioning for Distributed Graph Pattern Query Processing	2024	SIGMOD	5.093636e-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
145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029548428
177	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00027100548
187	Algorithmics and Applications of Tree and Graph Searching	2002	PODS	0.00026138589
322	Fast and Practical Indexing and Querying of Very Large Graphs	2007	SIGMOD	0.00021275303
326	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00021152829
727	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00014565738
1,993	Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data	2001	SIGMOD	9.3421788e-05
4,221	Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs	2008	SIGMOD	6.8233111e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	294	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,035	RapidMatch: A Holistic Approach to Subgraph Query Processing	2021	VLDB
4	12,159	Leveraging Graph Dimensions in Online Graph Search	2015	VLDB
5	1,128	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB
6	9,693	Subgraph Matching: A New Decomposition Based Approach	2025	VLDB
7	659	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD
8	11,762	Simulation-based Approximate Graph Pattern Matching	2020	SIGMOD
9	442	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB
10	11,756	Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees	2020	SIGMOD