%-----------------------------------------------------------------------
%                  HTM2: Spatial Toolkit for the Virtual Observatory
%-----------------------------------------------------------------------
\documentclass[11pt,twoside]{article}
%\newcommand{\be}{\begin{equation}}
%\newcommand{\ee}{\end{equation}}
\usepackage{adassconf}

\begin{document}
\paperID{P3-9}
%%%% ID=P3-9

\title{HTM2: Spatial Toolkit for the Virtual Observatory}  
\titlemark{HTM2: Spatial Toolkit for the Virtual Observatory}

\author{Gy\"orgy Fekete\altaffilmark{1}, Alex
Szalay\altaffilmark{1}, Jim Gray\altaffilmark{2}}

\iffalse	%% Mod FO
\altaffiltext{1}{Dept.\ of Physics \& Astronomy, Johns Hopkins
University, Baltimore, MD 21218, USA}
\altaffiltext{2}{Microsoft Bay Area Research Center, San Francisco,
CA 94105, USA}
\else
\vspace*{2ex}   % Corrected style FO
\altaffilmark{1}\affil{Dept.\ of Physics \& Astronomy, Johns Hopkins
University, Baltimore, MD 21218, USA}
\altaffilmark{2}\affil{Microsoft Bay Area Research Center, San Francisco,
CA 94105, USA}
\fi
% contact
\contact{Gy\"orgy Fekete} \email{gfekete@pha.jhu.edu}

% index
\paindex{Fekete, G.} 
\aindex{Szalay, A. S.} 
\aindex{Gray, J.}

\authormark{Fekete et al.}

\keywords{SkyQuery, Virtual Observatory: table, ConeSearch, HTM, spatial: index}


%-----------------------------------------------------------------------
%                  Abstract
%-----------------------------------------------------------------------

\begin{abstract}
 The hierarchical tringular mesh (HTM) is a discrete foundation for
 describing location, size and shape on the celestial sphere. Indices
 derived from HTM descriptors are used in a relational database for
 managing spatial information. Some of the new features available in
 the current implementation support operations such as the ability to
 perform searches based on arbitrary polygons, convex hulls of
 polygons or any region bounded by great or small circles. These
 functions are reached through a language that is implemented as an
 extension to MSQL Server 2000 relational database engine. The heart
 of the HTM tools can also be used through various interfaces in
 several langugages, like C++, C\# and Java. An extensive XML
 specification for describing spatial structures to support spatial
 queries is also under development.
\end{abstract}

%-----------------------------------------------------------------------
%                  Main body
%-----------------------------------------------------------------------
%\begin{figure}
%\epsscale{0.5}
%\plotone{fig1.ps}
%\caption{Figure 1 Blah.}
%\label{P3-9:fig:scr}
%\end{figure}
\section{Motivation}
 One of the major functions of a spatial data management system is the
 effective exploitation and manipulation of the information inherent
 in points and regions. It does this to make searching through a vast
 collection of objects as efficient as possible. When this power is
 coupled to a state-of-the-art database management system, it provides
 a substanatial speedup for queries that have a spatial component.

 Current astronomical surveys, like the Sloan Digital Sky Survey are
 expected to describe on the order of hundreds of millions of
 objects. The metadata associated with each object is managed in a
 database. Astronomers use databases of this kind to find objects not
 only by their physical attributes, but also by their location. In fact
 the spatial component of the query can take complex forms, such as
 {\em ``find pairs of objects that are separated by $\theta$ degrees,
 and have other physical attributes''}. Furthermore, spatial
 correlation of pairs, triples, etc. of objects and regions of interest
 require complex (therefore expensive, time consuming) geometric
 computation. The challenge facing the astronomical database designer
 is that databases handle information that is organized into rows and
 columns (tables) very well, but the nature of spherical topology is
 such, that mapping (flattening) a sphere into a rectangle using {\em
 any} cartographic projection invariably introduces distortions, and
 worse, unacceptable discontinuities. But relational database
 management systems (RDBMS) are extremely good at organizing
 information contained in tables by manipulating {\em indices}. By
 mapping the sphere into a table, or onto a line, we harness the power
 of the database engine maximally.
%%
%%
\section{Constraints, Convexes, Regions} These are the building blocks
of regions on the sphere. A {\em constraint} is a region of the sphere
that looks like a cap. Its boundary is described by the intersection
of a plane with the sphere. This circle divides the sphere into two
regions, so we make precise which region is the constraint by
specifying the unit normal vector $\vec{v} = (x, y, z)$ so that $|\vec{v}| = 1$,
that points to the center of the cap, and a signed distance $D$, that
controls the distance of the of the perpendicular cutting plane from
the origin in the direction of the unit vector. For $D < 0$, we get
large caps, for $D > 0$ smaller ones. The two extreme cases are a
degenerate constraint that collapses into a point when $D = 1$, and
the whole sphere when $D=-1$. In fact, in our language for building
shapes, the simplest is the constraint, and is represented by a
4-tuple $(x, y, z, D)$
%%
%%
\section{Trixels}
{\em Trixels} form the web of spherical triangles that tesselate the
sphere. The mesh is obtained by recursively subdividing the spherical
triangles created by projecting the edges of an octahedron onto the
unit sphere. We can get an arbitrarily fine triangular mesh by
increasing the number of succsessive subdivisions for each
triangle. Because the method is so systematic, there is a natural way
to encode each trixel at each level with a number. We call these
numbers HTM ID's, or {\em hids} for short. For practical
considerations, we impose an upper limit of 64 bits on the number of bits.
%%
%%
\section{HTM Fundamentals}
%%
%%
The {\em Hierarchical Triangluar Mesh} (HTM) is used for managing
spatial information without the problems of flattening the sphere. It
provides an arbitrary resolution partitioning of the sphere, so that
sets of {\em hids} encode a
region. This effectively collapses two dimensions into one, so that
the index management capabilities of relational databases are
maximally exploited.

The 64-bit {\em hids} that represent unique trixels are used as
  indices by the RDBMS. As a result, queries that involve examining
  regions merely manipulate sets of {\em hids}. These functions are
  made accessible to the database engine by defining wraper functions
  particular to the databse in use.  In our testbed and production
  system, Microsoft SQL Server 2000 is extended by providing an
  interface to our function through so-called {\em extended stored
  procedures}. These functions provide adequate encapsulation of the
  HTM methods, so that users need not know the details of HTM
  algorithms, but can formulate their requests at a substantially high
  level.

Familiar shapes, like rectangles, circles, bands, are transformed into
an internal normal form based on the union of {\em convexes}, which,
in turn are intersections of {\em constraints}. In a computer program,
the region is an object that contains the {\em hids} of the trixels
that represent the region. These are generated by the library from
descriptions in terms of familiar shapes, such as circles, rectangles,
arbitrary polygons. If a user needs to know whether an observation is
outside of a region of interest, a simple call to the HTM toolkit with
the coordinates of the observation provides the answer. 

It is important to note, that {\em any} single shape (or a convex) is an
intersection of a finite number of constraints, and any region
consisting of disconnected shapes is nothing more that a union of
convexes.
%%
\section{SQL Interface}
%%
Typical queries with spatial components would sound like:
\vskip8pt
\begin{itemize}
\item Find all objects within a cone
\item Find all objects within these Ra/Dec limits
\item Find all objects within this spherical polygon
\end{itemize}
\vskip8pt
%

With SQL and the extra functions that implement the HTM algorithms, we
can express these easily. The details of using SQL to express a
general query is beyond the scope of the limited space in this
article, but as an illustration, we show one simple example.

The most powerul funtion is {\tt HTMCover()}. The argument given to it
is a description of the region expressed as a union of convexes, but
the interface also supports more intuitive shape descriptors made up
of rectangles, polygons and circles.  Figure~\ref{P3-9:fig:arch} shows two
search cones. In this example, our region of interest is their
intersection, which is represented a {\em convex} with two
constraints. The language which allows coordinates to be expressed in
either as RA DEC pairs, or as Cartesian coordinates.

\begin{verbatim}
CONVEX CARTESIAN 1 1 0 0.8  1 0 0 0.8
\end{verbatim}

\begin{figure}
\plottwo{P3-9_1.eps}{P3-9_2.eps}
\caption{Two intersecting constraints and a trixel covering.}
\label{P3-9:fig:arch} \end{figure}

This convex specification is a intersection of two constraints, both of whose
 $D = 0.8$.  
The two centers are $(1, 0, 0)$ and $(1, 1, 0) / ||(1, 1, 0)||$, respectively.  The
toolkit automatically normalizes the vectors. The hids that cover the specified convex is the list:

\begin{verbatim}
    32     62     141     253  9120   9121 
 16144  16146   36494   36608  64589 65408
\end{verbatim}

The smaller numbers represent the larger spherical triangles in Figure 1.
%
In some queries, the list of hids may become huge.
Fortunately, the hid values have a local coherence property, that is to say,
clumps of trixels in a neighborhood have large runs of consecutive hids.
Therefore we can consider a list of {\em runs}
of hids instead of a very large number of individual hids.
%
Consequently, the actual value returned by {\tt HtmCover()} is an SQL table
where each row is a pair hid values.
This is an effective run-length encoding of the hid list.

It is possible, that a particular request for a cover would
produce a very fragmented hid range list. Therefore 
our software ensures that the list of hid range values is always bound
by a specific, but tunable parameter (between 15 - 100). This is accomplished
by merging ranges with small gaps first, then those with greater gaps until
the number of ranges is within the specified parameter. This introduces
``false positives'' into the cover, but that is preferable to ignoring an
hid value that is actually inside (or intersecting) the convex.

For an extensive discussion and references the reader is directed to
the link at the end of this page.
%%
\section{Concluding Remarks}
%%
Version 1 of the HTM has already been in operation for a while, but as
the size of the databases grow, so does our need for improved
performance. The current version (HTM2) of the libraries has had a
significant improvement in performance and stability. Many bottlenecks
in the code were identified, and recoded for speed. The bitlist feature was 
eliminated to give way to hid ranges. Internal data structures were redesigned
where appropriate for better overall performance.
Ports and a major
restructuring of the code is underway to provide better support for
multiple platforms without sacrificing performance.

%%\acknowledgments 
%%This work  is supported by NSF Awards 0122449 and 9980044, and NASA AISRP 
%%awards NAG5-10742 (2001) and NAG5-12092 (2002).

%-----------------------------------------------------------------------
%                 Links
%-----------------------------------------------------------------------
\paragraph{Links} \mbox{} \\

\htmladdURL{http:/www.sdss.jhu.edu/htm}


%-----------------------------------------------------------------------
%                 References
%-----------------------------------------------------------------------
%\begin{references}
%\reference Kunszt, P. Z., Szalay, A. S., and Thakar, A. R. 2001,
%Mining the Sky: Proc. of the MPA/ESO/MPE workshop, Garching,
%A.J.Banday, S. Zaroubi, M. Bartelmann (ed.), (Springer-Verlag Berlin
%Heidelberg), 631.
%\end{references}

\end{document}
