Ett av de största öppna problemen i externa minnesdatastrukturer är det prioriterade köproblemet med MinskaKey-operationer. Om endast Infoga och ExtractMin-åtgärder behöver stödjas kan man utforma en jämförelsebaserad prioritetskö som utför O ((N /B) lg M /B N ) I/Os över en sekvens av N-operationer, där B är diskblockets storlek i antal ord och M är huvudminnets storlek i antal ord. Detta matchar den nedre gränsen för jämförelsebaserad sortering och är därför optimalt för jämförelsebaserade prioriterade köer. Men om vi också behöver stödja Av-creaseKeys, prestanda för den mest kända prioriteringskön är endast O ((N /B) lg 2 N ) I/Os. Den stora öppna frågan är om en försämring av prestanda verkligen är nödvändig. Vi besvarar den här frågan på ett normativt sätt genom att bevisa en lägre gräns för (N /B) lg lg N B) I/Os för behandling av en sekvens av N blandade Infoga, ExtraxtMin och MinskaKey operationer. Vår nedre gräns är bevisad i cellsonden modell och därmed innehar också för icke-jämförande-baserade prioriterade köer. • Teori för beräkning → Kommunikation komplexitet; Cell sond modeller och nedre gränser; KEYWORDS Prioriterade köer, externt minne, kommunikations komplexitet, lägre bundna ACM Referensformat:
Deras övre gräns matchar nästan en villkorslös nedre gräns av Enberg et al. REF (bevisades också i cellsondmodellen).
DecreaseKeys are expensive for external memory priority queues
{'venue': 'STOC 2017', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}