An Adaptive Packed-Memory Array

Summary: Adaptive Packed‑Memory Array (APMA) auto‑tunes gap placement to update patterns, preserving PMA worst‑case O(log^2 N) amortized element moves and memory‑transfer bounds while often reducing costs to O(log N). Analyzes sequential/hammer/random/bulk inserts and reports ~4× fewer moves and >7× faster runtime in simulations. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1372
Venue: PODS
Year: 2006
Pagerank: 7.9260861e-05
Overall Rank: 2,950 | 79.77%
DOI: 10.1145/1142351.1142355

Incoming Non-self Citations Over Time

Authors

1. Michael A. Bender (State University of New York at Stony Brook)
2. Haodong Hu (State University of New York at Stony Brook)

BibTeX Citation

@inproceedings{bender_pods06,
        address = {New York, NY, USA},
        series = {{PODS} '06},
        title = {{An Adaptive Packed-Memory Array}},
        url = {https://dl.acm.org/doi/10.1145/1142351.1142355},
        doi = {10.1145/1142351.1142355},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Bender, Michael A. and Hu, Haodong},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
447	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD	0.00018322593
2,141	Teseo and the Analysis of Structural Dynamic Graphs	2021	VLDB	9.0978534e-05
2,866	Optimal Column Layout for Hybrid Workloads	2019	VLDB	8.0175489e-05
3,558	Updating a Cracked Database	2007	SIGMOD	7.3101789e-05
4,171	Accelerating Dynamic Graph Analytics on GPUs	2018	VLDB	6.8537202e-05
4,578	PLIN: A Persistent Learned Index for Non-Volatile Memory with High Performance and Instant Recovery	2023	VLDB	6.6210545e-05
4,946	Spruce: A Fast yet Space-saving Structure for Dynamic Graph Storage	2024	SIGMOD	6.4319457e-05
8,154	Revisiting the Design of In-Memory Dynamic Graph Storage	2025	SIGMOD	5.4769071e-05
10,489	RadixGraph: A Fast, Space-Optimized Data Structure for Dynamic Graph Storage	2026	SIGMOD	5.093636e-05
11,087	Towards Sufficient GPU-accelerated Dynamic Graph Management: Survey and Experiment	2025	VLDB	5.093636e-05
11,134	Layered List Labeling	2024	PODS	5.093636e-05
12,025	Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries	2016	PODS	5.093636e-05
12,164	Cost-Oblivious Storage Reallocation	2014	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1,112	Cache-Oblivious String B-trees	2006	PODS	0.00012125766
2,721	Good Worst-Case Algorithms for Inserting and Deleting Records in Dense Sequential Files	1986	SIGMOD	8.206745e-05
4,784	Locality preserving dictionaries: theory & application to clustering in databases	1999	PODS	6.5088664e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,173	Dynamic Top-K Range Reporting in External Memory	2012	PODS
2	5,954	When Tree Meets Hash: Reducing Random Reads for Index Structures on Persistent Memories	2023	SIGMOD
3	8,689	Adaptive Index Structures	2002	VLDB
4	1,811	Merging What's Cracked, Cracking What's Merged: Adaptive Indexing in Main-Memory Column-Stores	2011	VLDB
5	6,429	Just-In-Time Data Structures	2015	CIDR
6	8,937	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS
7	12,033	A Study of Sorting Algorithms on Approximate Memory	2016	SIGMOD
8	477	The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds	2020	VLDB
9	12,163	A Dynamic I/O-Efficient Structure for One-Dimensional Top-k Range Reporting	2014	PODS
10	12,025	Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries	2016	PODS