Locality preserving dictionaries: theory & application to clustering in databases

Summary: Locality preserving dictionaries (LPDs): partitioned sorted layouts with deliberate gaps so any key range maps to contiguous space proportional to range size, enabling efficient search/insert/delete. On-disk LPD clustering yields 5–13× faster range/sorted scans vs clustered B-trees, at 0–75% storage and up to 28% update overhead. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1186
Venue: PODS
Year: 1999
Pagerank: 6.5088664e-05
Overall Rank: 4,784 | 67.18%
DOI: 10.1145/303976.304009

Incoming Non-self Citations Over Time

Authors

1. Vijayshankar Raman (University of California Berkeley)

BibTeX Citation

@inproceedings{raman_pods99,
        address = {New York, NY, USA},
        series = {{PODS} '99},
        title = {{Locality preserving dictionaries: theory \& application to clustering in databases}},
        url = {https://dl.acm.org/doi/10.1145/303976.304009},
        doi = {10.1145/303976.304009},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Raman, Vijayshankar},
        year = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,950	An Adaptive Packed-Memory Array	2006	PODS	7.9260861e-05
11,134	Layered List Labeling	2024	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 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,968	On-line Reorganization of Sparsely-populated B+-trees	1996	SIGMOD	7.9149281e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,075	Distributing a Search Tree Among a Growing Number of Processors	1994	SIGMOD
2	2,082	A Dynamic Clustering Technique For Physical Database Design	1980	SIGMOD
3	1,551	Updatable Learned Index with Precise Positions	2021	VLDB
4	2,020	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB
5	6,451	Efficient Search of Multidimensional B-Trees	1995	VLDB
6	6,687	Making In-Memory Learned Indexes Efficient on Disk	2024	SIGMOD
7	925	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD
8	8,214	Tuning Hierarchical Learned Indexes on Disk and Beyond	2022	SIGMOD
9	12,025	Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries	2016	PODS
10	5,423	Updatable Learned Indexes Meet Disk-Resident DBMS - From Evaluations to Design Choices	2023	SIGMOD