Vi designar nya, asymptotiskt effektivare datastrukturer och algoritmer för program vars dataåtkomstmönster uppvisar en viss grad av förutsägbarhet. I detta syfte föreslår vi två nya tekniker, en pekarbaserad teknik och en lokalbaserad teknik. Vi visar att dessa två tekniker är kraftfulla byggstenar för att göra datastrukturer och algoritmer omedvetna. Speciellt tillämpar vi dessa tekniker på ett brett spektrum av allmänt använda datastrukturer, inklusive kartor, uppsättningar, prioritetsqueues, stackar, deques; och algoritmer, inklusive en minnesalgoritm, max-flöde på grafer med låg dubblering dimension, och kortaste sökväg avstånd frågor på viktade planar grafer. Våra omedvetna motsvarigheter till ovanstående överträffar det mest kända ORAM-systemet både asymptotiskt och i praktiken.
Wang m.fl. I REF föreslogs genomförandet av kartor, uppsättningar, prioriterade köer, staplar och deques baserade på ORAM-teknik som modifierats för specifika dataåtkomstmönster.
Oblivious Data Structures
{'venue': "CCS '14", 'journal': None, 'mag_field_of_study': ['Computer Science']}