% Sample file for the use of compsoft style file.
%
\documentclass[T]{compsoft}

% Preamble
%
% $B!V%3%s%T%e!<%?%=%U%H%&%'%"!W;o$K7G:\$5$l$kO@J8$N>l9g!$<!$G(B
% $B4,?t!$9f?t!$3+;O%Z!<%8!$=*N;%Z!<%8$r;XDj$9$k!%(B
%\volNoPp{16}{5}{78}{83}

% $B%o!<%/%7%g%C%W$K$h$k?dA&O@J8$N>l9g!$%o!<%/%7%g%C%WL>$r;XDj$9$k!%(B
% \suisen{$B%o!<%/%7%g%C%WL>(B}

% $BFC=8$N>l9g!$FC=8$N%?%$%H%k$rM?$($k!%(B
% \tokushu{$BFC=8$N%?%$%H%k(B}

% $BBg2qO@J8$N>l9g!$(B\taikai $B$G3+:EG/$r;XDj$9$k!%$3$3$G;XDj$7$?G/$+$i(B
% $BBg2q$N2s?t$O7W;;$5$l$k!%(B
\taikai{2010}

% $B$3$3$K!$;HMQ$9$k%Q%C%1!<%8$rNs5s$9$k!%(B
\usepackage[dvips]{graphics}

% $B%f!<%6$,Dj5A$7$?%^%/%m$J$I$O$3$3$KCV$/!%$?$@$73X2q;o$N%9%?%$%k$N(B
% $B:FDj5A$O86B'$H$7$FHr$1$k$3$H!%(B

\begin{document}

% $BO@J8$N%?%$%H%k(B
\title{Meta Engine $B$rMQ$$$?(B Federated Linda $B$N<B83(B}

% $BCx<T(B
% $BOBJ8O@J8$N>l9g!$@+$HL>$N4V$K$OH>3Q%9%Z!<%9$rF~$l!$(B
% $BJ#?t$NCx<T$N4V$OA43Q%9%Z!<%9$G6h@Z$k(B
%
\author{$B@VNf(B $B0l<y!!2OLn(B $B??<#(B
%
% $B$3$3$K%?%$%H%k1QLu(B ($B1QJ8$N>l9g$OOBLu(B) $B$r=q$/!%(B
%
\ejtitle{Experiment of Federated Linda with Meta Engine}
%
% $B$3$3$KCx<T1QJ8I=5-(B ($B1QJ8$N>l9g$OOBJ8I=5-(B) $B$*$h$S(B
% $B=jB0(B ($BOBJ8$*$h$S1QJ8(B) $B$r=q$/!%(B
% $BJ#?tCx<T$N=jB0$O$^$H$a$F$h$$!%(B
%
\shozoku{Kazuki Akamine}{$BN05eBg3XM}9)3X8&5f2J>pJs9)3X@l96(B}%
{Dept.\ of Information and Computer Science, Waseda University}
%
% $B=PE5>pJs$O(B \shutten $B$H$9$l$P=PNO$5$l$k!%(B
%\shutten
%
% $B<uIUG/7nF|!$5-;v%+%F%4%j$J$I$O<+F0E*$K@8@.$5$l$k!%(B
%\uketsuke{1999}{8}{3}
%
% $B$=$NB>!$5SCm$KF~$l$k$b$N$,$"$l$P!$(B\note $B$K5-=R$9$k!%(B
%\note{$B5SCm$KF~$l$kFbMF(B}
}

%
% $BOBJ8%"%V%9%H%i%/%H(B
\Jabstract{%
$BK\8&5f<<$G$O!"J,;67?%?%W%k%9%Z!<%9$N<B83MQ$K(B Federated Linda $B$r(B
$BDs0F$7!"<BAu$7$F$-$?!#=>Mh$N(B Federated Linda $B$O3F%N!<%I$N4V$KG[CV$5$l$?(B
Protocol Engine $B$K$h$C$F8_$$$KO"7H$9$k$,!"%W%m%;%9$,0[$J$k$?$aL5BL$JDL?.(B
$B$,B8:_$7$?!#$=$3$G(B Federated Linda $B$HF10l%W%m%;%9>e$GF0:n$9$k(B Meta Engine
$B$rDs0F$7!"<BAu$7$F$-$?!#K\8&5f$G$O!"%/%i%9%?!<>e$G(B Meta Engine $B$rMQ$$$?<B(B
$B83MQ%H%]%m%8!<$r9=C[$7!"(BMetaEngine $B$N;HMQNc$r<($9!#(B
}
%
% $B1QJ8%"%V%9%H%i%/%H!JBg2qO@J8$K$OI,MW$J$7(B)
% \Eabstract{}
%
\maketitle

\section{$B$O$8$a$K(B}

twitter $B$r$O$8$a$H$9$kBg?M?t;22C7?(B Web $B%5!<%S%9$d(B MMORPG $B$J$I$NBg?M?t;2(B
$B2C7?%j%"%k%?%$%`%M%C%H%o!<%/%2!<%`$,!"$3$l$^$G0J>e$KBg5,LO$J$b$N$H$J$C$F(B
$B$$$/$?$a$K$O!"J,;6%M%C%H%o!<%/%W%m%0%i%`$NH/E8$,IT2D7g$G$"$k!#(B

$B$7$+$7!"J,;6%M%C%H%o!<%/%W%m%0%i%`$K$*$1$k%9%1!<%i%S%j%F%#!<$N3NJ]$O(B
$BFq$7$$!#$3$3$G8@$&%9%1!<%i%S%j%F%#!<$H$O!"%5!<%S%9$NBg$-$5$,A}$($?$H$-$K(B
$B%5!<%P!<$J$I$N%j%=!<%9$rDI2C$9$k$3$H$N$_$G%5!<%S%9$N<A$r%j%K%"$K0];}$G$-(B
$B$k$3$H$r;X$9!#(B

$B$9$J$o$AM}A[E*$J%b%G%k$O!"J#?t$N%5!<%P!<$r@\B3$9$k$3$H$GIi2Y$rJ,;6$7!"%/(B
$B%i%$%"%s%H$N?t$K=>$C$F%5!<%S%9$,<+A3$K%9%1!<%k$9$k$b$N$G$J$/$F$O$J$i$J$$!#(B

$BNc$($P!"8=:_$NJ,;65;=Q$r=u$1$F$$$k(B Key-Value Store $B$J$I$G$O!"$9$Y$F$N%G!<(B
$B%?$N%l%W%j%1!<%7%g%s$rJ#?tBfMQ0U$9$k$H$$$&<jK!$,$H$i$l$F$$$k!#(B
$B$7$+$7$J$,$i!"Bg?M?t$,;22C$9$k%5!<%S%9$K$*$$$F!"A40w$,8D?M$N$H$"$k%G!<%?(B
$B$r;}$C$F$$$kI,MW@-$O$J$$!#<+J,$H4XO"$N$"$k?MJ*$N>pJs$5$(<hF@$G$-$k$h$&$K(B
$B$J$C$F$$$l$P$h$$$N$G$"$k!#$D$^$j!"A4%G!<%?$N%l%W%j%1!<%7%g%s$rMQ0U$9$kI,(B
$BMW$O$J$/!"%5!<%P!<$,%/%i%$%"%s%H$NI,MW$J>pJs$H$O2?$+$rGD0.$7!">pJs$r<h<N(B
$B$7$J$,$iEAHB$7$F$$$/I,MW$,$"$k!#(B

$BK\8&5f<<$G$O!"%?%W%k%9%Z!<%9$r@)8f$9$k(B Linda $B%W%m%H%3%k$r:NMQ$7$?!#$5$i(B
$B$K!"J#?tBf$N(B Linda $B%5!<%P!<$r@\B3$7$?%b%G%k$G$"$kJ,;67?%?%W%k%9%Z!<%9(B
Federated Linda $B$rDs0F$7!"<BAu$7$F$-$?!#K\8&5f$G$O!"(BLinda $B$N%W%m%H%3%k$N(B
$B8+D>$7$H!"(B Federated Linda $B$rMQ$$$?%"%W%j%1!<%7%g%s$N<BAu$r9T$$!"8=:_$N(B
$B%7%9%F%`$NLdBjE@$r@v$$=P$9$3$H$K$9$k!#(B

% $B<+8JD4@0FsJ,LZ(B($B%9%W%l!<LZ(B, splay tree) \cite{ST85}$B$O!$%"%/%;%9$7$?@a(B
% $BE@$KBP$7$FY(J?2=(B(splaying)$BA`:n(B(\ref{subsection:splaying}$B@a(B)
% $B$r;\$9$3$H$K$h$j!$LZ$N7A>u$rF0E*$K:GE,2=$9(B
% $B$kFsJ,C5:wLZ$NAm>N$G$"$j!$(B
% %
% % $B$5$^$6$^$J%"%/(B
% % $B%;%9%Q%?!<%s$KBP$7$FLZ$N7A>u$,F0E*$K:GE,2=$7$F$f$/FsJ,LZ$G$"$j!$(B
% %
% $BB?$/$N6/NO$J@-<A$,@.$jN)$D$3$H$,$o$+$C$F$$$k!%K\O@J8$G$O!$(B
% $BF10l$N%9%W%l!<LZ$KBP$9$kJ#?t$NA^F~:o=|Ey$NA`:n(B
% $B$N%Q%$%W%i%$%sE*JBNs<B9T$r2DG=$K$9$kJ}K!$r8!F$$9$k!%L\I8$O!$2<5-$NMW@A$rK~$?$9(B
% $BA`:n%"%k%4%j%:%`$rF@$k$3$H$G$"$k!%(B
%
% \begin{enumerate}
% \item ({\bf $B%l%9%]%s%9(B}) $BDL>o$N%9%W%l!<LZ$NA`:n$HF1MM!$(B
% $BBP?tE*$J=~5Q7W;;NL(B(amortized complexity)\cite{T85}$B$r$b$D!%(B

% \item ({\bf $B%9%k!<%W%C%H(B}) $BA`:n8e$NLZ$N7A>u$,!$:,$K6a$$ItJ,$+(B
% $B$iMU$K8~$+$C$F(B
% $BA2A}E*$K3NDj$9$k$h$&$K$9$k$3$H$G!$8D!9$NA`:n$,F1;~$K;\>{$7$J$1$l$P$J(B
% $B$i$J$$@aE@$N?t$r9b!9(B${\rm O}(1)$$B8D$K$*$5$($k!%(B
% \end{enumerate}
% %
% $B$b$7%9%k!<%W%C%H$@$1$,L\I8$J$i$P!$FsJ,LZ$rMQ$$$J$/$F$b!$(B
% $B@~7A%j%9%H$rMQ$$$FMF(B
% $B0W$KC#@.$G$-$k!%$7$?$,$C$F!$%l%9%]%s%9$H%9%k!<%W%C%H(B
% $B$rF1;~$KC#@.$9$k$3$H$,K\<AE*$K=EMW$G$"$k!%(B
% %
% B$BLZ$d$=$NJQ<o$KBP$9$kJBNsA`:n$N8&5f$O>/$J$/$J$$(B\cite{LS86}$B$,!$%9%W(B
% $B%l!<LZ$NJBNs@-$K4X$9$k8&5f$O>/$J$/!$Cx<T$NCN$k8B$j!$>e5-$NFs>r7o$rK~$?$9(B
% $BJBNs%"%k%4%j%:%`$O$^$@Ds0F$5$l$F$$$J$$!%(B

% $BK\O@J8$G$O!$FsJ,C5:wLZ$N3F@aE@$O%-!<$HCM$NBP$rJ];}$9$k$b$N$H$7!$@aE@$O(B
% $B%-!<$NBP>N=g(B(symmetric order)$B$KJB$s$G$$$k$H$9$k!%4pK\A`:n$H$7$F!$(B
% $B<!$NFs$D$r9M$($k!%C1$J$k@aE@CM$NFI=P$7$O(B${\it update\/}$$B$NC1=c$JJQ(B
% $B<o$H9M$($k$3$H$,$G$-$k!%(B

% \begin{description}
% \item{${\it update}(i,v,v',t)$:} $B%-!<(B$i$$B$r$b$D@aE@$,LZ(B$t$$B$NCf$K$"$l$P!$$=(B
% $B$N@aE@$N8=:_$NCM$r(B$v$$B$KBeF~$7$?$"$H!$@aE@$K?7$?$JCM(B$v'$$B$r3JG<$9$k!%(B
% $B$J$1$l$P!$%-!<(B$i$$B$HCM(B$v'$$B$r$b$D@aE@$r(B$t$$B$KA^F~$7!$(B$v$$B$K$O@aE@$,$J$+$C$?(B
% $B$3$H$r<($9FCJL$NCM$rBeF~$9$k!%(B

% \item{${\it delete}(i,v,t)$:} $B%-!<(B$i$$B$r$b$D@aE@$,LZ(B$t$$B$NCf$K$"$l$P!$$=$N@a(B
% $BE@$N8=:_$NCM$r(B$v$$B$KBeF~$7$?$"$H!$@aE@$r>C5n$9$k!%$J$1$l$P(B$v$$B$KFCJL$N(B
% $BCM$rBeF~$9$k!%(B
% \end{description}


\section{$B4XO"8&5f(B}

\subsection{$BY(J?2=$H%H%C%W%@%&%sY(J?2=(B}\label{subsection:splaying}

$B%9%W%l!<LZ$K$*$1$kY(J?2=$H$O!$@aE@$NC5:wA`:n$K$*$$$F(B
$B%"%/%;%9$7$?%Q%9$ND9$5$r$*$h$=H>J,$K$7$D$D!$L\I8(B
$B@aE@(B(${\it delete\/}$$B$K$*$$$F$O!$L\I8@aE@$ND>A0$^$?$OD>8e$N%-!<$r$b$D@aE@(B)
$B$rLZ$N:,$^$GIb>e$5$;$kA`:n$G$"$k!%Y(J?2=$O;^$N2sE>(B(rotation)$B$r4pK\A`(B
$B:n$H$7$F$*$j!$?^(B\ref{figure:splaying}$B$K<($9(B
zig, zig-zig, zig-zag$B$N$&$A$NE,@Z$JA`:n$r%\(B
$B%H%`%"%C%W$K7+$jJV$9!%0J2<K\O@J8$G$O!$:81&BP>N$JA`:n72$O$=$NJRJ}$N$_$r<((B
$B$9!%$^$??^Cf$N>.J8;z$O@aE@!$BgJ8;z$OItJ,LZ$r<($9!%(B
%
${\it update}$, ${\it delete\/}$$BEy$N8DJL$N(B
$BA`:n%"%k%4%j%:%`$K$D$$$F$OB?$/$NJQ<o$,$"$k!%Y(J?2=$NBg$-$JFCD'$O!$%"%/%;(B
$B%9$7$?%Q%9>e$N3F@aE@$N?<$5$rLsH>J,$K$9$k0lJ}$G!$%"%/(B
$B%;%9$7$?%Q%9$N>e$K$J$$@aE@$r!$9b!9(B${\rm O}(1)$$BCJ$7$+?<$/$7$J$$$3$H(B
$B$G$"$k!%(B

\begin{figure}[tb]
\begin{center}
\scalebox{1.00}{\includegraphics{fig1.eps}}
\end{center}
\caption{
$B%\%H%`%"%C%WY(J?2=A`:n$N(B1$B%9%F%C%W!%(B % \cite{ST85}
$x$ $B$,%"%/%;%9$7$?@aE@!%(B(a) zig: 1$B2s$N1&2sE>(B($y$$B$,:,$N>l9g(B
$B$N$_(B)$B!$(B
(b) zig-zig: $B;^(B$yz$$B$H;^(B$xy$$B$r$3$N=g$K1&2sE>!$(B(c) zig-zag: $B;^(B$xy$
$B$r:82sE>$7!$$G$-$?;^(B$xz$$B$r1&2sE>!%(B}
\label{figure:splaying}
\end{figure}

$BY(J?2=$O%\%H%`%"%C%W$JJQ7AA`:n$G$"$k$?$a!$JBNsA`:n$K$OE,$5$J$$!%(B
$BJ88%(B\Cite{ST85}$B$O%H%C%W%@%&%sY(J?2=$bDs0F$7$F$$$k$,!$$3$l$O<BAu$N(B
$BMF0W2=$,<g$JL\E*$G$"$j!$LZ$N:,$OA`:n=*N;$ND>A0$^$G3NDj$7$J$$!%(B


\subsection{$BJBNsA`:n$K4X$9$k2a5n$N8&5f(B}\label{subsection:related-parallel}

$BOBED(B\cite{W90}$B$O!$JB9TO@M}7?8@8l(B\cite{S89}$B$NO@M}JQ?t$rMQ$$$?Y((B
$BJ?2=%"%k%4%j%:%`$rDs0F$7$F$$$k!%$3$l$O!$O@M}JQ?t$rMxMQ$7$F!$(B
$B%H%C%W%@%&%sY(J?2=$r(Bin-place$B$G9T$J$&$h$&$K$7$?$b$N$H8+$J$9$3$H$b$G$-$k(B
$B$,!$(B${\it update\/}$$B$N$h$&$K!$BP>]$H$J$k@aE@$,A`:n=*N;8e$NLZ$KB8:_$9$k$3(B
$B$H$,$o$+$C$F$$$k>l9g$O!$LZ$N:,$N%-!<$rA`:n$N:G=i$K3NDj$5$;$kE@$,Bg$-$JFCD'$G(B
$B$"$k!%(B
% 
% $B?tI4@aE@$NO"B3A^F~A`:n$NJBNsEY$O(B4$B!A(B8$B$G$"$k$H$$$&<B837k2L$,(B
% $BJs9p$5$l$F$$$k(B\cite{W90}$B!%(B
%
$B$7$+$7$3$N5;K!$O!$(B
${\it delete\/}$$B$N$h$&$K!$A`:n7k2L$NLZ$N:,$,;vA0$K$o$+$i(B
$B$J$$>l9g$K$OE,MQ$G$-$J$$!%(B


\subsection{$B%H%C%W%@%&%sY(J?2=$NLdBjE@(B}

$B%H%C%W%@%&%sY(J?2=$K$h$k(B${\it update\/}$$B$O!$(B
\ref{subsection:related-parallel}$B@a$N$h$&$K(B
$B:,$N%-!<$r:G=i$K3NDj$5$;$k$h(B
$B$&$K$7$F$b!$JBNs=hM}$N4QE@$+$i$OLdBj$,;D$k!%$?$H$($P!$@aE@(B
$x(<b)$ ($<$$B$O%-!<$K$h$k=g=x4X78(B)$B$N(B${\it update\/}$$B$K$h$C$F5/$-$k(B
$B?^(B\ref{figure:topdown}$B$N(B
zig-zig$BA`:n(B\cite{W90} $B$r9M$($k(B($L$$B$H(B$R$$B$O!$LZ(B$C$$B$r%H%C%W%@%&%sY(J?(B
$B2=$7$?7k2L$N:8(B($B1&(B)$BItJ,LZ$G!$(B${\it update\/}$$B40N;;~$^$G$K3NDj(B)$B!%(B

% \begin{adjustvboxheight}
\begin{figure}[tb]
\begin{center}
\scalebox{1.00}{\includegraphics{fig2.eps}}
\end{center}
\caption{$B%H%C%W%@%&%sY(J?2=$K$h$k(B${\it update\/}$}
\label{figure:topdown}
\end{figure}
% \end{adjustvboxheight}

$B$3$N(B${\it update\/}$$B$N8e!$(B$y(<x)$, $z(>b)$$B$X$N%"%/%;%9$,$3$N=g$KB3$/$H(B
$B$9$k!%:G=i$N(B$x$$B$X$N%"%/%;%9;~$K(B$x$$B$,ItJ,LZ(B$C$$B$N:8$NJ}$K$"$C$?$?$a$K(Bzig-zig$BA`:n(B
$B$,B3$/>l9g!$(B$L$$B$N(B
$B:,$,3N(B
$BDj$9$k$N$OCY$/$J$k!%$7$+$7(B$L$$B$N:,$,3NDj$9$k$^$G$O!$<!$N(B$y$$B$X$N%"%/%;(B
$B%9$,(Bzig, zig-zig, zig-zag$B$N$I$l$r$^$:E,MQ$9$k$+7h$a$i$l$J$$!%(B
% 
% $BD9$/BT$C$F$b!$L\I8$N@aE@$N>e>:CJ?t$,B?$1$l$PLdBj$O$J$$$N$G$"$k$,!$(B
% $B$=$l$,(B
%
$B$=$3$G(B3$BHVL\$N(B
$z$$B$X$N%"%/%;%9$,!$(B2$BHVL\$NA`:n$K$h$C$F1F6A$r<u$1$k$3$H$N$J$$(B$b$$B$N1&ItJ,(B
$BLZ$K8~$+$&$K$b$+$+$o$i$:!$D9;~4V%V%m%C%/$7$F$7$^$&!%(B

$B:o=|A`:n$O$5$i$KLdBj$G$"$k!%0lHL$K!$FsJ,LZ$+$i@aE@(B$x$$B$r:o=|$9$k$K$O!$(B
$x$$B$N:8It(B
$BJ,LZ$N:GBg$N@aE@(B$y$$B$rC5$7$F$=$l$r(B$x$$B$N>l=j$K0\$9$3$H$,4pK\$H$J(B
$B$k!%$7$+$7!$Y(J?2=$NM-L5$K$+$+$o$i$:!$(B$y$$B$,8+$D$+$k$^$G$O(B$x$$B$N>l=j(B
$B$K$/$k?7$?$J%-!<$O3NDj$;$:!$8eB3$NA`:n$r%V%m%C%/$7$F$7$^$&!%0J2<$N$h$&(B
$B$J2r7hK!$b9M$($i$l$k$,!$$$$:$l$b$&$^$/F0:n$7$J$$!%(B

\begin{enumerate}
\item % {\bf $B0l;~E*$J%-!<(B}
$y$$B$,8+$D$+$k$^$G!$(B$x$$B$r0l;~E*$J%-!<$H$7$FMxMQ$9$k$H!$(B
$y\le z\le x$$B$G$"$k$h$&$J@aE@(B$z$$B$X$NA`:n$r8m$C$?J}8~$XF3$/!%(B

\item % {\bf $BAPJ}8~%j%9%H(B}
$B3F@aE@$,D>A0$HD>8e$N%-!<$r$b$D@aE@$X$N%]%$%s%?$rJ];}$9$k$3$H$K$h$C$F!$(B
$x$$B$ND>A0$NMWAG(B$y$$B$K(B${\rm O}(1)$$B;~4V$G%"%/%;%9$G$-$k$h$&$K$9$k(B
$B$3$H$,9M$($i$l$k!%$3$l$i$N%]%$%s%?$OLZ(B
$B$NY(J?2=;~$KJQ99$9$kI,MW$,$J$$$H$$$&FCD'$,$"$k!%(B
% 
$B$7$+$7$3$NJ}K!$OC`<!A`:n$N$H$-$7$+$&$^$/F0:n$7$J$$!%(B
% 
% $B$"$k%W%m%;%9$,@aE@(B
% $x$$B$r:o=|$7$h$&$H$7$?$H$9$k!%$=$N%W%m%;%9$O@aE@(B$y$$B$K(B${\rm O}(1)$$B;~4V$G%"(B
% $B%/%;%9$G$-$k$b$N$N!$C1$K$=$l$r:o=|$7$F(B$x$$B$N$+$o$j$KMQ$$$k$3$H$O$G$-$J$$!%(B
% (invisible pointer?)
%
$B$J$<$J$i$3$N:o=|A`:n$NA0$NA`:n$,(B$x$$B$H(B$y$$B$r7k(B
$B$V%Q%9$r2<9_Cf$G!$$$$:$l(B$y$$B$KE~C#$9$k$+$b$7$l$J$$$+$i$G$"$k!%(B
\end{enumerate}

$B$7$?$,$C$FK\O@J8$G$O!$9b!9(B${\rm O}(1)$$B8D$N@a$r;\>{$7$D$D!$87L)$K%H%C%W%@%&(B
$B%s$KLZ$rJQ7A$7$F$f$/%"%k%4%j%:%`$r9M$($k$3$H$H$9$k!%(B

\section{$BJBNs99?7%"%k%4%j%:%`(B}\label{section:update}

$BK\@a$G$O!$8eB3$NA`:n$r%V%m%C%/$7$J$$(B${\it update\/}$$BA`:n$rM?$($k!%4pK\E*$J(B
$B%"%$%G%"$O!$(Bzig-zig$B$H(Bzig-zag$B$NN>J}$K$D$$$F!$L\I8@aE@$r$=$N?<$5$N(B
$BH>J,$^$G$7$+Ib>e$5$;$J$$H>Y(J?2=(B(semi-splaying)$B$rMQ$$$k$3$H$G$"$k(B($BJ88%(B
\cite{ST85}$B$NH>Y(J?2=$O!$(Bzig-zig$B$N$_$,Y(J?2=$H0[$J$C$F$$$?(B)$B!%(B$x$$B$r99?7BP(B
$B>]$N@aE@$H$9$k$H!$%"%k%4%j%:%`$O0J2<$N$h$&$K$J$k!%(B
%
% $B$3$3$G$b:81&BP>N$JA`:n$NJRJ}$N$_$r=R$Y$k!%(B

\begin{itemize}
% \medskip\noindent (a)
\item[(a)]
$B6u$NLZ$KBP$9$kA^F~$O?^(B\ref{figure:update}
(a1)$B$NA`:n!$(B($B6u$G$J$$(B)$BLZ$N:,$KBP$9$k99?7$O(B
$B?^(B\ref{figure:update}(a2)$B$NA`:n$r9T$J$&!%(B

% \begin{adjustvboxheight}
\begin{figure*}[t]
\begin{center}
\scalebox{1.00}{\includegraphics{fig3.eps}}
\end{center}
\caption{$B8eB3A`:n$r%V%m%C%/$7$J$$99?7%"%k%4%j%:%`$N(B1$B%9%F%C%W(B}
\label{figure:update}
\end{figure*}
% \end{adjustvboxheight}

% \medskip\noindent (b)
\item[(b)]
zig: 
$x$$B$,:8ItJ,LZ$N:,$G$"$k>l9g$O?^(B\ref{figure:update}(b1)
$B$NA`:n!$(B$x$$B$,B8:_$9$Y$-:8ItJ,LZ$,6u$N(B
$B>l9g$O?^(B\ref{figure:update}(b2)$B$NA`:n$r9T$J$&!%(B

% \medskip\noindent (c)
\item[(c)]
zig-zig: $B?^(B\ref{figure:update}(c)$B:8$NLZ$K$*$1$k(B$x (<b)$$B$NC5:w$G$O!$(B
$B;^(B$ba$$B$N1&2sE>$r9T$J$C$F%"%/%;%9$7$?%Q%9$ND9$5$r(B1$BC;=L$9$k!%<!$O(B1$B%l%Y%k(B
($BC;=LA0$ND9$5$G$O(B2$B%l%Y%k(B)$B2<9_$7$F!$ItJ,LZ(B$A$$B$KBP$7$F:F5"E*$KC5:w$r9T$J$&!%(B

% \medskip\noindent (d)
\item[(d)]
zig-zag: $B?^(B\ref{figure:update}(d)$B:8$NLZ$K$*$1$k@aE@(B$x$ ($b<x<a$) $B$N(B
$BC5:w$G$O!$(B
$B;^(B$cb$$B$N:82sE>$H!$$G$-$?;^(B$ca$$B$N1&2sE>$r9T$J$$!$(B
$B%"%/%;%9$7$?%Q%9$r(B1$BC;=L$9$k!%(B
%
% $BFs$D$NCfB&$NItJ,LZ$NE,Ev$JJ}$KBP$7$F:F5"E*$KC5:w$r9T$J$&!%(B
%
% \noindent
$x=c$$B$J$i$P$3$l$GC5:w=*N;$G$"$k!%(B$x<c$$B$J$i$P(B2$B%l%Y%k(B($BC;=LA0$ND9$5$G$O(B3$B%l(B
$B%Y%k(B)$B2<9_$7$F(B$B$$B$NCf$+$i(B$x$$B$r:F5"E*$K(B
$BC5:w$9$k!%(B$x>c$$B$J$i$PF1MM$K(B$C$$B$NCf$+$i:F5"E*$KC5:w$9$k!%(B$x\ge c$$B$N>l9g$K$O(B
$B;^(B$ca$$B$N2sE>A`:n$r>JN,$9$k$3$H$b9M$($i$l$k!%(B
%
$b$$B$N1&ItJ,LZ$,6u$N>l9g$O!$$=$3$K@aE@(B$x$$B$rA^F~(B
$B$7$?$"$H!$>e$K=R$Y$?2sE>A`:n$r9T$J$&!%(B

\end{itemize}
% \medskip
$B0J>e$NA`:n$G!$%"%/%;%9$7$?%Q%9$ND9$5$O:G0-$G$bLs(B$2/3$$B$K$J$k!%(B
%
$BH>J,$G$J$/$F(B$2/3$$B$J$N$O!$>e5-(Bzig-zag$BA`:n$N@-<A$K$h$k$b$N$G$"$k!%(B


\section{$BJBNs:o=|%"%k%4%j%:%`(B}\label{section:delete}

$BJBNs:o=|$N$?$a$N4pK\E*$JCeA[$O!$Y(J?2=A`:n$r!$:o=|$9$Y$-@aE@$r2<9_$5(B
$B$;$k$?$a$KMxMQ$9$k$3$H$G$"$k!%$3$l$^$G$O!$Y(J?2=A`:n$O$b$C$Q$i!$:FEY%"%/(B
$B%;%9$7$=$&(B
$B$J@aE@$rIb>e$5$;$k$?$a$KMQ$$$i$l$F$-$?!%$3$3$G=EMW$J$3$H$O!$:o=|BP>]$N(B
$B@aE@0J30$O9b!9(B${\rm O}(1)$$B%l%Y%k$7$+2<9_$5$;$J$$$h$&$K$9$k$3$H$G$"$k!%(B
$B0J2<$G$O!$(B$z$$B$r:o=|BP>]$N@aE@$H$9$k!%(B

$B$^$:!$:,@aE@$,:o=|BP>]@aE@(B$z$$B$G$"$k>l9g$r9M$($k!%$3$N>l9g!$(Bzipping$B$H8F$V(B
$BA`:n$K$h$C$F(B
$B$=$l$r(B``$BMF0W$K(B''$B:o=|$G$-$k>l=j$^$G2<9_$5$;$k!%@aE@$,(B``$BMF0W$K(B''$B:o=|$G$-(B
$B$k$H$O!$$=$N:8ItJ,LZ!$1&ItJ,LZ!$:8ItJ,LZ$N1&ItJ,LZ!$1&ItJ,LZ$N:8ItJ,LZ$N(B
$B$$$:$l$+$,6u$G$"$k$3$H$G$"$k!%:,@aE@$N2<9_$K$h$C$F!$$=$N:8ItJ,LZ$H(B
$B1&ItJ,LZ$NK%$$9g$;$,5/$-$k!%(B
% 
% $B$3$l$,8@MU$NM3Mh$G$"$k!%(B

\begin{enumerate}
% \medskip\noindent (a)
\item[(a)]
``$BMF0W$K(B''$B:o=|$G$-$k>l9g!'?^(B\ref{figure:delete}(a1)$B$^$?$O(B(a2)
$B$N$h$&$KJQ7A$9$k!%(B


% \begin{adjustvboxheight}
\begin{figure*}[t]
\begin{center}
\scalebox{1.00}{\includegraphics{fig4.eps}}
\end{center}
\caption{$B8eB3A`:n$r%V%m%C%/$7$J$$:o=|%"%k%4%j%:%`$N(B1$B%9%F%C%W(B}
\label{figure:delete}
\end{figure*}
% \end{adjustvboxheight}

% \medskip\noindent (b)
\item[(b)]
``$BMF0W$K(B''$B:o=|$G$-$J$$>l9g!'?^(B\ref{figure:delete}(b)$B$N$h$&$K(B
zig-zag$B$r;\$7!$$=(B
$B$N7k2L$G$-$k(B$b$$B$N1&ItJ,LZ$K!$(B($B0l$D$a$H$O:81&BP>N$J(B) zig-zag$B$r;\$9!%(B

\noindent
4$B2s$N2sE>$G(B$z$$B$O(B2$B%l%Y%k2<9_$9$k!%(B$z$$B$N?7$?$JItJ,LZ(B$C$$B$H(B$F$
$B$O!$F1$8%l%Y%k$K$H$I$^$k!%$=$l0J30$N@aE@$b9b!9(B1$B%l%Y%k$7$+2<9_(B
$B$7$J$$!%(B$z$$B$r:,$H$9$k?7$?$JItJ,LZ$KBP$7$F:F5"E*$K:o=|A`:n$r9T$J$&$,!$(B$z$$B$N;RB9(B
$B$G$J$$@aE@$,$=$l$K$h$C$F$5$i$K2<9_$9$k$3$H$O$J$$!%(B
\end{enumerate}

% \medskip
$B?^(B\ref{figure:zipping}$B$K!$:,@aE@(B$z$$B$N:o=|$K$h$kLZ$N7A>u$NJQ2=$r<($9!%(B
\begin{figure*}[t]
\begin{center}
\scalebox{1.00}{\includegraphics{fig5.eps}}
\end{center}
\caption{Zipping$B$K$h$k@aE@(B$z$$B$N:o=|(B}
\label{figure:zipping}
\end{figure*}

$B:o=|BP>]@aE@(B$z$$B$,:,$G$"$k$H$O8B$i$J$$>l9g$O!$$^$:Bh(B\ref{section:update}$B@a$N(B
$BJ}K!$G(B$z$$B$rC5:w$9$k!%$3$l$O:,$+$i(B$z$$B$K;j$k%Q%9$rC;=L$9$k8z2L$r$b$D!%$D$.(B
$B$K!$(B$z$$B$r(Bzipping$B$K$h$C$F2<9_$5$;$F:o=|$9$k!%(B

Zipping$BA`:n$O%Q%9$NC;=L$r9T$J$o$J$$$,!$%"%/%;%9$7$?@aE@$OIb>e$5$;(B
$B$k$H$$$&86B'$K$7$?$,$&$J$i$P!$(Bzipping$B$K@h$@$C$F!$:8ItJ,LZ$N:GBgMWAG$K;j(B
$B$k%Q%9$H1&ItJ,LZ$N:G>.MWAG$K;j$k%Q%9$r$=$l$>$l%H%C%W%@%&%s$NH>Y(J?2=(B
(zig-zig ($B?^(B\ref{figure:update}(c)) $B$N7+JV$7(B)$B$K$h$C(B
$B$FC;=L$9$l$P$h$$!%$3$NC;=L2=$O(Bzipping$B$HJB9T$7$F9T$J$&$3$H$,$G$-$k!%(B

Zipping$B$O99?7A`:n$H0[$J$j!$3F@aE@$N%-!<CM$rFI$`$3$H$J$/LZ$r2<9_$9$k!%(B
$B$^$?(Bzipping$B$O!$LZ(B$T_1$$B$HLZ(B$T_2$ ($T_1$$B$N$I(B
$B$N%-!<$b!$(B$T_2$$B$N$I$N%-!<$h$j$b>.$5$$$b$N$H$9$k(B)$B$H$N%H%C%W%@%&%sJ;9gA`:n(B
$B$K$b1~MQ$G$-$k!%$9$J$o$A!$?7$?$J@aE@(B($B%-!<$OG$0U(B)$B$rD4C#$7!$$=$N:8ItJ,LZ(B
$B$r(B$T_1$$B!$1&ItJ,LZ$r(B$T_2$$B$H$7$F0l$D$NLZ$r9=@.$7$?(B
$B$N$A!$D4C#$7$?:,@aE@$r>C5n$9$l$P$h$$!%(B

\section{$B7W;;NL$K4X$9$k7k2L$H9M;!(B}

$B8zN($NFs$D$N<\EY$N$&$A!$%9%k!<%W%C%H$K$D(B
$B$$$F$OMF0W$K5DO@$,$G$-$k!%$9$J$o$A!$Fs$D$NA`:n$O!$%l%Y%k(B$l$ ($B:,$r%l(B
$B%Y%k(B$0$$B$H$7$F(B)$B$N@aE@$r(B${\rm O}(l)$$B2s(B --- ${\it update\/}$$B$O9b!9(B$(l+2)$$B2s!$(B
zipping$B$O9b!9(B$(2l+2)$$B2s(B ---
$B$N2sE>A`:n$N$N$A$K3NDj$5$;$k!%(B
$B$5$i$K$I$A$i$NA`:n$b!$O"B3$9$k9b!9(B$3$
$B%l%Y%k$N@aE@$rF1;~$K;\>{$9$k$@$1$G$h$$!%$3$l$i$N$3$H$+$i!$LZ$NBg$-$5$d?<(B
$B$5$K$h$i$J$$%9%k!<%W%C%H$G!$A`:n7ONs$r%Q%$%W%i%$%sE*$KJBNs=hM}$9$k$3(B
$B$H$,$G$-$k!%(B

$B%l%9%]%s%9$O!$(B${\it update\/}$$B$K$D$$$F$O!$DL>o$N%9%W%l!<(B
$BLZ$HF1Ey$N=~5Q7W;;NL$r$b$D$3$H$,>ZL@$G$-$k!%6qBNE*$K$O!$(B
$B@aE@(B$x$$B$N(B{\bf $BBg$-$5(B}$s(x)$$B$r(B$x$$B$r:,$H$9$kItJ,LZ$N@aE@?t$HDj5A$7!$(B
{\bf $B%i%s%/(B}$r(x)$$B$r(B$\log_2(s(x))$$B$H$9$k!%(B
$B$=$7$F(B
%
$BLZ$N(B{\bf $B%]%F%s%7%c%k(B}$B$r!$$9$Y$F$N@aE@$N%i%s%/$NOB$HDj5A$9$k!%(B
$B$9$k$H!$(B${\it update\/}$$B$N=~5Q;~4V!$$D$^$j2sE>A`:n$N2s?t$GB,$C$?=j(B
$BMW;~4V$KA`:nA08e$N%]%F%s%7%c%k$NJQ2=$r2C$($?$b$N$O!$(B$n$$B$rLZ$N@aE@?t$H$7(B
$B$F!$(B${\rm O}(\log n)$$B$G$"$k$3$H$r<($9$3$H$,$G$-$k!%(B
$B$3$N$3$H$+$i!$==J,D9$$A`:n7ONs$NJ?6Q%l%9%]%s%9$O!$:G0-$G$bBP?tE*$G$"$k$3(B
$B$H$,$o$+$k!%(B
$BJ88%(B\Cite{ST85}$B$N$h$&(B
$B$K!$@aE@$K0[$J$k=E$_$r$D$1$F(B$s$$B$d(B$r$$B$rDj5A$9$k$3$H$K$h$j!$$h$j6/$$@-<A(B
$B$r<($9$3$H$b$G$-$k$,!$K\O@J8$G$O>J$/!%(B

$B0lJ}!$(B${\it delete\/}$$B$K$D$$$F$O!$J88%(B\Cite{ST85}$B$N2r@OJ}K!$G$O!$BP(B
$B?tE*=~5Q7W(B
$B;;NL$rF3$/$3$H$O$G$-$J$$!%$=$N$3$H$r<($9$?$a$K!$?^(B\ref{figure:delete}
(b)$B$N(B4$B2s$N2sE>$K$h$k%]%F%s%7%c%kJQ2=$r9M$($k!%(B

$B?^(B\ref{figure:delete}(b)$B$N0lHV1&B&(B
$B$NLZ$N%i%s%/4X?t$r(B$r'$$B$H$9$k!%0lHV:8B&$NLZ$+$i$N%]%F%s%7%c%k$NJQ2=$r!$(B
$k$$B$r$"$k@5Dj?t$H$7$F(B$k(r'(b)-r'(z))$$B0JFb$K2!$5$($k$3$H$,$G$-$k$3$H$r<($9$N$,!$(B
$BJ88%(B\Cite{ST85}$B$K$*$1$k=~5Q7W;;NL$N>ZL@5;K!$N4pK\$G$"$C$?!%$7$+$7!$(B
$B$3$l$i$NLZ$K(B
$B$D$$$F(B$s(A)= s(B) = s(C) = h\gg t = s(D) = s(E) = s(F)$
$B$r2>Dj$9$k$H!$%]%F%s%7%c%kJQ2=$,(B$h/t$$B$K4X$7$F(B${\rm O}(\log
(h/t))$$B$H$J$k!%0lJ}(B$r'(b)-r'(z)$$B$O(B$h/t$$B$K4X$7$F(B${\rm O}(1)$$B$G$"$k$N$G!$(B
$B>e5-$NMW@A$rK~$?$9(B
$k$$B$OB8:_$7$J$$$3$H$,$o$+$k!%(BZipping$B$K@hN)$C$F%Q%9C;=L2=$r9T$J$C(B
$B$?>l9g$K$D$$$F$b!$F1MM$N$3$H$,<($;$k!%(B

$B$7$+$7!$Bh(B\ref{section:delete}$B@a$N:o=|A`:n$O!$(B
%
$B%"%/%;%9$7$?%Q%9>e$N@aE@$N?<$5$,LsH>J,$K$J$j(B($B;vA0$K%Q%9(B
$BC;=L2=$r;\$7$?>l9g(B)$B!$$=$l0J30$N@aE@$b9b!9Dj?t%l%Y%k$7$+D@$^$J$$(B
%
$B$H$$$&!$@aE@$NIb$-D@$_$K$D$$$F$N%9%W%l!<LZ0lHL$N@-<A$OK~$?$7$F$$$k!%(B
%
$B$G$O0lHL$K!$$3$NFs$D$N@-<A$rK~$?$9<+8JD4@0E*$JLZ%"%k%4%j%:%`$G!$J?6Q%l%9(B
$B%]%s%9$,BP?t;~4V$G2!$5$($i$l$J$$$h$&$J!$==J,D9$$A`:n7ONs$OB8:_$9(B
$B$k$N$@$m$&$+!)(B $B$3$l$OL$2r7h$G$"$k$,!$K\O@J8$GDs0F$7$?FsA`:n$K(B
$B$D$$$F$O!$J?6Q%l%9%]%s%9$O>/$J$/$H$b(B${\rm O}(\sqrt n)$ ($B99?7$N$_$J$i$P(B
${\rm O}(\log n)$)$B$HM=A[$5$l$k!%(B

$B$=$N:,5r(B
$B$H$7$F!$3F@aE@$N:o=|$7$d$9$5$NJQ2=$r9M$($k!%(B
$B@aE@(B$x$$B$N(B{\bf $B:o=|:$FqEY(B}$d(x)$$B$r!$(B$x$$B$+$i$=$ND>A0$N%-!<(B$x_-$$B$r$b$D@a(B
$BE@$X;j$k%Q%9D9(B($x_-$$B$,B8:_$7$J$$>l9g$d!$(B$x_-$$B$,(B$x$$B$N;RB9$G(B
$B$J$$>l9g$O(B$0$$B$HDj$a$k(B)$B$HD>8e$N%-!<(B$x_+$$B$r$b$D@a$K;j$k%Q%9D9$N:G>.CM(B
$B$HDj$a$k$H!$Bh(B\ref{section:delete}$B@a$N(B
${\it delete\/}$$B$O!$(B$d$$B$NBg$-$J@aE@$N>C5n$K$O;~4V$,$+$+$k$b(B
$B$N$N!$;D$C$?3F@aE@$N(B$d$$B$r9b!9(B${\rm O}(1)$
$B$7$+Bg$-$/$7$J$$!%$^$?Bh(B\ref{section:update}$B@a$N(B
${\it update\/}$$B$G?7$?$KA^F~$7$?@aE@$N(B$d$
$B$O(B$0$$B$G$"$j!$(B${\it update\/}$$B$O$9$G$KB8:_$7$F$$$?3F@aE@$N(B$d$$B$b9b!9(B${\rm
O}(1)$$B$7$+Bg$-$/$7$J$$!%(B($B%\%H%`%"%C%WY(J?2=$K$*$1$k@aE@$N(B$d$$B$NA}2C$O!$Dj?t$G(B
$B2!$($k$3$H$,$G$-$J$$!%(B)$B$3$l$i$N$3$H$+$i(B
%
\begin{enumerate}
\item[1.]
$B?7$?$J@aE@$N(B$d$$B$NCM$,(B$k$$B$^$G@.D9$9$k$K$O!$B>$N@aE@$N(B$\Omega(k)$
$B2s$NA^F~:o=|$,I,MW(B
\end{enumerate}
%
$B$G$"$k$3$H$,$o$+$k!%$5$i$K(B
%
\begin{enumerate}
\item[2.]
$BFsJ,LZ$K$*$1$k3F@aE@$N(B$d$$B$NAmOB$O!$(B
$BLZ$r%H%i%P!<%9$7$?$H$-$KDL$k;^$N1d$YK\?t$r>e2s$k$3$H$O$J$$$+$i(B
${\rm O}(n)$
\end{enumerate}
%
$B$G$"$k!%(B1.$B$H(B2.$B$+$i!$(B
$B?7$?$J@aE@$NA^F~$H!$(B$d$$B$NBg$-$J@aE@$N>C5n$,7+$jJV$5$l$k$H$$$&:G0-$NA`:n(B
$B7ONs$r9M$($F$b!$A`:n$NJ?6Q$N<j4V$O(B${\rm O}(\sqrt n)$$B$G$"$j!$<BMQ>e$N8zN((B
$B$O99?7A`:n$N$_$N>l9g$H$[$H$s$IJQ$o$i$J$$$HM=A[$5$l$k!%(B

\section{$B$^$H$a$H:#8e$N2]Bj(B}

$B@aE@$NIb$-D@$_$K4X$9$kK>$^$7$$@-<A$rJ]$A!$$+$D7W;;NL$N0UL#$G:GE,$J%9%k!<(B
$B%W%C%H$r$b$D<+(B
$B8JD4@0FsJ,LZ$NJBNsA`:n(B($B99?7!$A^F~!$:o=|!$J;9g(B)$B%"%k%4%j%:%`$rDs0F$7$?!%@aE@$N(B
$B99?7$dA^F~$K4X$7$F(B
$B$OBP?tE*=~5Q7W;;NL$r;}$D$3$H$,>ZL@$G$-$F$*$j!$$5$i$K%"%/%;%9%Q%?!<%s$NJP(B
$B$j$dJQ2=$KBP$9$kDI=>@-$J$I!$%9%W%l!<LZ$N;}$D6/NO$+$D4h7r$J@-<A(B
$B$NB?$/$r0z$-7Q$$$G$$$k!%:o=|$N=~5Q7W;;NL$N$h$jNI$$M}O@E*8B3&$rF3$/(B($B$^$?(B
$B$O$=$NITB8:_$r<($9(B)$B$3$H$O:#(B
$B8e$N2]Bj$G$"$k!%$^$?!$%"%k%4%j%:%`$N<B:]E*8zN(!$JBNsJ,;64D6-$G$N<BAu!$1~(B
$BMQ$N8!F$$b:#8e$N2]Bj$G$"$k!%(B


{\bf $B<U<-(B}\
$BK\O@J8$N=i4|$NHG$K$D$$$F5DO@$7$F$$$?$@$$$?(BRobert Tarjan$B;a(B(Princeton$BBg(B)$B!$(B
$BLS<uE/;a(B(NEC)$B!$CfC+M42p;a(B($BAa0pEDBg(B)$B$K46<U$9$k!%(B
%
\begin{adjustvboxheight} % needed only when Appendix follows
\begin{thebibliography}{99}
\bibitem{LS86} Lanin, V. and Shasha, D.$B!'(BA Symmetric Concurrent B-Tree
Algorithm,
Proc.\ 1986 Fall Joint Computer Conference, IEEE, 1986, pp.~380--389$B!%(B

\bibitem{ST85} Sleator, D. D. and Tarjan, R. E.$B!'(BSelf-Adjusting Binary Search
Trees, {\it J. ACM}, Vol.~32, No.~3 (1985), pp.~652--686$B!%(B

\bibitem{S89} Shapiro E.$B!'(BThe Family of Concurrent Logic Programming Languages.
{\it ACM Computing Surveys}, Vol.~21, No.~3 (1989), pp.~413--510$B!%(B

\bibitem{T85} Tarjan, R. E.$B!'(BAmortized Computational Complexity, {\it
SIAM J.\ Alg.\ Disc.\ Math.}, Vol.~6, No.~2 (1985), pp.~306--318.

\bibitem{W90} $BOBED5WH~;R!'%9%W%l%$LZ$NJBNs%G!<%?C5:w(B, Proc.\ KL1
Programming Workshop '90, Tokyo, ICOT, 1990, pp.~42--49$B!%(B
\end{thebibliography}
\end{adjustvboxheight} % needed only when Appendix follows

\appendix
\section{$BIUO?(B: \LaTeX $B$K$h$kO@J8:n@.$N%,%$%I(B} 

$B$3$3$K!$0JA0$N(B \verb|sample.tex| $B$G$O!$O@J8:n@.$N%,%$%I$,$"$C$?$,!$(B
$B$=$NFbMF$O(B \verb|guide.tex| $B$K0\F0$7$?!%(B

\end{document}