PS-Tree-Based Efficient Boolean Expression Matching for High-Dimensional and Dense Workloads

Summary: PS-Tree enables 1D subscription indexing via disjoint predicate spaces. PSTBloom/PSTHash prune non-matches in high-dim workloads, delivering up to 84% faster matching, 78% faster index construction, 94% memory savings, and 92% gains for dense workloads. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12150
Venue: VLDB
Year: 2019
Pagerank: 5.2755515e-05
Overall Rank: 9,400 | 35.51%
DOI: 10.14778/3291264.3291270

Incoming Non-self Citations Over Time

Authors

1. Shuping Ji (Technical University of Munich)
2. Hans-Arno Jacobsen (University of Toronto)

BibTeX Citation

@article{ji_vldb19,
        title = {{PS-Tree-Based Efficient Boolean Expression Matching for High-Dimensional and Dense Workloads}},
        author = {Ji, Shuping and Jacobsen, Hans-Arno},
        journal = {PVLDB},
        series = {{VLDB} '19},
        volume = {12},
        number = {3},
        pages = {251--264},
        doi = {10.14778/3291264.3291270},
        url = {https://doi.org/10.14778/3291264.3291270},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,577	A-Tree: A Dynamic Data Structure for Efficiently Indexing Arbitrary Boolean Expressions	2021	SIGMOD	5.409313e-05
10,520	Efficient Temporal Subgraph Management: A New Interval Index	2026	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0020210012
85	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00035405879
441	Filtering Algorithms and Implementation for Very Fast Publish/Subscribe Systems	2001	SIGMOD	0.00018407547
2,739	Indexing Boolean Expressions	2009	VLDB	8.1872509e-05
3,528	Practical Applications of Triggers and Constraints: Successes and Lingering Issues	2000	VLDB	7.3411417e-05
5,199	Efficiently Evaluating Complex Boolean Expressions	2010	SIGMOD	6.3216824e-05
5,517	Scalable Ranked Publish/Subscribe	2008	VLDB	6.1889819e-05
6,006	End-to-End Support for Joins in Large-Scale Publish/Subscribe Systems	2008	VLDB	6.0119118e-05
6,016	BE-Tree: An Index Structure to Efficiently Match Boolean Expressions over High-dimensional Discrete Space	2011	SIGMOD	6.0082425e-05
6,861	An Efficient Publish/Subscribe Index for E-Commerce Databases	2014	VLDB	5.7517379e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,971	Persistent Bloom Filter: Membership Testing for the Entire History	2018	SIGMOD
2	8,408	A Shifting Bloom Filter Framework for Set Queries	2016	VLDB
3	2,061	Selectivity Estimation For Boolean Queries	2000	PODS
4	6,716	SigMatch: Fast and Scalable Multi-Pattern Matching	2010	VLDB
5	442	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB
6	1,492	BF-Tree: Approximate Tree Indexing	2014	VLDB
7	6,861	An Efficient Publish/Subscribe Index for E-Commerce Databases	2014	VLDB
8	2,739	Indexing Boolean Expressions	2009	VLDB
9	6,016	BE-Tree: An Index Structure to Efficiently Match Boolean Expressions over High-dimensional Discrete Space	2011	SIGMOD
10	8,577	A-Tree: A Dynamic Data Structure for Efficiently Indexing Arbitrary Boolean Expressions	2021	SIGMOD