An Implementation of Impure Surrogates

Summary: Introduces “impure” surrogates generated from primary keys, avoiding B-tree indirection while enabling fast random and sequential access. Compression, hashing, ordered placement, dynamic overflows, and hash-tree indexing sustain performance at 90% occupancy despite schema and page-size changes. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 7746
Venue: VLDB
Year: 1982
Pagerank: 5.0723324e-05
Overall Rank: 13,320 | 8.93%
DOI: -

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. S. M. Deen (University of Aberdeen)

BibTeX Citation

@article{deen_vldb82,
        title = {{An Implementation of Impure Surrogates}},
        author = {Deen, S. M.},
        journal = {PVLDB},
        series = {{VLDB} '82},
        pages = {245},
        year = {1982}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
10	Extending the Data Base Relational Model to Capture More Meaning	1979	SIGMOD	0.00076970202
1,227	Trie Hashing	1981	SIGMOD	0.00011557551

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,813	Main-Memory Index Structures with Fixed-Size Partial Keys	2001	SIGMOD
2	546	Improving Index Performance through Prefetching	2001	SIGMOD
3	4,156	Efficiently Supporting Procedures In Relational Database Systems	1987	SIGMOD
4	12,079	Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries	2016	PODS
5	5,169	External Perfect Hashing	1985	SIGMOD
6	9,671	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD
7	5,505	Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps	2006	VLDB
8	5,513	Practical Prefetching via Data Compression (extended abstract)	1993	SIGMOD
9	5,305	Order-Preserving Key Compression for In-Memory Search Trees	2020	SIGMOD
10	13,140	Fast Search In Main Memory Databases	1992	SIGMOD