SQL Server

Artículo
12/07/2016

Indización personalizada para datos de latitud y longitud

Descargar el ejemplo de código

En este artículo describo una técnica para crear índices personalizados para datos geográficos que contienen información sobre la ubicación de latitud y longitud. Los índices personalizados permiten una recuperación rápida de los datos en tiempo real. Veamos, por ejemplo, la siguiente situación: supongamos que tenemos un conjunto de datos muy grande (varios millones de elementos) similares a estos:

0001 47.610 -122.330
0002 36.175 -115.136
0003 47.613 -122.332
...

Aquí, la primera columna representa el identificador del usuario, (o el identificador de cualquier objeto asociado con una ubicación), la segunda columna representa la latitud del usuario, y la tercera columna la longitud. Las latitudes van de -90,0 grados a +90,0 grados y representan la coordenada arriba-abajo. Las longitudes van de -180,0 grados a +180,0 grados y representan la coordenada izquierda-derecha. Las ubicaciones del primer y tercer usuario están cerca de Seattle. Un valor de latitud de cero se encuentra en el ecuador. Una longitud de cero es el meridiano de Greenwich, que pasa por Greenwich en Inglaterra. Supongamos ahora que nuestros datos están almacenados en una tabla SQL y que queremos encontrar todos los usuarios que se encuentran en el mismo rectángulo de 1 grado por 1 grado que el usuario 0001. Podríamos hacerlo con una instrucción SQL sencilla como esta:

    SELECT userID
    FROM tblUsers
    WHERE latitude >= 47.0 AND latitude < 48.0
    AND longitude >= -123.0 AND longitude < -122.0

En muchas situaciones esto funcionará bien. Pero si necesitamos un rendimiento en tiempo real (quizás un tiempo de respuesta menor que 3 segundos) cuando el tamaño de los datos supera cierto límite (según los recursos del sistema), el tiempo de respuesta comienza a deteriorarse drásticamente.

Una solución para lograr un rendimiento en tiempo real en situaciones como esta, es asignar cada ubicación a un identificador de sector determinado. Supongamos, entonces, que podemos generar una tabla auxiliar a partir de los datos iniciales que se parece a esta:

Aquí, la primera columna representa el identificador del usuario y la segunda columna representa el identificador del sector. Ahora, si el identificador del sector tiene un índice, las instrucciones SQL como la siguiente serán muy rápidas, incluso si la tabla contiene cientos de millones de elementos:

    SELECT userID
    FROM tblSectors
    WHERE sector = 49377

El identificador de sector actúa como un índice personalizado para el conjunto de datos principal. El verdadero desafío radica en escribir una función que acepte una latitud y una longitud y devuelva un sector.

Para entender mejor el concepto de los índices personalizados, puede echar una mirada a la aplicación Windows Presentation Foundation (WPF) de ejemplo en la Ilustración 1. La aplicación tiene un control de mapa Bing Maps insertado. Después de centrar el mapa en una ubicación en Redmond, Washington y acercarme, hice doble clic en el mapa. El evento del doble clic estaba conectado con un controlador de eventos que determinó la latitud y longitud del clic y posicionó un círculo rojo como marcador de la posición del clic. Luego, la aplicación calculó el identificador del sector del clic y realizó una búsqueda en una base de datos SQL de back-end con 100 millones de elementos de ubicación de usuario aleatorios y encontró ocho usuarios dentro del mismo sector. La búsqueda tardó 0,36 segundos: un rendimiento bastante impresionante.

Custom Indexing Design Ilustración 1 Indización espacial personalizada en acción

Microsoft SQL Server 2008 cuenta con una característica de indización espacial sofisticada que podemos usar en la situación que acabamos de ver. Y en muchos casos, los índices espaciales de SQL Server son la mejor alternativa. Al menos en dos escenarios, sin embargo, resulta preferible la indización personalizada. Primero, los índices espaciales solo se pueden crear en las columnas SQL del tipo geometría o geografía. Si tenemos una base de datos u origen de datos heredado, donde las latitudes y longitudes están almacenadas como valores numéricos simples, es posible que no podamos convertir estos valores en tipos geográficos. Segundo, aunque los índices espaciales de SQL Server 2008 son extremadamente poderosos y permiten un buen grado de personalización, en algunos casos podemos requerir de un control total sobre el esquema de indización.

