Abstrakt. Vi undersöker diameterproblemet i streaming- och skjutfönstermodellerna. Vi visar att för en ström av n-punkter eller ett skjutfönster av storlek n, kräver varje exakt algoritm för diameter (n) bitar av utrymme. Vi presenterar en enkel ε-approximation 4-algoritm för beräkning av diametern i den strömmande modellen. Vårt huvudresultat är en ε-approximationsalgoritm som bibehåller diametern i två dimensioner i skjutfönstermodellen med hjälp av O((1/ε 3/2 ) log 3 n(log R + log log n + log(1/ε))) bitar av utrymme, där R är den maximala, över alla fönster, förhållandet mellan diametern och minsta icke-noll avstånd mellan två punkter i fönstret. Nyckelord. Massiva dataströmmar, glidfönster, Diameter. Under de senaste åren har massiva datamängder blivit allt viktigare i ett brett spektrum av tillämpningar. I många av dessa applikationer kan inmatningen ses som en dataström [3], [19], [9] som algoritmen läser i ett pass. Algoritmen bör ta lite tid att bearbeta varje dataelement och bör använda lite utrymme jämfört med inmatningsstorleken. I vissa scenarier kan inmatningsströmmen vara oändlig, och programmet kan bara bry sig om nya data. I detta fall kan skjutfönstermodellen [8] vara lämpligare. Som i den strömmande modellen bör en skjutfönsteralgoritm gå igenom inmatningsströmmen en gång, och det finns inte tillräckligt med lagringsutrymme för alla data, även för data i ett fönster. I detta dokument undersöker vi det tvådimensionella diameterproblemet i dessa två modeller. Med tanke på en uppsättning punkter P, är diametern den maximala, över alla par x, y i P, av avståndet mellan x och y. Det finns effektiva algoritmer för att beräkna den exakta diametern [6], [25] [5]. Dock har lite gjorts för beräknings-geometri problem i streaming eller skjutfönster modeller. I synnerhet är föga känt om diameter problemet i dessa två modeller.
Feigenbaum, Kannan och Zhang REF gav en rymdalgoritm för beräkning av diametern på punkter i två dimensioner i streamingmodellen och en O(
Computing Diameter in the Streaming and Sliding-Window Models
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Mathematics', 'Computer Science']}