Um algoritmo online para encontrar os elementos da fronteira de Pareto

6

Estou procurando um algoritmo on-line que utiliza um fluxo de elementos e preserva os elementos que estão na fronteira de Pareto (por exemplo, todos os elementos não dominados).

Por exemplo. Dadas as seguintes entradas, o conjunto de fronteiras retidas de Pareto evoluiria da seguinte maneira:

  • (3,7)
    • inserir elemento b / c é o primeiro elemento
    • conjunto de pareto agora inclui {(3,7)}
  • (7,3)
    • inserir elemento b / c não é dominado no primeiro
    • conjunto de pareto agora inclui {(3,7), (7,3)}
  • (8,4)
    • insira o elemento b / c não é dominado; remova o (7,3)que é dominado em ambas as dimensões
    • conjunto de pareto agora inclui {(3,7), (8,4)}
  • (1,1)
    • não insira porque domina nas duas dimensões
    • conjunto de pareto agora inclui {(3,7), (8,4)}
  • (9,9)
    • insira o elemento b / c não é dominado; remova todos os outros elementos porque isso os domina nas duas dimensões
    • conjunto de pareto agora inclui {(9,9)}

No meu exemplo, estou usando duas tuplas, mas estou procurando um algoritmo que possa manipular N-tuplas para N "pequeno" (digamos <10).

A solução ingênua é apenas comparar cada elemento com todos os elementos atualmente no conjunto. Na prática, a abordagem ingênua pode não ser tão ruim (por exemplo, subO(n2)) porque os elementos serão expulsos regularmente pelo conjunto de comparação. Mas eu queria saber se havia um algoritmo eficiente conhecido para isso. Estou interessado em eficiência na memória e na complexidade computacional. (Ha! E, de fato, estou procurando o conjunto de algoritmos que são ótimos de Pareto em relação à memória e à complexidade computacional.)

Minha aplicação atual disso é a construção de um documento de pesquisa LuceneCollector que não coleta os documentos mais relevantes (o caso de uso típico de um mecanismo de pesquisa), mas coleta os documentos ideais do Pareto nas dimensões especificadas.

JnBrymn
fonte
11
Você está interessado no custo amortizado ou no máximo do custo de cada atualização?
2
A fronteira de Pareto também é chamada de horizonte ou máximos. Portanto, tente palavras-chave como "on-line, horizonte / máximos, fluxo de dados, manutenção" no google.
precisa saber é
Este artigo tem várias soluções dl.acm.org/citation.cfm?doid=1142473.1142530

Respostas:

4

Em duas dimensões, cada atualização pode ser feita em O(lgn)tempo, usando uma estrutura de dados de árvore binária balanceada. Mas quando você está trabalhando em um espaço de alta dimensão, não conheço nenhuma solução eficiente.

Deixe-me descrever um algoritmo eficiente para o caso 2D. DeixeiFdenotar o conjunto de pontos na fronteira de Pareto. LojaF em uma árvore binária equilibrada, usando o x-coordenado de cada ponto como sua chave. Observe que quando você classificaF acrescentando xcoordenados, eles também serão classificados diminuindo y-coordenada.

Agora, dado um novo ponto (xq,yq), você pode verificar com eficiência se é dominado por Pareto por qualquer elemento do F. Encontre o primeiro elemento deF para a direita de (xq,yq) (ou seja, o elemento (x,y)F de tal modo que xxq e xé mínimo); então verificando se ele domina(xq,yq).

Além disso, dado um novo ponto (xq,yq), é possível descobrir com eficiência se Dometo domina algum elemento do F. Em particular, você pode encontrar índicesi,j de modo que os pontos (xi,yi),(xi+1,yi+1),,(xj,yj) do F são todos dominados por Pareto por (xq,yq) (assumindo que os pontos de F foram ordenados por xcoordenados, os pontos dominados por Pareto estarão em um intervalo consecutivo). Aqui está como. Encontre o primeiro elemento deF à esquerda de (xq,yq) (ou seja, o elemento (xj,yj)F de tal modo que xjxq e xj é o maior possível) e verifique se (xq,yq)domina isso. Se sim, encontre o menor índicei de tal modo que i<j (tão xi<xj) e yiyq. Ambas as etapas podem ser realizadas emO(lgn)Tempo. (Encontrari pode ser feito em O(lgn) tempo, tratando a árvore como ramificação no y-coordenada de pontos, e aproveitando o fato de que os pontos de F são classificados diminuindo y-coordenada.)

Agora isso nos diz o que fazer. E se(xq,yq) é dominado por algum ponto de F, não o adicione a F; Você Terminou. Como alternativa, se(xq,yq) dominar pontos i..j do F, é necessário excluir esses pontos de F e adicione (xq,yq) para dentro F. Isso pode ser feito emO(lgn) observando que qualquer intervalo de índices consecutivos pode ser expresso como a união de O(lgn) subárvores da árvore binária (grosso modo, você trabalha com os irmãos dos nós ao longo do caminho de i para a raiz e o mesmo para o caminho de jpara a raiz); você pode excluir cada subárvore emO(1)Tempo. Isso permite excluir um intervalo inteiro de pontos consecutivos noF no O(lgn)tempo, não importa o tamanho da faixa. Para obter detalhes, consulte Excluir um intervalo consecutivo de folhas de uma árvore binária .

Tudo isso pode ser feito em O(lgn) tempo, usando uma estrutura de dados de árvore binária balanceada.

Isso funciona em duas dimensões (isto é, duas tuplas). Em dimensões mais altas, o problema fica muito mais difícil. Você pode encontrar referências à literatura, com técnicas para dimensões mais altas, em Como encontrar um subconjunto de vetores potencialmente máximos (de números) em um conjunto de vetores ; mas receio que, em altas dimensões, todos os algoritmos conhecidos provavelmente sejam bastante lentos (eles têm um fator que é algo comoO((lgn)d1) Onde d é o número de dimensões).

DW
fonte
11
Árvores binárias balanceadas permitem O (log (n)) - exclusões de intervalos de tempo ?
11
Esta é uma boa resposta. Embora me chame a atenção que impliquei uma restrição ao meu exemplo que não pretendia. No meu exemplo, estou usando 2 tuplas, mas eu precisaria de um algoritmo que manipule N-tuplas.
precisa saber é o seguinte
11
@JnBrymn, veja minha resposta atualizada: adicionei um parágrafo ao final para abordar a situação em dimensões mais altas.
DW
Consulte "remova todos os outros elementos porque isso os domina nas duas dimensões". (Não pode facilmente ser um elementos número lineares a serem removidos, por isso, se você tem que fazer que um elemento de cada vez, em seguida, as atualizações podem tomar O tempo de pior caso (n).)
Em duas dimensões, como os elementos agora estritamente dominados são removidos no tempo O (log (n))?