Aunque la creación de índices personalizados no es un concepto nuevo, hay pocos ejemplos disponibles. En lo que sigue del artículo, presentaré un ejemplo completo de cómo crear y usar un índice personalizado. Para entender completamente el ejemplo, al menos debe tener conocimientos de programación de nivel intermedio en C# y T-SQL. Luego puede obtener el código clave en C# para el ejemplo que presento aquí en archive.msdn.microsoft.com/mag201206Indexing.

Asignación de una latitud-longitud a un identificador de sector

Existen varias formas para asignar un par latitud-longitud a un identificador de sector. El método que describo aquí es el más sencillo y está descrito en el diagrama de la Ilustración 2. La primera decisión en un esquema de indización personalizado es elegir la segmentación del globo. En la Ilustración 2 dividí cada grado de latitud (los valores de las filas) y cada grado de longitud (las columnas) en dos partes, tal como indica la fracción = 0,5 en la esquina superior izquierda de la ilustración. Esto resulta en 360 intervalos de latitud, de [-90,0; -89,5) a [+89,5; +90,0], y 720 intervalos de longitud, de [-180,0; -179,5) a [+179,5; +180,0]. Uso los corchetes para indicar límites inclusivos y los paréntesis para los exclusivos. Una fracción con el valor 0,5 resulta en 360 * 720 = 259.200 sectores enumerados de 0 a 259.199. Ordeno los sectores de izquierda a derecha y de arriba hacia abajo, tal como se aprecia en la Ilustración 2.

Ilustración 2 Diseño del índice personalizado

fracción = 0,5	[-180.0, -179.5) 0	[-179.5, -170.0) 1	[-170.0, -169.5) 2		[179.5, 180.0] 719
[-90,0; -89,5) -> 0	0	1	2	...	719
[-89,5; -80,0) -> 1	720	721	722	...	1439
[-80,0; -79,5) -> 2	1440	1441	1442	...
	...

[89,5; 90,0] -> 359	258,480			...	259,199

Los valores menores del parámetro de fracción crean más intervalos por grado y generan más sectores. En este ejemplo uso el mismo valor de fracción para la latitud y la longitud, pero usted puede usar valores diferentes si esto se acomoda mejor la distribución de sus datos. Sin embargo, los sectores no tienen todos la misma superficie, como veremos pronto. Dado un índice de fila (latitud), ri, y un índice de columna (longitud), ci, se puede calcular el identificador del sector correspondiente del siguiente modo:

sid = (ri * 360 * 1/fraction) + ci

En la Ilustración 2, por ejemplo, el sector 1441 está asociado con el índice de fila 2 y el índice de columna 1, y se calcula como (2 * 360 * 1 / 0,5) + 1 = (2 * 720) + 1 = 1441. El término 360 * 1 / fracción determina la cantidad de intervalos de columna que se encuentran en cada fila, y al multiplicar esto por ri obtenemos el primer identificador de sector en la fila adecuada. Al sumar el término ci, en esencia nos movemos ci columnas hacia la derecha a partir del comienzo de la fila adecuada, lo que entrega el resultado final del identificador de sector.

La parte final del rompecabezas es asignar el valor de latitud a un índice de fila y un valor de longitud a un índice de columna. Una opción ingenua podría ser la búsqueda lineal sencilla. Experiencias dolorosas del pasado con conjuntos de datos muy grandes me enseñaron que en este caso resulta preferible la búsqueda binaria. La idea es comenzar con un índice pequeño de cero, el índice medio y un índice grande igual al último índice posible. Luego, determinamos el intervalo de latitud (o longitud) correspondiente al índice medio. Si la latitud (o longitud) buscada se encuentra dentro del intervalo, entonces el índice medio es el valor de devolución correcto. Si la latitud (o longitud) buscada es menor que el intervalo actual, desplazamos el índice medio al punto medio entre el índice bajo y el antiguo índice medio. Si la latitud (o longitud) buscada es mayor que el intervalo actual, desplazamos el índice medio al punto medio entre el antiguo índice medio y el índice alto. Repetimos el proceso hasta encontrar el índice medio correcto.

