Praktische Informatik/Datenbankenhttps://kobra.uni-kassel.de:443/handle/123456789/20080521216582024-03-29T14:35:53Z2024-03-29T14:35:53ZHeapsort for Equal KeysSchweinsberg, KaiTeuhola, JukkaWegner, Lutzhttps://kobra.uni-kassel.de:443/handle/123456789/137072022-03-21T14:47:54Z2014-09-01T00:00:00ZDas 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.; 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.
2014-09-01T00:00:00ZSchweinsberg, KaiTeuhola, JukkaWegner, LutzDas 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.
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.Gestengestützte Schema- und DatenexplorationAchler, Stefanhttps://kobra.uni-kassel.de:443/handle/123456789/20160613503932023-03-31T07:10:27Z2016-06-13T00:00:00ZDer Zugang zu Datenbanken über die universelle Abfragesprache SQL stellt für Nicht-Spezialisten eine große Herausforderung dar. Als eine benutzerfreundliche Alternative wurden daher seit den 1970er-Jahren unterschiedliche visuelle Abfragesprachen (Visual Query Languages, kurz VQLs) für klassische PCs erforscht. Ziel der vorliegenden Arbeit ist es, eine generische VQL zu entwickeln und zu erproben, die eine gestenbasierte Exploration von Datenbanken auf Schema- und Instanzdatenebene für mobile Endgeräte, insbesondere Tablets, ermöglicht. Dafür werden verschiedene Darstellungsformen, Abfragestrategien und visuelle Hints für Fremdschlüsselbeziehungen untersucht, die den Benutzer bei der Navigation durch die Daten unterstützen. Im Rahmen einer Anforderungsanalyse erwies sich die Visualisierung der Daten und Beziehungen mittels einer platzsparenden geschachtelten NF2-Darstellung als besonders vorteilhaft. Zur Steuerung der Datenbankexploration wird eine geeignete Gestensprache, bestehend aus Stroke-, Multitouch- und Mid-Air-Gesten, vorgestellt. Das Gesamtkonzept aus Darstellung und Gestensteuerung wurde anhand des im Rahmen dieser Arbeit entwickelten GBXT-Prototyps auf seine reale Umsetzbarkeit hin, als plattformunabhängige Single-Page-Application für verschiedene mobile Endgeräte mittels JavaScript und HTML5/CSS3 untersucht.; For non-specialists, interacting with databases through the universal query language SQL turns out to be a big challenge. As a user-friendly alternative, various visual query languages (short VQLs) for classical personal computers have been investigated since the Seventies. Aim of this thesis is to develop and test a generic VQL which allows a gesture-based exploration of databases through mobile devices, in particular tablets, both on the level of a given schema and on the level of the actual data. To find out what supports a user's navigation best, various forms of representations, query strategies and visual hints for foreign key relationships are investigated and compared. As the result of a requirement analysis, a space-saving visualization along the lines of nested relations (the so-called NF2 data model) came out as winner. To guide the database exploration, a suitable gesture language with stroke , multi-touch and mid-air gestures is proposed. As proof of concept for this combination of visualization and gesture-based control, a prototype implementation, named GBXT, was developed and evaluated as part of this thesis. The exploration tool runs as a platform-independent single page application for mobile devices using JavaScript and HTML5/CSS3.
2016-06-13T00:00:00ZAchler, StefanDer Zugang zu Datenbanken über die universelle Abfragesprache SQL stellt für Nicht-Spezialisten eine große Herausforderung dar. Als eine benutzerfreundliche Alternative wurden daher seit den 1970er-Jahren unterschiedliche visuelle Abfragesprachen (Visual Query Languages, kurz VQLs) für klassische PCs erforscht. Ziel der vorliegenden Arbeit ist es, eine generische VQL zu entwickeln und zu erproben, die eine gestenbasierte Exploration von Datenbanken auf Schema- und Instanzdatenebene für mobile Endgeräte, insbesondere Tablets, ermöglicht. Dafür werden verschiedene Darstellungsformen, Abfragestrategien und visuelle Hints für Fremdschlüsselbeziehungen untersucht, die den Benutzer bei der Navigation durch die Daten unterstützen. Im Rahmen einer Anforderungsanalyse erwies sich die Visualisierung der Daten und Beziehungen mittels einer platzsparenden geschachtelten NF2-Darstellung als besonders vorteilhaft. Zur Steuerung der Datenbankexploration wird eine geeignete Gestensprache, bestehend aus Stroke-, Multitouch- und Mid-Air-Gesten, vorgestellt. Das Gesamtkonzept aus Darstellung und Gestensteuerung wurde anhand des im Rahmen dieser Arbeit entwickelten GBXT-Prototyps auf seine reale Umsetzbarkeit hin, als plattformunabhängige Single-Page-Application für verschiedene mobile Endgeräte mittels JavaScript und HTML5/CSS3 untersucht.
For non-specialists, interacting with databases through the universal query language SQL turns out to be a big challenge. As a user-friendly alternative, various visual query languages (short VQLs) for classical personal computers have been investigated since the Seventies. Aim of this thesis is to develop and test a generic VQL which allows a gesture-based exploration of databases through mobile devices, in particular tablets, both on the level of a given schema and on the level of the actual data. To find out what supports a user's navigation best, various forms of representations, query strategies and visual hints for foreign key relationships are investigated and compared. As the result of a requirement analysis, a space-saving visualization along the lines of nested relations (the so-called NF2 data model) came out as winner. To guide the database exploration, a suitable gesture language with stroke , multi-touch and mid-air gestures is proposed. As proof of concept for this combination of visualization and gesture-based control, a prototype implementation, named GBXT, was developed and evaluated as part of this thesis. The exploration tool runs as a platform-independent single page application for mobile devices using JavaScript and HTML5/CSS3.Gone with the internet - How the old education was lostWegner, Lutz M.https://kobra.uni-kassel.de:443/handle/123456789/20150408480572022-06-17T14:45:38Z2015-04-08T00:00:00ZDespite its young history, Computer Science Education has seen a number of "revolutions". Being a
veteran in the field, the author reflects on the many changes he has seen in computing and its teaching.
The intent of this personal collection is to point out that most revolutions came unforeseen and that
many of the new learning initiatives, despite high financial input, ultimately failed.
The author then considers the current revolution (MOOC, inverted lectures, peer instruction, game
design) and, based on the lessons learned earlier, argues why video recording is so successful. Given the
fact that this is the decade we lost print (papers, printed books, book shops, libraries), the author then
conjectures that the impact of the Internet will make this revolution different from previous ones in that
most of the changes are irreversible. As a consequence he warns against storming ahead blindly and
suggests to conserve - while it is still possible - valuable components of what might soon be called the
antebellum age of education.
2015-04-08T00:00:00ZWegner, Lutz M.Despite its young history, Computer Science Education has seen a number of "revolutions". Being a
veteran in the field, the author reflects on the many changes he has seen in computing and its teaching.
The intent of this personal collection is to point out that most revolutions came unforeseen and that
many of the new learning initiatives, despite high financial input, ultimately failed.
The author then considers the current revolution (MOOC, inverted lectures, peer instruction, game
design) and, based on the lessons learned earlier, argues why video recording is so successful. Given the
fact that this is the decade we lost print (papers, printed books, book shops, libraries), the author then
conjectures that the impact of the Internet will make this revolution different from previous ones in that
most of the changes are irreversible. As a consequence he warns against storming ahead blindly and
suggests to conserve - while it is still possible - valuable components of what might soon be called the
antebellum age of education.Neue Medien und Hochschule: Nach der EuphorieWegner, Lutzhttps://kobra.uni-kassel.de:443/handle/123456789/20150402480012021-06-23T14:24:27Z2002-01-01T00:00:00ZVortragsfolien eines eingeladenen Vortrags auf der 58. Jahrestagung Bundesverband Deutscher Stiftungen am 16.05.2002 in Hamburg.
Das Thema der Jahrestagung war „Stiftungen in der Wissensgesellschaft“. Der Vortrag geht in kurzer und unterhaltsamer Form auf Vorstellungen und Hoffnungen der Wissensvermittlung mittels E-Learning ein. Stiftungen waren ganz wesentlich an der Gründung der Informatik in Kassel beteiligt, was im Vortrag auch gestreift wird.
2002-01-01T00:00:00ZWegner, LutzVortragsfolien eines eingeladenen Vortrags auf der 58. Jahrestagung Bundesverband Deutscher Stiftungen am 16.05.2002 in Hamburg.
Das Thema der Jahrestagung war „Stiftungen in der Wissensgesellschaft“. Der Vortrag geht in kurzer und unterhaltsamer Form auf Vorstellungen und Hoffnungen der Wissensvermittlung mittels E-Learning ein. Stiftungen waren ganz wesentlich an der Gründung der Informatik in Kassel beteiligt, was im Vortrag auch gestreift wird.