Vi studerar frågan om "hur robusta är de kända lägre gränserna för märkningssystem när man ökar antalet tillfrågade etiketter". Låt f vara en funktion på par av hörn. En f - märkning schema för en familj av grafer F etiketter hörnen av alla grafer i F så att för varje graf G - F och varannan hörn u, v - märkning G, värdet f (u, v) kan härledas genom att bara inspektera etiketter av u och v. Detta papper introducerar en naturlig generalisering: begreppet f - märkning system med frågor, där värdet f (u, v) kan härledas genom att inspektera inte bara etiketter av u och v men möjligen etiketter av vissa ytterligare hörn. Vi visar att inspektionen av etiketten på en enda ytterligare vertex (en fråga) gör det möjligt för oss att minska etikettstorleken på många märkningssystem avsevärt. I synnerhet visar vi att för att stödja avståndsfunktionen på n-node träd samt flödesfunktionen på n-node allmänna grafer, O(log n + log W )-bit etiketter är tillräckliga och nödvändiga, där W är den maximala (integral) kapaciteten i en kant. Vi noterar att det visades att alla märkningsscheman (utan frågor) som stöder antingen flödesfunktionen på allmänna grafer eller avståndsfunktionen på träd, måste ha etikettstorlek (log 2 n + log n log W ). Med hjälp av en enda fråga, visar vi också en routing märkningsschema i fast port modell med hjälp av O(log n)-bitarsetiketter, medan den lägre gränsen på etikettstorleken för någon sådan routing märkningsschema (utan frågor) är  och (log 2 n/log log n). Vi noterar att alla våra märkningssystem med frågor har asymptotiskt optimal etikettstorlek. Vi visar sedan flera förlängningar. I synnerhet visar vi att våra märkningssystem med frågor om träd kan utvidgas till det dynamiska scenariot genom vissa anpassningar av kända modellöversättningsmetoder. För det andra visar vi att studiet av frågemodellen kan hjälpa till med den traditionella modellen också. Det vill säga, med hjälp av idéer från vår routing märkning system med en fråga, visar vi hur man konstruerar en 3- approximation routing system utan frågor i fast-port modellen med  på (log n)-bitars etiketter. Slutligen vänder vi oss till en icke-distribuerad miljö och först översätta kända resultat om att hitta NCA till stöd för distansfrågor. Vi använder sedan ovanstående för att visa att man kan förbehandla en allmän vägd graf med nästan linjärt utrymme så att flödesfrågor kan besvaras i nästan konstant tid.
I REF studeras en modell (1-query) där en, förutom etiketten på indatanoder, kan få tillgång till etiketten på ytterligare en nod.
Labeling Schemes with Queries
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}