En la Ilustración3 se presenta la implementación en C# de un método LatIndex que acepta un valor de latitud y una fracción y devuelve el índice de la fila correspondiente. El método LonIndex equivalente que devuelve el índice de la columna para una longitud es completamente simétrico, a excepción de la constante 180 que se reemplaza por 360 y las constantes -90,0 y 90,0 que se reemplazan por -180,0 y 180,0.

Ilustración 3 Índice de fila/latitud para una latitud

static int LatIndex(double latitude, double fraction)
{
  latitude = Math.Round(latitude, 8);
  int lastIndex = (int)(180 * (1.0 / fraction) - 1);
  double firstLat = -90.0;
  if (latitude == -90.0) return 0;
  if (latitude == 90.0) return lastIndex;
  int lo = 0;
  int hi = lastIndex;
  int mid = (lo + hi) / 2;
  int ct = 0; // To prevent infinite loop
  while (ct < 10000)
  {
    ++ct;
    double left = firstLat + (fraction * mid); // Left part interval
    left = Math.Round(left, 8);
    double right = left + fraction;         // Right part interval
    right = Math.Round(right, 8);
    if (latitude >= left && latitude < right)
      return mid;
    else if (latitude < left)
    {
      hi = mid - 1; mid = (lo + hi) / 2;
    }
    else
    {
      lo = mid + 1; mid = (lo + hi) / 2;
    }
  }
  throw new Exception("LatIndex no return for input = " + latitude);
}

Como el método de la Ilustración 3 funciona con latitudes del tipo double, el parámetro de latitud de entrada se redondea a ocho cifras decimales para evitar los errores de igualdad de dos tipos double. La variable ct es un método un poco chapucero para prevenir un bucle infinito. Por abreviar el código, eliminé las comprobaciones de error más normales (p. ej. la validación de los parámetros de entrada) que emplearíamos en una situación de producción. Observe que el bucle principal revisa los intervalos de la forma [a;b), por lo que debo revisar explícitamente el último valor 90,0.

Ahora que tenemos listo el diseño de los sectores y los métodos auxiliares, podemos asignar un par latitud-longitud a un sector con un método como el siguiente:

static int LatLonToSector(double latitude, double longitude,
  double fraction)
{
  int latIndex = LatIndex(latitude, fraction); // row
  int lonIndex = LonIndex(longitude, fraction);  // col
  return (latIndex * 360 * (int)(1.0 / fraction)) + lonIndex;
}

Tamaño de los sectores

El esquema de indización personalizado que describo en este artículo divide el globo en intervalos numéricamente iguales a partir del valor del parámetro de fracción. Por ejemplo, si la fracción es 0,5, entonces cada intervalo mide 0,5 grados de latitud o longitud. Sin embargo, esto no significa que todos los sectores tengan la misma superficie geográfica. Observe la Ilustración 4. Las líneas de latitud son paralelas entre sí y tienen todas la misma distancia, aproximadamente 111 kilómetros. Por lo tanto, la distancia A en la Ilustración 4 es la misma que la distancia B. Pero las líneas de longitud se juntan a medida que se aproximan a los polos. Por lo tanto, la distancia C es menor que la distancia D.

Sectors Have Different Geographical Areas
Ilustración 4 Los sectores tienen superficies geográficas diferentes

La distancia en kilómetros entre dos puntos cualesquiera en el globo se puede calcular con el siguiente método:

