Perhaps the most flexible synopsis of a database is a uniform random sample of the data; such samples are widely used to speed up processing of analytic queries and data-mining tasks, enhance query optimization, and facilitate information integration. The ability to bound the maximum size of a sample can be very convenient from a system-design point of view, because the task of memory management is simplified, especially when many samples are maintained simultaneously. In this paper, we study methods for incrementally maintaining a bounded-size uniform random sample of the items in a dataset in the presence of an arbitrary sequence of insertions and deletions. For “stable” datasets whose size remains roughly constant over time, we provide a novel sampling scheme, called “random pairing” (RP), that maintains a bounded-size uniform sample by using newly inserted data items to compensate for previous deletions. The RP algorithm is the first extension of the 45-year-old reservoir sampling algorithm to handle deletions; RP reduces to the “passive” algorithm of Babcock et al. when the insertions and deletions correspond to a moving window over a data stream. Experiments show that, when dataset-size fluctuations over time are not too extreme, RP is the algorithm of choice with respect to speed and sample-size stability. For “growing” datasets, we consider algorithms for periodically resizing a bounded-size random sample upwards. We prove that any such algorithm cannot avoid accessing the base data, and provide a novel resizing algorithm that minimizes the time needed to increase the sample size. We also show how to merge uniform samples from disjoint datasets to obtain a uniform sample of the union of the datasets; the merged sample can be incrementally maintained. Our new RPMerge algorithm extends the HRMerge algorithm of Brown and Haas to effectively deal with deletions, thereby facilitating efficient parallel sampling.

Die vorliegende Ausgabe untersucht theoretische und empirische Ergebnisse zu Hemmnissen in Entscheidungsprozessen in Organisationen. Zu Beginn steht die Aufarbeitung der Theorie zum Hemmnisbegriff anhand folgender Forschungsfragen: Wie wird der Hemmnisbegriff definiert? Welche Wörter werden synonym verwendet? Wie entstehen Hemmnisse? Was gibt es für Methoden zur Messung und Bewertung von Hemmnissen? Ausgehend von diesen theoretischen Betrachtungen erfolgt eine Zusammenschau von 104 empirischen Studien zu Hemmnissen in Entscheidungsprozessen unter der Fragestellung: Was gibt es für empirische Studien zu diesem Thema? Wie unterschieden sich diese bzw. wie lassen sie sich charakterisieren und systematisieren? Dabei werden der Hintergrund der Studien (Land, Branche, Ent-scheidungsprozess, Befragte), ihre Methodik, die Methodik der Hemmnisanalyse, der Hemmnisbegriff und die Entstehungsfaktoren betrachtet. Zur Systematisierung der Studien werden Gruppierungsansätze nach einzelnen Merkmalen (Veröffentlichungsjahrzehnt, Kontinent, Entwicklungsniveau des untersuchten Landes, Branche, Entscheidungsprozess, Studienmethodik) und eine Clusteranalyse über 49 Variablen durchgeführt. Die Gruppierungsansätze werden mittels ihrer Aussagekraft zum Entscheidungsprozess, zur Hemmnismethodik und zu den Entstehungsfaktoren von Hemmnissen beurteilt. Die Aufschlüsselung nach Entscheidungsprozessen erscheint als empfehlenswert. Die Ergebnisse der Clusteranalyse lassen darauf schließen, dass sich die Studien relativ ähnlich sind. Zusammenfassend gibt es keine allgemeingültige First-Best-Lösung zur Systematisierung der Studien. Die Gruppierungsansätze bewegen sich im Spannungsdreieck, möglichst von der Größe her vergleichbare aber vom Inhalt her unterscheidbare Studiengruppen zu bilden und dabei alle Studien in die Gruppierung einzubeziehen. Der zu wählende Gruppierungsansatz ist davon abhängig, welche Forschungsfragen im Vordergrund der jeweiligen Untersuchung stehen.