FIFO Indexes for Decomposable Problems

Summary: FIFO indexes for datasets with deletions in insertion order, and a black-box technique to convert efficiently-constructible static structures for decomposable problems into FIFO indexes. Delivers linear-space methods for half-plane, nearest-neighbor, and extreme-point queries with optimal or near-optimal query costs. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hbba9b42b0f539fab
Venue: PODS
Year: 2011
Pagerank: 4.9605343e-05
Overall Rank: 12,703 | 14.85%
DOI: 10.1145/1989284.1989291

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Cheng Sheng (Chinese University of Hong Kong)
2. Yufei Tao (Chinese University of Hong Kong)

BibTeX Citation

@inproceedings{sheng_pods11,
        address = {New York, NY, USA},
        series = {{PODS} '11},
        title = {{FIFO Indexes for Decomposable Problems}},
        url = {https://dl.acm.org/doi/10.1145/1989284.1989291},
        doi = {10.1145/1989284.1989291},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Sheng, Cheng and Tao, Yufei},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
26	Models and Issues in Data Stream Systems	2002	PODS	0.00051942573
344	The Onion Technique: Indexing for Linear Optimization Queries	2000	SIGMOD	0.00020463118
576	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00016130425
713	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014582248
1,594	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00010103178
2,262	Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring	2005	SIGMOD	8.7350282e-05
6,619	Wave-Indices: Indexing Evolving Databases	1997	SIGMOD	5.7149564e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,941	I/O-Efficient Planar Range Skyline and Attrition Priority Queues	2013	PODS
2	930	On Indexing Mobile Objects	1999	PODS
3	1,654	Indexing Moving Points (Extended Abstract)	2000	PODS
4	12,104	On the I/O Complexity of the k-Nearest Neighbors Problem	2020	PODS
5	12,372	Efficient Top-k Indexing via General Reductions	2016	PODS
6	7,798	Efficient Indexes for Diverse Top-k Range Queries	2020	PODS
7	12,643	Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility	2012	PODS
8	6,678	Optimal Indexing Using Near-Minimal Space [Extended Abstract]	2003	PODS
9	2,051	Indexing for Data Models with Constraints and Classes (Extended Abstract)	1993	PODS
10	1,514	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS