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: 13391
Venue: VLDB
Year: 2024
Pagerank: 4.1945683e-05
Overall Rank: 11,009 | 23.42%
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.00036538405
193	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00035610321
624	Hexastore: Sextuple Indexing for Semantic Web Data Management	2008	VLDB	0.00018988711
2,067	HippogriffDB: Balancing I/O and GPU Bandwidth in Big Data Analytics	2016	VLDB	9.6392739e-05
2,451	Write-limited sorts and joins for persistent memory	2014	VLDB	8.7856313e-05
4,281	Maximizing Persistent Memory Bandwidth Utilization for OLAP Workloads	2021	SIGMOD	6.2940039e-05
4,427	TreeLine: An Update-In-Place Key-Value Store for Modern Storage	2023	VLDB	6.1965873e-05
5,493	Worst-Case Optimal Graph Joins in Almost No Space	2021	SIGMOD	5.4771449e-05
6,229	When Tree Meets Hash: Reducing Random Reads for Index Structures on Persistent Memories	2023	SIGMOD	5.1463389e-05
6,472	NBTree: a Lock-free PM-friendly Persistent B+-Tree for eADR-enabled PM Systems	2022	VLDB	5.0510585e-05
6,998	PetPS: Supporting Huge Embedding Models with Persistent Memory	2023	VLDB	4.8676312e-05
6,999	WiscSort: External Sorting For Byte-Addressable Storage	2023	VLDB	4.8676312e-05
7,043	NVM: Is it Not Very Meaningful for Databases?	2023	VLDB	4.8539749e-05
8,831	Hamming Tree: The Case for Energy-Aware Indexing for NVMs	2023	SIGMOD	4.4402596e-05
8,855	A Design Space Exploration and Evaluation for Main-Memory Hash Joins in Storage Class Memory	2023	VLDB	4.4348906e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,607	A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort	2014	SIGMOD	0.00011162682
6,229	When Tree Meets Hash: Reducing Random Reads for Index Structures on Persistent Memories	2023	SIGMOD	5.1463389e-05
13,073	Experiments With B-Tree Reorganization	1980	SIGMOD	4.1945683e-05
9,498	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD	4.3341665e-05
4,832	Dynamic Memory Adjustment for External Mergesort	1997	VLDB	5.8924168e-05
4,655	SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures	2015	VLDB	6.0221672e-05
1,524	Sorting And Indexing With Partitioned B-Trees	2003	CIDR	0.00011516282
6,999	WiscSort: External Sorting For Byte-Addressable Storage	2023	VLDB	4.8676312e-05
11,832	A Study of Sorting Algorithms on Approximate Memory	2016	SIGMOD	4.1945683e-05
10,368	B-Trees Are Back: Engineering Fast and Pageable Node Layouts	2025	SIGMOD	4.1945683e-05