• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 4
  • 2
  • 1
  • 1
  • Tagged with
  • 11
  • 4
  • 3
  • 3
  • 3
  • 3
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

The 'Synopsis Chronike' and its place in the Byzantine chronicle tradition : its sources (Creation – 1081 CE)

Zafeiris, Konstantinos January 2007 (has links)
The subject of this thesis is the Synopsis Chronike (or Synopsis Sathas), a Byzantine chronicle of the thirteenth century that conveys the history of the world, starting from Adam and concluding with the recapture of Constantinople in 1261. The study focuses on the first part of the text (Adam – Nikephoros Botaneiates), and more specifically on the comprehensive presentation and analysis of the whole corpus of its sources, passage by passage, in order to reconstruct the background of the chronicle and to determine its place in the Byzantine chronicle tradition. Following the introductory first chapter, which sets out the aims of the thesis and establishes its methodology, chapter two offers an overview of the chronicle itself, and a first discussion of the main issues it presents: the key characteristics of its narrative structure, its manuscript tradition, and – mainly – the problem of its authorship, with special reference to the commonly supposed author, Theodore Skoutariotes, bishop of Kyzikos. Chapter three conveys a detailed presentation of the results of our research; following the discussion of the sources and influences of the proem, it attempts to place each passage of the Synopsis Chronike in the context of any related texts, which are then identified as 'main sources', 'other sources' and 'parallel passages', depending on their link to the Synopsis Chronike. Chapter four discusses individually each text that appears as a source of the Synopsis Chronike, and locates its place amongst the whole corpus of the sources. Furthermore, it examines the passages for which we were not able to identify a main source, and suggests possible sources that have not survived. Finally, the concluding chapter of the thesis summarises the earlier discussion, and attempts to combine the different pieces of information, and to provide an overall picture of the background of the Synopsis Chronike in order to establish – to the degree that it is possible – its position in the Byzantine chronicle tradition.
2

Filogenia, sistemática e evolução de Adenocalymma (Bignonieae, Bignoniaceae) / Phylogeny, systematics and evolution of Adenocalymma (Bignoniae, Bignoniaceae)

