logo móvil
Contáctanos

DenseZDD: un índice compacto y rápido para familias de conjuntos

Autores: Denzumi, Shuhei; Kawahara, Jun; Tsuda, Koji; Arimura, Hiroki; Minato, Shin-ichi; Sadakane, Kunihiko

Idioma: Inglés

Editor: MDPI

Año: 2018

Descargar PDF

Acceso abierto

Artículo científico
2018

DenseZDD: un índice compacto y rápido para familias de conjuntos


Categoría

Ingeniería y Tecnología

Subcategoría

Ingeniería de Software

Palabras clave

Estructura de datos
ZDD
Conjuntos
Combinaciones
Compresión
DenseZDD

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 32

Citaciones: Sin citaciones


Descripción
En este artículo, proponemos una estructura de datos sucinta de diagramas de decisión binaria suprimida de cero (ZDDs). Un ZDD representa conjuntos de combinaciones de manera eficiente y podemos realizar diversas operaciones de conjunto en el ZDD sin extraer explícitamente combinaciones. Gracias a estas características, los ZDDs se han aplicado a la recuperación de información en la web, integración de información y minería de datos. Sin embargo, para admitir una manipulación rica de conjuntos de combinaciones y actualizar ZDDs en el futuro, los ZDDs necesitan demasiado espacio, lo que significa que todavía hay margen para ser comprimidos. El documento presenta una nueva estructura de datos sucinta, llamada DenseZDD, para comprimir aún más un ZDD cuando no necesitamos realizar operaciones de conjunto en el ZDD pero queremos examinar si un conjunto dado está incluido en la familia representada por el ZDD, y contar el número de elementos en la familia. También proponemos un método híbrido, que combina DenseZDDs con ZDDs ordinarios. Mediante experimentos numéricos, mostramos que los tamaños de nuestras estructuras de datos son tres veces más pequeños que los de ZDDs ordinarios, y las operaciones de pertenencia y muestreo aleatorio en DenseZDDs son aproximadamente diez veces y tres veces más rápidas que las de ZDDs ordinarios para algunos conjuntos de datos, respectivamente.

Otros recursos que podrían interesarte

Temas Virtualpro