Um algoritmo online para encontrar os elementos da fronteira de Pareto

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, sub$O(n^2)$) 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.

Em duas dimensões, cada atualização pode ser feita em $O(\lg n)$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. Deixei$F$denotar o conjunto de pontos na fronteira de Pareto. Loja$F$ em uma árvore binária equilibrada, usando o $x$-coordenado de cada ponto como sua chave. Observe que quando você classifica$F$ acrescentando $x$coordenados, eles também serão classificados diminuindo $y$-coordenada.

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

Além disso, dado um novo ponto $(x_q,y_q)$, é possível descobrir com eficiência se Dometo domina algum elemento do $F$. Em particular, você pode encontrar índices$i,j$ de modo que os pontos $(x_i,y_i),(x_{i+1},y_{i+1}),\dots,(x_j,y_j)$ do $F$ são todos dominados por Pareto por $(x_q,y_q)$ (assumindo que os pontos de $F$ foram ordenados por $x$coordenados, os pontos dominados por Pareto estarão em um intervalo consecutivo). Aqui está como. Encontre o primeiro elemento de$F$ à esquerda de $(x_q,y_q)$ (ou seja, o elemento $(x_j,y_j) \in F$ de tal modo que $x_j \le x_q$ e $x_j$ é o maior possível) e verifique se $(x_q,y_q)$domina isso. Se sim, encontre o menor índice$i$ de tal modo que $i<j$ (tão $x_i<x_j$) e $y_i \le y_q$. Ambas as etapas podem ser realizadas em$O(\lg n)$Tempo. (Encontrar$i$ pode ser feito em $O(\lg n)$ 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$(x_q,y_q)$ é dominado por algum ponto de $F$, não o adicione a $F$; Você Terminou. Como alternativa, se$(x_q,y_q)$ dominar pontos $i..j$ do $F$, é necessário excluir esses pontos de $F$ e adicione $(x_q,y_q)$ para dentro $F$. Isso pode ser feito em$O(\lg n)$ observando que qualquer intervalo de índices consecutivos pode ser expresso como a união de $O(\lg n)$ 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 $j$para a raiz); você pode excluir cada subárvore em$O(1)$Tempo. Isso permite excluir um intervalo inteiro de pontos consecutivos no$F$ no $O(\lg n)$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(\lg n)$ 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 como$O((\lg n)^{d-1})$ Onde $d$ é o número de dimensões).