Abstrakt. Utdatakänsliga datastrukturer är ett resultat av förbehandling av n-poster och kan rapportera de poster som uppfyller en on-line fråga under O(t(n) + l) tid, där t(n) är kostnaden för att passera strukturen och l ≤ n är antalet rapporterade poster som uppfyller förfrågan. I det här dokumentet fokuserar vi på rankkänsliga datastrukturer, som dessutom ges en rankning av n-poster, så att bara de bästa k-klassade objekten ska rapporteras vid frågestunden, sorteras i rankordning, till en kostnad av O(t(n) + k) tid. Observera att k är en del av frågan som en parameter under användarens kontroll (i motsats till l som är frågeberoende). Vi utforskar problemet med att lägga till rank-känslighet till datastrukturer såsom suffix träd eller intervall träd, där l objekt som uppfyller frågeformuläret O(polylog(n)) intervall av på varandra följande poster som vi väljer de översta k bäst rankade. Låta s (n) vara antalet objekt (inklusive deras kopior) som lagras i de ursprungliga datastrukturerna, vi ökar utrymmet med en ytterligare term av O(s(n) lg  på n) minnesord i rymden, var och en av O(lg n) bitar, för eventuella positiva konstant  till < 1. Vi gör det möjligt att ändra rankningen i farten under datastrukturernas livstid, med rankningsvärden i 0... O(n). I detta fall blir frågetiden O(t(n)+k) plus O(lg n/lg lg n) per intervall; varje ändring i rankningen och varje insättning/deletion av ett objekt tar O(lg n) tid; den ytterligare termen i rymdtäthet ökar till O(s(n) lg n/lg lg n).
Ur teoretisk synvinkel inför Bialynicka-Birula och Grossi Ref begreppet rankkänsliga datastrukturer, och presenterar ett generiskt ramverk för att stödja rankning i avståndsrapporteringsdatastrukturer, såsom suffixträd och försök.
Rank-sensitive data structures
{'venue': 'In Proc. 12th International Symposium on String Processing and Information Retrieval (SPIRE), LNCS v. 3772', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}