Fonseca, Luiz Henrique Martins 19 June 2017 (has links)
O clado \"Adenocalymma-Neojobertia\" representa um dos dois principais clados da tribo Bignonieae. Ele inclui lianas, arbustos e arvoretas distribuídas por todo o neotrópico, e possui como centro de diversidade a Amazônia brasileira e a Mata Atlântica. O clado é extremamente variável em termos da morfologia e distribuição geográfica, o que o torna um desafio taxonômico para a circunscrição de espécies e gêneros. A classificação atual de Bignonieae reconhece Adenocalymma de forma ampla (82 espécies), já Neojobertia (três espécies) está entre os menores gêneros. Aqui, nós utilizamos sequenciamento de última geração (plastomas completos ou quase completos) e sequenciamento Sanger (ndhF, rpl32-trnL, PepC) para inferir a filogenia do clado \"Adenocalymma-Neojobertia\" utilizando uma ampla amostragem de caracteres (>88,137 pb) e taxa (90% de todas as espécies). Nossos resultados indicam que Adenocalymma é parafilético como circunscrito atualmente, com Neojobertia e Pleonotoma albiflora incluídos. Padrões de evolução morfológica foram avaliados para todo o clado utilizando métodos comparativos. Sinal filogenético e evolução pontuada foram testados e estados ancestrais inferidos para 32 caracteres. Desses, 19 caracteres possuem sinal filogenético e quatro são sinapomorfias de clados internos. Pecíolos e peciólulos articulados emergiu como potencial sinapomorfia de todo o clado \"Adenocalymma-Neojobertia\". Entre os caracteres que não possuem sinal filogenético, quatro caracteres com importância ecológica chamam a atenção: (i) Habito, (ii) cor da corola, (iii) forma da corola e (iv) presença de tricomas cupulares na corola. Hábito emergiu como altamente homoplástico e está potencialmente relacionado com a ocupação de novos habitats. A morfologia floral também emergiu como altamente homoplástica e evoluindo de forma pontuada, sugerindo que a cor da corola, forma da corola e a presença de tricomas cupulares na corola podem ter sido os responsáveis pela diversificação em pelo menos parte do clado. A filogenia molecular e o estudo morfológico foram então utilizados como subsídio para propor uma sinopse atualizada de Adenocalymma. A nova circunscrição do gênero proposta aqui revisa os limites das espécies e incluí todas as espécies de Neojobertia e P. Albiflora agora todas em Adenocalymma. Ao todo, estão sendo propostas quatro novas combinações, três espécies novas apresentadas e 15 novos sinônimos, fazendo com que o Adenocalymma tenha agora 74 espécies reconhecidas. Para todas as espécies reconhecidas, nós apresentamos comentários taxonômicos, comparações com espécies próximas, informação sobre o habitat, distribuição e fenologia. Além disso, mapas de distribuição e gráficos de fenologia são apresentados para todas as espécies / The \"Adenocalymma-Neojobertia\" clade represents one of two main clades of tribe Bignonieae. It includes lianas, shrubs, and treelets that are distributed throughout the Neotropics, and centered in Amazonia and the Atlantic Forest of Brazil. This clade is extremely variable in terms of morphology and geography, which has led to a series of taxonomic challenges in the circumscription of species and genera. The most recent classification of tribe Bignonieae recognizes a broad Adenocalymma (82 species) and a small Neojobertia (three species). Here, we used NGS (complete and nearly-complete plastomes) and Sanger sequencing data (ndhF, rpl32-trnL, pepC) to infer a robust phylogeny of the \"Adenocalymma-Neojobertia\" clade based on a broad sampling of molecular characters (> 88,137 bp), and taxa (90% of the overall species diversity). Our findings indicate that Adenocalymma is paraphyletic as currently circumscribed, with Neojobertia and Pleonotoma albiflora nested herein. Patterns of morphological evolution were evaluated for the whole clade using comparative methods. Phylogenetic signal and punctuated evolution was tested and ancestral character states inferred for 32 selected characters. Of these, 19 characters have significant phylogenetic signal and four are synapomorphies of internal clades. Articulated petioles and petiolules emerged as a putative synapomorphy of the whole \"Adenocalymma-Neojobertia\" clade. Among the characters without phylogenetic signal, four morphological traits of ecological significance are particularly relevant: (i) plant habit, (ii) corolla color, (iii) corolla shape, and (iv) corolla cupular trichomes. Plant habit was shown to be highly homoplastic and is thought to be associated with the occupation of new environments. Flower morphology was also highly homoplastic and evolved in a punctuated manner, suggesting that corolla color, corolla shape, and corolla cupular trichomes may have been important drivers of evolution in at least portions of this clade. The molecular phylogeny and the morphological information were then used to subsidize an updated synopsis of Adenocalymma. The new circumscription of the genus proposed here revises species limits and includes all species of Neojobertia and P. albiflora within Adenocalymma. Overall, four new combinations, three new species, and 15 new synonomies are proposed, leading to 74 taxa within Adenocalymma. For each species recognized, we provided taxonomic comments, comparisons between closely related taxa, information on the habitat, distribution, and phenology. In addition, distribution maps, and phenology plots are also shown for all species
3

Constructing Accurate Synopses for Database Query Optimization and Re-optimization

Yu, Feng 01 May 2013 (has links) (PDF)
Fast and accurate estimations for complex queries are profoundly beneficial for large databases with heavy workloads. The most widely adopted query optimizers use synopses to tune up the databases in manners of optimization and re-optimization. From Chapter 1 to Chapter 3, we focus on the synopses for query optimization. We propose a statistical summary for a database, called CS2 (Correlated Sample Synopsis), to provide rapid and accurate result size estimations for all queries with joins and arbitrary selections. Unlike the state-of-the-art techniques, CS2 does not completely rely on simple random samples, but mainly consists of correlated sample tuples that retain join relationships with less storage. We introduce a statistical technique, called reverse sample, and design an innovative estimator, called reverse estimator, to fully utilize correlated sample tuples for query estimation. We prove both theoretically and empirically that the reverse estimator is unbiased and accurate using CS2. Extensive experiments on multiple datasets show that CS2 is fast to construct and derives more accurate estimations than existing methods with the same space budget. In Chapter 4, we focus on the synopses for query re-optimization on repetitive queries. Repetitive queries refer to those queries that are likely to be executed repeatedly in the future, such as those that are used to generate periodic reports, perform routine maintenance, summarize data for analysis, etc. They can constitute a large part of daily activities of a database system and deserve more optimization efforts. In this paper, we propose to collect information about how tuples are joined in a query, called the query or join trace, during execution of a query. We intend to use this join trace to compute the selectivities of joins in all join orders for the query. We use existing operators, as well as new operators, to gather such information. We show that the trace gathered from a query is sufficient to compute the exact selectivities of all plans of the query. To reduce the overheads of generating a trace, we propose a sampling scheme that generates only a sample of the trace. Experimental results have shown that with only a small sample of the trace, accurate estimates of join selectivities can be obtained. The sample trace makes re-estimation of join selectivities of a repetitive query efficient and accurate.
4

