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.6010222e-05
Overall Rank: 4,739 | 67.07%
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
2,951	An Adaptive Packed-Memory Array	2006	PODS	7.9796299e-05
10,917	Layered List Labeling	2024	PODS	5.1725247e-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,913	On-line Reorganization of Sparsely-populated B+-trees	1996	SIGMOD	8.0358014e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,012	Distributing a Search Tree Among a Growing Number of Processors	1994	SIGMOD	7.0291093e-05
2,283	A Dynamic Clustering Technique For Physical Database Design	1980	SIGMOD	8.8915952e-05
1,742	Updatable Learned Index with Precise Positions	2021	VLDB	9.9382185e-05
1,990	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB	9.4360871e-05
6,355	Efficient Search of Multidimensional B-Trees	1995	VLDB	5.9660428e-05
6,958	Making In-Memory Learned Indexes Efficient on Disk	2024	SIGMOD	5.7990776e-05
904	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD	0.00013358074
8,697	Tuning Hierarchical Learned Indexes on Disk and Beyond	2022	SIGMOD	5.4473761e-05
11,830	Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries	2016	PODS	5.1725247e-05
5,789	Updatable Learned Indexes Meet Disk-Resident DBMS - From Evaluations to Design Choices	2023	SIGMOD	6.1471889e-05