Bråkdel kaskad

Inom datavetenskap är fraktionerad kaskadteknik en teknik för att påskynda en sekvens av binära sökningar efter samma värde i en sekvens av relaterade datastrukturer. Den första binära sökningen i sekvensen tar en logaritmisk tid, vilket är standard för binära sökningar, men på varandra följande sökningar i sekvensen är snabbare. Den ursprungliga versionen av fraktionerad cascading, som introducerades i två artiklar av Chazelle och Guibas 1986 ( Chazelle & Guibas 1986a ; Chazelle & Guibas 1986b ), kombinerade idén om cascading, med ursprung i datastrukturer för intervallsökning av Lueker (1978) och Willard (1978) ) , med idén om fraktionerad provtagning, som har sitt ursprung i Chazelle (1983) . Senare författare introducerade mer komplexa former av fraktionerad kaskad som gör att datastrukturen kan bibehållas när data ändras genom en sekvens av diskreta infognings- och raderingshändelser.

Exempel

Som ett enkelt exempel på fraktionerad kaskad, överväg följande problem. Vi ges som indata en samling k- ordnade listor Li _med tal, så att den totala längden Σ| L _i | av alla listor är n och måste bearbeta dem så att vi kan utföra binära sökningar efter ett frågevärde q i var och en av k listorna. Till exempel, med k = 4 och n = 17,

L ₁ = 24, 64, 65, 80, 93

L ₂ = 23, 25, 26

L ₃ = 13, 44, 62, 66

L ₄ = 11, 35, 46, 79, 81

Den enklaste lösningen på detta sökproblem är bara att lagra varje lista separat. Om vi ​​gör det är utrymmeskravet O( n ), men tiden för att utföra en fråga är O( k log( n / k )), eftersom vi måste utföra en separat binär sökning i var och en av k listor. Det värsta fallet för att fråga den här strukturen inträffar när var och en av k- listorna har samma storlek n / k , så var och en av de k binära sökningarna som är involverade i en fråga tar tid O(log( n / k )).

En andra lösning tillåter snabbare förfrågningar på bekostnad av mer utrymme: vi kan slå samman alla k listorna till en enda stor lista L och associera med varje punkt x i L en lista över resultaten av att söka efter x i var och en av de mindre listorna L _i . Om vi ​​beskriver ett element i denna sammanslagna lista som x [ a , b , c , d ] där x är det numeriska värdet och a , b , c och d är positionerna (det första talet har position 0) för nästa element minst lika stort som x i var och en av de ursprungliga inmatningslistorna (eller positionen efter slutet av listan om inget sådant element finns), då skulle vi ha

L = 11 [0,0,0,0], 13 [0,0,0,1], 23 [0,0,1,1], 24 [0,1,1,1], 25 [1, 1,1,1], 26 [1,2,1,1],

35 [1,3,1,1], 44 [1,3,1,2], 46 [1,3,2,2] , 62 [1,3,2,3], 64 [1,3,3,3], 65 [2,3,3,3],

66 [3,3,3,3], 79 [3,3 ,4,3], 80 [3,3,4,4], 81 [4,3,4,4], 93 [4,3,4,5]

Denna sammanslagna lösning tillåter en fråga i tid O(log n + k ): sök helt enkelt efter q i L och rapportera sedan resultaten lagrade vid objektet x som hittats av denna sökning. Till exempel, om q = 50, sökning efter q i L hittar objektet 62[1,3,2,3], från vilket vi returnerar resultaten L ₁ [1] = 64, L ₂ [3] (ett flaggvärde vilket indikerar att q är förbi slutet av L ₂ ), L ₃ [2] = 62 och L ₄ [3] = 79. Denna lösning betalar dock ett högt straff i rymdkomplexitet: den använder mellanslag O( kn ) som varje av de n objekten i L måste lagra en lista med k sökresultat.

Fractional cascading gör att samma sökproblem kan lösas med tids- och rymdgränser som möter det bästa av två världar: frågetid O(log n + k ) och mellanrum O( n ). Den fraktionella kaskadlösningen är att lagra en ny sekvens av _listor Mi. Den slutliga listan i denna sekvens, _Mk , Lk _är lika med ; varje tidigare lista Mi _Li bildas genom att slå samman med varannan _. post från Mi _{+ 1} Med varje objekt x i den här sammanslagna listan lagrar vi två siffror: positionen som resulterar från sökning efter x i L _i och positionen som resulterar från sökning efter x i M _{i +1} . För data ovan skulle detta ge oss följande listor:

