Stable duplicate-key extraction with optimal time and space bounds

DOI10.1007/BF00289147MaRDI QIDQ1103387zbMATH OpenOpenAlexFDO

Authors Bing-Chao Huang, Michael A. Langston

Publication date 1989

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf00289147

zbMATH Keywords

file processingblock rearrangementduplicate-key extractionstable mergetransforming of list of records

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Data structures (68P05) Searching and sorting (68P10)

Recommendations

• Stable in situ sorting and minimum data movement
• Sorting multisets stably in minimum space
• Fast stable in-place sorting with \(O(n)\) data moves
• Stable minimum space partitioning in linear time
• Stable set and multiset operations in optimal time and space

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3374945 (Why is no real title available?)
• Simplified stable merging tasks
• Stable Sorting and Merging with Optimal Space and Time Bounds
• Stable Sorting in Asymptotically Optimal Time and Extra Space
• Stable unmerging in linear time and constant space

Cited in

(3)

• Sorting multisets stably in minimum space
• Stable set and multiset operations in optimal time and space
• Sorting multisets stably in minimum space

This page was built for publication: Stable duplicate-key extraction with optimal time and space bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1103387)