\documentclass[11pt,twoside]{article}\makeatletter

\IfFileExists{xcolor.sty}%
  {\RequirePackage{xcolor}}%
  {\RequirePackage{color}}
\usepackage{colortbl}
\usepackage{wrapfig}
\usepackage{ifxetex}
\ifxetex
  \usepackage{fontspec}
  \usepackage{xunicode}
  \catcode`⃥=\active \def⃥{\textbackslash}
  \catcode`❴=\active \def❴{\{}
  \catcode`❵=\active \def❵{\}}
  \def\textJapanese{\fontspec{Noto Sans CJK JP}}
  \def\textChinese{\fontspec{Noto Sans CJK SC}}
  \def\textKorean{\fontspec{Noto Sans CJK KR}}
  \setmonofont{DejaVu Sans Mono}
  
\else
  \IfFileExists{utf8x.def}%
   {\usepackage[utf8x]{inputenc}
      \PrerenderUnicode{–}
    }%
   {\usepackage[utf8]{inputenc}}
  \usepackage[english]{babel}
  \usepackage[T1]{fontenc}
  \usepackage{float}
  \usepackage[]{ucs}
  \uc@dclc{8421}{default}{\textbackslash }
  \uc@dclc{10100}{default}{\{}
  \uc@dclc{10101}{default}{\}}
  \uc@dclc{8491}{default}{\AA{}}
  \uc@dclc{8239}{default}{\,}
  \uc@dclc{20154}{default}{ }
  \uc@dclc{10148}{default}{>}
  \def\textschwa{\rotatebox{-90}{e}}
  \def\textJapanese{}
  \def\textChinese{}
  \IfFileExists{tipa.sty}{\usepackage{tipa}}{}
\fi
\def\exampleFont{\ttfamily\small}
\DeclareTextSymbol{\textpi}{OML}{25}
\usepackage{relsize}
\RequirePackage{array}
\def\@testpach{\@chclass
 \ifnum \@lastchclass=6 \@ne \@chnum \@ne \else
  \ifnum \@lastchclass=7 5 \else
   \ifnum \@lastchclass=8 \tw@ \else
    \ifnum \@lastchclass=9 \thr@@
   \else \z@
   \ifnum \@lastchclass = 10 \else
   \edef\@nextchar{\expandafter\string\@nextchar}%
   \@chnum
   \if \@nextchar c\z@ \else
    \if \@nextchar l\@ne \else
     \if \@nextchar r\tw@ \else
   \z@ \@chclass
   \if\@nextchar |\@ne \else
    \if \@nextchar !6 \else
     \if \@nextchar @7 \else
      \if \@nextchar (8 \else
       \if \@nextchar )9 \else
  10
  \@chnum
  \if \@nextchar m\thr@@\else
   \if \@nextchar p4 \else
    \if \@nextchar b5 \else
   \z@ \@chclass \z@ \@preamerr \z@ \fi \fi \fi \fi
   \fi \fi  \fi  \fi  \fi  \fi  \fi \fi \fi \fi \fi \fi}
\gdef\arraybackslash{\let\\=\@arraycr}
\def\@textsubscript#1{{\m@th\ensuremath{_{\mbox{\fontsize\sf@size\z@#1}}}}}
\def\Panel#1#2#3#4{\multicolumn{#3}{){\columncolor{#2}}#4}{#1}}
\def\abbr{}
\def\corr{}
\def\expan{}
\def\gap{}
\def\orig{}
\def\reg{}
\def\ref{}
\def\sic{}
\def\persName{}\def\name{}
\def\placeName{}
\def\orgName{}
\def\textcal#1{{\fontspec{Lucida Calligraphy}#1}}
\def\textgothic#1{{\fontspec{Lucida Blackletter}#1}}
\def\textlarge#1{{\large #1}}
\def\textoverbar#1{\ensuremath{\overline{#1}}}
\def\textquoted#1{‘#1’}
\def\textsmall#1{{\small #1}}
\def\textsubscript#1{\@textsubscript{\selectfont#1}}
\def\textxi{\ensuremath{\xi}}
\def\titlem{\itshape}
\newenvironment{biblfree}{}{\ifvmode\par\fi }
\newenvironment{bibl}{}{}
\newenvironment{byline}{\vskip6pt\itshape\fontsize{16pt}{18pt}\selectfont}{\par }
\newenvironment{citbibl}{}{\ifvmode\par\fi }
\newenvironment{docAuthor}{\ifvmode\vskip4pt\fontsize{16pt}{18pt}\selectfont\fi\itshape}{\ifvmode\par\fi }
\newenvironment{docDate}{}{\ifvmode\par\fi }
\newenvironment{docImprint}{\vskip 6pt}{\ifvmode\par\fi }
\newenvironment{docTitle}{\vskip6pt\bfseries\fontsize{22pt}{25pt}\selectfont}{\par }
\newenvironment{msHead}{\vskip 6pt}{\par}
\newenvironment{msItem}{\vskip 6pt}{\par}
\newenvironment{rubric}{}{}
\newenvironment{titlePart}{}{\par }

\newcolumntype{L}[1]{){\raggedright\arraybackslash}p{#1}}
\newcolumntype{C}[1]{){\centering\arraybackslash}p{#1}}
\newcolumntype{R}[1]{){\raggedleft\arraybackslash}p{#1}}
\newcolumntype{P}[1]{){\arraybackslash}p{#1}}
\newcolumntype{B}[1]{){\arraybackslash}b{#1}}
\newcolumntype{M}[1]{){\arraybackslash}m{#1}}
\definecolor{label}{gray}{0.75}
\def\unusedattribute#1{\sout{\textcolor{label}{#1}}}
\DeclareRobustCommand*{\xref}{\hyper@normalise\xref@}
\def\xref@#1#2{\hyper@linkurl{#2}{#1}}
\begingroup
\catcode`\_=\active
\gdef_#1{\ensuremath{\sb{\mathrm{#1}}}}
\endgroup
\mathcode`\_=\string"8000
\catcode`\_=12\relax

\usepackage[a4paper,twoside,lmargin=1in,rmargin=1in,tmargin=1in,bmargin=1in,marginparwidth=0.75in]{geometry}
\usepackage{framed}

\definecolor{shadecolor}{gray}{0.95}
\usepackage{longtable}
\usepackage[normalem]{ulem}
\usepackage{fancyvrb}
\usepackage{fancyhdr}
\usepackage{graphicx}
\usepackage{marginnote}

\renewcommand{\@cite}[1]{#1}


\renewcommand*{\marginfont}{\itshape\footnotesize}

\def\Gin@extensions{.pdf,.png,.jpg,.mps,.tif}

  \pagestyle{fancy}

\usepackage[pdftitle={Data Aggregators},
 pdfauthor={}]{hyperref}
\hyperbaseurl{}

	 \paperwidth210mm
	 \paperheight297mm
              
\def\@pnumwidth{1.55em}
\def\@tocrmarg {2.55em}
\def\@dotsep{4.5}
\setcounter{tocdepth}{3}
\clubpenalty=8000
\emergencystretch 3em
\hbadness=4000
\hyphenpenalty=400
\pretolerance=750
\tolerance=2000
\vbadness=4000
\widowpenalty=10000

\renewcommand\section{\@startsection {section}{1}{\z@}%
     {-1.75ex \@plus -0.5ex \@minus -.2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\Large\bfseries}}
\renewcommand\subsection{\@startsection{subsection}{2}{\z@}%
     {-1.75ex\@plus -0.5ex \@minus- .2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\Large}}
\renewcommand\subsubsection{\@startsection{subsubsection}{3}{\z@}%
     {-1.5ex\@plus -0.35ex \@minus -.2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\large}}
\renewcommand\paragraph{\@startsection{paragraph}{4}{\z@}%
     {-1ex \@plus-0.35ex \@minus -0.2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\normalsize}}
\renewcommand\subparagraph{\@startsection{subparagraph}{5}{\parindent}%
     {1.5ex \@plus1ex \@minus .2ex}%
     {-1em}%
     {\reset@font\normalsize\bfseries}}


\def\l@section#1#2{\addpenalty{\@secpenalty} \addvspace{1.0em plus 1pt}
 \@tempdima 1.5em \begingroup
 \parindent \z@ \rightskip \@pnumwidth 
 \parfillskip -\@pnumwidth 
 \bfseries \leavevmode #1\hfil \hbox to\@pnumwidth{\hss #2}\par
 \endgroup}
\def\l@subsection{\@dottedtocline{2}{1.5em}{2.3em}}
\def\l@subsubsection{\@dottedtocline{3}{3.8em}{3.2em}}
\def\l@paragraph{\@dottedtocline{4}{7.0em}{4.1em}}
\def\l@subparagraph{\@dottedtocline{5}{10em}{5em}}
\@ifundefined{c@section}{\newcounter{section}}{}
\@ifundefined{c@chapter}{\newcounter{chapter}}{}
\newif\if@mainmatter 
\@mainmattertrue
\def\chaptername{Chapter}
\def\frontmatter{%
  \pagenumbering{roman}
  \def\thechapter{\@roman\c@chapter}
  \def\theHchapter{\roman{chapter}}
  \def\thesection{\@roman\c@section}
  \def\theHsection{\roman{section}}
  \def\@chapapp{}%
}
\def\mainmatter{%
  \cleardoublepage
  \def\thechapter{\@arabic\c@chapter}
  \setcounter{chapter}{0}
  \setcounter{section}{0}
  \pagenumbering{arabic}
  \setcounter{secnumdepth}{6}
  \def\@chapapp{\chaptername}%
  \def\theHchapter{\arabic{chapter}}
  \def\thesection{\@arabic\c@section}
  \def\theHsection{\arabic{section}}
}
\def\backmatter{%
  \cleardoublepage
  \setcounter{chapter}{0}
  \setcounter{section}{0}
  \setcounter{secnumdepth}{2}
  \def\@chapapp{\appendixname}%
  \def\thechapter{\@Alph\c@chapter}
  \def\theHchapter{\Alph{chapter}}
  \appendix
}
\newenvironment{bibitemlist}[1]{%
   \list{\@biblabel{\@arabic\c@enumiv}}%
       {\settowidth\labelwidth{\@biblabel{#1}}%
        \leftmargin\labelwidth
        \advance\leftmargin\labelsep
        \@openbib@code
        \usecounter{enumiv}%
        \let\p@enumiv\@empty
        \renewcommand\theenumiv{\@arabic\c@enumiv}%
	}%
  \sloppy
  \clubpenalty4000
  \@clubpenalty \clubpenalty
  \widowpenalty4000%
  \sfcode`\.\@m}%
  {\def\@noitemerr
    {\@latex@warning{Empty `bibitemlist' environment}}%
    \endlist}

\def\tableofcontents{\section*{\contentsname}\@starttoc{toc}}
\parskip0pt
\parindent1em
\def\Panel#1#2#3#4{\multicolumn{#3}{){\columncolor{#2}}#4}{#1}}
\newenvironment{reflist}{%
  \begin{raggedright}\begin{list}{}
  {%
   \setlength{\topsep}{0pt}%
   \setlength{\rightmargin}{0.25in}%
   \setlength{\itemsep}{0pt}%
   \setlength{\itemindent}{0pt}%
   \setlength{\parskip}{0pt}%
   \setlength{\parsep}{2pt}%
   \def\makelabel##1{\itshape ##1}}%
  }
  {\end{list}\end{raggedright}}
\newenvironment{sansreflist}{%
  \begin{raggedright}\begin{list}{}
  {%
   \setlength{\topsep}{0pt}%
   \setlength{\rightmargin}{0.25in}%
   \setlength{\itemindent}{0pt}%
   \setlength{\parskip}{0pt}%
   \setlength{\itemsep}{0pt}%
   \setlength{\parsep}{2pt}%
   \def\makelabel##1{\upshape ##1}}%
  }
  {\end{list}\end{raggedright}}
\newenvironment{specHead}[2]%
 {\vspace{20pt}\hrule\vspace{10pt}%
  \phantomsection\label{#1}\markright{#2}%

  \pdfbookmark[2]{#2}{#1}%
  \hspace{-0.75in}{\bfseries\fontsize{16pt}{18pt}\selectfont#2}%
  }{}
      \def\TheFullDate{2012-01-15 (revised: 15 January 2012)}
\def\TheID{\makeatother }
\def\TheDate{2012-01-15}
\title{Data Aggregators}
\author{}\makeatletter 
\makeatletter
\newcommand*{\cleartoleftpage}{%
  \clearpage
    \if@twoside
    \ifodd\c@page
      \hbox{}\newpage
      \if@twocolumn
        \hbox{}\newpage
      \fi
    \fi
  \fi
}
\makeatother
\makeatletter
\thispagestyle{empty}
\markright{\@title}\markboth{\@title}{\@author}
\renewcommand\small{\@setfontsize\small{9pt}{11pt}\abovedisplayskip 8.5\p@ plus3\p@ minus4\p@
\belowdisplayskip \abovedisplayskip
\abovedisplayshortskip \z@ plus2\p@
\belowdisplayshortskip 4\p@ plus2\p@ minus2\p@
\def\@listi{\leftmargin\leftmargini
               \topsep 2\p@ plus1\p@ minus1\p@
               \parsep 2\p@ plus\p@ minus\p@
               \itemsep 1pt}
}
\makeatother
\fvset{frame=single,numberblanklines=false,xleftmargin=5mm,xrightmargin=5mm}
\fancyhf{} 
\setlength{\headheight}{14pt}
\fancyhead[LE]{\bfseries\leftmark} 
\fancyhead[RO]{\bfseries\rightmark} 
\fancyfoot[RO]{}
\fancyfoot[CO]{\thepage}
\fancyfoot[LO]{\TheID}
\fancyfoot[LE]{}
\fancyfoot[CE]{\thepage}
\fancyfoot[RE]{\TheID}
\hypersetup{citebordercolor=0.75 0.75 0.75,linkbordercolor=0.75 0.75 0.75,urlbordercolor=0.75 0.75 0.75,bookmarksnumbered=true}
\fancypagestyle{plain}{\fancyhead{}\renewcommand{\headrulewidth}{0pt}}

\date{}
\usepackage{authblk}

\providecommand{\keywords}[1]
{
\footnotesize
  \textbf{\textit{Index terms---}} #1
}

\usepackage{graphicx,xcolor}
\definecolor{GJBlue}{HTML}{273B81}
\definecolor{GJLightBlue}{HTML}{0A9DD9}
\definecolor{GJMediumGrey}{HTML}{6D6E70}
\definecolor{GJLightGrey}{HTML}{929497} 

\renewenvironment{abstract}{%
   \setlength{\parindent}{0pt}\raggedright
   \textcolor{GJMediumGrey}{\rule{\textwidth}{2pt}}
   \vskip16pt
   \textcolor{GJBlue}{\large\bfseries\abstractname\space}
}{%   
   \vskip8pt
   \textcolor{GJMediumGrey}{\rule{\textwidth}{2pt}}
   \vskip16pt
}

\usepackage[absolute,overlay]{textpos}

\makeatother 
      \usepackage{lineno}
      \linenumbers
      
\begin{document}

             \author[1]{Dr. P.  Prabhakar}

             \author[2]{S. Nageswara  Rao}

             \affil[1]{  M.Tech Student, Dept of CSE, Madanapalle Institute of Technology and Science, AP, India.}

\renewcommand\Authands{ and }

\date{\small \em Received: 15 December 2011 Accepted: 31 December 2011 Published: 15 January 2012}

\maketitle


\begin{abstract}
        


Typically a user desires to obtain the value of some aggregation function over distributed data items. We present a low-cost, scalable technique to answer continuous aggregation queries using a network of aggregators of dynamic data items. In such a network of data aggregators, each data aggregator serves a set of data items at specific coherencies. Our technique involves decomposing a client query into sub-queries and executing sub-queries on judiciously chosen data aggregators with their individual subquery incoherency bounds. We provide a technique for getting the optimal set of sub-queries with their incoherency bounds, which satisfies client query?s coherency requirement with least number of refresh messages sent from aggregators to the client. For estimating the number of refresh messages, we build a query cost model which can be used to estimate the number of messages required to satisfy the client specified incoherency bound. Performance results using real-world traces show that our cost based query planning leads to queries being executed using less than one third the number of messages required by existing schemes.

\end{abstract}


\keywords{Content distribution network, continuous query, online decision making, data dissemination, coherency, performance.}

\begin{textblock*}{18cm}(1cm,1cm) % {block width} (coords) 
\textcolor{GJBlue}{\LARGE Global Journals \LaTeX\ JournalKaleidoscope\texttrademark}
\end{textblock*}

\begin{textblock*}{18cm}(1.4cm,1.5cm) % {block width} (coords) 
\textcolor{GJBlue}{\footnotesize \\ Artificial Intelligence formulated this projection for compatibility purposes from the original article published at Global Journals. However, this technology is currently in beta. \emph{Therefore, kindly ignore odd layouts, missed formulae, text, tables, or figures.}}
\end{textblock*}


\let\tabcellsep& 	 	 		 
\section[{INTRODUCTION}]{INTRODUCTION}\par
pplication such as auctions, personal portfolio for financial decisions, sensors based monitoring, route planning based on traffic information, etc., make extensive use of dynamic data. For such applications, data from one or more independent data sources may be aggregated to determine if some action is warranted. Given the increasing number of such applications that make use of highly dynamic data, there is significant interest in systems that can efficiently deliver the relevant updates automatically. Many data intensive applications delivered over the Web suffer from performance and scalability issues. Content distribution networks (CDNs) solved the problem for static content using caches at the edge nodes of the networks. CDNs continue to evolve to serve more and more dynamic applications \hyperref[b0]{[1,}\hyperref[b1]{2]}. A dynamically generated web page is usually assembled using a number of static or dynamically generated fragments. The static fragments are served from the local caches whereas dynamic fragments are created either by using the cached data Author ? : M.Tech Student, Dept of CSE, Madanapalle Institute of Technology and Science, AP, India. E-mail : prabhakar.mth@gmail.com Author ? : Assistant Professor, Dept of CSE, Madanapalle Institute of Technology and Science, AP, India. E-mail : nag\textunderscore sirisala@yahoo.com or by fetching the data items from the origin data sources. One important question for satisfying client requests through a network of nodes is how to select the best node(s) to satisfy the request. For static pages content requested, proximity to the client and load on the nodes are the parameters generally used to select the appropriate node \hyperref[b2]{[3]}. In dynamic CDNs, while selecting the nodes node(s) to satisfy the client request, the central site (top-level CDN node) has to ensure that page/data served meets client's coherency requirements also. Techniques to efficiently serve fast changing data items with guaranteed incoherency bounds have been proposed in the literature \hyperref[b3]{[4,}\hyperref[b4]{5]}. Such dynamic data dissemination networks can be used to disseminate data such as stock quotes, temperature data from sensors, traffic information, and network monitoring data. In this paper we propose a method to efficiently answer aggregation queries involving such data items. In data dissemination schemes proposed in literature \hyperref[b3]{[4,}\hyperref[b10]{11]}, a hierarchical network of data aggregators is employed such that each data aggregator serves the data item at some guaranteed incoherency bound. Incoherency of a data item at a given node is defined as the difference in value of the data item at the data source and the value at that node. Although CDNs use page-purge \hyperref[b7]{[8]} based coherency management, we assume that in dynamic data dissemination networks, these messages carry the new data values thereby an invalidation message becomes a refresh message. For maintaining a certain incoherency bound, a data aggregator gets data updates from the data source or some higher level data aggregator so that the data incoherency is not more than the data incoherency bound. In a hierarchical data dissemination network a higher level aggregator guarantees a tighter incoherency bound compared to a lower level aggregator. Thus, data refreshes are pushed from the data sources to the clients through the network of aggregators.\par
Data incoherency: data accuracy can be specified in terms of incoherency of a data item, defined as the absolute difference in value of the data item at the data source and the value known to a client of the data. Let ? i (t ) denote the value of i th data item at the data source at time t; and let the value the data item known to the client be u i (t ). Then the data incoherency at the client is given by |u i (t )-? i (t )|. For a data item which needs to be refreshed at an incoherency bound C aA ( D D D D )\par
data refresh message is sent to the client as soon as data exceeds C, i.e., |u i (t )-? i (t )|>C.\par
Network of data aggregators: Data aggregators are one kind of secondary server it serves as data sources (data items). The data refreshes can be done using two mechanisms.(a)Push based mechanism data source send update messages to client on their own.(b)Pull based mechanism data sources send messages to the client only when client makes a request. For scalable handling of push based data dissemination, network of DA's are proposed in the literature \hyperref[b11]{[12,}\hyperref[b14]{15,}\hyperref[b15]{16]}. 
\section[{Sources}]{Sources}\par
Clients Figure 1 : Data dissemination network for multiple data items\par
In such network of DA's, data refreshes occur from data sources to the client through one or more DA's. In this paper we assume that each DA maintains its configured incoherency bounds for various data items. Dissemination networks for various data items can be overlaid over a single network of data aggregators as shown in Figure 1. Thus, From a data dissemination capability point of view, each data aggregator (DA) is characterized by a set of (d i ,c i ) pairs, where d i is a data item which the DA can disseminate at an incoherency bound C i .The configured incoherency bound of data item at a DA can be maintained using any of following methods: (a) the data source refreshes the data value of the DA whenever DA's incoherency bound is about to get violated. This method is scalability problems. (b) data aggregators with tighter incoherency bound help the DA to maintain its incoherency bound in scalable manner as explained in \hyperref[b3]{[4,}\hyperref[b6]{7]}.\par
Example 1: In a network of data aggregators managing data items D1-D4, various aggregators can be characterized as-A1: \{(D1, 0.5), (D3, 0.2)\} A2: \{(D1, 1.0), (D2, 0.1), (D4, 0.2)\}\par
Aggregator A1 can serve values of D1 with an incoherency bound greater than or equal to 0.5 whereas A2 can disseminate the same data item at a looser incoherency bound of 1.0 or more. Usually, client is interested in an aggregation of these dynamic data items at a certain incoherency bound. These continuous queries are used to monitor changes in dynamic data and provide results useful for online decision-making.\par
For generating the result of a query, data from multiple sources is required. As a result, the query has to be evaluated either at data aggregators or at the client. In this work, our aim is to satisfy the client's query requirements while minimizing the query execution cost in terms of number of dissemination messages. Towards that end, we have achieved the following: 1. Developed techniques for estimating the cost of disseminating a data item, at specified incoherency bound. 2. Using the estimated data dissemination cost, we developed query cost model for estimating the cost of executing an incoherency bounded continuous query. 3. Used the query cost model for assigning a client query to one or more data aggregators so that the query can be executed with the least number of messages.\par
Our work involves dividing the client query into sub-queries and allocating it to different data aggregators for optimal execution. In comparison, all the related work in literature \hyperref[b2]{[3,}\hyperref[b4]{5]} propose getting individual data items from the aggregators which, as we show in this report, leads to large number of dissemination messages. In the rest of the Introduction, we present basic concepts underlying incoherency bounded continuous query execution using a distributed network of data aggregators. 
\section[{a) Problem Statement and Contributions}]{a) Problem Statement and Contributions}\par
In this paper, we develop query cost model for aggregation query involving multiple data items: -Additive aggregation with each data item possibly different weights, and -MIN/MAX aggregation queries. The weighted aggregation query can be mathematically written as: ( ) ( )1 q q q i i i n s i v t s t w = = = × ?\textbf{(1)}\par
V s q is the value of a client query q involving n q data items with the weight of the i th data item being w q i , 1< i< n q . s i (t ) is the value of the i th data item at the data source at time t. Such a query encompasses SQL aggregation operators SUM and AVG besides general weighted aggregation queries such as portfolio queries, involving aggregation of stock prices, weighted with number of shares of stocks in the portfolio. Due to( D D D D )\par
Year space limitations, we are not presenting execution schemes for other aggregation queries such as MIN/MAX. Interested readers are referred to \hyperref[b12]{[13]} for the extended version of this paper.\par
Let the value of i th data item, in Equation ( \hyperref[formula_1]{1}), known to the client/DA be d i (t). Then the data incoherency is given by |s i (t)-d i (t)|. For a data item which needs to be disseminated at an incoherency bound C the data refresh is sent to the client or lower level DA, if the |s i (t)d i (t)| is more than C. If user specified incoherency bound for the query q is C q , then the dissemination network has to ensure that: ( ) ( )1 q q q i i i n i s t d w c = ? × ? ?\textbf{(2)}\par
Whenever data values at sources change such that query incoherency bound is violated, the updated value(s) is disseminated to the client. If the network of aggregators can ensure that the i th data item has incoherency bound C i then the following condition ensure that the query incoherency bound C q is satisfied:1 q q q i i n i c w c = × ? ?\textbf{(3)}\par
For additive aggregation queries, a client specified query incoherency bound needs to be translated into incoherency bounds for individual data items or sub-queries such that these satisfy Equation \hyperref[b2]{(3)}.\par
MIN/MAX queries involve of data items, whose extremes are the required result, and its incoherency bound. In a MIN (MAX) query, even if one data value changes it is possible that that value is minimum (maximum) thus individual data incoherency bound cannot be more than query incoherency bound. Thus in case of MIN/MAX queries the dissemination network has to ensure that Ci ? Cq for all the data items appearing in the query. 
\section[{b) Summary of Distributed Execution approach}]{b) Summary of Distributed Execution approach}\par
Consider a client query Q=50 D1 + 200 D2 + 150 D3 with a required incoherency bound of 80 (in a stock portfolio D1, D2, D3 can be different stocks and incoherency bound can be \$80).We want to execute this query over data aggregators given in Example1, minimizing number of refreshes. There are various options for the client to get the data items.\par
The client may get the data items D1, D2 and D3 separately. The query incoherency bounds can be divided among data items in various ways while satisfying Equation \hyperref[formula_4]{3}. In this report, we show that getting data items independently is a costly option. This strategy ignores facts that the client is interested only in the aggregated value of the data items and various aggregators can disseminate more than one data item.\par
If a single DA can disseminate all three data items required to answer the client query, the DA can construct a composite data item corresponding to the client query (Sq=50 D1 + 200 D2+ 150 D3 ) and disseminate the result to the client so that the query incoherency bound is not violated. It is obvious that if we get the query result from a single DA, the number of refreshes will be minimum (as in this case data item updates may cancel out each other, thereby keeping the query result within the incoherency bound). As different data aggregators disseminate different subsets of data items, no data aggregator may have all the data items required to execute the client query, which is indeed the case in Example1. Further, even if an aggregator can disseminate all the data items, it may not be able to satisfy the query coherency requirements. In such cases, the query has to be executed with data from multiple aggregators.\par
Another option is to divide the query into a number of sub-queries and get their values from individual DAs. In that case, the client query result is obtained by combining the results of more than one sub-query. For the DAs given in Example1, the query Q can be divided in two alternative ways:Plan1: A1 \{50 D1 + 150 D3 \}; D2 \{D2 \} Plan2: A1 \{D3 \}; D2 \{50 D1, + 200 D2 \}\par
i.e., in plan1 result of sub-query 50 D1 + 150 D3 is served by A1 whereas value of (or 200 D2 ) by D2 is served by A2. In plan2, value of D3 is served by A1 whereas result of sub-query 50 D1 + 200 D2 is served by A2. Combining them at the client gives the query result.\par
Selecting the optimal plan among various options is not-trivial. As a thumb-rule, we should be selecting the plan with lesser number of sub-queries. But that is not guaranteed to be the plan with the least number of messages. Further, we should select the subqueries such that updates to various data items appearing in a sub-query have more chances of cancelling each other as that will reduce the need for refresh to the client (Equation \hyperref[formula_3]{2}). In the above example, if updates to D1 and D3 are such that when D1 increases, D3 decreases, and vice-versa, then selecting plan1 may be beneficial. We give an algorithm to select the query plan based on these observations. While solving the above problem of selecting the optimal plan we ensure that each data item for a client query is disseminated by one and only one data aggregator. Although a query can be divided in such a way that a single data item is served by multiple DAs multiple aggregators, increasing the unnecessary processing load. By dividing the client query into disjoint sub-queries we ensure that a data item update is processed only once for each query (For example, in case of paid data subscriptions it is not prudent to get the same data item from the multiple sources).\par
The query incoherency bound needs to be divided among sub-query incoherency bounds such that, besides satisfying the client coherency requirements, the chosen DA (where the sub-query is to be executed) is capable of satisfying the allocated subquery incoherency bound. For example, in plan1 allocated incoherency bound to the sub-query 50D1 + 150D3 should be greater than 55 (=50*0.5+150*0.2) as that is the tightest incoherency bound which the aggregator D1 can satisfy. We prove that the number of refreshes depends on the division of the query incoherency bounds among sub-query incoherency bounds.\par
Thus, what we need is a method of (a) optimally dividing client query into sub-queries and (b) assigning incoherency bounds to them; such that (c) selected sub-queries can be executed at chosen. And (d) total query execution cost, in terms of number of refreshes, is minimized. 
\section[{II.}]{II.} 
\section[{DATA DISSEMINATION COST MODEL}]{DATA DISSEMINATION COST MODEL}\par
Cost of disseminating a data item at a certain given incoherency bound C can be estimated by combining two models: 
\section[{a) Incoherency bound model}]{a) Incoherency bound model}\par
The incoherency bound model is used for estimating dependency of data dissemination cost over the desired incoherency bound. As per this model, we have shown in \hyperref[b12]{[13]} that the number of data refreshes is inversely proportional to the square of the incoherency bound (1/C2 ). Similar result was earlier reported in \hyperref[b3]{[4]} where the data dynamics was modeled as a random walk process.Data dissemination cost ? 1/C 2 (4) b) Data synopsis Model\par
The Data synopsis model is used for estimating the effect of data dynamics on number of data refreshes. We define a data dynamics measure called, sumdiff, to obtain a synopsis of the data for predicting the dissemination cost. The number of update messages for a data item is likely to be higher if the data item changes more in a given time window. Thus we hypothesize that cost of data dissemination for a data item will be proportional to data synopsis, called sumdiff, defined as: ( )1 s i i i R s s ? = ? ?\textbf{(5)}\par
Where S i and S i-1 are the sampled values of the data item at i th and (i-1) th time instances (consecutive ticks). Data sumdiff can be maintained at the source or aggregators. For calculating this quantity, the data source can accumulate the absolute value of changes in data items or the data aggregator can estimate this quantity using changes in pushed values. Next we use this result for developing the query cost model.\par
Consider a case where a query consists of two data items P and Q with weights w p and w q respectively; and we want to estimate its dissemination cost. If data items are disseminated separately query sumdiff will be:\par
Instead, if the aggregator uses the information Instead, if the aggregator uses the information that client is interested in a query over P and Q (rather than their individual values), it makes a composite data item w pP + w q q and disseminates that data item then the query sumdiff will be: \hyperref[b6]{(7)} R query is clearly less than or equal compared to R data . Thus we need to estimate the sumdiff of an aggregation query (i.e., R query ) given the sumdiff values of individual data items (i.e., R p and R q ). Only data aggregators are in position to calculate R query as different data items may be from different sources. 
\section[{III.}]{III.} 
\section[{QUERY COST MODEL}]{QUERY COST MODEL}\par
For getting an estimation of the query dissemination cost what we need is R query whereas we know R p and R q (in Equation ( 6) and \hyperref[b6]{(7)}. As different data items may be disseminated by different servers, R query can be calculated only at data aggregators. If two data items are correlated such that if value of one data item increases other also increases, then R query will be closer R data ; whereas if the data items are inversely correlated then R query will be much less than R data . Thus, institutively, we can represent the relationship between R query and sumdiff of individual data items involved using a correlation measure between data items. Specifically, if ? is the correlation measure then R query can be written as:\par
( )2 2 2 2 2 2 p p q q p p q q query R w R w R w R w R ? ? + +\textbf{(8)}\par
The correlation measure is defined such that-1??? +1, so, Rquery will always be less than |w p R p +w q R q | (as explained earlier) and always be more than |w p R p ? w q R q |. R data = w p R p + w q R q =w p ?| pi -p i-1 | +w q ?| q i ?q i-1 | R query =?|w p (p i ?p i-1 )+w q (q i ?q i-1 )| by data items P and Q. Cosine similarity is a widely used measure in information retrieval domain where documents are represented using a vector-space model and document similarity is measured using cosine of angle between two document representations. For data streams P and Q, ?? can be calculated as: (9) a) Executing queries using sub queries For executing an incoherency bounded continuous query, a query plan is required which includes the set of sub-queries, their individual incoherency bounds and data aggregators which can execute these sub-queries. We need to find the optimal query execution plan which satisfies client coherency requirement with the least number of refreshes. What we need is a mechanism to: While satisfying the following conditions identified in Section 1.2: Condition 1. Query incoherency bound is satisfied.\par
Condition 2. The chosen DA should be able to provide all the data items appearing in the sub-query assigned to it. Condition 3. Data incoherency bounds at the chosen DA should be such that the sub-query incoherency bound can be satisfied at the chosen DA. Objective: Number of refreshes should be minimized. 
\section[{b) Minimum Cost}]{b) Minimum Cost}\par
Figure 2 shows the outline of greedy heuristics where different criteria (?) can be used to select subqueries. In this section we describe the case where the estimate of query execution cost is minimized in each step of the algorithm (min-cost) whereas in the next section we present the case where gain due to executing a query using sub-queries is maximized (maxgain). 
\section[{c) Query Plan with Pre-decided Incoherency Bound Allocation}]{c) Query Plan with Pre-decided Incoherency Bound Allocation}\par
For the given client query (q) and mapping between data aggregators and the corresponding \{data-item, data incoherency bound \} pairs (f : D?(S, C )) maximal sub-queries can be obtained for each data aggregator. Let A be the set of such maximal sub queries. In this set, each query a ? A can be disseminated by a designated data aggregator at the assigned incoherency bound. For each sub-query a ?A, its sumdiff Ra is calculated. Using the set A and sub-query sumdiffs, we use the algorithm outlined in Figure 2 to get the set of sub-queries minimizing the query cost. 
\section[{In this Figure each sub-query a ? A is represented by}]{In this Figure each sub-query a ? A is represented by}\par
the set of data items covered by it. As we need to minimize the query cost, a sub-query with minimum cost per data item is chosen in each iteration of the algorithm i.e., criteria ? ? minimize (Ra/Ca 2 |a|).\par
All data items covered by the selected sub query are removed from all the remaining sub-queries in A before performing the next iteration. 
\section[{Algorithm:}]{Algorithm:}\par
Result  The decision is taken based on client query information. The greedy method is the most straight forward method. It is popular for obtaining the optimized solutions. In the greedy method there are some important activities. (a) A selection of solution from the given input domain is performed. (b). The feasibility of the solution is performed and then all the feasible solutions are obtained. (c) From the set of feasible solutions, the particular solution that minimizes or maximizes the given objective function is obtained. Such a solution is called optimal solution. For an algorithm that uses greedy method works in stages. At each stage only one input is considered at a time. Based on this input it is decided whether particular input gives the optimal solution or not. 
\section[{d) Maximum Gain}]{d) Maximum Gain}\par
In this section we present an algorithm which, instead of minimizing the estimated query execution cost, maximizes the estimated gains of executing client query using sub-queries. In this algorithm, for each subquery, we calculate the relative gain of executing it by finding the sumdiff difference between cases when each data item is obtained separately and when all the data items are aggregated as a single sub-query. (i.e., maximal sub-query). 
\section[{IV.}]{IV.} 
\section[{Related work}]{Related work}\par
We divide the related work on scalable answering of aggregation queries over a network of data aggregators in to two interrelated topics.( D D D D ) E 2012 Year ? ?? ? ? ? ? ? 1 1 1 1 2 2 i i i i i i i i p p q q p p q q ? ? ? ? ? ? ? ? ? ? ? ? ? a) 
\section[{Answering Incoherency bounded aggregation queries}]{Answering Incoherency bounded aggregation queries}\par
Various mechanism for efficiently answering incoherency bounded aggregation queries over continuously changing data items are proposed in the literature \hyperref[b2]{[3,}\hyperref[b3]{4,}\hyperref[b8]{9]}. i.e., in this thesis, to develop and evaluate client-pull-based techniques for refreshing data so that the results of the queries over distributed data can be correctly reported, conforming to the limited incoherency acceptable to the users. Here considered the problem of answering queries for online decision making at web data aggregators.\par
Our work distinguishes itself by employing subquery based evaluation to minimize number of refreshes. Pull based data dissemination techniques, where client or data aggregators pull data items such that query requirements are met, are described in \hyperref[b2]{[3]}. For minimizing the number of pulls, both predict data values and pull instances. In comparison, we use push based mechanism to refresh sub-query values at the client. In \hyperref[b3]{[4]}, authors propose push based scheme using data filters at the sources. i.e., distributed data sources continuously stream updates to a centralized processor that monitors continuous queries over the distributed data. Based on we specified a new approach for reducing communication cost in an environment of centralized continuous query processing over distributed data streams.\par
This approach hinges on specifying precision constraints for continuous queries, which are used to generate adaptive filters at remote data sources that significantly reduce update stream rates while still guaranteeing sufficient precision of query results at all times. And enables users or applications to trade precision for lower communication cost at a fine granularity by individually adjusting precision constraints of continuous queries. Imprecision of query results is bounded numerically so applications need not deal with any uncertainty. To validate our approach we performed a number of experiments using simulations and a real network monitoring implementation approach in achieving low communication overhead. According to that work can an aggregation query, the number of refresh messages can be minimized by performing incoherency bound allocation to individual data items such that the number of messages from different data sources is the same. Instead we execute more dynamic assigning incoherency bounds. And minimizing the total number of messages send by DAs. Like us ,authors of \hyperref[b8]{[9]},also assume that dissemination tree from sensor node[data source] to root[client]already exist; and they also install error filters on partial aggregates (similar to in coherency bound assign to sub queries) but, in our work each data aggregator can only discriminates data at some pre-specified incoherency bound depending on its capability where as such a constraints does not exist for \hyperref[b8]{[9]}.further, we also be give method to select partial aggregates (sub queries)to be used to answering the query.\par
Authors propose using data filters at the sources; instead we assign incoherency bounds to subqueries which reduce the number of refreshes for query evaluation, Further, we propose that more dynamic data items should be executed as part of larger sub-query. In \hyperref[b7]{[8]}, i.e., here discuss various techniques of reorganizing a data dissemination network when client requirements change. Instead, we try to answer the client query using the existing network. Reorganizing aggregators is a longer term activity whereas query planning can be done for short as well as long running queries on more dynamic basis.\par
Like us, author of \hyperref[b8]{[9]} also assume that dissemination tree from sensor nodes (data-sources) to root (clients) already exists. In-network data aggregation has been recently proposed as an effective means to reduce the number of messages exchanged in wireless sensor networks. Nodes of the network form an aggregation tree, in which parent nodes aggregate the values received from their children and propagate the result to their own parents. However, this schema provides little flexibility for the end-user to control the operation of the nodes in a data sensitive manner. For large sensor networks with severe energy constraints, the reduction (in the number of messages exchanged) obtained through the aggregation tree might not be sufficient. In this thesis we present new algorithms for obtaining approximate aggregate statistics from large sensor networks. The user specifies the maximum error that he is willing to tolerate and, in turn, our algorithms program the nodes in a way that seeks to minimize the number of messages exchanged in the network, while always guaranteeing that the produced estimate lies within the specified error from the exact answer. And they also install error filters on partial aggregates. But in our work, each data aggregators can only disseminate data some pre-specified incoherency bound depending on its capability whereas such a constraint does not exist for \hyperref[b8]{[9]}. Further, we also give a method to select partial aggregates (sub queries) to be used for answering the query. In \hyperref[b11]{[12]} Pull based data dissemination techniques, where clients or data aggregators pull data items such that query requirements are met, are described in \hyperref[b2]{[3]}. i.e., we develop and evaluate client-pull-based techniques for refreshing data so that the results of the queries over distributed data can be correctly reported, conforming to the limited incoherency acceptable to the users. For minimizing the number of pulls, both model the individual data items and predict data values. In comparison, we consider the situation where different sub-queries, involving multiple data items, can be evaluated at different nodes. Further, incoherency bound is applied over the sub-query rather than to Spatial and temporal correlations between sensor data are used to reduce data refresh instances in \hyperref[b4]{[5,}\hyperref[b5]{6]}. We also consider correlation in terms of cosine similarity between data items, but we use it for dividing client query into sub-queries. 
\section[{b) Construction and maintenance of network of data aggregators}]{b) Construction and maintenance of network of data aggregators}\par
Authors of \hyperref[b0]{[1,}\hyperref[b1]{2,}\hyperref[b7]{8]} describe Construction and maintenance of hierarchical network of data aggregators for providing scalability and fidelity in disseminating dynamic data items to large number of clients.. In these works, fidelity is defined as fraction of time when the client coherence requirements are met. Each data aggregators is given client requirements in the form of data items and their respective incoherency bounds. Instead we use such networks for efficiently answering client's aggregation queries.\par
One can use client queries to optimally construct a network of data aggregators while, on the other hand, one can also use a given network of aggregators to efficiently answer client queries. Authors of \hyperref[b0]{[1,}\hyperref[b1]{2,}\hyperref[b7]{8]} deal with the first part where as we have studied the second part. Changes in data dynamics may lead to reorganization of the network of data aggregators which, in turn necessitate changes in query plans. Whereas query plan can change more often depending on data dynamics.\par
Instead of optimizing fidelity of data items at data aggregators, as proposed in \hyperref[b1]{[2]}, using our work, one can optimize fidelity all the way up to client queries. Fidelity of a data item can be approximately calculated as number of dissemination messages multiplied by the total delay in the message transmission. Author of \hyperref[b1]{[2]} assume that each client's requirements are fulfilled by a single data aggregator. But in case of data aggregators may need to disseminate a large number of data items which will lead to processing large number of refresh messages, hence increase in delay. Thus , each client getting all its data items from a single data aggregators(using a single sub-query) is optimal from number of messages point of view but not necessarily from the query fidelity point of view. By using our work, one can model expected number of messages for client query. Thus, our work can complement the of \hyperref[b1]{[2]} for end-to-end (source-to-client) fidelity optimization.\par
V. 
\section[{Conclusion and future work}]{Conclusion and future work}\par
In this literature presents a cost based approach to minimize the number of refreshes required to execute an incoherency bounded continuous query. For optimal execution we divide the query into subqueries and evaluate each sub-query at a chosen aggregator. Performance results show that by our method the query can be executed using less than one third the messages required for existing schemes.\par
Further we showed that by executing queries such that more dynamic data items are part of a larger sub-query we can improve performance. Our query cost model can also be used for other purposes such as load balancing various aggregators, optimal query execution plan at an aggregator node, etc.\par
Developing efficient strategies for multiple invocations of our algorithm, considering hierarchy of data aggregators. Another area for future research is changing a query plan as data dynamics changes. Another area of our future work is using the cost model for these applications and developing the cost model for more complex queries.\begin{figure}[htbp]
\noindent\textbf{}\includegraphics[]{image-2.png}
\caption{\label{fig_0}}\end{figure}
     		 		\backmatter  			  				\begin{bibitemlist}{1}