M ₁ = 24 [0, 1], 25 [1, 1], 35 [1, 3], 64 [1, 5], 65 [2, 5], 79 [3, 5], 80 [3, 6 ], 93 [4, 6]

M2 = 23 [0, 1], 25 [1, 1], 26 [2, 1], 35 [3, 1], 62 [3, 3], ₇₉ [ 3, 5]

M3 = _{13 [} 13[0, 1], 35[1, 1], 44[1, 2], 62[2, 3], 66[3, 3], 79[4, 3]

M₄ = 11[0, 0], 35[1, 0], 46[2, 0], 79[3, 0], 81[4, 0]

Antag att vi vill utföra en fråga i denna struktur, för q = 50. Vi gör först en standard binär sökning efter q i M ₁ och hittar värdet 64 [1,5]. "1:an" i 64[1,5] talar om för oss att sökningen efter q i L ₁ bör returnera L ₁ [1] = 64. "5:an" i 64 [1,5] talar om för oss att den ungefärliga platsen för q i M ₂ är position 5. Närmare bestämt skulle binär sökning efter q i M ₂ returnera antingen värdet 79[3,5] vid position 5, eller värdet 62[3,3] en plats tidigare. Genom att jämföra q med 62, och observera att den är mindre, bestämmer vi att det korrekta sökresultatet i M ₂ är 62[3,3]. Den första "3" i 62[3,3] säger oss att sökningen efter q i L ₂ bör returnera L ₂ [3], ett flaggvärde som betyder att q är förbi slutet av listan L ₂ . Den andra "3" i 62[3,3] säger oss att den ungefärliga platsen för q i M ₃ är position 3. Närmare bestämt skulle binär sökning efter q i M ₃ returnera antingen värdet 62[2,3] vid position 3, eller värdet 44[1,2] en plats tidigare. En jämförelse av q med det mindre värdet 44 visar att det korrekta sökresultatet i M ₃ är 62[2,3]. "2" i 62[2,3] talar om för oss att sökningen efter q i L ₃ ska returnera L ₃ [2] = 62, och "3" i 62[2,3] talar om för oss att resultatet av sökningen för q i M4 är antingen M4 [3] = 79[3,0] eller _M4 [ 2] = 46[2,0 _{] ;} att jämföra q med 46 visar att det korrekta resultatet är 79[3,0] och att resultatet av att söka efter q i L ₄ är L ₄ [3] = 79. Således har vi hittat q i var och en av våra fyra listor, av gör en binär sökning i den enda listan Mi följt av en enda jämförelse i var och en av de successiva listorna _.

Mer generellt, för alla datastrukturer av denna typ, utför vi en fråga genom att göra en binär sökning efter q i M ₁ och bestämma positionen för q i L _{1 utifrån det resulterande värdet} . Mi _Sedan , för varje i > 1, använder vi den kända positionen för q i för att hitta dess position i _{Mi 1} + . Värdet som är associerat med positionen för q i Mi _{q pekar eller} på en position i _{Mi som} +1 antingen är det korrekta resultatet av den binära sökningen efter i Mi +1 är ett enda steg bort från det korrekta resultatet, så stega från i till i + 1 kräver endast en enda jämförelse. Således är den totala tiden för en fråga O(log n + k ).

I vårt exempel har de bråkade kaskadlistorna totalt 25 element, mindre än dubbelt så mycket som den ursprungliga inmatningen. I allmänhet är storleken på _Mi i denna datastruktur högst

$|L_{i}|+{\frac {1}{2}}|L_{i+1}|+{\frac {1}{4}}|L_{i+2}| +\cdots +{\frac {1}{2^{j}}}|L_{i+j}|+\cdots ,$

vilket lätt kan bevisas genom induktion. Därför är den totala storleken på datastrukturen högst

$\sum |M_{i}|=\summa |L_{i}|\left(1+{\frac {1 }{2}}+{\frac {1}{4}}+\cdots \right)\leq 2n=O(n),$

som kan ses genom att omgruppera bidragen till den totala storleken som kommer från samma ingångslista L _i tillsammans med varandra.

Det allmänna problemet

I allmänhet börjar bråkdelar kaskad med en kataloggraf , en riktad graf där varje hörn är märkt med en ordnad lista. En fråga i denna datastruktur består av en sökväg i grafen och ett frågevärde q ; datastrukturen måste bestämma positionen för q i var och en av de ordnade listorna som är associerade med banans hörn. För det enkla exemplet ovan är kataloggrafen i sig en väg, med bara fyra noder. Det är möjligt för senare hörn i sökvägen att bestämmas dynamiskt som en del av en fråga, som svar på resultaten som hittats av sökningar i tidigare delar av sökvägen.

För att hantera frågor av denna typ, för en graf där varje vertex har högst d inkommande och högst d utgående kanter för någon konstant d , utökas listorna som är associerade med varje vertex med en bråkdel av objekten från varje utgående granne till vertex; bråkdelen måste väljas att vara mindre än 1/ d , så att den totala mängden med vilken alla listor utökas förblir linjär i inmatningsstorleken. Varje objekt i varje utökad lista lagrar med sig positionen för det objektet i den ej utökade listan som är lagrad vid samma vertex och i var och en av de utgående grannlistorna. I det enkla exemplet ovan, d = 1, och vi utökade varje lista med en 1/2 bråkdel av de närliggande objekten.

En fråga i denna datastruktur består av en standard binär sökning i den utökade listan som är associerad med det första hörnet på frågevägen, tillsammans med enklare sökningar vid varje på varandra följande hörn av sökvägen. Om en 1/ r bråkdel av objekt används för att utöka listorna från varje angränsande objekt, kan varje efterföljande frågeresultat hittas inom högst r steg från positionen lagrad vid frågeresultatet från föregående sökvägspunkt, och kan därför vara hittas i konstant tid utan att behöva utföra en fullständig binär sökning.

Dynamisk fraktionerad kaskadkoppling

I dynamisk fraktionerad kaskaddelning kan listan som lagras vid varje nod i katalogdiagrammet ändras dynamiskt genom en sekvens av uppdateringar där listobjekt infogas och raderas. Detta orsakar flera svårigheter för datastrukturen.

För det första, när ett objekt infogas eller tas bort vid en nod i katalogdiagrammet, måste det placeras i den utökade listan som är associerad med den noden och kan orsaka att ändringar sprids till andra noder i katalogdiagrammet. Istället för att lagra de utökade listorna i arrayer bör de lagras som binära sökträd, så att dessa ändringar kan hanteras effektivt samtidigt som de tillåter binära sökningar av de utökade listorna.

För det andra kan en infogning eller borttagning orsaka en ändring av delmängden av listan som är associerad med en nod som skickas vidare till angränsande noder i katalogdiagrammet. Det är inte längre möjligt, i den dynamiska inställningen, för denna delmängd att väljas som objekt på var d: te position i listan, för vissa d , eftersom denna delmängd skulle förändras för drastiskt efter varje uppdatering. Snarare tillåter en teknik som är nära relaterad till B-träd valet av en bråkdel av data som garanterat är mindre än 1/ d , med de valda objekten garanterade att vara fördelade med ett konstant antal positioner från varandra i den fullständiga listan, och sådant att en infogning eller radering i den utökade listan som är associerad med en nod gör att ändringar sprids till andra noder för en bråkdel av operationerna som är mindre än 1/ d . På detta sätt uppfyller fördelningen av data mellan noderna de egenskaper som behövs för att frågealgoritmen ska vara snabb, samtidigt som det garanterar att det genomsnittliga antalet binära sökträdsoperationer per datainsättning eller radering är konstant.

För det tredje, och mest kritiskt, upprätthåller den statiska fraktionerade kaskaddatastrukturen, för varje element x i den utökade listan vid varje nod i katalogdiagrammet, indexet för resultatet som skulle erhållas när man söker efter x bland indataposterna från den noden och bland de utökade listorna som lagras vid angränsande noder. Denna information skulle dock vara för dyr att underhålla i den dynamiska miljön. Att infoga eller ta bort ett enstaka värde x kan göra att indexen som lagras med ett obegränsat antal andra värden ändras. Istället upprätthåller dynamiska versioner av fraktionerad kaskad flera datastrukturer för varje nod:

• En mappning av objekten i nodens utökade lista till små heltal, så att ordningen av positionerna i den utökade listan är likvärdig med jämförelseordningen av heltal, och en omvänd mappning från dessa heltal tillbaka till listobjekten. En teknik av Dietz (1982) gör att denna numrering kan upprätthållas effektivt.
• En heltalssökningsdatastruktur såsom ett van Emde Boas-träd för numren som är associerade med nodens inmatningslista. Med denna struktur, och mappningen från objekt till heltal, kan man effektivt hitta för varje element x i den utökade listan, det objekt som skulle hittas vid sökning efter x i inmatningslistan.
• För varje angränsande nod i katalogdiagrammet, en liknande heltalssökningsdatastruktur för siffrorna som är associerade med delmängden av data som sprids från den angränsande noden. Med denna struktur, och mappningen från objekt till heltal, kan man effektivt hitta för varje element x i den utökade listan, en position inom ett konstant antal steg av platsen för x i den utökade listan som är associerad med den angränsande noden.

Dessa datastrukturer tillåter att dynamisk fraktionerad kaskadkoppling utförs vid en tidpunkt för O(log n ) per infogning eller radering, och en sekvens av k binära sökningar som följer en väg med längden k i kataloggrafen för att utföras i tiden O(log n + k log log n ).

Ansökningar

De konvexa skikten i en punktuppsättning, en del av en effektiv datastruktur med bråkdelar kaskad för halvplansrapportering.

Typiska tillämpningar av fraktionerad cascading involverar datastrukturer för räckviddsökning i beräkningsgeometri . Tänk till exempel på problemet med halvplansrapportering : det vill säga skära en fast uppsättning av n punkter med ett frågehalvplan och lista alla punkter i skärningspunkten. Problemet är att strukturera punkterna på ett sådant sätt att en fråga av denna typ kan besvaras effektivt när det gäller skärningsstorleken h . En struktur som kan användas för detta ändamål är de konvexa skikten i ingångspunktsuppsättningen, en familj av kapslade konvexa polygoner som består av punktuppsättningens konvexa skrov och de återstående punkternas rekursivt uppbyggda konvexa skikt. Inom ett enda lager kan punkterna inuti frågehalvplanet hittas genom att utföra en binär sökning efter halvplansgränslinjens lutning bland den sorterade sekvensen av konvexa polygonkantlutningar, vilket leder till polygonvertexet som är inuti frågehalvan -plan och längst bort från dess gräns, och sedan sekventiellt söka längs polygonkanterna för att hitta alla andra hörn inuti frågans halvplan. Hela halvplansavståndsrapporteringsproblemet kan lösas genom att upprepa denna sökprocedur med början från det yttersta lagret och fortsätta inåt tills man når ett lager som är skilt från frågehalvrummet. Fraktionerad kaskadbildning påskyndar de successiva binära sökningarna bland sekvenserna av polygonkantlutningar i varje lager, vilket leder till en datastruktur för detta problem med mellanslag O(n) och frågetid O(log n + h ). Datastrukturen kan konstrueras i tiden O( n logn ) av en algoritm av Chazelle (1985) . Som i vårt exempel involverar denna applikation binära sökningar i en linjär sekvens av listor (den kapslade sekvensen av de konvexa lagren), så kataloggrafen är bara en sökväg.

En annan tillämpning av fraktionerad kaskadring i geometriska datastrukturer gäller punktplacering i en monoton underavdelning, det vill säga en uppdelning av planet i polygoner så att vilken vertikal linje som helst skär vilken polygon som helst i högst två punkter. Som Edelsbrunner, Guibas & Stolfi (1986) visade kan detta problem lösas genom att hitta en sekvens av polygonala banor som sträcker sig från vänster till höger över underavdelningen, och binärt söka efter den lägsta av dessa banor som är ovanför frågepunkten. Att testa om frågepunkten är över eller under en av banorna kan i sig själv lösas som ett binärt sökproblem, genom att söka efter x-koordinaten för punkterna bland x-koordinaterna för banans hörn för att bestämma vilken vägkant som kan vara över eller under frågepunkt. Således kan varje punktlokaliseringsfråga lösas som ett yttre lager av binär sökning bland vägarna, vars varje steg själv utför en binär sökning bland x-koordinater av hörn. Fractional cascading kan användas för att snabba upp tiden för de inre binära sökningarna, vilket minskar den totala tiden per fråga till O(log n ) med hjälp av en datastruktur med mellanslag O( n ). I denna applikation är kataloggrafen ett träd som representerar de möjliga söksekvenserna för den yttre binära sökningen.

Utöver beräkningsgeometri tillämpar Lakshman & Stiliadis (1998) och Buddhikot, Suri & Waldvogel (1999) fraktionerad kaskaddelning i designen av datastrukturer för snabb paketfiltrering i internetroutrar . Gao et al. (2004) använder fraktionerad cascading som modell för datadistribution och hämtning i sensornätverk .

•    Atallah, Mikhail J. ; Blanton, Marina; Goodrich, Michael T. ; Polu, Stanislas (2007), "Discrepans-sensitive dynamic fraktional cascading, dominated maxima searching, and 2-d nearest neighbours in any Minkowski metric" ( PDF) , Algoritms and Data Structures, 10th International Workshop, WADS 2007 in Computer, Lecture Notes Science, vol. 4619, Springer-Verlag, s. 114–126, arXiv : 0904.4670 , doi : 10.1007/978-3-540-73951-7_11 , ISBN 978-3-540-73928-7 , S 540-73928-7 .
• Buddhikot, Milind M.; Suri, Subhash ; Waldvogel, Marcel (1999), "Space Decomposition Techniques for Fast Layer-4 Switching" (PDF) , Proceedings of the IFIP TC6 WG6.1 & WG6.4 / IEEE ComSoc TC on Gigabit Networking Sjätte internationella workshopen om protokoll för höghastighetsnätverk VI , s. 25–42, arkiverad från originalet (PDF) 2004-10-20 .
• Chazelle, Bernard (1983), "Filtreringssökning: A new approach to query-answering" (PDF) , Proc. 24 IEEE FOCS .
•   Chazelle, Bernard (1985), "On the convex layers of a point set" (PDF) , IEEE Transactions on Information Theory , 31 (4): 509–517, CiteSeerX 10.1.1.113.8709 , doi : 10.1109/561015970. .
•   Chazelle, Bernard ; Guibas, Leonidas J. (1986), "Fractional cascading: I. A data structuring technique" (PDF) , Algorithmica , 1 (1–4): 133–162, doi : 10.1007/BF01840440 , S2CID 424500 .
•   Chazelle, Bernard ; Guibas, Leonidas J. (1986), "Fractional cascading: II. Applications" (PDF) , Algorithmica , 1 (1-4): 163-191, doi : 10.1007/BF01840441 , S2CID 11232235 .
•   Chazelle, Bernard ; Liu, Ding (2004), "Lower bounds for intersection searching and fractional cascading in higher dimension" (PDF) , Journal of Computer and System Sciences , 68 (2): 269–284, CiteSeerX 10.1.1.298.7772 , doi : 10.10 . /j.jcss.2003.07.003 .
•    Dietz, F. Paul (1982), "Att upprätthålla ordning i en länkad lista", 14:e ACM Symp. Theory of Computing , s. 122–127, doi : 10.1145/800070.802184 , ISBN 978-0-89791-070-5 , S2CID 24008786 .
• Edelsbrunner, H. ; Guibas, LJ; Stolfi, J. (1986), "Optimal point location in a monotone subdivision" (PDF) , SIAM Journal on Computing , 15 (1): 317–340, doi : 10.1137/0215023 .
•    Gao, J.; Guibas, LJ; Hershberger, J.; Zhang, L. (2004), "Fraktionellt kaskadad information i ett sensornätverk" (PDF) , Proc. av det 3:e internationella symposiet om informationsbehandling i sensornätverk (IPSN'04) , s. 311–319, doi : 10.1145/984622.984668 , ISBN 978-1-58113-846-7 , S2328 70 .
• JaJa, Joseph F.; Shi, Qingmin (2003), Snabb fraktionell kaskadbildning och dess tillämpningar (PDF) , Univ. från Maryland, Tech. Rapport UMIACS-TR-2003-71 .
•     Lakshman, TV; Stiliadis, D. (1998), "High-speed policy-based packet forwarding using efficient multi-dimensional range matching", Proceedings of the ACM SIGCOMM '98 Conference on Applications, Technologies, Architectures and Protocols for Computer Communication , s. 203 –214, CiteSeerX 10.1.1.39.697 , doi : 10.1145/285237.285283 , ISBN 978-1-58113-003-4 , S2CID 15363397 .
•   Lueker, George S. (1978), "A data structure for ortogonal range queries", Proc. 19:e Symp. Foundations of Computer Science , IEEE, s. 28–34, doi : 10.1109/SFCS.1978.1 , S2CID 14970942 .
•   Mehlhorn, Kurt ; Näher, Stefan (1990), "Dynamic fraktional cascading", Algorithmica , 5 (1): 215–241, doi : 10.1007/BF01840386 , S2CID 7721690 .
• Sen, SD (1995), "Fractional cascading revisited", Journal of Algorithms , 19 (2): 161–172, doi : 10.1006/jagm.1995.1032 .
• Willard, DE (1978), Predicate-oriented databas search algorithms , Ph.D. avhandling, Harvard University .
• Japp, Chee; Zhu, Yunyue (2001), "Yet another look at fractional cascading: B-graphs with application to point location", Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01) , s. 173–176 .