Techniques for indexing large and complex datasets with missing attribute values (2016)
- Authors:
- Autor USP: BRINIS, SAFIA - ICMC
- Unidade: ICMC
- Sigla do Departamento: SCC
- Subjects: PROCESSAMENTO DE DADOS; FRACTAIS
- Keywords: Busca por similaridade; Dimensão fractal; Fractal dimension; Métodos de acesso métricos; Metric access methods; Missing attribute values; Similarity search; Valores de atributos faltantes
- Language: Inglês
- Abstract: O crescimento em quantidade e complexidade dos dados processados e armazenados torna a busca por similaridade uma tarefa fundamental para tratar esses dados. No entanto, atributos faltantes ocorrem freqüentemente, inviabilizando os métodos de acesso métricos (MAMs) projetados para apoiar a busca por similaridade. Assim, técnicas de tratamento de dados faltantes precisam ser desenvolvidas. A abordagem mais comum para executar as técnicas de indexação existentes sobre conjuntos de dados com valores faltantes é usar um indicador de valores faltantes e usar as técnicas de indexação tradicionais. Embora, esta técnica seja útil para os métodos de indexação multidimensionais, é impraticável para os métodos de acesso métricos. Esta dissertação apresenta os resultados da pesquisa realizada para identificar e lidar com os problemas de indexação e recuperação de dados em espaços métricos com valores faltantes. Uma análise experimental dos MAMs aplicados a conjuntos de dados incompletos identificou dois problemas principais: distorção na estrutura interna do índice quando a falta é aleatória e busca tendenciosa na estrutura do índice quando o processo de falta não é aleatório. Uma variante do MAM Slim-tree, chamada Hollow-tree foi proposta com base nestes resultados. A Hollow-tree usa novas técnicas de indexação e de recuperação de dados com valores faltantes quando o processo de falta é aleatório. A técnica de indexação inclui um conjunto de políticas de indexação que visam a evitardistorções na estrutura interna dos índices. A técnica de recuperação de dados melhora o desempenho das consultas por similaridade sobre bases de dados incompletas. Essas técnicas utilizam o conceito de dimensão fractal do conjunto de dados e a densidade local da região de busca para estimar um raio de busca ideal para obter uma resposta mais correta, considerando os dados com valores faltantes como uma resposta potencial. As técnicas propostas foram avaliadas sobre diversos conjuntos de dados reais e sintéticos. Os resultados mostram que a Hollow-tree atinge quase 100% de precisão e revocação para consultas por abrangência e mais de 90% para k vizinhos mais próximos, enquanto a Slim-tree rapidamente deteriora com o aumento da quantidade de valores faltantes. Tais resultados indicam que a técnica de indexação proposta ajuda a estabelecer a consistência na estrutura do índice e a técnica de busca pode ser realizada com um desempenho notável. As técnicas propostas são independentes do MAM básico usado e podem ser aplicadas em uma grande variedade deles, permitindo estender a classe dos MAMs em geral para tratar dados faltantes.
- Imprenta:
- Publisher place: São Carlos
- Date published: 2016
- Data da defesa: 18.07.2016
-
ABNT
BRINIS, Safia. Techniques for indexing large and complex datasets with missing attribute values. 2016. Tese (Doutorado) – Universidade de São Paulo, São Carlos, 2016. Disponível em: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-01122016-150947/. Acesso em: 07 jun. 2025. -
APA
Brinis, S. (2016). Techniques for indexing large and complex datasets with missing attribute values (Tese (Doutorado). Universidade de São Paulo, São Carlos. Recuperado de http://www.teses.usp.br/teses/disponiveis/55/55134/tde-01122016-150947/ -
NLM
Brinis S. Techniques for indexing large and complex datasets with missing attribute values [Internet]. 2016 ;[citado 2025 jun. 07 ] Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-01122016-150947/ -
Vancouver
Brinis S. Techniques for indexing large and complex datasets with missing attribute values [Internet]. 2016 ;[citado 2025 jun. 07 ] Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-01122016-150947/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
