Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs

Summary: Weighted graphs with weights render keyword twig queries NP-hard; monotonicity for ranked-joins fails. Proposes sum-max monotonicity and HR-Join, a horizon-based, self-punctuating ranked-join for twig queries on graphs; experiments confirm efficiency. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9603
Venue: VLDB
Year: 2007
Pagerank: 4.792172e-05
Overall Rank: 7,240 | 49.64%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,143	Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs	2008	SIGMOD	6.4129418e-05
7,166	Ranked Enumeration of Join Queries with Projections	2022	VLDB	4.8124491e-05
7,762	Optimal Enumeration: Efficient Top-k Tree Matching	2015	VLDB	4.6583829e-05

Outgoing Citations (Sorted by Pagerank)

Showing 24 of 24 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
54	DISCOVER: Keyword Search in Relational Databases	2002	VLDB	0.00066047203
61	DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases	1997	VLDB	0.00064329285
72	Combining Fuzzy Information from Multiple Systems	1996	PODS	0.00058577335
73	XRANK: Ranked Keyword Search over XML Documents	2003	SIGMOD	0.00058443993
240	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00031603463
320	ObjectRank: Authority-Based Keyword Search in Databases	2004	VLDB	0.00027577867
336	Bidirectional Expansion For Keyword Search on Graph Databases	2005	VLDB	0.00027020919
434	XSEarch: A Semantic Search Engine for XML	2003	VLDB	0.0002328559
552	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB	0.00020310903
674	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00018327585
817	Covering Indexes for Branching Path Queries	2002	SIGMOD	0.00016352717
869	APEX: An Adaptive Path Index for XML Data	2002	SIGMOD	0.00015788339
1,235	Minimization of Tree Pattern Queries	2001	SIGMOD	0.00013120483
1,262	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.00012986539
1,733	Efficient Structural Joins on Indexed XML Documents	2002	VLDB	0.00010724888
2,556	Probabilistic Optimization of Top N Queries	1999	VLDB	8.5465733e-05
3,807	Supporting Ad-hoc Ranking Aggregates	2006	SIGMOD	6.747576e-05
4,587	On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques	2005	SIGMOD	6.0658154e-05
6,787	FICSR: Feedback-based InConSistency Resolution and Query Processing on Misaligned Data Sources	2007	SIGMOD	4.92548e-05
7,468	Boolean + Ranking: Querying a Database by K-Constrained Optimization	2006	SIGMOD	4.7210446e-05
7,738	AFilter: Adaptable XML Filtering with Prefix-Caching and Suffix-Clustering	2006	VLDB	4.6636747e-05
7,763	Covering Indexes for XML Queries: Bisimulation - Simulation = Negation	2003	VLDB	4.6575679e-05
12,730	A Multi-Similarity Algebra	1998	SIGMOD	4.1945683e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,393	Rank-aware Query Optimization	2004	SIGMOD	8.9016542e-05
1,038	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS	0.00014492414
7,166	Ranked Enumeration of Join Queries with Projections	2022	VLDB	4.8124491e-05
3,908	Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions	2007	SIGMOD	6.6392878e-05
12,111	Optimal Top-k Generation of Attribute Combinations based on Ranked Lists	2012	SIGMOD	4.1945683e-05
3,715	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8220943e-05
8,061	Efficient Computation of Quantiles over Joins	2023	PODS	4.5943269e-05
9,594	Fast Optimal Twig Joins	2010	VLDB	4.3197044e-05
2,961	Evaluating Rank Joins with Optimal Cost	2008	PODS	7.8110394e-05
7,692	Processing Top-k Join Queries	2010	VLDB	4.6761366e-05