Abstrakt. När man försöker bearbeta en dataström i små utrymmen, hur viktig är den ordning i vilken uppgifterna anländer? Finns det problem som är omöjliga att lösa när beställningen är som värst, men som kan lösas (med hög sannolikhet) när ordern väljs jämnt på måfå? Om vi betraktar strömmen som en order från en motståndare, vad händer då om vi begränsar motståndarens makt? Vi studerar dessa frågor i samband med kvantiluppskattning, ett av de mest väl studerade problemen i data-strömsmodellen. Våra resultat inkluderar en O(polylog n)-rymd, O(log log n)-pass algoritm för exakt val i en slumpmässigt ordnad ström av n element. Detta löser en öppen fråga om Munro och Paterson. Räkna. Sci., 23 (1980), s. I avsnitt 1C001.b ska led a ersättas med följande: Vi demonstrerar sedan en exponentiell separation mellan slumpmässiga och kontradiktoriska modeller: med hjälp av O(polylog n) utrymme, exakt val kräver  och (log n/ log log n) passerar i adversarial- order modell. Denna lägre gräns, i motsats till tidigare resultat, gäller helt allmänna randomiserade algoritmer och etableras via en ny gräns på kommunikations komplexiteten i en naturlig pekar-chasing stil problem. Vi bevisar också de första helt allmänna lägre gränserna i slumpmässiga-order-modellen: att hitta ett element med rang n/2 ± n δ i en-pass slumpmässiga-order-modellen med sannolikhet minst 9/10 kräver  till ( n 1−3δ / log n) utrymme. Nyckelord. Kommunikationskomplexitet, stokastiskt genererade strömmar, strömberäkning AMS ämnesklassificeringar. 68Q05, 68Q17, 68Q25, 68W20, 68W25 1. Inledning. En av de viktigaste teoretiska motiven för att studera dataströmsmodellen är att förstå den roll som spelas av den ordning i vilken ett problem avslöjas. Medan en algoritm i RAM-modellen kan bearbeta indata i godtycklig ordning, är den viktigaste begränsningen för data-ström-modellen att algoritmen måste behandla (i små utrymmen) indata i den ordning den anländer. Parameterisera antalet passer som en algoritm kan ha över data etablerar ett spektrum mellan RAM-modellen och en-pass data-stream-modellen. Hur varierar modellens beräkningskraft längs detta spektrum? I vilken utsträckning spelar det någon roll hur strömmen beställs? Dessa frågor går tillbaka till ett av de tidigaste dokumenten om dataströmsmodellen där Munro och Paterson övervägde problemen med sortering och urval i begränsat utrymme [21]. De visade att Õ(n 1/p ) utrymme var tillräckligt för att hitta den exakta medianen för en sekvens av n nummer ges p passerar över data. Men om uppgifterna slumpvis beställdes, Õ(n 1/(2p) ) utrymme räckte. Baserat på detta resultat och andra observationer, verkade det troligt att någon p-pass algoritm i random-order-modellen kunde simuleras av en 2p-pass-algoritm i den kontradiktoriska-order-modellen. Detta utgjordes av ett öppet problem av Kannan [17], och ytterligare stöd för denna gissning kom via arbete initierat av Feigenbaum et al. [6] som beaktade förhållandet
Guha och McGregor REF förespråkar användning av slumpmässiga datamodeller i motsats till kontradiktoriska modeller.
STREAM ORDER AND ORDER STATISTICS: QUANTILE ESTIMATION IN RANDOM-ORDER STREAMS ∗
{'venue': 'SIAM J. Comput.', 'journal': 'SIAM J. Comput.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}