Spatio-temporal Maximum Average Correlation Height Templates In Action Recognition And Video Summarization

Rodriguez, Mikel 01 January 2010 (has links)
Action recognition represents one of the most difficult problems in computer vision given that it embodies the combination of several uncertain attributes, such as the subtle variability associated with individual human behavior and the challenges that come with viewpoint variations, scale changes and different temporal extents. Nevertheless, action recognition solutions are critical in a great number of domains, such video surveillance, assisted living environments, video search, interfaces, and virtual reality. In this dissertation, we investigate template-based action recognition algorithms that can incorporate the information contained in a set of training examples, and we explore how these algorithms perform in action recognition and video summarization. First, we introduce a template-based method for recognizing human actions called Action MACH. Our approach is based on a Maximum Average Correlation Height (MACH) filter. MACH is capable of capturing intra-class variability by synthesizing a single Action MACH filter for a given action class. We generalize the traditional MACH filter to video (3D spatiotemporal volume), and vector valued data. By analyzing the response of the filter in the frequency domain, we avoid the high computational cost commonly incurred in template-based approaches. Vector valued data is analyzed using the Clifford Fourier transform, a generalization of the Fourier transform intended for both scalar and vector-valued data. Next, we address three seldom explored challenges in template-based action recognition. The first is the recognition and localization of human actions in aerial videos obtained from unmanned aerial vehicles (UAVs), a new medium which presents unique challenges due to the small number of pixels per human, pose, and moving camera. The second issue we address is the incorporation of multiple positive and negative examples of a target action class when generating an action template. We address this issue by employing the Fukunaga-Koontz Transform as a means of generating a single quadratic template which, unlike traditional temporal templates (which rely on positive examples alone), effectively captures the variability associated with an action class by including both positive and negative examples in the template training process. Third, we explore the problem of generating video summaries that include specific actions of interest as opposed to all moving objects. In doing so, we explore the role of action templates in video summarization in an effort to provide a means of generating a compact video representation based on a set of activities of interest. We introduce an approach in which a user specifies the activities that interest him and the video is automatically condensed to a short clip which captures the most relevant events based on the user's preference. We follow the output summary video format of non-chronological video synopsis approaches, in which different events which occur at different times may be displayed concurrently, even though they never occur simultaneously in the original video. However, instead of assuming that all moving objects are interesting, priority is given to specific activities of interest which pertain to a user's query. This provides an efficient means of browsing through large collections of video for events of interest.
5

Systematics and evolution of Chresta Vell. ex. DC. (Vernonieae, Asteraceae) / Sistemática e evolução de Chresta Vell. ex DC. (Vernonieae, Asteraceae)

