A Study of Sorting Algorithms on Approximate Memory

Summary: Study of sorting on hybrid precise/approximate memory; three sorts. Proposes approx-refine: offload to approximate storage, and refine to precise output; yields 95% sorted accuracy with up to 40% write-latency reduction and up to 11% mem-access-time savings. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5161
Venue: SIGMOD
Year: 2016
Pagerank: 5.093636e-05
Overall Rank: 12,033 | 17.45%
DOI: 10.1145/2882903.2882908

Incoming Non-self Citations Over Time

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

Authors

1. Shuang Chen (Nanyang Technological University; Shanghai Jiao Tong University)
2. Shunning Jiang (Nanyang Technological University; Shanghai Jiao Tong University)
3. Bingsheng He (Nanyang Technological University)
4. Xueyan Tang (Nanyang Technological University)

BibTeX Citation

@inproceedings{chen_sigmod16,
        title = {{A Study of Sorting Algorithms on Approximate Memory}},
        author = {Chen, Shuang and Jiang, Shunning and He, Bingsheng and Tang, Xueyan},
        series = {{SIGMOD} '16},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2882903.2882908},
        url = {https://dl.acm.org/doi/10.1145/2882903.2882908},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
252	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00023242719
305	GPUTeraSort: High Performance Graphics Co-processor Sorting for Large Database Management	2006	SIGMOD	0.00021872796
363	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.0002005475
603	Scalable Logging through Emerging Non-Volatile Memory	2014	VLDB	0.00015853456
621	Persistent B+-Trees in Non-Volatile Main Memory	2015	VLDB	0.00015695264
658	Rethinking Database Algorithms for Phase Change Memory	2011	CIDR	0.0001523554
1,177	A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort	2014	SIGMOD	0.00011808761
1,401	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD	0.00010889902
1,996	Write-limited sorts and joins for persistent memory	2014	VLDB	9.3396464e-05
2,608	A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries	2001	SIGMOD	8.347674e-05
12,216	When Data Management Systems Meet Approximate Hardware: Challenges and Opportunities	2014	VLDB	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,220	Sorting on Byte-Addressable Storage: The Resurgence of Tree Structure	2024	VLDB
2	712	Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture	2008	VLDB
3	4,177	SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures	2015	VLDB
4	2,667	A Memory Bandwidth-Efficient Hybrid Radix Sort on GPUs	2017	SIGMOD
5	4,955	Dynamic Memory Adjustment for External Mergesort	1997	VLDB
6	7,705	A Study of Sort Algorithms for Multiprocessor Database Machines	1986	VLDB
7	12,216	When Data Management Systems Meet Approximate Hardware: Challenges and Opportunities	2014	VLDB
8	1,996	Write-limited sorts and joins for persistent memory	2014	VLDB
9	4,708	Memory-Adaptive External Sorting	1993	VLDB
10	1,177	A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort	2014	SIGMOD