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: 9604
Venue: VLDB
Year: 2007
Pagerank: 4.7877732e-05
Overall Rank: 7,236 | 49.72%
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.4096394e-05
7,165	Ranked Enumeration of Join Queries with Projections	2022	VLDB	4.807833e-05
7,761	Optimal Enumeration: Efficient Top-k Tree Matching	2015	VLDB	4.6543114e-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
8	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015436578
53	DISCOVER: Keyword Search in Relational Databases	2002	VLDB	0.00065993143
61	DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases	1997	VLDB	0.00064281097
72	Combining Fuzzy Information from Multiple Systems	1996	PODS	0.00058498396
73	XRANK: Ranked Keyword Search over XML Documents	2003	SIGMOD	0.0005840064
239	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00031581944
320	ObjectRank: Authority-Based Keyword Search in Databases	2004	VLDB	0.00027574254
337	Bidirectional Expansion For Keyword Search on Graph Databases	2005	VLDB	0.00027002505
436	XSEarch: A Semantic Search Engine for XML	2003	VLDB	0.00023264416
551	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB	0.00020310856
673	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00018325667
812	Covering Indexes for Branching Path Queries	2002	SIGMOD	0.00016343476
864	APEX: An Adaptive Path Index for XML Data	2002	SIGMOD	0.00015781693
1,207	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.0001327437
1,236	Minimization of Tree Pattern Queries	2001	SIGMOD	0.00013107769
1,732	Efficient Structural Joins on Indexed XML Documents	2002	VLDB	0.00010716665
2,552	Probabilistic Optimization of Top N Queries	1999	VLDB	8.5540341e-05
3,809	Supporting Ad-hoc Ranking Aggregates	2006	SIGMOD	6.7413981e-05
4,584	On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques	2005	SIGMOD	6.0599995e-05
6,787	FICSR: Feedback-based InConSistency Resolution and Query Processing on Misaligned Data Sources	2007	SIGMOD	4.9207828e-05
7,469	Boolean + Ranking: Querying a Database by K-Constrained Optimization	2006	SIGMOD	4.7165172e-05
7,737	AFilter: Adaptable XML Filtering with Prefix-Caching and Suffix-Clustering	2006	VLDB	4.6592327e-05
7,763	Covering Indexes for XML Queries: Bisimulation - Simulation = Negation	2003	VLDB	4.6531059e-05
12,739	A Multi-Similarity Algebra	1998	SIGMOD	4.1905499e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,249	Rank-aware Query Optimization	2004	SIGMOD	9.1956569e-05
1,039	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS	0.00014488271
7,165	Ranked Enumeration of Join Queries with Projections	2022	VLDB	4.807833e-05
3,911	Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions	2007	SIGMOD	6.6343292e-05
12,119	Optimal Top-k Generation of Attribute Combinations based on Ranked Lists	2012	SIGMOD	4.1905499e-05
3,702	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8251643e-05
8,065	Efficient Computation of Quantiles over Joins	2023	PODS	4.5899218e-05
9,594	Fast Optimal Twig Joins	2010	VLDB	4.3155661e-05
2,965	Evaluating Rank Joins with Optimal Cost	2008	PODS	7.8049517e-05
7,660	Processing Top-k Join Queries	2010	VLDB	4.6814547e-05