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: 1187
Venue: PODS
Year: 1999
Pagerank: 6.5085743e-05
Overall Rank: 4,037 | 71.92%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Vijayshankar Raman

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,366	An Adaptive Packed-Memory Array	2006	PODS	7.1726818e-05
10,913	Layered List Labeling	2024	PODS	4.1945683e-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
1,982	On-line Reorganization of Sparsely-populated B+-trees	1996	SIGMOD	9.8662834e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,804	Distributing a Search Tree Among a Growing Number of Processors	1994	SIGMOD	6.7525564e-05
1,709	A Dynamic Clustering Technique For Physical Database Design	1980	SIGMOD	0.00010811082
2,552	Updatable Learned Index with Precise Positions	2021	VLDB	8.5530411e-05
1,774	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB	0.00010604097
6,480	Efficient Search of Multidimensional B-Trees	1995	VLDB	5.0475112e-05
7,390	Making In-Memory Learned Indexes Efficient on Disk	2024	SIGMOD	4.7431654e-05
1,134	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD	0.00013761456
8,811	Tuning Hierarchical Learned Indexes on Disk and Beyond	2022	SIGMOD	4.4441574e-05
6,445	Updatable Learned Indexes Meet Disk-Resident DBMS - From Evaluations to Design Choices	2023	SIGMOD	5.0589805e-05
11,822	Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries	2016	PODS	4.1945683e-05