Siniscalchi, Carolina Moriani 24 April 2018 (has links)
Chresta belongs to tribe Vernonieae, subtribe Chrestinae, and presents eighteen species distributed in the Caatinga, Cerrado and Mata Atlântica domains. Its species display a fairly wide range of characters that led the species to be ascribed to several distinct genera, sometimes also classified into different groups inside the tribe. Attempts to define the position of the genus in relation to other Vernonieae subtribes and to understand the relationships within the genus have so far been unsuccessful. In this work, we present a novel phylogeny for Chresta, based on a complete set of sampled taxa from which hundreds of molecular markers were assessed, and for the first time, phylogenomics methods are applied to a Neotropical group of Asteraceae. We confirm the monophyly of Chresta and resolve infrageneric relationships with high support for all clades. We also successfully define the sister group to the genus, although the relations of this whole lineage with Lychnophorinae and Lepidaploinae are still doubtful, and. We use the obtained trees to reconstruct ancestral states of ten selected characters, which seem to have played an important role during the history of the genus, and propose a biogeographical scenario where the diversification of the group may have taken place. We also use evidence from microsatellite markers to study the population genetics of five species from the Caatinga that naturally present isolated populations restricted to narrow rupiculous habitats. These species present contrasting patterns, varying in their degree of genetic diversity and structuring, and this data enable us to discuss the relative impact of factors such as spatial distance, substrate preference, population size and dispersal ability on the genetic flow among the populations assessed. We also present an illustrated synopsis of the genus, with a new phylogenetic infrageneric classification, summarizing the accumulated knowledge about Chresta so far. We provide descriptions of four new species, a key for identification of 18 accepted species and three infrageneric taxa, synonyms, illustrations and distribution maps of the species, as well as their current conservation status / Chresta pertence à tribo Vernonieae e apresenta dezoito espécies distribuídas nos domínios da Caatinga, Cerrado e Mata Atlântica. A extensa variabilidade de caracteres observada no gênero fez com que suas espécies fossem atribuídas a diversos gêneros distintos e até mesmo classificadas em diferentes grupos dentro da tribo. Tentativas anteriores de definir a posição do gênero em relação a outras subtribos de Vernonieae não foram bem-sucedidas. Nesse trabalho, apresentamos uma nova filogenia para Chresta, baseada numa amostragem taxonômica completa da qual obtivemos centenas de marcadores moleculares e, pela primeira vez, métodos filogenômicos são aplicados a um grupo neotropical de Asteraceae. Essa análise confirma a monofilia de Chresta, resolve as relações infragenéricas com alto suporte, e define com sucesso o grupo-irmão do gênero, embora as relações dessa linhagem com Lychnophorinae e Lepidaploinae ainda sejam duvidosas. Usamos as árvores obtidas para reconstruir estados ancestrais de dez caracteres morfológicos selecionados face a sua provável relevância na história do grupo, e assim propomos um cenário biogeográfico no qual a diversificação do grupo pode ter ocorrido. Também usamos marcadores de microssatélites para estudar a genética de populações de cinco espécies da Caatinga que apresentam populações naturalmente isoladas, devido a sua restrição a afloramentos rochosos de área limitada. Essas espécies apresentam diferentes padrões, variando no grau de diversidade e estruturação genética. Esses dados permitem uma discussão do impacto relativo de fatores como distância espacial, preferência de substrato, tamanho populacional e capacidade de dispersão, sobre o fluxo gênico entre as populações analisadas. Também apresentamos uma sinopse ilustrada do gênero, com uma nova classificação infra-genérica filogenética, condensando o conhecimento acumulado até o momento sobre Chresta. A sinopse inclui descrição de quatro espécies novas, chave de identificação das 18 espécies aceitas e três táxons infragenéricos, sinonímia completa, ilustrações e mapas de distribuição das espécies, bem como seu status de conservação atual
6

Myxozoa Grass?, 1970 (Cnidaria: Myxosporea): Sinopse das esp?cies parasitando peixes nas Am?ricas e diagn?stico morfol?gico e molecular das esp?cies parasitando Characiformes, Leporinus friderici (Anostomidae) e Astyanax altiparanae (Characidae) oriundos do rio Mogi Gua??, S?o Paulo, Brasil / Myxozoa Grass?, 1970 (Cnidaria: Myxosporea): Synopsis of species parasiating fish in the Americas and morphological and molecular diagnosis of species parasiating Characiformes species, Leporinus friderici (Anostomidae) and Astyanax altiparanae (Characidae) from the Mogi Gua?? River, S?o Paulo, Brazil

VIDAL, Let?cia Gabriela Poblete 08 March 2017 (has links)
Submitted by Jorge Silva (jorgelmsilva@ufrrj.br) on 2017-08-22T19:39:56Z No. of bitstreams: 1 2017 - Let?cia Gabriela Poblete Vidal.pdf: 2525390 bytes, checksum: 162c0cfed2f6b4d8e94cb85c1c0254da (MD5) / Made available in DSpace on 2017-08-22T19:39:56Z (GMT). No. of bitstreams: 1 2017 - Let?cia Gabriela Poblete Vidal.pdf: 2525390 bytes, checksum: 162c0cfed2f6b4d8e94cb85c1c0254da (MD5) Previous issue date: 2017-03-08 / CNPq / The hope of this study was increased the knowledge of biodiversity of myxozoan fish parasites, unknown to some groups. In chapter 1, the goal was provide a synopsis of Myxozoa Grass?, 1970 species in the Americas based on records of the valid species of myxozoans (Myxozoa: Myxosporea) described in the Americas is provided based on a comprehensive survey of the literature since 1893, when the first myxozoan species was reported, until December 2015. The synopsis include the habitat of the host, site of the infection of the parasite, locality, size (?m or mm) and form of the plasmodia, spore measurements, provide specimens to parasitological collections, molecular data and explicit linkage of host. This synopsis was based on original descriptions. In chapter 2, the present work complements the original description of H. friderici Casal Matos and Azevedo, 2003 with new morphological and molecular data with Gill filaments on Leporinus friderici (Bloch, 1794) from the Mogi Gua?? River, state of S?o Paulo. Finaly, in chapter 3, specie of Henneguya was found in the kidneys of Astyanax altiparanae (Characiformes: Characidae) and were analyzed by morphological and molecular studies with analysis of the rDNA of the small subunid of the ribosome (18S). These data identify a new species of Myxozoa. / O presente trabalho teve como objetivo ampliar os conhecimentos sobre a biodiversidade de mixospor?deos parasitos de peixes, visto o escasso conhecimento para esse grupo. No cap?tulo 1 o objetivo foi fornecer uma sinopse de esp?cies de Myxozoa Grass?, 1970 nas Am?ricas com base em um levantamento bibliogr?fico desde 1893, quando a primeira esp?cie de myxospor?deo foi descrita, at? dezembro de 2015. A sinopse inclui uma lista parasito-hospedeiro com dados sobre o habitat do hospedeiro, s?tio de infec??o, localidade, tamanho e formato do cisto, medidas dos esporos e esp?cimes em cole??es e uma lista de parasitos-hospedeiros. Nessa sinopse s?o relatados somente as descri??es originais encontradas nas Am?ricas. No cap?tulo 2, ? inclu?da uma descri??o de H. friderici Casal, Matos e Azevedo, 2003 com novos dados morfol?gicos e moleculares com material proveniente de amostras de filamentos branquiais de Leporinus friderici (Bloch, 1794) do rio Mogi Gua??, estado de S?o Paulo. Finalmente, no cap?tulo 3, uma esp?cie de Henneguya encontrada nos rins de Astyanax altiparanae (Characiformes: Characidae) foi descrita e ilustrada com base na sua morfologia e na an?lise do rDNA da subunidade maior do ribossomo (28S). Estes dados identificam uma poss?vel esp?cie nova de Myxozoa.
7

