Heapsort for Equal Keys
| dc.date.accessioned | 2022-03-18T13:58:03Z | |
| dc.date.available | 2022-03-18T13:58:03Z | |
| dc.date.issued | 2014-09 | |
| dc.identifier | doi:10.17170/kobra-202203165893 | |
| dc.identifier.uri | http://hdl.handle.net/123456789/13707 | |
| dc.language.iso | eng | eng |
| dc.rights | Attribution-NoDerivatives 4.0 International | * |
| dc.rights.uri | http://creativecommons.org/licenses/by-nd/4.0/ | * |
| dc.subject | Sortieren | ger |
| dc.subject | Multimengen | ger |
| dc.subject | Duplikatsentfernung | ger |
| dc.subject | Heapsort | ger |
| dc.subject.ddc | 004 | |
| dc.title | Heapsort for Equal Keys | eng |
| dc.type | Preprint | |
| dcterms.abstract | Das effiziente Entfernen von Duplikaten in Datenbeständen ist eine algorithmische Herausforderung in theoretischer und praktischer Hinsicht. Tabellen mit Duplikaten entstehen in Datenbanken nach einer Projektion, beim Verfolgen von Seiten im Web, bei Messreihen und in der Stochastik. Ein häufige Methode, diese sog. Multisets in echte Mengen zu wandeln, ist die Sortierung mit folgender Entfernung aller gleichen Sätze bis auf einen. Idealerweise kann dies bereits bei der Sortierung in situ erfolgen, so dass vorne die sortierten Sätze stehen und hinten deren Duplikate. Noch wichtiger ist die Reduzierung der Laufzeit für n Sätze mit k unterschiedlichen Schlüsseln auf die untere Schranke von O(n log k) Schritte. Dies galt für das klassische Heapsort-Verfahren als nicht erreichbar ohne eine grundsätzliche Umstrukturierung im Stil von Dijkstras Smoothsort. Wir zeigen mit unserem Algorithmus DDHeapsort, dass diese Annahme irreführend ist und dass DDHeapsort in der Praxis die gewünschte Beschleunigung beim Vorliegen von Duplikaten aufweist, ohne dass eine erhebliche Verlangsamung bei duplikatfreien Datensätzen eintritt. | ger |
| dcterms.abstract | Efficient duplicate detection and deletion is an algorithmic challenge both in practical terms and from a theoretical stand point. Duplicates may occur in database tables after a projection, in tracking web traffic, experimentation and statistics. To reduce these multisets to proper sets, the most common approach is o sort the file first and then – in an additional sweep – take one instance, say the first, from each multiplicity of keys. If done in place, ideally the front of the file contains afterwards the sorted subset of unique keys and the duplicates are in the back. Sorting methods which can be engineered to do early duplicate deletion may reduce the effort spent to O(n log k), where k is the number of distinct keys. General wisdom had it that this smooth behaviour wasn’t achievable with heapsort unless the sort was totally redesigned in the style of Dijkstra’s Smoothsort. Here we show that this is a misperception and present DDHeapsortas a duplicate elimination method which achieves the lower bound of O (n log k) steps – both on the averageand in the worst case – and requires O(1) extra space. Empirical evidence suggests that DDHeapsort comes with very little penalty in the case of no duplicates when compared to a fast heapsort with subsequent duplicate detection sweep. | eng |
| dcterms.accessRights | open access | |
| dcterms.alternative | Sortierung mittels Heapsort bei Vorliegen gleicher Schlüssel | ger |
| dcterms.creator | Schweinsberg, Kai | |
| dcterms.creator | Teuhola, Jukka | |
| dcterms.creator | Wegner, Lutz | |
| dc.contributor.corporatename | Kassel, Universität Kassel, Fachbereich Elektrotechnik / Informatik | |
| dc.subject.swd | Daten | ger |
| dc.subject.swd | Sortieren | ger |
| dc.subject.swd | Multimenge | ger |
| dc.subject.swd | Dublette | ger |
| dc.subject.swd | Datenstruktur | ger |
| dc.subject.swd | Algorithmus | ger |
| dc.type.version | draft | |
| kup.iskup | false |
Dateien zu dieser Ressource
Das Dokument erscheint in:
-
Publikationen [18]
Solange nicht anders angezeigt, wird die Lizenz wie folgt beschrieben: Attribution-NoDerivatives 4.0 International