Finding a Minimal Tree Pattern Under Neighborhood Constraints

Summary: Find minimal tree patterns conforming to schemas mapping each label to allowed neighbor bags; NP-hard but FPT parameterized by label-set size. Treats two schema languages: pairwise mutual exclusions (W[1]-hard, FPT for circular-arc graphs) and regular-expression schemas (FPT). (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1555
Venue: PODS
Year: 2011
Pagerank: 5.2426111e-05
Overall Rank: 9,652 | 33.78%
DOI: 10.1145/1989284.1989318

Incoming Non-self Citations Over Time

Authors

1. Benny Kimelfeld (IBM)
2. Yehoshua Sagiv (Hebrew University)

BibTeX Citation

@inproceedings{kimelfeld_pods11,
        address = {New York, NY, USA},
        series = {{PODS} '11},
        title = {{Finding a Minimal Tree Pattern Under Neighborhood Constraints}},
        url = {https://dl.acm.org/doi/10.1145/1989284.1989318},
        doi = {10.1145/1989284.1989318},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kimelfeld, Benny and Sagiv, Yehoshua},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,703	Finding Patterns in a Knowledge Base using Keywords to Compose Table Answers	2014	VLDB	6.5549049e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
37	DISCOVER: Keyword Search in Relational Databases	2002	VLDB	0.00048017193
496	Schema-Free XQuery	2004	VLDB	0.0001750537
1,429	Finding and Approximating Top-k Answers in Keyword Proximity Search	2006	PODS	0.00010811133
1,542	Keyword Proximity Search in Complex Data Graphs	2008	SIGMOD	0.00010421046
1,555	Keyword Search in Databases: The Power of RDBMS	2009	SIGMOD	0.00010370683
3,032	Learning to Create Data-Integrating Queries	2008	VLDB	7.8323614e-05
9,588	IQ: The Case for Iterative Querying for Knowledge	2011	CIDR	5.2521703e-05
12,434	Exploratory Keyword Search on Data Graphs	2010	SIGMOD	5.093636e-05
12,512	ExQueX: Exploring and Querying XML Documents	2009	SIGMOD	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,680	Efficient Algorithms for Minimizing Tree Pattern Queries	2002	SIGMOD
2	12,098	Defining Relations on Graphs: How Hard is it in the Presence of Node Partitions?	2015	PODS
3	12,625	The Complexity of Reasoning about Pattern-based XML Schemas	2007	PODS
4	7,622	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB
5	1,068	Minimization of Tree Pattern Queries	2001	SIGMOD
6	10,044	The (Almost) Complete Guide to Tree Pattern Containment	2015	PODS
7	4,986	Querying Graph Patterns	2011	PODS
8	12,030	Minimization of Tree Pattern Queries	2016	PODS
9	3,463	Efficient Evaluation and Approximation of Well-designed Pattern Trees	2015	PODS
10	6,005	Minimization of Tree Pattern Queries with Constraints	2008	SIGMOD