Global Slope Change Synopses for Measurement Maps

Lehner, Wolfgang, Rosenthal, Frank, Fischer, Ulrike, Volk, Peter B. 01 November 2022 (has links)
Quality control using scalar quality measures is standard practice in manufacturing. However, there are also quality measures that are determined at a large number of positions on a product, since the spatial distribution is important. We denote such a mapping of local coordinates on the product to values of a measure as a measurement map. In this paper, we examine how measurement maps can be clustered according to a novel notion of similarity - mapscape similarity - that considers the overall course of the measure on the map. We present a class of synopses called global slope change that uses the profile of the measure along several lines from a reference point to different points on the borders to represent a measurement map. We conduct an evaluation of global slope change using a real-world data set from manufacturing and demonstrate its superiority over other synopses.
8

Hemmnisse in Entscheidungsprozessen - Entstehungsfaktoren, deren Messung und Bewertung: Systematisierung und Analyse theoretischer und empirischer Ergebnisse

Hüske, Anne-Karen 20 April 2010 (has links) (PDF)
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.
9

Bible and theology at work : the creative energy of Dorothy L. Sayers' 'The Man Born to be King'

Wehr, Kathryn Hannah January 2017 (has links)
This study centres on the biblical and theological work behind Dorothy L. Sayers' 12-part play-cycle, The Man Born to be King, aired on the BBC between 1941-42. Investigation begins by testing various unsubstantiated statements by biographers and scholars through a line-by-line analysis of the scripts, the results of which can be found in two large tables of information about how Sayers used each pericope in the Gospels (Appendix A) and a list of every known biblical reference within the play-cycle (Appendix C). Sayers' reported privileging of the Gospel of John gives way to evidence that Synoptic content outweighs Johannine by sheer bulk of material while preference is clearly given to stories that appear in both John and the Synoptics. Sayers' reported avoidance of the Authorized Version gives way to limited but consistent use of the AV for the narrator, for Old Testament quotations, and a special use of the Coverdale Psalms from the Book of Common Prayer. A study of Sayers' six secondary sources shows significant influence upon historic details and characterisation. By covering new ground through in-depth script and source analysis, these studies reveal, expand upon, and often contradict previous assumptions regarding Sayers' sources and working process. In the area of theological studies, investigation begins with Sayers' own claim that she had no original theology—that she merely re-stated the Church's teaching. First, Sayers' identity as an Anglo-Catholic is explored to understand what she means by ‘Catholic' and ‘the Church'. Having thus located Sayers within a particular tradition, Sayers' Christology (building upon her emphasis on the Creed) and Eschatology (building upon her chosen theme of the Kingship of Christ) within the plays are considered within their broader context of early twentieth-century Anglo-Catholic and wider theology. Sayers' theological originality is then proposed in relation to how she brought theology to life in dramatic form.
10

Maintaining bounded-size sample synopses of evolving datasets

Gemulla, Rainer, Lehner, Wolfgang, Haas, Peter J. 12 January 2023 (has links)
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.

Page generated in 0.037 seconds