Modelos de custo e estatísticas para consultas por similaridade (2017)
- Authors:
- Autor USP: BêDO, MARCOS VINíCIUS NAVES - ICMC
- Unidade: ICMC
- Sigla do Departamento: SCC
- Subjects: GERENCIADORES DE BANCO DE DADOS; RECUPERAÇÃO DA INFORMAÇÃO; OTIMIZAÇÃO GLOBAL
- Keywords: Concentração de distâncias; Consultas por similaridade; Distance concentration; Otimização de consultas; Query optimization; Similarity searching
- Language: Português
- Abstract: Consultas por similaridade constituem um paradigma de busca que fornece suporte à diversas tarefas computacionais, tais como agrupamento, classificação e recuperação de informação. Neste contexto, medir a similaridade entre objetos requer comparar a distância entre eles, o que pode ser formalmente modelado pela teoria de espaços métricos. Recentemente, um grande esforço de pesquisa tem sido dedicado à inclusão de consultas por similaridade em Sistemas Gerenciadores de Bases de Dados (SGBDs), com o objetivo de (i) permitir a combinação de comparações por similaridade com as comparações por identidade e ordem já existentes em SGBDs e (ii) obter escalabilidade para grandes bases de dados. Nesta tese, procuramos dar um próximo passo ao estendermos também o otimizador de consultas de um SGBD. Em particular, propomos a ampliação de dois módulos do otimizador: o módulo de Espaço de Distribuição de Dados e o módulo de Modelo de Custo. Ainda que o módulo de Espaço de Distribuição de Dados permita representar os dados armazenados, essas representações são insuficientes para modelar o comportamento das comparações em espaços métricos, sendo necessário estender este módulo para contemplar distribuições de distância. De forma semelhante, o módulo Modelo de Custo precisa ser ampliado para dar suporte à modelos de custo que utilizem estimativas sobre distribuições de distância. Toda a investigação aqui conduzida se concentra em cinco contribuições. Primeiro, foi criada uma nova sinopsepara distribuições de distância, o Histograma Compactado de Distância (CDH), de onde é possível inferir valores de seletividade e raios para consultas por similaridade. Uma comparação experimental permitiu mostrar os ganhos das estimativas da sinopse CDH com relação à diversos competidores. Também foi proposto um modelo de custo baseado na sinopse CDH, o modelo Stockpile, cujas estimativas se mostraram mais precisas na comparação com outros modelos. Os Histogramas-Omni são apresentados como a terceira contribuição desta tese. Estas estruturas de indexação, construídas a partir de restrições de particionamento de histogramas, permitem a execução otimizada de consultas que mesclam comparações por similaridade, identidade e ordem. A quarta contribuição de nossa investigação se refere ao modelo RVRM, que é capaz de indicar quanto é possível empregar as estimativas das sinopses de distância para otimizar consultas por similaridade em conjuntos de dados de alta dimensionalidade. O modelo RVRM se mostrou capaz de identificar intervalos de dimensões para os quais essas consultas podem ser executadas eficientes. Finalmente, a última contribuição desta tese propõe a integração das sinopses e modelos revisados em um sistema com sintaxe de alto nível que pode ser acoplado em um otimizador de consultas.
- Imprenta:
- Publisher place: São Carlos
- Date published: 2017
- Data da defesa: 10.10.2017
-
ABNT
BÊDO, Marcos Vinícius Naves. Modelos de custo e estatísticas para consultas por similaridade. 2017. Tese (Doutorado) – Universidade de São Paulo, São Carlos, 2017. Disponível em: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-31012018-101031/. Acesso em: 14 out. 2024. -
APA
Bêdo, M. V. N. (2017). Modelos de custo e estatísticas para consultas por similaridade (Tese (Doutorado). Universidade de São Paulo, São Carlos. Recuperado de http://www.teses.usp.br/teses/disponiveis/55/55134/tde-31012018-101031/ -
NLM
Bêdo MVN. Modelos de custo e estatísticas para consultas por similaridade [Internet]. 2017 ;[citado 2024 out. 14 ] Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-31012018-101031/ -
Vancouver
Bêdo MVN. Modelos de custo e estatísticas para consultas por similaridade [Internet]. 2017 ;[citado 2024 out. 14 ] Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-31012018-101031/ - Incluindo funções de distância e extratores de características para suporte a consultas por similaridade
- Pushing diversity into higher dimensions: the LID effect on diversified similarity searching
- Deep extracted features to support content-based image retrieval systems in the diagnosis of Covid-19 and interstitial diseases
- Wia-Spine: a CBIR environment with embedded radiomic features to assess fragility fractures
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas