Vi presenterar en ram för att utforma effektiva distribuerade datastrukturer för flerdimensionella data. Våra strukturer, som vi kallar skip-webs, utöka och förbättra tidigare randomiserade distribuerade datastrukturer, inklusive skipnets och skip grafer. Vårt ramverk gäller en allmän klass av dataförfrågan scenarier, som inkluderar linjära (endimensionella) data, såsom sorterade uppsättningar, samt flerdimensionella data, såsom d-dimensionella oktrees och digitala försök av teckensträngar definieras över ett fast alfabet. Vi visar hur man utför en fråga över en sådan uppsättning n objekt utspridda bland n värddatorer med O(log n/ log log n) meddelanden för endimensionella data, eller O(log n) meddelanden för fasta-dimensionella data, medan endast O(log n) utrymme per värddator. Vi visar också hur man gör sådana strukturer dynamiska så att det går att infoga och radera i O(log n) meddelanden för quadtrees, oktrees, och digitala försök, och O(log n / log log log n) meddelanden för endimensionella data. Slutligen visar vi hur man tillämpar en blockeringsstrategi för att hoppa över webbplatser för att ytterligare förbättra meddelande komplexiteten för endimensionella data när värdar kan lagra mer data.
Arge och Al. REF presenterar ett ramverk, som kallas skip- webs, som generaliserar datastrukturen för skip- diagram till högre dimensioner och uppnår O(log n/ log log n) frågetider, om än med M som O (log n) snarare än konstant storlek.
Skip-webs: efficient distributed data structures for multi-dimensional data sets
{'venue': "PODC '05", 'journal': None, 'mag_field_of_study': ['Computer Science']}