static double Distance(double lat1, double lon1, 
  double lat2, double lon2)
{
  double r = 6371.0; // approx. radius of earth in km
  double lat1Radians = (lat1 * Math.PI) / 180.0;
  double lon1Radians = (lon1 * Math.PI) / 180.0;
  double lat2Radians = (lat2 * Math.PI) / 180.0;
  double lon2Radians = (lon2 * Math.PI) / 180.0;
  double d = r * Math.Acos((Math.Cos(lat1Radians) *
    Math.Cos(lat2Radians) *
    Math.Cos(lon2Radians - lon1Radians) +
   (Math.Sin(lat1Radians) * Math.Sin(lat2Radians)));
  return d;
}

Por lo tanto, si conocemos la latitud y longitud de un sector dado, podemos calcular el ancho y alto aproximado, y luego la superficie aproximada. Para determinar el extremo izquierdo del intervalo que contiene un sector, podemos usar el siguiente método:

static double SectorToLat(int sector,
    double fraction)
  {
    int divisor = 360 * (int)(1.0 / fraction);
    int row = sector / divisor;
    return -90.0 + (fraction * row);
  }

Este método realiza esencialmente el proceso inverso del método LatLonToSector. Por ejemplo, si el sector de entrada es 1441 y el parámetro de fracción tiene el valor 0,5, tal como aparece en la Ilustración 2, entonces la variable local divisor es 360 * 1,0 / 0,5 = 720, lo que corresponde a la cantidad de intervalos de longitud. Luego el valor de la variable row es 1441 / 720 = 2, lo que corresponde al índice de la fila (tome nota de la división de enteros). Por último, -90,0 + 0,5 * 2 = -90,0 + 1,0 = -89,0, que corresponde a la parte izquierda del intervalo [-89,0; -79,5) asociado con el sector 1441.

El método para determinar la parte izquierda del intervalo de longitud de un sector es similar pero no completamente simétrico:

static double SectorToLon(int sector, double fraction)
{
  int divisor = 360 * (int)(1.0 / fraction);
  int col = sector % divisor;
  return -180.0 + (fraction * col);
}

Con estos métodos auxiliares podemos determinar la superficie aproximada, en kilómetros cuadrados, de un a sector definido mediante el parámetro de fracción:

static double Area(int sector, double fraction)
{
  double lat1 = SectorToLat(sector, fraction);
  double lon1 = SectorToLon(sector, fraction);
  double lat2 = lat1 + fraction;
  double lon2 = lon1 + fraction;
  double width = Distance(lat1, lon1, lat1, lon2);
  double height = Distance(lat1, lon1, lat2, lon1);
  return width * height;
}

Sectores adyacentes

Es probable que en algunas situaciones debamos determinar cuáles son los sectores adyacentes a un sector dado. Por ejemplo, en la Ilustración 2, si un usuario se encuentra en el sector 721, podríamos querer determinar qué usuarios se encuentran en los sectores adyacentes 0, 1, 2, 720, 722, 1440, 1441 y 1442. Observe que los sectores izquierda-derecha difieren en más uno y menos uno, con la excepción de los sectores en los extremos izquierdo y derecho Y los sectores arriba-abajo, con la excepción de los sectores de los extremos superior e inferior, difieren en más o menos la cantidad de intervalos de columna, que es 360 * (1 / fracción). Para escribir un método AdjacentSectors que acepte un sector (y una fracción generadora), resulta útil saber si un sector se encuentra en uno de los extremos izquierdo o derecho, o en la fila superior o inferior. En la Ilustración 5 vemos estos cuatro métodos.

Ilustración 5 Métodos auxiliares para el método AdjacentSectors

static bool IsLeftEdge(int sector, double fraction)
{
  int numColumns = (int)(1.0 / fraction) * 360;
  if (sector % numColumns == 0) return true;
  else return false;
}
static bool IsRightEdge(int sector, double fraction)
{
  if (IsLeftEdge(sector + 1, fraction) == true) return true;
  else return false;
}
static bool IsTopRow(int sector, double fraction)
{
  int numColumns = (int)(1.0 / fraction) * 360;
  if (sector >= 0 && sector <= numColumns - 1) return true;
  else return false;
}
static bool IsBottomRow(int sector, double fraction)
{
  int numColumns = (int)(1.0 / fraction) * 360;
  int numRows = (int)(1.0 / fraction) * 180;
  int firstValueInLastRow = numColumns * (numRows - 1);
  int lastValueInLastRow = numColumns * numRows - 1;
  if (sector >= firstValueInLastRow && sector <= lastValueInLastRow)
    return true;
  else
    return false;
}

Podemos escribir el método AdjacentSectors de muchas formas, que deben conciliar la claridad y el tamaño del código. Una solución es devolver una matriz de valores de sector, donde el valor de devolución [0] es el sector adyacente a la esquina superior izquierda del sector de entrada, [1] es el sector superior, [2] el superior derecho, [3] el izquierdo, [4] el derecho, [5] el inferior izquierdo, [6] el inferior y [7] el inferior derecho. En el código de la Ilustración 6 se delinea una implementación posible de AdjacentSectors. Aunque el caso general donde el sector de entrada no se encuentra en un extremo del mapa es sencillo, algunos casos especiales, como los cuatro sectores de las esquinas son más difíciles. Consulte el código en la descarga de este artículo para ver la implementación completa.

Ilustración 6 Una implementación del método AdjacentSectors

static int[] AdjacentSectors(int sector, double fraction)
{
  int[] result = new int[8]; // Clockwise from upper-left
  int numCols = (int)(1.0 / fraction) * 360;
  int numRows = (int)(1.0 / fraction) * 180;
  int firstValueInLastRow = numCols * (numRows - 1);
  int lastValueInLastRow = numCols * numRows - 1;
  // General case
  if (IsLeftEdge(sector, fraction) == false &&
    IsRightEdge(sector, fraction) == false &&
    IsTopRow(sector, fraction) == false &&
    IsBottomRow(sector, fraction) == false)
  {
    result[0] = sector - numCols - 1;
    result[1] = sector - numCols;
    result[2] = sector - numCols + 1; 
    result[3] = sector - 1;
    result[4] = sector + 1;
    result[5] = sector + numCols - 1;
    result[6] = sector + numCols;
    result[7] = sector + numCols + 1;
    return result;
  }
  // Deal with special cases here. See code download.
  throw new Exception("Unexpected logic path in AdjacentSectors");
}

Combinación de las piezas del esquema de indización geográfica

Una forma excelente de entender el esquema de indización geográfica personalizado descrito en este artículo es examinar un ejemplo sencillo pero completo de principio a fin. Primero creamos una base de datos SQL de ensayo en código T-SQL, del siguiente modo:

    use master
    if exists(select * from sys.sysdatabases where name='dbGeoData')
      drop database dbGeoData
    create database dbGeoData on
    (
    name=dbGeoData,
    filename='D:\SomePlace\dbGeoData.mdf'
    )

Luego, creamos una tabla para contener algunos datos artificiales:

    use dbGeoData
    create table tblUsers
    (
    userID int primary key,
    latitude real not null,
    longitude real not null
    )

Luego escribimos el código C# para generar los datos artificiales:

Random r = new Random(0);
string initialDataFile = "..\\..\\UserIDLatLon.txt";
FileStream ofs = new FileStream(initialDataFile, FileMode.Create);
StreamWriter sw = new StreamWriter(ofs);
for (int i = 0; i < 1000000; ++i)
{
  double lat = (90.0 - (-90.0)) * r.NextDouble() + (-90.0);
  double lon = (180.0 - (-180.0)) * r.NextDouble() + (-180.0);
  sw.WriteLine(i.ToString().PadLeft(6,'0') + "," +
    lat.ToString("F8") + "," + lon.ToString("F8"));
}
sw.Close(); ofs.Close();

Aquí creo 1 millón de líneas de datos delimitados por comas. Para generar latitudes y longitudes aleatorias dentro del rango [hi;lo), uso el patrón convencional (hi - lo) * random.NextDouble() + lo. Luego copio los datos artificiales a la tabla SQL mediante el programa de línea de comandos bcp.exe:

> bcp.exe dbGeoData..tblUsers in UserIDLatLon.txt -c -t , -r \n -S(local) -T

Este comando significa “copiar a la tabla tblUsers, que se encuentra en la base de datos dbGeoData, los datos del archivo UserIDLatLon.txt, que contienen datos de caracteres (es decir, un archivo de texto), donde cada columna se termina o separa con el carácter coma y cada línea termina con el carácter nueva línea. El servidor de la base de datos se encuentra en la máquina local, y se usa una autenticación de confianza (Windows) para la conexión”.

Luego creamos los datos de sector para la indización personalizada en código C#, del siguiente modo:

string initialDataFile = "..\\..\\UserIDLatLon.txt";
string sectorDataFile = "..\\..\\ UserIDSector.txt";
FileStream ifs = new FileStream(initialDataFile, FileMode.Open);
StreamReader sr = new StreamReader(ifs);
FileStream ofs = new FileStream(sectorDataFile, FileMode.Create);
StreamWriter sw = new StreamWriter(ofs);
string line = "";
string[] tokens = null;
while ((line = sr.ReadLine()) != null)
{
  tokens = line.Split(',');
  int userID = int.Parse(tokens[0]);
  double lat = double.Parse(tokens[1]);
  double lon = double.Parse(tokens[2]);
  int sector = LatLonToSector(lat, lon, 0.5);
  sw.WriteLine(userID.ToString().PadLeft(6, '0') + "," + sector);
}
sw.Close(); ofs.Close(); sr.Close(); ifs.Close();

El código recorre el archivo de datos artificiales línea por línea; lee el identificador del usuario, latitud y longitud; calcula el sector asociado con un parámetro de fracción de 0,5; y escribe el identificador y sector en formato delimitado por comas en un archivo de texto.

Luego creamos una tabla SQL para contener los datos de sector:

    create table tblSectors
    (
    userID int primary key,
    sector int
    )

Luego copiamos los datos de sector a la tabla:

> bcp.exe dbGeoData..tblSectors in UserIDSector.txt -c -t , -r \n -S
(local) -T

Por último, indizamos los datos de sector:

    if exists(select name from sys.sysindexes where name='ndxSector')
      drop index ndxSector on tblSectors
    create nonclustered index ndxSector on tblSectors(sector)

Aquí puede realizar varios experimentos. Por ejemplo, puede seleccionar con código T-SQL todos los usuarios que se encuentran en el mismo sector que el usuario 3, del siguiente modo:

declare @userID int
set @userID = 3
declare @sector int
select @sector = sector from tblSectors where userID=@userID
print @sector
select userID from tblSectors where sector = @sector

Por supuesto, si accede a los datos de SQL desde una aplicación, puede usar los equivalentes en ADO.NET o LINQ para este tipo de código SQL.

Rendimiento en tiempo real

La indización personalizada resulta útil en varios tipos de aplicaciones. Por ejemplo, supongamos que tenemos una aplicación web en ASP.NET o una aplicación Silverlight con un control de mapa Bing Maps. Podríamos crear un sistema que permita al usuario hacer clic en el mapa. El evento del clic está asociado con código para determinar la latitud y longitud del clic, calcular el sector asociado y luego recuperar todos los usuarios dentro del sector de una base de datos SQL back-end. Tal como podemos apreciar en la Ilustración 1, incluso con varios cientos de millones de filas se puede lograr un rendimiento en tiempo real.

En algunas situaciones podríamos querer crear varios índices personalizados. Por ejemplo, un índice grueso con una fracción = 1,0 (de modo que cada sector mide 1 grado por 1 grado), un índice de granularidad media donde la fracción = 0,25 y un índice fino, donde la fracción = 0,05. El uso de varios índices nos permite filtrar los datos SQL en forma sucesiva. Primero determinamos la cantidad de usuarios que se encuentran en el sector de granularidad baja. Si son demasiados usuarios para nuestras intenciones, determinamos la cantidad de usuarios que se encuentran en el sector de granularidad media. Si son muy pocos, determinamos los siete sectores adyacentes con los usuarios correspondientes. Y así sucesivamente.

Vuelvo a afirmar que SQL Server 2008 tiene unas funciones de indización espacial poderosas que debe tomar en cuenta antes de crear índices personalizados. Los índices personalizados requieren de tablas SQL adicionales explícitas que imponen una carga administrativa adicional en el sistema. Dicho esto, sin embargo, en algunas situaciones los índices personalizados pueden conducir a un rendimiento extremadamente rápido. Con el creciente uso de los dispositivos móviles con GPS, la posibilidad de recopilar cantidades enormes de datos geográficos seguirá creciendo. La posibilidad de crear esquemas de indización personalizados puede ser una herramienta útil para analizar estos datos.

El Dr. James McCaffreytrabaja en Volt Information Sciences, donde está a cargo del entrenamiento técnico de los ingenieros informáticos que trabajan en el campus de Microsoft en Redmond, Washington. Ha trabajado en el desarrollo de varios productos de Microsoft, como Internet Explorer y MSN Search. McCaffrey también es el autor de “.NET Test Automation Recipes” (Apress, 2006). Puede ponerse en contacto con él en jammc@microsoft.com.

Gracias a los siguientes expertos técnicos por su ayuda en la revisión de este artículo: Isaac Kunen y Dan Liebling

Compartir a través de