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
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
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.
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.