Pesquisa sucinta de estruturas de dados?

O artigo de Fischer este mês me lembrou o pouco que sei sobre a arte de estruturas sucintas de dados e algoritmos para usá-las.

Para aqueles que não conhecem estruturas de dados sucintas:

Dada uma estrutura combinatória, com configurações diferentes (n) e uma representação "útil" conhecida . Existe uma estrutura de dados "sucinta" que leva o armazenamento de cerca de lg ( um ( n ) ) pedaços ainda nos permite executar operações o mais rápido que pudermos com a representação normal de R ?$R(n)$$\lg(a(n))$$R$

Os principais em que estou interessado, se alguém quiser participar de uma discussão

1. Matrizes de sufixo. Eles são um subconjunto de todas as permutações.

2. Árvores ordenadas. Eles são um subconjunto de todas as seqüências binárias de "parênteses" (a variedade correspondente).

3. Todos os valores menores mais próximos, como no artigo ( 1 ). Não apenas você pode comprimir nas duas dimensões; as admissíveis de matrizes "menor valor" em um sentido é um pequeno subconjunto de listas e, portanto, você precisa armazenar menos de n lg ( n ) bits.$\{0,...,n-1\}^n$$n \lg(n)$

Confira também a tese de Ankur Gupta , com ênfase em dados compactáveis.

Se falar sobre estruturas de dados com sufixos sucintos, esta de Navarro e Mäkinen é realmente boa: http://portal.acm.org/citation.cfm?doid=1216370.1216372

Agora há um livro sobre o assunto: Estruturas compactas de dados: uma abordagem prática, de Gonzalo Navarro. https://dl.acm.org/citation.cfm?id=3092586