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: 13579
Venue: VLDB
Year: 2024
Pagerank: 5.093636e-05
Overall Rank: 11,220 | 23.03%
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 (National University of Singapore)
2. Kian-Lee Tan (National University of Singapore)

BibTeX Citation

@article{zheng_vldb24,
        title = {{Sorting on Byte-Addressable Storage: The Resurgence of Tree Structure}},
        author = {Zheng, Ying and Tan, Kian-Lee},
        journal = {PVLDB},
        series = {{VLDB} '24},
        volume = {17},
        number = {6},
        pages = {1487--1500},
        doi = {10.14778/3648160.3648185},
        url = {https://doi.org/10.14778/3648160.3648185},
        year = {2024}
}

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
103	DuckDB: an Embeddable Analytical Database	2019	SIGMOD	0.00034161428
163	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00027839792
542	Hexastore: Sextuple Indexing for Semantic Web Data Management	2008	VLDB	0.00016838296
1,666	HippogriffDB: Balancing I/O and GPU Bandwidth in Big Data Analytics	2016	VLDB	0.00010068964
1,996	Write-limited sorts and joins for persistent memory	2014	VLDB	9.3396464e-05
3,535	TreeLine: An Update-In-Place Key-Value Store for Modern Storage	2023	VLDB	7.3333933e-05
3,647	Maximizing Persistent Memory Bandwidth Utilization for OLAP Workloads	2021	SIGMOD	7.2271935e-05
4,753	Worst-Case Optimal Graph Joins in Almost No Space	2021	SIGMOD	6.5231863e-05
5,954	When Tree Meets Hash: Reducing Random Reads for Index Structures on Persistent Memories	2023	SIGMOD	6.0292226e-05
5,993	NBTree: a Lock-free PM-friendly Persistent B+-Tree for eADR-enabled PM Systems	2022	VLDB	6.0158662e-05
7,046	NVM: Is it Not Very Meaningful for Databases?	2023	VLDB	5.7185159e-05
7,190	PetPS: Supporting Huge Embedding Models with Persistent Memory	2023	VLDB	5.6772818e-05
7,191	WiscSort: External Sorting For Byte-Addressable Storage	2023	VLDB	5.6772818e-05
8,833	Hamming Tree: The Case for Energy-Aware Indexing for NVMs	2023	SIGMOD	5.3599647e-05
8,904	A Design Space Exploration and Evaluation for Main-Memory Hash Joins in Storage Class Memory	2023	VLDB	5.3483178e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,177	A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort	2014	SIGMOD
2	5,954	When Tree Meets Hash: Reducing Random Reads for Index Structures on Persistent Memories	2023	SIGMOD
3	13,274	Experiments With B-Tree Reorganization	1980	SIGMOD
4	9,635	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD
5	4,955	Dynamic Memory Adjustment for External Mergesort	1997	VLDB
6	4,177	SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures	2015	VLDB
7	1,508	Sorting And Indexing With Partitioned B-Trees	2003	CIDR
8	7,191	WiscSort: External Sorting For Byte-Addressable Storage	2023	VLDB
9	12,033	A Study of Sorting Algorithms on Approximate Memory	2016	SIGMOD
10	9,810	B-Trees Are Back: Engineering Fast and Pageable Node Layouts	2025	SIGMOD