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: 1535
Venue: PODS
Year: 2011
Pagerank: 5.093636e-05
Overall Rank: 12,363 | 15.18%
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.00052982574
333	The Onion Technique: Indexing for Linear Optimization Queries	2000	SIGMOD	0.0002089582
560	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00016525569
691	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014927798
1,561	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00010361147
2,205	Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring	2005	SIGMOD	8.9591376e-05
6,479	Wave-Indices: Indexing Evolving Databases	1997	SIGMOD	5.8671916e-05

Semantically Similar Papers

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