\bibitem[ NEFSC Scientific Computer System]{b9}\label{b9} 	 		\textit{},  		 \url{http://sole.wh.whoi.edu/jmanning//cruise/serve1et.cgi}  	 	 		\textit{NEFSC Scientific Computer System}  		 	 
\bibitem[ Pearson Product moment correlation coefficient]{b10}\label{b10} 	 		\textit{},  		 \url{http://www.nyx.net/\textasciitilde tmacfarl/STAT\textunderscore TUT/correlat.ssi/}  	 	 		\textit{Pearson Product moment correlation coefficient}  		 	 
\bibitem[Fei ()]{b7}\label{b7} 	 		\textit{A Novel Approach to Managing Consistency in Content Distribution},  		 			Zongming Fei 		.  		2001. WCW.  	 
\bibitem[Olston et al. ()]{b5}\label{b5} 	 		\textit{Adaptive Filter for Continuous Queries over Distributed Data Streams},  		 			C Olston 		,  		 			J Jiang 		,  		 			J Widom 		.  		2003.  	 
\bibitem[Hochbaum ()]{b6}\label{b6} 	 		‘Approximation algorithms for the set covering and vertex cover problems’.  		 			D S Hochbaum 		.  	 	 		\textit{SIAM Journal on Computing}  		1982. 11  (3) .  	 
\bibitem[Shah et al. ()]{b16}\label{b16} 	 		\textit{Client Assignment in Content Dissemination Networks for Dynamic Data},  		 			S Shah 		,  		 			K Ramamritham 		,  		 			C Ravishankar 		.  		2005.  	 
\bibitem[Agrawal et al. ()]{b11}\label{b11} 	 		\textit{Construction of a Temporal Coherency Preserving Dynamic Data Dissemination networks},  		 			S Agrawal 		,  		 			K Ramamritham 		,  		 			S Shah 		.  		2004.  	 	 (RTSS) 
\bibitem[Davis et al. ()]{b0}\label{b0} 	 		\textit{Edge Computing: Extending Enterprise Applications to the Edge of the Internet},  		 			A Davis 		,  		 			J Parikh 		,  		 			W Weihl 		.  		2004. WWW.  	 
\bibitem[Gupta et al. ()]{b8}\label{b8} 	 		\textit{Executing Incoherency Bounded Continuous Queries at Web Data Aggregators},  		 			R Gupta 		,  		 			A Puri 		,  		 			K Ramamritham 		.  		2005. WWW.  	 
\bibitem[Dilley et al. (2002)]{b2}\label{b2} 	 		‘Globally Distributed Content Delivery’.  		 			J Dilley 		,  		 			B Maggs 		,  		 			J Parikh 		,  		 			H Prokop 		,  		 			R Sitaraman 		,  		 			B Weihl 		.  	 	 		\textit{IEEE Internet Computing}  		Sept 2002.  	 
\bibitem[Shah et al. ()]{b3}\label{b3} 	 		\textit{Maintaining Coherency of Dynamic Data in Cooperating Repositories},  		 			S Shah 		,  		 			K Ramamritham 		,  		 			P Shenoy 		.  		2002.  	 
\bibitem[Optimized Execution of Continuous Queries, APS2006]{b12}\label{b12} 	 		\textit{Optimized Execution of Continuous Queries, APS2006},  		 \url{www.cse.iitb.ac.in/\textasciitilde grajeev/APS06.PDF}  		 	 
\bibitem[Guptha and Ramamritham ()]{b14}\label{b14} 	 		\textit{Optimized Query Planning of Continuous Aggregation Queries in Dynamic Data Dissemination Networks},  		 			R Guptha 		,  		 			K Ramamritham 		.  		2007. WWW.  	 
\bibitem[Vander Meer et al. (2004)]{b1}\label{b1} 	 		‘Proxy-Based Acceleration of Dynamically Generated Content on the World Wide Web’.  		 			D Vander Meer 		,  		 			A Datta 		,  		 			K Dutta 		,  		 			H Thomas 		,  		 			K Ramamritham 		.  	 	 		\textit{ACM Transactions on Database Systems (TODS}  		June 2004. 29.  	 
\bibitem[Query cost model validation for sensor data]{b4}\label{b4} 	 		\textit{Query cost model validation for sensor data},  		 \url{www.cse.iitb.ac.in/\textasciitilde ravivj/BTP06.pdf}  		 	 
\bibitem[Guptha and Ramamritham]{b15}\label{b15} 	 		\textit{Query Planning for Continuous Aggregation Queries over a network of Data Aggregators},  		 			R Guptha 		,  		 			K Ramamritham 		.  		 IEEE 2011.  		 	 
\bibitem[Rangarajan et al. ()]{b13}\label{b13} 	 		‘User Specific Request Redirection in a Content Delivery Year Network, 8th Intl’.  		 			S Rangarajan 		,  		 			S Mukerjee 		,  		 			P Rodriguez 		.  	 	 		\textit{Workshop on Web Content Caching and Distribution (IWCW)},  				2003.  	 
\end{bibitemlist}
 			 		 	 
\end{document}
