Método de Acesso Métrico Dinâmico Eficiente

Prévia do material em texto

Desenvolvimento de um método de acesso métrico dinâmico
eficiente baseado em pivôs adicionais∗
Paulo Henrique de Oliveira1,
Prof. Dr. Daniel dos Santos Kaster1
1Programa de Pós-Graduação em Ciência da Computação
Universidade Estadual de Londrina
oliveira.ph17@gmail.com, dskaster@uel.br
Nı́vel Mestrado
Ano de ingresso no programa Agosto de 2013
Data da defesa da proposta Dezembro de 2014
Época esperada de conclusão Julho de 2015
Etapa Estado
Revisão bibliográfica Concluı́da
Definição do problema Concluı́da
Definição da metodologia Concluı́da
Definição da avaliação de resultados Concluı́da
Implementação do método Em desenvolvimento
Escrita do texto para o exame de qualificação Em desenvolvimento
Realização de experimentos Etapa futura
Análise de resultados Etapa futura
Resumo. Estruturas de indexação tradicionais não são adequadas para dados
complexos, uma vez que a relação de ordem total não se aplica para tais dados.
Existem estruturas adequadas para executar consultas sobre dados complexos,
como os Métodos de Acesso Métricos (MAMs). A utilização de pivôs em MAMs
permite particionar o espaço de busca de diferentes formas. Propostas recentes
de estruturas baseadas em pivôs globais têm apresentado bom desempenho em
consultas. Entretanto, o uso de pivôs globais pode comprometer a dinamicidade
das estruturas. Assim, este trabalho propõe a construção de um MAM dinâmico
baseado em múltiplos pivôs locais eficiente em termos de cálculos de distância
e de acessos a disco.
Palavras-chave: consultas por similaridade, MAMs, pivôs adicionais.
∗Os autores agradecem à CAPES o apoio financeiro para o desenvolvimento deste trabalho.
29th SBBD – WTDBD – ISSN 2316-5170 October 6-9, 2014 – Curitiba, PR, Brazil
paper:13
318
1. Fundamentação teórica
Dados complexos, no contexto deste trabalho, são dados que não são representáveis por
tipos de dados tradicionais, como números, datas e textos curtos. Dados multimı́dia, dados
georreferenciados e séries temporais são alguns exemplos de dados complexos. O volume
de dados complexos tem aumentado rapidamente devido à disseminação de dispositivos
de aquisição de dados, tais como câmeras digitais e equipamentos para exames médicos e
moleculares. O sucesso de serviços de compartilhamento como YouTube e Flickr é mais
uma evidência do crescimento desses tipos de dados [Barrios and Bustos 2011].
Para permitir a execução de consultas sobre dados complexos, usualmente, extrai-
se deles um conjunto de caracterı́sticas. A recuperação de dados complexos através dessas
caracterı́sticas é conhecida como recuperação baseada em conteúdo. O conjunto de ca-
racterı́sticas extraı́do, chamado de vetor de caracterı́sticas, é usado no lugar dos dados
originais para avaliar as consultas. Dados complexos são comparados através de relações
de (dis)similaridade entre pares de vetores de caracterı́sticas. Isso ocorre aplicando-se
uma função de distância cujo valor de retorno representa o quão distantes os dois vetores
de caracterı́sticas estão um do outro. Assim, consultas realizadas sobre dados complexos
são chamadas de consultas por similaridade. Essas consultas recuperam os elementos
mais similares ao elemento de consulta de acordo com a condição fornecida. As consultas
por similaridade mais comuns são a consulta por abrangência (Range query), que retorna
os elementos cuja dissimilaridade em relação ao elemento de consulta é menor ou igual a
um dado limiar, e a consulta aos k-vizinhos mais próximos (k-Nearest Neighbors query),
que retorna os k elementos mais similares ao elemento de consulta [Barioni et al. 2011].
Grande parte das estruturas de indexação implementadas por Sistemas Gerencia-
dores de Bancos de Dados (SGBDs) comerciais é capaz de executar consultas com muita
eficiência sobre dados tradicionais fazendo uso da propriedade de relação de ordem total
[Vieira et al. 2010]. O significado dessa propriedade é que, para cada par de elementos
do domı́nio, é possı́vel identificar qual deles precede o outro. No entanto, a propriedade
de relação de ordem total não se aplica para a maioria dos domı́nios de dados complexos
[Faloutsos 1996]. Portanto, as estruturas de indexação tradicionais não podem ser utiliza-
das para trabalhar em domı́nios complexos de forma apropriada. Por outro lado, existem
estruturas de indexação adequadas para a execução de consultas por similaridade sobre
dados complexos, dentre as quais destacam-se os Métodos de Acesso Métricos (MAMs).
1.1. Métodos de Acesso Métricos
Métodos de Acesso Métricos (MAMs) são estruturas de indexação que consideram que
os dados estão imersos em um espaço métrico. Um espaço métrico é definido por um par
〈S, δ〉, onde S é o domı́nio de dados e δ é uma função de distância definida sobre esse
domı́nio. A função δ : S× S 7→ R+ é denominada métrica e deve satisfazer as proprieda-
des a seguir, também conhecidas como postulados do espaço métrico [Zezula et al. 2006]:
• ∀x, y ∈ S, δ(x, y) ≥ 0 não-negatividade
• ∀x, y ∈ S, δ(x, y) = δ(y, x) simetria
• ∀x, y ∈ S, x = y ⇐⇒ δ(x, y) = 0 identidade
• ∀x, y, z ∈ S, δ(x, z) ≤ δ(x, y) + δ(y, z) desigualdade triangular
Com base nesses conceitos, os MAMs são capazes de indexar praticamente qual-
quer tipo de dado, sendo necessário apenas definir uma métrica para o domı́nio de dados
29th SBBD – WTDBD – ISSN 2316-5170 October 6-9, 2014 – Curitiba, PR, Brazil
319
em questão, que, tipicamente, são vetores de caracterı́sticas extraı́dos do conteúdo dos da-
dos complexos. Existem inúmeros MAMs relatados na literatura, categorizados em geral
com base em algumas caracterı́sticas. Uma caracterı́stica importante é se o MAM permite
responder a consultas de forma exata (a resposta é exata) ou aproximada (a precisão da
resposta é relaxada a fim de permitir uma execução mais eficiente). Outra caracterı́stica é
se a estrutura é estática (exige a existência a priori do conjunto de dados indexado e não
permite atualizações posteriores) ou dinâmica (permite adicionar elementos sem degene-
rar a estrutura). Por fim, o tipo de particionamento do espaço e o tipo dos pivôs (globais
ou locais) também são fatores importantes que diferenciam os MAMs. No contexto deste
trabalho, pivôs são elementos referenciados pelo restante dos elementos da base de dados
(ou por parte deles no caso de pivôs locais).
1.2. Escolha de pivôs em MAMs
O critério de escolha de pivôs no processo de construção dos MAMs influencia o desem-
penho das consultas, uma vez que eles ajudam a restringir a região de busca ao serem uti-
lizados na poda de elementos não relevantes. Estudos realizados por [Bustos et al. 2003]
apontam que bons pivôs estão distantes uns dos outros. Essa afirmação faz sentido, uma
vez que pivôs muito próximos tendem a dar a mesma informação no processo de poda.
Tipicamente, os pivôs podem ser pivôs globais ou pivôs locais. Pivôs globais são
referenciados por todos os elementos da base de dados, enquanto pivôs locais são refe-
renciados por apenas alguns elementos, isto é, cada pivô local é associado a um número
limitado de elementos do conjunto de dados. Para pivôs locais, existe também o critério
de proximidade: um pivô é bom se estiver próximo a algum elemento da base de dados ou
ao elemento de consulta. Em ambas as situações, o pivô fornece informações de distância
mais precisas em relação ao elemento de quem está próximo, o que torna mais efetiva a
poda de elementos não relevantes [Skopal and Hoksza 2007].
2. Caracterização da contribuição
2.1. Definição do problema e objetivo da pesquisa
MAMs que fazem uso de pivôs podem ser categorizados em: baseados em pivôs globais,
baseados em pivôs locais e hı́bridos. MAMs baseados em pivôs globais particionam bem
o espaço de busca se o número de pivôs e sua distribuição forem adequados. Porém, uma
eventual necessidade de modificaçãono conjunto de pivôs, em geral, exige a reconstrução
da estrutura. Por outro lado, a manutenção de pivôs locais requer a atualização de apenas
uma parte dos elementos indexados. Essa caracterı́stica é comum nos MAMs dinâmicos.
Para aprimorar o desempenho das estruturas dinâmicas com pivôs locais, uma estratégia
consiste em acrescentar pivôs globais ou locais. MAMs hı́bridos acrescentam pivôs glo-
bais, aumentando o desempenho, mas limitando a dinamicidade. Já no caso das propostas
existentes que utilizam múltiplos pivôs locais, os ganhos obtidos dizem respeito apenas à
redução no número de cálculos de distância.
Diante disso, este trabalho de mestrado tem como objetivo desenvolver um MAM
dinâmico baseado em múltiplos pivôs locais que seja eficiente tanto em termos de cálculos
de distância quanto de acessos a disco, explorando diferentes abordagens. O modo como
pretende-se atingir esses objetivos é descrito na subseção 2.2.
29th SBBD – WTDBD – ISSN 2316-5170 October 6-9, 2014 – Curitiba, PR, Brazil
320
2.2. Metodologia para resolução do problema
A metodologia desta proposta tem como foco estender um MAM dinâmico hierárquico.
As estratégias fundamentais do trabalho são: (i) eleger elementos em cada nó como pivôs
adicionais a fim de aprimorar a capacidade de poda da estrutura sem modificar a região de
cobertura dos nós, (ii) modificar a estrutura do nó a fim de obter os valores das distâncias
dos elementos aos pivôs e dos raios de cobertura sem acessar o nó em disco e (iii) definir
formas de particionamento dos nós em regiões disjuntas, mantendo a estrutura dinâmica.
As atividades a serem desenvolvidas são apresentadas a seguir.
1. Definir polı́ticas de escolha de pivôs adicionais.
2. Modificar o MAM para acrescentar pivôs adicionais sem alterar o particionamento
dos nós (i.e. as regiões de cobertura de cada nó são definidas pelo pivô principal).
3. Modificar a estrutura dos nós para antecipar o acesso às distâncias e aos raios.
4. Modificar o MAM definindo formas de particionamento dos nós em nós “gêmeos”
de forma que cubram regiões disjuntas. Note-se que as regiões de cobertura de nós
irmãos (não “gêmeos”) podem ainda ter sobreposição.
5. Acomodar essas mudanças nos métodos de inserção e remoção e nas consultas.
6. Executar experimentos e analisar os resultados.
7. Disseminar os resultados da pesquisa.
3. Estado atual do trabalho
Primeiramente, as atividades deste trabalho de mestrado concentraram-se no aprendizado
dos conceitos relacionados a dados complexos, buscas por similaridade, espaços métricos
e MAMs. Em seguida, iniciou-se o desenvolvimento do novo MAM utilizando a primeira
estratégia (utilizar pivôs adicionais sem modificar a região de cobertura dos nós), que usa
como base a estrutura hierárquica da Slim-tree [Traina Jr. et al. 2002]. Esta seção dá uma
visão geral da Slim-tree e do MAM em desenvolvimento, que recebeu o nome Slim*-tree.
3.1. Visão geral da Slim-tree
Na Slim-tree, os elementos são agrupados em páginas de tamanho fixo para serem grava-
dos em disco, cada página correspondendo a um nó da árvore, e são guardados nas folhas.
Os elementos são organizados em uma estrutura hierárquica em que um elemento deno-
minado representativo é utilizado como centro da região de cobertura de uma subárvore,
delimitada por um raio máximo. Cada elemento de um nó tem sua distância ao represen-
tativo calculada e armazenada no momento de construção da árvore. Isso é feito a fim de
que sejam economizados cálculos de distância durante as consultas.
Existem dois tipos de nós na Slim-tree: os nós ı́ndice (index nodes) e os nós folha
(leaf nodes). Um nó folha possui a seguinte estrutura:
leaf node [vetor de 〈OIDi, si, δ(si, srep)〉]
Nessa estrutura, OIDi é o identificador do elemento em questão, si é o elemento
propriamente dito, armazenado como um vetor de caracterı́sticas, e δ(si, srep) é a distância
de si ao representativo do nó. Um nó ı́ndice possui a seguinte estrutura:
index node [vetor de 〈si, ri, δ(si, srep), P tr(Tsi),#Ent(Tsi)〉]
Nessa estrutura, si é o vetor de caracterı́sticas do representativo da subárvore apon-
tada por Ptr(Tsi), ri é o raio de cobertura do nó dessa subárvore (definido pela distância
entre o representativo e o elemento mais distante nesse nó), δ(si, srep) é a distância de si
ao representativo dessa subárvore e #Ent(Tsi) é o número de entradas em Tsi .
29th SBBD – WTDBD – ISSN 2316-5170 October 6-9, 2014 – Curitiba, PR, Brazil
321
3.2. Visão geral da Slim*-tree
Na Slim*-tree, os elementos são organizados de forma hierárquica como na Slim-tree. A
principal diferença em sua estrutura está no conteúdo dos nós, de forma que os valores de
distância e o raio de cada elemento são deslocados um nı́vel acima para que sejam obtidos
antes de acessar o nó em disco, conforme descrito na subseção 2.2. Outra caracterı́stica é
que são escolhidos pivôs em cada nó para serem usados no processo de poda de elementos
não relevantes. Esse processo de poda faz uso da propriedade de desigualdade triangular
e ocorre da seguinte maneira:
1. Considerando o representativo do nó (Figura 1(a)), é podado todo elemento si (i.e.
não é preciso calcular a distância de si a sq) que satisfaz uma das inequações:
• δ(srep, si) + ri < δ(srep, sq)− ξ
• δ(srep, si)− ri > δ(srep, sq) + ξ
2. Para todo si não podado, considera-se cada um dos pivôs (Figura 1(b)) para tentar
podar mais elementos. É podado todo elemento que satisfaz uma das inequações:
• δ(pj, si) + ri < δ(pj, sq)− ξ
• δ(pj, si)− ri > δ(pj, sq) + ξ
Por fim, outra melhoria que a Slim*-tree possui é que os elementos de cada nó são
ordenados da maior para a menor soma da distância ao representativo mais o raio (apenas
pela distância ao representativo em um nó folha). Com isso, durante a varredura do nó que
utiliza a desigualdade triangular pelo representativo, ao encontrar o primeiro elemento que
satisfaz δ(srep, si) + ri < δ(srep, sq)− ξ, pode-se ignorar o restante dos elementos do nó
seguramente, pois sabe-se que eles não farão parte da resposta da consulta. Atualmente,
já existe uma implementação inicial da Slim*-tree em fase de testes.
 
s
q
s
rep
ξ
δ(s
rep
, s
q
) - ξ
δ(s
rep
, s
q
) + ξ
(a) Pelo representativo.
 
s
rep
δ(s
rep
, s
q
) - ξ
δ(s
rep
, s
q
) + ξ
s
q
ξ
p
δ(p, s
q
) - ξ
δ(p, s
q
) + ξ
(b) Pelo representativo mais um pivô adicional.
Figura 1. Processo de poda através da desigualdade triangular. Circunferências
pontilhadas representam nós podados durante a consulta.
29th SBBD – WTDBD – ISSN 2316-5170 October 6-9, 2014 – Curitiba, PR, Brazil
322
4. Trabalhos correlatos
Em [Traina Jr. et al. 2007], é proposta a técnica Omni, baseada em pivôs globais selecio-
nados a partir do conjunto de dados, que pode ser aplicada em diversos MAMs dinâmicos.
Tais MAMs podem ser considerados dinâmicos no que diz respeito a inserções e remoções
de elementos. No entanto, no caso de mudança de pivôs, deve-se atualizar toda a estrutura.
O trabalho de [Esuli 2012] apresenta um ı́ndice baseado em permutação, que realiza bus-
cas aproximadas, em que cada elemento é representado por uma sequência, ordenada em
relação à distância dos pivôs globais do conjunto, do pivô mais próximo ao pivô mais dis-
tante. A fim de economizar espaço em disco, são armazenados prefixos das permutações
que representam os elementos (daı́ o nome Permutation Prefix Index — PP-Index). Nesse
ı́ndice, também é necessário atualizar toda a estrutura no caso de mudança de pivôs. Como
resultado, esses métodos permitem diminuir os acessos a disco e os cálculos de distância.
Diferentemente desses métodos baseados em pivôs globais, a Slim-tree (apresen-
tada na subseção 3.1) usa pivôs locais, que são os representativos dos nós. Existe também
a M*-tree, proposta por [Skopal and Hoksza 2007], que utiliza múltiplos pivôs locaisem
cada nó, além do representativo. Tais métodos têm a vantagem de serem dinâmicos, pois
apenas parte da estrutura precisa ser reajustada quando há mudança de pivô. O mesmo
vale para a Slim*-tree, que é a proposta deste trabalho. Porém, tanto a Slim-tree quanto
a M*-tree são beneficiadas pelos pivôs apenas na redução de cálculos de distância. No
caso da Slim*-tree, deseja-se reduzir também os acessos a disco modificando-se sua es-
trutura. Outro método baseado em pivôs locais é a DAHC-tree [Almeida et al. 2010], cuja
maior diferença é o uso de regiões disjuntas e não disjuntas. Esse método é aproximado e
sua estrutura pode ser desbalanceada. Ele permite diminuir acessos a disco e cálculos de
distância. Porém, alguns de seus parâmetros dependem do conjunto de dados.
Existem também métodos hı́bridos. O trabalho feito por [Skopal et al. 2005] apre-
senta a PM-tree, uma estrutura que reduz a região de busca dos nós através de pivôs glo-
bais. Uma evolução dessa estrutura, a PM*-tree [Skopal and Hoksza 2007], acrescenta o
uso de múltiplos pivôs locais assim como na M*-tree. Entretanto, ambas são estáticas. Os
conceitos introduzidos pela PM-tree que diminuem a região de busca foram formalizados
em [Lokoč et al. 2014] e podem ser aplicados em outros métodos de acesso.
5. Avaliação dos resultados
Os resultados serão avaliados através de experimentos envolvendo dados reais e sintéticos.
No que diz respeito a dados reais, exemplos de bases de dados a serem usadas são: ALOI
[Geusebroek et al. 2005], que tem 72 mil imagens, e CoPhIR [Bolettieri et al. 2009], que
tem quase 106 milhões de imagens. Em relação a dados sintéticos, serão avaliados con-
juntos de dados variando-se a dimensionalidade, o tamanho e a distribuição dos dados. Os
parâmetros de avaliação incluem o desempenho de construção das estruturas, consumo de
espaço e desempenho de execução de consultas por similaridade. Esses são os parâmetros
normalmente considerados em trabalhos em que MAMs são desenvolvidos. Quanto ao de-
sempenho de consultas por similaridade, espera-se que seu tempo de execução seja menor
uma vez que os acessos a disco e os cálculos de distância possam ser reduzidos.
Referências
Almeida, J., Valle, E., da S. Torres, R., and Leite, N. J. (2010). DAHC-tree: An Effec-
tive Index for Approximate Search in High-Dimensional Metric Spaces. Journal of
29th SBBD – WTDBD – ISSN 2316-5170 October 6-9, 2014 – Curitiba, PR, Brazil
323
Information and Data Management, 1(3):375–390.
Barioni, M. C. N., Kaster, D. S., Razente, H. L., Traina, A. J. M., and Traina Jr., C.
(2011). Querying Multimedia Data by Similarity in Relational DBMS. In Yan, L. and
Ma, Z., editors, Advanced Database Query Systems: Techniques, Applications and
Technologies, pages 323–359. IGI Global, Hershey, PA, USA.
Barrios, J. M. and Bustos, B. (2011). Automatic Weight Selection for Multi-Metric Dis-
tances. In Proceedings of the 4th International Conference on Similarity Search and
Applications, SISAP ‘11, pages 61–68, New York, NY, USA. ACM.
Bolettieri, P., Esuli, A., Falchi, F., Lucchese, C., Perego, R., Piccioli, T., and Rabitti,
F. (2009). CoPhIR: a Test Collection for Content-Based Image Retrieval. CoRR,
abs/0905.4627v2.
Bustos, B., Navarro, G., and Chávez, E. (2003). Pivot selection techniques for proximity
searching in metric spaces. Pattern Recognition Letters, 24(14):2357–2366.
Esuli, A. (2012). Use of permutation prefixes for efficient and scalable approximate sim-
ilarity search. Information Processing & Management, 48(5):889–902.
Faloutsos, C. (1996). Searching Multimedia Databases by Content, volume 3 of Advances
in Database Systems. Kluwer Academic Publishers.
Geusebroek, J.-M., Burghouts, G. J., and Smeulders, A. W. M. (2005). The Amsterdam
Library of Object Images. International Journal of Computer Vision, 61(1):103–112.
Lokoč, J., Moško, J., Čech, P., and Skopal, T. (2014). On indexing metric spaces using
cut-regions. Information Systems, 43(0):1–19.
Skopal, T. and Hoksza, D. (2007). Improving the Performance of M-Tree Family by
Nearest-Neighbor Graphs. In Proceedings of the 11th East European Conference on
Advances in Databases and Information Systems, ADBIS ‘07, pages 172–188, Berlin,
Heidelberg. Springer-Verlag.
Skopal, T., Pokorný, J., and Snášel, V. (2005). Nearest Neighbours Search Using the
PM-Tree. In Zhou, L.-Z., Ooi, B. C., and Meng, X., editors, Database Systems for
Advanced Applications, volume 3453 of Lecture Notes in Computer Science, pages
803–815. Springer Berlin Heidelberg.
Traina Jr., C., Filho, R. F. S., Traina, A. J. M., Vieira, M. R., and Faloutsos, C. (2007).
The Omni-family of all-purpose access methods: a simple and effective way to make
similarity search more efficient. The VLDB Journal, 16(4):483–505.
Traina Jr., C., Traina, A. J. M., Faloutsos, C., and Seeger, B. (2002). Fast Indexing and
Visualization of Metric Data Sets Using Slim-Trees. IEEE Transactions on Knowledge
and Data Engineering, 14(2):244–260.
Vieira, M. R., Traina Jr., C., Chino, F. J. T., and Traina, A. J. M. (2010). DBM-Tree: A
Dynamic Metric Access Method Sensitive to Local Density Data. Journal of Informa-
tion and Data Management, 1(1):111–128.
Zezula, P., Amato, G., Dohnal, V., and Batko, M. (2006). Similarity Search — The Metric
Space Approach, volume 32 of Advances in Database Systems. Springer, 1st edition.
29th SBBD – WTDBD – ISSN 2316-5170 October 6-9, 2014 – Curitiba, PR, Brazil
324