Sorting on Byte-Addressable Storage: The Resurgence of Tree Structure

Summary: Revisits tree-based sorting for hybrid DRAM–byte-addressable storage (BAS), exploiting the tree's write-once property to align with BAS's asymmetric read/write costs and studying compatibility of existing sorts. Proposes TSort—an optimized tree-sort that outperforms in-place and external sorts across distributions. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13392
Venue: VLDB
Year: 2024
Pagerank: 4.1905499e-05
Overall Rank: 11,012 | 23.47%
DOI: 10.14778/3648160.3648185

Incoming Non-self Citations Over Time

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

Authors

1. Ying Zheng
2. Kian-Lee Tan

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
185	DuckDB: an Embeddable Analytical Database	2019	SIGMOD	0.00036529607
193	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00035591171
625	Hexastore: Sextuple Indexing for Semantic Web Data Management	2008	VLDB	0.00018963452
2,072	HippogriffDB: Balancing I/O and GPU Bandwidth in Big Data Analytics	2016	VLDB	9.6300019e-05
2,257	Write-limited sorts and joins for persistent memory	2014	VLDB	9.1808674e-05
4,269	Maximizing Persistent Memory Bandwidth Utilization for OLAP Workloads	2021	SIGMOD	6.2950779e-05
4,404	TreeLine: An Update-In-Place Key-Value Store for Modern Storage	2023	VLDB	6.2052645e-05
5,503	Worst-Case Optimal Graph Joins in Almost No Space	2021	SIGMOD	5.4718854e-05
6,226	When Tree Meets Hash: Reducing Random Reads for Index Structures on Persistent Memories	2023	SIGMOD	5.1413982e-05
6,466	NBTree: a Lock-free PM-friendly Persistent B+-Tree for eADR-enabled PM Systems	2022	VLDB	5.04625e-05
6,997	PetPS: Supporting Huge Embedding Models with Persistent Memory	2023	VLDB	4.8629617e-05
6,998	WiscSort: External Sorting For Byte-Addressable Storage	2023	VLDB	4.8629617e-05
7,040	NVM: Is it Not Very Meaningful for Databases?	2023	VLDB	4.8493186e-05
8,831	Hamming Tree: The Case for Energy-Aware Indexing for NVMs	2023	SIGMOD	4.4360431e-05
8,855	A Design Space Exploration and Evaluation for Main-Memory Hash Joins in Storage Class Memory	2023	VLDB	4.4306395e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,610	A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort	2014	SIGMOD	0.00011155922
6,226	When Tree Meets Hash: Reducing Random Reads for Index Structures on Persistent Memories	2023	SIGMOD	5.1413982e-05
13,086	Experiments With B-Tree Reorganization	1980	SIGMOD	4.1905499e-05
9,499	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD	4.3300131e-05
4,826	Dynamic Memory Adjustment for External Mergesort	1997	VLDB	5.8892345e-05
1,524	Sorting And Indexing With Partitioned B-Trees	2003	CIDR	0.00011509464
4,649	SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures	2015	VLDB	6.0171025e-05
6,998	WiscSort: External Sorting For Byte-Addressable Storage	2023	VLDB	4.8629617e-05
11,840	A Study of Sorting Algorithms on Approximate Memory	2016	SIGMOD	4.1905499e-05
10,380	B-Trees Are Back: Engineering Fast and Pageable Node Layouts	2025	SIGMOD	4.1905499e-05