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.9793485e-05
Overall Rank: 12,654 | 14.93%
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.00052121228
342	The Onion Technique: Indexing for Linear Optimization Queries	2000	SIGMOD	0.00020530255
574	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00016173068
710	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014608975
1,589	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00010139591
2,243	Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring	2005	SIGMOD	8.7678247e-05
6,607	Wave-Indices: Indexing Evolving Databases	1997	SIGMOD	5.736384e-05

Semantically Similar Papers

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