Pensando Além dos Limites Computacionais
Coleção Escola de Lógica Matemática
JOÃO CARLOS MOREIRA
Doutor em Matemática
Universidade Federal de Uberlândia
Copyright©2013-2025 Coleção Escola de Lógica Matemática. Todos os direitos reservados.
Imagine tentar contar quantas pessoas passaram por uma estação de metrô movimentada durante o dia inteiro, mas você só pode olhar rapidamente para algumas delas. Ou pense em descobrir se dois arquivos gigantescos são idênticos sem precisar comparar cada byte. Parece impossível? Bem-vindo ao fascinante universo da lógica sublinear, onde fazemos o aparentemente impossível: resolvemos problemas enormes olhando apenas para uma pequena parte deles. Esta é a mágica matemática que permite ao Google processar bilhões de páginas, ao Netflix recomendar filmes entre milhões de opções, e aos cientistas analisarem o DNA sem examinar cada gene individualmente.
A lógica sublinear estuda algoritmos e estruturas de dados que usam menos recursos — tempo, espaço ou ambos — do que o tamanho da entrada que estão processando. Se você tem um bilhão de números e quer saber aproximadamente qual é a média, um algoritmo tradicional precisaria olhar todos eles. Um algoritmo sublinear consegue dar uma resposta muito boa olhando apenas alguns milhares, economizando tempo e recursos preciosos.
Vivemos na era do big data. A cada minuto, são enviados 500 milhões de tweets, assistidos 4 milhões de horas de vídeo no YouTube, e realizadas 4 milhões de buscas no Google. Processar toda essa informação da maneira tradicional seria como tentar beber água do oceano com um canudinho. A lógica sublinear nos dá ferramentas para extrair informações úteis desse dilúvio de dados sem nos afogarmos nele.
Na matemática tradicional, buscamos respostas exatas. Na lógica sublinear, abraçamos a aproximação como uma ferramenta poderosa. Se você quer saber quantas pessoas moram no Brasil, precisa realmente saber se são 213.456.789 ou 213.456.790? Para a maioria dos propósitos, saber que são aproximadamente 213 milhões é perfeitamente adequado e muito mais rápido de calcular.
A teoria da complexidade tradicional classifica algoritmos pelo tempo que levam em relação ao tamanho da entrada. Linear O(n) significa que o tempo cresce proporcionalmente ao tamanho. Sublinear significa crescer menos que isso: O(log n), O(√n), ou até mesmo O(1) — tempo constante, independente do tamanho! É como ter um superpoder computacional que permite resolver problemas gigantescos em tempo recorde.
A lógica sublinear abraça a aleatoriedade como aliada. Algoritmos probabilísticos fazem escolhas aleatórias durante sua execução, e isso, surpreendentemente, os torna mais eficientes. É como jogar dados para tomar decisões, mas de forma calculada e com garantias matemáticas sobre a qualidade do resultado. A probabilidade nos permite trocar certeza absoluta por eficiência extraordinária.
A lógica sublinear é sobre fazer escolhas inteligentes. Trocamos precisão absoluta por velocidade, memória infinita por estruturas compactas, certeza por alta probabilidade de acerto. Esses trade-offs não são defeitos, são características projetadas que nos permitem lidar com problemas que seriam intratáveis de outra forma.
A lógica sublinear não é apenas teoria abstrata — ela está transformando o mundo ao nosso redor. Desde a forma como buscamos informações na internet até como descobrimos novos medicamentos, passando por como detectamos fraudes bancárias e prevemos o tempo. Cada vez que você usa um aplicativo que processa milhões de dados instantaneamente, há uma boa chance de que algoritmos sublineares estejam trabalhando nos bastidores.
À medida que geramos mais dados do que nunca — estima-se que criamos 2,5 quintilhões de bytes por dia — a necessidade de processar informação eficientemente só aumenta. A lógica sublinear não é apenas uma otimização; é uma necessidade fundamental para o futuro da computação. Ela nos permite fazer mais com menos, transformando montanhas de dados em insights acionáveis sem precisar escalar toda a montanha.
Nossa jornada pela lógica sublinear será progressiva e empolgante. Começaremos com os fundamentos dos algoritmos probabilísticos, exploraremos técnicas de amostragem, mergulharemos em estruturas de dados revolucionárias, e terminaremos vendo como tudo isso se aplica no seu dia a dia. Cada capítulo constrói sobre o anterior, mas também pode ser apreciado independentemente.
A lógica sublinear representa uma mudança fundamental em como pensamos sobre computação e resolução de problemas. Ela nos ensina que limitações podem inspirar criatividade, que aleatoriedade pode trazer eficiência, e que aproximações inteligentes podem ser mais valiosas que respostas exatas demoradas. Prepare-se para descobrir como fazer muito com pouco, como o impossível se torna possível, e como a matemática continua a surpreender e encantar com suas soluções elegantes para os desafios do mundo moderno!
Jogar uma moeda para tomar decisões importantes pode parecer loucura, mas e se eu dissesse que alguns dos algoritmos mais poderosos e eficientes do mundo fazem exatamente isso? Os algoritmos probabilísticos usam aleatoriedade de forma controlada e inteligente para resolver problemas que seriam impraticáveis de outra forma. Como mágicos matemáticos, eles transformam o caos do acaso em soluções elegantes e surpreendentemente confiáveis. Neste capítulo, descobriremos como a aleatoriedade, longe de ser um obstáculo, torna-se nossa maior aliada na busca por eficiência computacional.
Algoritmos probabilísticos não são sobre deixar tudo ao acaso. Eles usam aleatoriedade estrategicamente, com garantias matemáticas rigorosas sobre seu comportamento. É como um chef que adiciona uma pitada de sal "a gosto" — parece impreciso, mas anos de experiência garantem um resultado consistentemente bom. Na computação, usamos teoria das probabilidades para garantir que nossos "palpites aleatórios" sejam surpreendentemente precisos.
Algoritmos Monte Carlo são como jogadores calculistas em um cassino matemático. Eles sempre terminam rapidamente, mas existe uma pequena chance de erro. Imagine estimar o valor de π jogando dardos aleatoriamente em um quadrado com um círculo inscrito. Quanto mais dardos você joga, mais precisa fica sua estimativa. Este método, aparentemente caótico, converge para o valor correto com precisão impressionante.
Algoritmos Las Vegas são perfeccionistas que usam sorte para acelerar. Eles sempre dão a resposta correta, mas o tempo pode variar. É como embaralhar um baralho até conseguir uma ordem específica — você sabe que vai conseguir, só não sabe quanto tempo vai levar. Quicksort com pivô aleatório é um exemplo clássico: sempre ordena corretamente, mas a escolha aleatória do pivô afeta dramaticamente o desempenho.
Determinar se um número gigantesco é primo costumava ser computacionalmente proibitivo. O teste de Miller-Rabin mudou isso usando probabilidade. Ele escolhe números aleatórios como "testemunhas" para verificar primalidade. Se o número passa em vários testes, a probabilidade de ser primo é altíssima. Com 40 rodadas, a chance de erro é menor que 1 em um trilhão — mais confiável que muitos sistemas que consideramos "determinísticos"!
Muitos problemas difíceis tornam-se tratáveis quando combinamos aproximação com aleatoriedade. MAX-CUT, o problema de dividir um grafo em dois grupos maximizando arestas entre eles, é NP-difícil. Mas um algoritmo randomizado simples — atribuir cada vértice aleatoriamente a um grupo — garante encontrar um corte com pelo menos metade das arestas em expectativa. Simples, rápido e surpreendentemente eficaz!
Analisar algoritmos probabilísticos requer ferramentas matemáticas especiais. Usamos valor esperado para medir desempenho médio, variância para entender dispersão, e desigualdades de concentração como Chernoff e Hoeffding para garantir que resultados ruins são raros. É como prever o clima: não sabemos se vai chover amanhã com certeza, mas podemos dar probabilidades confiáveis baseadas em modelos matemáticos.
Um truque poderoso dos algoritmos probabilísticos é a amplificação: repetir um algoritmo com chance moderada de sucesso para obter confiabilidade arbitrária. Se um algoritmo acerta 60% das vezes, executá-lo 100 vezes e tomar a resposta majoritária dá mais de 99% de acerto. É o princípio da sabedoria das multidões aplicado à computação — múltiplas tentativas independentes convergem para a verdade.
Funções hash transformam dados em números aparentemente aleatórios, fundamentais para estruturas de dados eficientes. Hashing universal escolhe funções aleatoriamente de uma família, garantindo boa distribuição independente dos dados. É como ter um embaralhador mágico que funciona bem para qualquer baralho, não importa como estava organizado inicialmente.
Random walks — caminhadas aleatórias — são surpreendentemente poderosas. O algoritmo PageRank do Google modela a web como uma caminhada aleatória, onde a importância de uma página é a probabilidade de um "surfista aleatório" estar nela. Essa ideia simples revolucionou a busca na internet e demonstra como aleatoriedade pode capturar estruturas complexas.
Paradoxalmente, algoritmos probabilísticos às vezes podem ser "derandomizados" — convertidos em determinísticos mantendo eficiência. O método das expectativas condicionais substitui escolhas aleatórias por escolhas que garantem pelo menos o desempenho esperado. É como transformar um jogo de azar em estratégia pura, mantendo as vantagens da abordagem probabilística.
Algoritmos probabilísticos nos ensinam uma lição profunda: abraçar a incerteza pode levar a soluções mais certas. Eles transformam o que parece ser fraqueza — dependência do acaso — em força computacional. Como vimos, aleatoriedade bem aplicada não é sobre deixar tudo à sorte, mas sobre usar probabilidade como uma ferramenta matemática poderosa. No próximo capítulo, exploraremos como essa filosofia se aplica especificamente à arte da amostragem, onde pequenas porções revelam verdades sobre o todo!
Como uma colher de sopa pode revelar o sabor de toda a panela, a amostragem nos permite conhecer o todo através de suas partes. Esta técnica milenar, usada desde que humanos provavam comida antes de servir, tornou-se uma ciência matemática sofisticada na era digital. Quando temos bilhões de dados mas precisamos de respostas em milissegundos, a amostragem inteligente é nossa salvação. Neste capítulo, exploraremos como escolher as amostras certas, quanto precisamos para ter confiança em nossas estimativas, e como transformar pequenos vislumbres em visões completas.
Uma boa amostra é como uma miniatura perfeita: pequena mas fiel ao original. A teoria da amostragem nos ensina que, sob condições adequadas, propriedades estatísticas de uma amostra convergem para as da população. O Teorema Central do Limite garante que médias de amostras se distribuem normalmente, independente da distribuição original. Esta magia matemática transforma incerteza em previsibilidade.
A forma mais básica de amostragem é escolher elementos com igual probabilidade. Como tirar bolas numeradas de um globo de bingo, cada elemento tem a mesma chance. Para estimar a altura média de uma floresta, medimos algumas árvores escolhidas aleatoriamente. Simples, mas poderoso: com apenas 1000 amostras, podemos estimar médias de bilhões com erro menor que 3%.
Como amostrar de um fluxo quando não sabemos quantos elementos virão? Reservoir sampling é a solução elegante. Mantemos um "reservatório" de k amostras. Cada novo elemento tem chance k/n de substituir um elemento aleatório do reservatório, onde n é o número de elementos vistos. Magicamente, isso garante que cada elemento tem probabilidade k/n de estar na amostra final, mesmo sem saber n antecipadamente!
Quando a população tem subgrupos distintos, amostragem estratificada garante representação de todos. É como montar uma equipe diversa: queremos pessoas de diferentes departamentos. Dividimos a população em estratos e amostramos de cada um proporcionalmente. Isso reduz variância e melhora estimativas, especialmente quando estratos são homogêneos internamente mas diferentes entre si.
Nem todos os elementos são igualmente importantes. Importance sampling dá mais peso a elementos que contribuem mais para nossa estimativa. É como entrevistar mais especialistas que leigos sobre um tema técnico. Amostramos com probabilidades proporcionais à importância, depois corrigimos o viés repondendo pela probabilidade de seleção. Isso pode reduzir drasticamente a variância quando bem aplicado.
Bootstrap é quase mágico: estimamos a variabilidade de uma estatística reamostrando da própria amostra! Criamos milhares de "reamostras" do mesmo tamanho, com reposição, calculamos a estatística em cada uma, e usamos a distribuição resultante para intervalos de confiança. É como criar universos paralelos a partir dos dados que temos, cada um contando uma versão ligeiramente diferente da história.
Um estimador é uma receita para calcular uma estimativa a partir de amostras. Bons estimadores são não-viesados (acertam em média), consistentes (melhoram com mais dados) e eficientes (têm baixa variância). A média amostral é o estimador não-viesado de variância mínima para a média populacional. Mas às vezes, um pouco de viés vale a pena para reduzir muito a variância — o trade-off bias-variance é fundamental em estatística.
Quantas amostras precisamos? A resposta depende da precisão desejada e confiança requerida. Para estimar uma proporção com margem de erro ε e confiança 95%, precisamos de n ≈ 1/ε² amostras. Surpreendentemente, isso independe do tamanho da população! Pesquisar opinião de 1000 pessoas dá a mesma precisão para uma cidade ou um país, desde que a amostragem seja adequada.
Amostragem adaptativa ajusta sua estratégia baseada no que já viu. Como um detetive que segue pistas, focamos esforços onde há mais informação. Se detectamos alta variabilidade numa região, aumentamos amostragem lá. Se uma área é homogênea, reduzimos. Isso maximiza informação por amostra, crucial quando amostragem é cara.
Desigualdades de concentração quantificam quão perto amostras ficam da média. Hoeffding nos diz que a probabilidade da média amostral desviar mais que t da média real cai exponencialmente com o número de amostras. Com 10.000 amostras, a chance de erro maior que 1% é menor que 0,0001%. Esses limites transformam amostragem de arte em ciência exata.
Amostragem é a arte de ver o invisível através do visível, de conhecer o todo através da parte. Como exploradores que mapeiam continentes visitando apenas alguns pontos estratégicos, usamos amostras para navegar oceanos de dados. A matemática nos garante que, com as técnicas certas, pequenas janelas revelam panoramas completos. No próximo capítulo, veremos como comprimir não apenas a quantidade de dados que observamos, mas também como os armazenamos, através de estruturas de dados compactas que preservam informação essencial em espaço mínimo!
Imagine guardar a Biblioteca Nacional inteira em um pendrive, ou representar toda a rede de amizades do Facebook usando menos memória que um filme em HD. As estruturas de dados compactas tornam esses milagres possíveis, comprimindo informação ao máximo enquanto mantêm acesso rápido. Como origami digital, elas dobram e redobram dados em formas mínimas mas ainda funcionais. Neste capítulo, descobriremos como espremer quintilhões de bits em gigabytes, mantendo a capacidade de responder perguntas em microssegundos.
Estruturas de dados tradicionais desperdiçam espaço em troca de simplicidade. Um array de booleanos usa 8 bits por valor verdadeiro/falso, quando 1 bit bastaria. Ponteiros em árvores podem consumir mais memória que os dados em si. Estruturas compactas eliminam esse desperdício usando representações próximas ao limite teórico da informação, mantendo operações eficientes através de truques engenhosos.
Bit vectors são arrays de bits com superpoderes. Além de armazenar bits, suportam operações rank (quantos 1s até a posição i?) e select (onde está o k-ésimo 1?) em tempo constante. Com apenas 5% de overhead sobre os bits originais, transformamos uma sequência passiva em uma estrutura navegável. É a base para estruturas mais complexas, como árvores sucintas.
Bloom filters são estruturas geniais que respondem "definitivamente não" ou "provavelmente sim" sobre pertinência a conjuntos. Usando apenas 10 bits por elemento, conseguem taxa de falso positivo de 1%. É como ter um porteiro com memória fotográfica imperfeita: nunca esquece quem viu, mas às vezes acha que viu alguém que não viu. Perfeito quando falsos positivos são toleráveis mas falsos negativos não.
Count-Min sketch estima frequências de elementos usando espaço sublinear. Como uma planilha comprimida que registra quantas vezes cada item apareceu, mas usando fração da memória. Com d arrays de w contadores e d funções hash, garantimos que superestimamos frequências por no máximo ε*n com probabilidade 1-δ. Netflix usa para contar visualizações, Twitter para trending topics.
Como contar bilhões de elementos únicos usando apenas kilobytes? HyperLogLog é a resposta surpreendente. Baseado na observação de que padrões em hashes revelam cardinalidade, estima números distintos com erro de apenas 2% usando 1.5KB. Google usa para contar usuários únicos, Redis oferece nativamente. É quase mágico: ver bilhões, lembrar kilobytes.
Suffix arrays permitem busca rápida de padrões em textos, mas normalmente usam n log n bits. Versões comprimidas alcançam nH₀ + o(n) bits (onde H₀ é entropia), mantendo busca em O(log n). É como comprimir um dicionário mantendo a capacidade de procurar palavras instantaneamente. Fundamental para genômica, onde genomas são gigantescos mas alfabeto é pequeno.
Tries armazenam strings com prefixos compartilhados, mas ponteiros desperdiçam espaço. Patricia tries comprimem caminhos únicos. Judy arrays vão além, adaptando estrutura por nível de densidade. XOR-tries usam propriedade XOR para navegação sem ponteiros. Resultado: dicionários que cabem em fração do espaço, mantendo busca logarítmica.
Representar grafos tradicionalmente usa O(m log n) bits para m arestas e n vértices. Representações sucintas alcançam 2m + o(m) bits mantendo navegação eficiente. Para grafos planares, apenas 2 bits por aresta! Redes sociais com bilhões de conexões tornam-se manipuláveis. É como desenhar o mapa-múndi em um guardanapo, mas ainda conseguir navegar.
Às vezes o melhor jeito de compactar é aproximar. Quantização reduz precisão numérica: em vez de floats de 32 bits, usamos 8 ou 4 bits. Sketches mantêm resumos aproximados. Product quantization divide vetores em subvetores quantizados independentemente. Machine learning abraçou essas técnicas: modelos com 1/10 do tamanho e 99% da precisão.
Estruturas cache-oblivious são otimizadas para hierarquia de memória sem conhecer tamanhos de cache. Como van Emde Boas layout para árvores, que coloca nós relacionados próximos. Fractional cascading conecta estruturas para busca paralela eficiente. Funcionam bem em qualquer máquina, do celular ao supercomputador, adaptando-se automaticamente.
Estruturas de dados compactas são a alquimia moderna: transformam montanhas de dados em cristais de informação pura. Elas nos mostram que o espaço não é fixo, mas maleável através de engenhosidade matemática. Como vimos, podemos ter nosso bolo e comê-lo também — espaço mínimo e acesso rápido não são mutuamente exclusivos. No próximo capítulo, continuaremos essa jornada de fazer mais com menos, explorando como contar aproximadamente quando contar exatamente é impossível!
Contar parece a coisa mais simples do mundo — um, dois, três... Mas e quando precisamos contar estrelas no céu, grãos de areia na praia, ou cliques em um site com milhões de visitantes por segundo? A contagem exata torna-se impossível ou impraticável. A contagem aproximada nos oferece uma saída elegante: em vez de saber que temos exatamente 1.234.567.890 itens, saber que temos aproximadamente 1,23 bilhões é frequentemente suficiente e incrivelmente mais eficiente. Neste capítulo, exploraremos técnicas engenhosas que transformam o problema de contagem infinita em soluções práticas e surpreendentemente precisas.
Cada contador exato precisa de log n bits para contar até n. Para contar até um trilhão, precisamos de 40 bits por contador. Com milhões de contadores (comum em sistemas distribuídos), a memória explode. Contadores aproximados quebram essa barreira usando representações logarítmicas, probabilísticas ou adaptativas. É como usar notação científica em vez de escrever todos os zeros — mantemos a essência descartando precisão desnecessária.
O algoritmo de Morris é genialmente simples: em vez de incrementar sempre, incrementamos com probabilidade 1/2^v onde v é o valor atual. O contador cresce logaritmicamente, usando apenas log log n bits para contar até n! Com 8 bits, contamos até cerca de 130.000 com erro relativo de 25%. É como subir uma escada onde cada degrau é duas vezes mais alto que o anterior — chegamos muito alto com poucos passos.
Generalizando Morris, podemos usar qualquer base b > 1. Com probabilidade 1/b^v, incrementamos. Bases menores dão mais precisão mas crescem mais rápido. Base φ (golden ratio) minimiza erro esperado. Podemos até variar a base dinamicamente: alta precisão para valores pequenos, menor precisão para grandes. É contagem adaptativa que se ajusta à escala.
Para contar elementos distintos, LogLog usa uma observação brilhante: em hashes uniformes, o padrão de bits revela cardinalidade. Se vemos um hash começando com k zeros, provavelmente vimos cerca de 2^k elementos. Mantendo o máximo de zeros líderes vistos, estimamos cardinalidade. Com múltiplos buckets para reduzir variância, alcançamos precisão impressionante em espaço mínimo.
Encontrar elementos mais frequentes (heavy hitters) em streams é crucial. Count-Min sketch com heap mantém top-k elementos aproximadamente. Quando um contador no sketch ultrapassa o mínimo do heap, substituímos. Garantimos encontrar todos elementos com frequência > ε*n, possivelmente incluindo alguns falsos positivos. Twitter trends, queries populares, IPs suspeitos — todos detectados assim.
Space-Saving mantém exatamente k contadores para encontrar top-k elementos. Quando chega novo elemento: se está nos contadores, incrementa; se há espaço, adiciona; senão, substitui o mínimo e incrementa. Surpreendentemente, isso garante que elementos frequentes permanecem, com erro limitado. Usa espaço fixo O(k), independente do stream.
Contar em janelas deslizantes (últimas 24 horas, último milhão de elementos) é desafiador. Exponential histograms mantêm buckets de tamanhos exponencialmente crescentes, permitindo consultas aproximadas sobre qualquer janela recente. Hokusai sketches estendem isso para múltiplas granularidades temporais. É como ter um telescópio temporal que vê detalhes recentes e resumos do passado.
Para economizar ainda mais, cascading counters usam representação variável. Contadores pequenos usam poucos bits; quando overflow, promovem para representação maior. Como um acordeão digital, expandem conforme necessário. A maioria dos contadores permanece pequena (lei de Zipf), economizando memória drasticamente.
Contar em sistemas distribuídos adiciona complexidade. CRDTs (Conflict-free Replicated Data Types) como G-Counter permitem incrementos concorrentes sem coordenação. Vector clocks rastreiam causalidade. Gossip protocols propagam contagens aproximadas. É como fazer um censo onde cada região conta independentemente, depois reconcilia.
Contagem aproximada é crucial em ML. Feature hashing conta frequências sem dicionário. Count sketches aproximam gradientes em treinamento distribuído. Quantização conta valores únicos após discretização. Reservoir sampling conta classes em streams desbalanceados. Cada técnica economiza memória mantendo qualidade do modelo.
Contagem aproximada nos ensina que perfeição é luxo, não necessidade. Como impressionistas que capturam essência sem detalhar cada folha, contadores aproximados revelam padrões gerais sacrificando precisão desnecessária. Vimos que com bits de criatividade matemática, podemos contar até o infinito em espaço finito. No próximo capítulo, aplicaremos essas ideias a um desafio ainda maior: processar fluxos infinitos de dados que nunca param de chegar!
Imagine tentar analisar um rio enquanto ele flui — você não pode parar a água, não pode voltar para ver o que passou, e não pode armazenar todo o rio em baldes. Este é o desafio dos fluxos de dados: processar informação que chega continuamente, uma única vez, com memória limitada. De tweets surgindo a cada milissegundo a sensores IoT transmitindo incessantemente, o mundo moderno é um dilúvio de dados em movimento. Neste capítulo, exploraremos as técnicas revolucionárias que nos permitem extrair insights de torrentes infinitas de informação sem nos afogar nelas.
Processamento tradicional assume dados estáticos que podemos revisitar. Streams quebram essa suposição: dados chegam continuamente, devemos processar imediatamente, e geralmente só podemos ver cada item uma vez. É como ser um inspetor em uma linha de produção que nunca para — você deve tomar decisões em tempo real sem poder voltar atrás. Esta restrição força criatividade e leva a algoritmos surpreendentemente elegantes.
Diferentes modelos capturam diferentes cenários. No modelo cash register, só vemos inserções (valores positivos). No turnstile, temos inserções e deleções. No sliding window, focamos em dados recentes. Cada modelo tem seus desafios e soluções. É como diferentes jogos com o mesmo baralho — as regras mudam a estratégia completamente.
Sketches são resumos compactos mantidos incrementalmente conforme dados chegam. Como um artista que captura a essência de uma cena com poucos traços, sketches preservam propriedades importantes descartando detalhes. AMS sketch estima momentos, Count-Min rastreia frequências, FM sketch conta elementos distintos. Cada sketch é otimizado para queries específicas.
Como amostrar de um stream quando não sabemos quantos elementos virão? Reservoir sampling mantém amostra uniforme de tamanho fixo. Biased sampling favorece elementos recentes ou importantes. Priority sampling preserva elementos de alto valor. É como pescar em um rio — diferentes redes capturam diferentes peixes, mas todas cabem no barco.
Encontrar agulhas em palheiros que se movem requer algoritmos especiais. Detectamos anomalias comparando comportamento atual com modelos aprendidos do stream. EWMA (médias móveis exponenciais) rastreia tendências. Isolation forests identificam outliers. Matrix sketching detecta mudanças em correlações. É vigilância constante sem memória infinita.
Muitas queries focam em dados recentes: vendas da última hora, tweets do último minuto. Sliding windows mantêm agregados sobre janelas móveis eficientemente. Exponential histograms aproximam somas, SWAT tracks quantis, Sticky sampling mantém frequent items. É como ter um periscópio temporal que sempre mostra o presente recente.
Combinar múltiplos streams é como sincronizar múltiplos relógios em movimento. Symmetric hash join processa chegadas de ambos streams. Band join foca em elementos temporalmente próximos. Sketch-based joins aproximam resultados usando resumos. Load shedding descarta dados menos importantes sob pressão. É malabarismo com dados voando de todas as direções.
CEP detecta padrões em sequências de eventos. Como encontrar melodias em ruído, identifica sequências significativas em streams caóticos. Máquinas de estado rastreiam progressão de padrões. Árvores de decisão filtram eventos relevantes. Janelas correlacionam eventos relacionados. Aplicações vão de detecção de fraude a trading algorítmico.
Aprender de streams requer algoritmos que adaptam modelos incrementalmente. Hoeffding trees constroem árvores de decisão online. Streaming k-means atualiza clusters conforme dados chegam. Online gradient descent ajusta modelos continuamente. Concept drift detection identifica quando padrões mudam. É educação perpétua onde o currículo nunca termina.
Frameworks modernos tornam stream processing acessível. Apache Kafka move dados entre sistemas. Flink e Spark Streaming processam streams em escala. Storm garante processamento exactly-once. Kinesis integra com cloud AWS. Cada sistema balanceia latência, throughput e garantias diferentemente.
Fluxos de dados nos ensinam a dançar com o caos, a encontrar padrões em movimento perpétuo. Como surfistas navegando ondas infinitas, aprendemos a extrair valor de dados que nunca param. As técnicas deste capítulo transformam o impossível — processar infinito com recursos finitos — em rotina. No próximo capítulo, aprofundaremos em uma das ferramentas mais poderosas para streams: sketches, as estruturas que comprimem universos em bytes!
Um artista talentoso pode capturar a essência de uma paisagem complexa com apenas algumas pinceladas. Da mesma forma, sketches matemáticos capturam propriedades essenciais de conjuntos de dados massivos usando espaço mínimo. Estes resumos probabilísticos são como fotografias comprimidas da realidade dos dados — não preservam cada detalhe, mas mantêm informação suficiente para responder perguntas importantes com precisão surpreendente. Neste capítulo, exploraremos a arte e ciência de criar estes resumos mágicos que transformam terabytes em kilobytes sem perder a alma dos dados.
Sketches abraçam perda controlada de informação em troca de eficiência extrema. Como mapas que omitem detalhes irrelevantes para destacar o importante, sketches preservam propriedades específicas descartando o resto. São projetados para queries particulares: alguns estimam frequências, outros medem similaridade, outros contam elementos únicos. Esta especialização permite compressão radical mantendo precisão para o que importa.
MinHash cria assinaturas compactas que preservam similaridade de Jaccard. Para cada conjunto, mantemos k valores mínimos de hash. Surpreendentemente, a probabilidade de duas assinaturas coincidirem equals a similaridade original! Com 128 hashes, estimamos similaridade de conjuntos com milhões de elementos usando apenas 512 bytes. Google usa para detectar páginas duplicadas entre bilhões.
Enquanto MinHash preserva similaridade de conjuntos, SimHash preserva similaridade de vetores. Bits do hash são determinados pelo sinal de projeções aleatórias. Vetores similares produzem hashes similares (pequena distância de Hamming). É como criar um código de barras onde produtos parecidos têm códigos parecidos. Fundamental para busca aproximada em alta dimensão.
T-digest mantém distribuições completas em espaço constante, com erro relativo uniforme para todos quantis. Usa clusters de tamanho variável: menores nas caudas (onde precisão importa para percentis extremos), maiores no centro. Atualização online, merge eficiente, queries rápidas. Elastic usa para agregações, muitos sistemas para SLAs (p99 latency).
DDSketch oferece garantias determinísticas de erro relativo para quantis. Usa buckets logaritmicamente espaçados, garantindo erro relativo máximo α. Cada valor cai em um bucket baseado em seu logaritmo. Merge é trivial (soma de histogramas), queries são rápidas (soma acumulada). DataDog usa para métricas, garantindo SLAs de precisão.
KLL (Karnin-Lang-Liberty) sketch atinge limites teóricos para estimativa de quantis. Mantém níveis de compactação, promovendo amostras entre níveis. Garante erro ε-relativo usando O(1/ε log εn) espaço — ótimo até fatores logarítmicos. Apache DataSketches implementa, usado em Druid e outros sistemas analíticos.
Theta sketches estendem conceitos de MinHash para operações complexas de conjuntos. Mantêm amostras com hash menor que theta (threshold). União, interseção e diferença computáveis diretamente nos sketches. Estimativas não-enviesadas com variância conhecida. Apache DataSketches fornece implementação otimizada, usado para analytics de usuários únicos.
Cuckoo filters melhoram Bloom filters: suportam deleção, melhor localidade de cache, e eficiência de espaço comparável. Usam cuckoo hashing com fingerprints pequenos. Inserção desloca elementos entre buckets alternativos. Quando cheio, evict elemento aleatório. False positive rate configurável, tipicamente 0.1-3%.
Frequent Directions aproxima SVD de matrizes em streams. Mantém sketch de posto k, atualizável por linha. Quando sketch enche, remove direção de menor valor singular. Garante erro aditivo ótimo. Aplicações em PCA online, detecção de anomalias, compressão de modelos neurais.
Resumir grafos massivos requer sketches especializados. Triangle counting usa coloração aleatória. Connectivity sketches mantêm componentes aproximados. Distance sketches estimam caminhos mínimos. SpanningEdge samples preservam conectividade. Cada sketch captura propriedades diferentes do grafo original.
Sketches são a poesia da ciência de dados — comprimem a essência descartando o supérfluo. Como haicais que capturam momentos em dezessete sílabas, sketches capturam terabytes em kilobytes. Dominá-los é dominar a arte de ver o todo através do mínimo. No próximo capítulo, exploraremos a fundação que torna muitos sketches possíveis: o mundo fascinante das funções hash!
Se os dados fossem pessoas em uma festa, funções hash seriam os anfitriões que designam cada convidado a uma mesa específica — rapidamente, eficientemente, e de forma que pessoas parecidas não necessariamente sentem juntas. Esta aleatorização controlada é o coração pulsante de inúmeras estruturas de dados e algoritmos modernos. Das tabelas hash que aceleram buscas aos checksums que verificam integridade, do blockchain que protege criptomoedas aos filtros que detectam spam, funções hash são os heróis silenciosos da computação. Neste capítulo, desvendaremos a matemática elegante por trás dessa aparente mágica.
Uma função hash transforma dados de tamanho arbitrário em valores de tamanho fixo, idealmente parecendo aleatórios mas sendo determinísticos. É como ter uma máquina que transforma qualquer objeto — uma formiga ou um elefante — em um número entre 1 e 1000, sempre dando o mesmo número para o mesmo objeto. Esta simplicidade esconde poder imenso: permite indexação em tempo constante, detecção eficiente de duplicatas, e distribuição uniforme de dados.
Hashing universal escolhe funções aleatoriamente de uma família com garantias probabilísticas. Para quaisquer x ≠ y, P(h(x) = h(y)) ≤ 1/m onde m é o tamanho da tabela. É como ter múltiplos anfitriões com diferentes estratégias de alocação — escolhemos um aleatoriamente, garantindo que conspiradores não podem prever onde sentarão. Fundamental para garantias teóricas em estruturas randomizadas.
Hashes não-criptográficos otimizados para velocidade dominam aplicações gerais. MurmurHash mistura bits através de multiplicações e rotações, produzindo excelente distribuição rapidamente. CityHash, do Google, otimiza para CPUs modernas com instruções SIMD. São os cavalos de batalha de sistemas distribuídos, bancos de dados, e caches — onde velocidade importa mais que segurança.
Consistent hashing revolucionou sistemas distribuídos. Imagine servidores organizados em um círculo; cada chave é mapeada ao servidor seguinte no sentido horário. Adicionar ou remover servidores afeta apenas chaves próximas, não todas. Com servidores virtuais (múltiplos pontos por servidor), balanceamos carga uniformemente. Amazon Dynamo, Cassandra, e CDNs modernas dependem disso.
LSH inverte a lógica tradicional: elementos similares devem ter hashes similares! Para distância de Hamming, usa projeções aleatórias. Para distância Euclidiana, usa hiperplanos aleatórios. Para Jaccard, usa MinHash. Permite busca aproximada de vizinhos próximos em tempo sublinear. Spotify usa para recomendações, Google para detecção de quase-duplicatas.
Rolling hash calcula hash de janelas deslizantes eficientemente. Rabin-Karp usa para buscar padrões: hash da janela atual calculado do anterior em O(1). Como uma impressão digital que desliza pelo texto, detecta rapidamente possíveis matches. rsync usa para sincronização, antivírus para assinaturas, sistemas de backup para deduplicação.
Para conjuntos estáticos, perfect hashing garante zero colisões. FKS scheme usa hash universal em dois níveis. Primeiro nível distribui em buckets, segundo resolve colisões dentro de cada bucket. Construção em tempo esperado linear, busca em tempo constante garantido. Ideal para tabelas de símbolos em compiladores, conjuntos fixos em jogos.
Cuckoo hashing garante busca em tempo constante worst-case usando duas funções hash. Cada elemento tem duas posições possíveis. Inserção pode deslocar elementos existentes para suas posições alternativas, como um cuco que expulsa outros ovos do ninho. Se ciclo detectado, re-hash com novas funções. Usado em roteadores de alta velocidade onde latência previsível é crucial.
SHA-256, base do Bitcoin, produz hash de 256 bits através de 64 rodadas de operações bitwise. Blake3 moderniza com paralelização e tree hashing. SipHash protege contra hash flooding attacks mantendo velocidade. Cada um balanceia segurança e desempenho diferentemente. Essenciais para integridade, autenticação, e proof-of-work.
Feature hashing (hashing trick) mapeia features de alta dimensão para espaço fixo menor. Em vez de dicionário palavra→índice, usa hash(palavra) mod m. Colisões acontecem mas raramente degradam performance de ML significativamente. Economiza memória, elimina vocabulário fixo, permite online learning. Vowpal Wabbit popularizou, agora ubíquo em sistemas de ML em produção.
Funções hash são os tradutores universais da computação, convertendo o complexo em simples, o grande em pequeno, o estruturado em aleatório. Como vimos, diferentes problemas pedem diferentes tipos de hash — de ultra-rápidos para tabelas a criptograficamente seguros para blockchain. Dominar hashing é dominar uma das ferramentas mais versáteis da ciência da computação. No próximo capítulo, veremos essas técnicas em ação na escala máxima: aplicações em big data!
Quando o Facebook processa 4 petabytes de dados por dia, quando o Large Hadron Collider gera 30 petabytes por ano, quando sensores IoT produzem zettabytes globalmente, técnicas tradicionais de processamento simplesmente colapsam. É aqui que a lógica sublinear deixa de ser uma otimização elegante e torna-se absolutamente essencial. Neste capítulo, exploraremos como gigantes da tecnologia e organizações científicas aplicam as técnicas que aprendemos para domar oceanos de dados, extraindo insights valiosos de volumes que desafiam a compreensão humana.
Sistemas de big data modernos combinam processamento batch e streaming. Lambda architecture mantém camadas separadas: batch para completude, speed para latência baixa, serving para queries. Kappa simplifica usando apenas streaming. Ambas dependem crucialmente de algoritmos sublineares — sketches na camada speed, sampling no batch, estruturas compactas no serving. LinkedIn usa Lambda, Uber prefere Kappa.
O Google foi pioneiro em aplicar lógica sublinear em escala web. PageRank é essencialmente uma random walk massiva. BigTable usa Bloom filters para reduzir leituras desnecessárias de disco. MapReduce emprega sampling para estimar progresso de jobs. Spanner usa HyperLogLog para cardinalidade. Cada otimização economiza milhões em infraestrutura quando aplicada a bilhões de páginas e usuários.
Com 200 milhões de assinantes e catálogo de milhares de títulos, Netflix não pode calcular todas as similaridades exatamente. LSH encontra conteúdo similar rapidamente. Matrix sketching comprime modelos de fatoração. Reservoir sampling seleciona dados de treino. A/B testing usa statistical sampling. Cada técnica permite personalização em escala impossível com métodos exatos.
Com 500 milhões de tweets por dia, Twitter epitomiza desafios de streaming. Trending topics usa Count-Min sketch. Follower counts emprega approximate counters. Timeline generation usa Bloom filters para deduplicação. Storm processa streams com sketches distribuídos. Cada segundo economizado por técnicas sublineares traduz-se em melhor experiência para milhões.
Amazon processa bilhões de transações, mantém trilhões de objetos em S3, e personaliza experiência para centenas de milhões de clientes. DynamoDB usa consistent hashing para particionamento. Recomendações empregam MinHash para similaridade de produtos. Detecção de fraude usa anomaly detection em streams. Logistics otimiza rotas com algoritmos aproximados. Escala demanda aproximação inteligente.
Sequenciamento genômico gera terabytes por experimento. MinHash identifica sequências similares entre espécies. Bloom filters detectam presença de k-mers. Suffix arrays comprimidos indexam genomas. Count-Min sketch conta mutações. Estas técnicas tornaram viável o projeto de sequenciar 100.000 genomas humanos, impossível com métodos tradicionais.
Bilhões de dispositivos IoT geram dados continuamente mas têm recursos limitados. Edge computing processa dados localmente usando técnicas sublineares. Sensores usam sketches para comprimir leituras. Gateways agregam com Count-Min. Fog nodes detectam anomalias com sliding windows. Cloud recebe apenas resumos essenciais. Hierarquia de compressão progressiva torna IoT escalável.
Mercados financeiros geram milhões de eventos por segundo. Trading algorithms precisam decidir em microssegundos. Order books usam estruturas compactas. Risk calculations empregam Monte Carlo sampling. Fraud detection usa streaming anomaly detection. Market surveillance aplica pattern matching aproximado. Velocidade é dinheiro, e técnicas sublineares são a chave.
Modelos de ML em produção enfrentam restrições severas de latência e recursos. Feature hashing elimina vocabulários. Quantização comprime modelos. Online learning usa SGD com sampling. Approximate nearest neighbors acelera inferência. Model serving emprega caching inteligente. Cada otimização permite servir mais requisições com menos recursos.
Big data continua crescendo exponencialmente. 5G multiplicará dados IoT. ML demandará mais computação. Privacidade requererá processamento descentralizado. Quantum computing trará novos paradigmas. Técnicas sublineares evoluirão para enfrentar estes desafios. O futuro pertence a quem souber fazer mais com menos, extrair sinal de ruído, e encontrar agulhas em palheiros do tamanho de planetas.
As aplicações em big data demonstram que lógica sublinear não é curiosidade acadêmica, mas necessidade prática. Cada empresa de tecnologia, cada projeto científico ambicioso, cada sistema que opera em escala global depende destas técnicas. Como vimos, o impossível torna-se rotineiro quando aplicamos inteligência matemática a problemas de escala. No capítulo final, traremos tudo isso para casa, mostrando como lógica sublinear aparece no seu dia a dia!
Você pode não perceber, mas a lógica sublinear está em toda parte ao seu redor. Desde o momento em que acorda e checa o celular até quando adormece assistindo Netflix, algoritmos sublineares trabalham silenciosamente tornando sua vida digital possível. Como eletricidade ou água encanada, tornaram-se tão fundamentais que só notamos quando faltam. Neste capítulo final, revelaremos a mágica escondida no mundano, mostrando como as técnicas que exploramos moldam experiências cotidianas de bilhões de pessoas.
Seu celular realiza milagres computacionais constantemente. O corretor ortográfico usa tries compactas para sugerir palavras instantaneamente entre milhões. Fotos são organizadas por faces usando LSH para encontrar rostos similares. Apps usam Bloom filters para verificar se recursos estão em cache. GPS calcula rotas com algoritmos aproximados. Cada swipe, toque e comando de voz desencadeia cascatas de computação sublinear.
Cada like, comentário e compartilhamento navega por sistemas massivamente sublineares. Facebook determina que posts mostrar usando ranking aproximado. Instagram detecta hashtags trending com Count-Min sketch. LinkedIn sugere conexões via similarity hashing. TikTok personaliza o feed com collaborative filtering aproximado. Sem essas técnicas, redes sociais com bilhões de usuários seriam impossíveis.
Netflix, YouTube, Spotify — todos dependem fundamentalmente de lógica sublinear. Adaptive bitrate streaming usa estimativas de bandwidth. Content delivery networks empregam consistent hashing. Recomendações usam matrix factorization aproximada. Sincronização entre dispositivos usa vector clocks. Aquela transição suave quando você pausa no celular e continua na TV? Algoritmos sublineares em ação.
Cada busca por produtos, cada "clientes também compraram", cada estimativa de entrega usa técnicas sublineares. Amazon processa seu histórico com MinHash para recomendar produtos. Detecção de fraude usa anomaly detection em tempo real. Preços dinâmicos empregam algoritmos de otimização aproximada. Reviews são sumarizados com técnicas de NLP aproximadas. O carrinho que salva seus itens? Distributed hash tables com eventual consistency.
Google Maps, Waze, Uber — todos resolvem problemas computacionalmente intratáveis usando aproximação. Roteamento em grafos com bilhões de arestas usa hierarchical hub labeling. Estimativas de tempo usam historical sampling. Surge pricing emprega approximate demand estimation. Compartilhamento de corridas resolve approximate matching. Cada decisão de navegação é um triunfo da lógica sublinear.
Seu smartwatch monitora saúde usando computação sublinear embarcada. Detecção de batimentos usa sliding windows. Análise de sono emprega pattern matching aproximado. Contagem de passos usa filtros e heurísticas. Alertas de saúde baseiam-se em anomaly detection. Apps de saúde agregam dados de milhões usando differential privacy e sketches. Telemedicina usa compressão com perdas para vídeo.
Plataformas educacionais personalizam aprendizado usando lógica sublinear. Khan Academy adapta dificuldade com estimativas de habilidade. Duolingo usa spaced repetition com scheduling aproximado. Coursera recomenda cursos via collaborative filtering. Sistemas de proctoring usam anomaly detection. Até mesmo este livro, se digital, usa índices comprimidos para busca rápida.
Sua segurança digital depende crucialmente de técnicas sublineares. Antivírus usa Bloom filters para assinaturas de malware. Firewalls empregam approximate matching para detectar ataques. Navegadores verificam sites maliciosos com hash prefixes. Two-factor authentication usa time-based hashing. VPNs fazem roteamento com consistent hashing. Privacidade é protegida com differential privacy e secure sketches.
Realidade aumentada renderizará mundos usando approximate ray tracing. Assistentes virtuais entenderão contexto com attention mechanisms aproximados. Carros autônomos navegarão com sensor fusion probabilístico. Smart homes otimizarão energia com approximate dynamic programming. Medicina personalizada usará approximate genome matching. O futuro será ainda mais sublinear, mais aproximado, mais eficiente.
A lógica sublinear é a força invisível que torna o mundo digital moderno possível. Como o ar que respiramos, está em toda parte mas raramente notada. Cada vez que uma busca retorna instantaneamente, um vídeo carrega suavemente, ou uma recomendação acerta em cheio, algoritmos sublineares estão trabalhando. Eles são a ponte entre o que queremos (respostas perfeitas instantâneas) e o que é fisicamente possível (processar quantidades finitas de dados em tempo finito).
Este livro levou você por uma jornada desde os fundamentos teóricos até aplicações práticas da lógica sublinear. Vimos como ideias aparentemente abstratas — amostragem, hashing, sketching — transformam-se em tecnologias que impactam bilhões. A mensagem central é poderosa: em um mundo de dados infinitos e recursos finitos, a inteligência está não em processar tudo, mas em processar inteligentemente. A lógica sublinear nos ensina que às vezes a melhor maneira de resolver um problema grande é torná-lo pequeno. E nessa transformação, nessa alquimia computacional que transmuta montanhas de dados em grãos de insight, encontramos não apenas eficiência, mas elegância. O futuro pertence àqueles que dominarem a arte de fazer muito com pouco — bem-vindo ao clube!
A lógica sublinear representa uma convergência fascinante de matemática, ciência da computação e engenharia prática. As referências aqui reunidas abrangem desde os trabalhos teóricos fundamentais que estabeleceram o campo até as implementações práticas que processam petabytes diariamente. Esta bibliografia oferece caminhos para aprofundamento em cada aspecto da lógica sublinear, desde algoritmos probabilísticos até aplicações em sistemas distribuídos modernos.
ALON, Noga; MATIAS, Yossi; SZEGEDY, Mario. The Space Complexity of Approximating the Frequency Moments. Journal of Computer and System Sciences, v. 58, n. 1, p. 137-147, 1999.
ARORA, Sanjeev; BARAK, Boaz. Computational Complexity: A Modern Approach. Cambridge: Cambridge University Press, 2009.
BAR-YOSSEF, Ziv et al. An Information Statistics Approach to Data Stream and Communication Complexity. Journal of Computer and System Sciences, v. 68, n. 4, p. 702-732, 2004.
BLUM, Avrim; HOPCROFT, John; KANNAN, Ravindran. Foundations of Data Science. Cambridge: Cambridge University Press, 2020.
BRASIL. Base Nacional Comum Curricular: Educação é a Base. Brasília: MEC/CONSED/UNDIME, 2018.
BRODER, Andrei Z. On the Resemblance and Containment of Documents. Proceedings of Compression and Complexity of Sequences, p. 21-29, 1997.
CHAKRABARTI, Amit. Data Stream Algorithms: Lecture Notes. Dartmouth College, 2020.
CHARIKAR, Moses. Similarity Estimation Techniques from Rounding Algorithms. Proceedings of STOC, p. 380-388, 2002.
CORMODE, Graham; GAROFALAKIS, Minos. Sketching Streams Through the Net: Distributed Approximate Query Tracking. Proceedings of VLDB, p. 13-24, 2005.
CORMODE, Graham; MUTHUKRISHNAN, S. An Improved Data Stream Summary: The Count-Min Sketch and its Applications. Journal of Algorithms, v. 55, n. 1, p. 58-75, 2005.
DASGUPTA, Sanjoy; GUPTA, Anupam. An Elementary Proof of a Theorem of Johnson and Lindenstrauss. Random Structures & Algorithms, v. 22, n. 1, p. 60-65, 2003.
DEAN, Jeffrey; GHEMAWAT, Sanjay. MapReduce: Simplified Data Processing on Large Clusters. Communications of the ACM, v. 51, n. 1, p. 107-113, 2008.
DATAR, Mayur et al. Maintaining Stream Statistics over Sliding Windows. SIAM Journal on Computing, v. 31, n. 6, p. 1794-1813, 2002.
DURAND, Marianne; FLAJOLET, Philippe. LogLog Counting of Large Cardinalities. Proceedings of ESA, p. 605-617, 2003.
ELIAS, Peter. Universal Codeword Sets and Representations of the Integers. IEEE Transactions on Information Theory, v. 21, n. 2, p. 194-203, 1975.
FAN, Bin et al. Cuckoo Filter: Practically Better Than Bloom. Proceedings of CoNEXT, p. 75-88, 2014.
FEIGENBAUM, Joan et al. On Graph Problems in a Semi-streaming Model. Theoretical Computer Science, v. 348, n. 2-3, p. 207-216, 2005.
FLAJOLET, Philippe et al. HyperLogLog: The Analysis of a Near-optimal Cardinality Estimation Algorithm. Proceedings of AofA, p. 137-156, 2007.
FLAJOLET, Philippe; MARTIN, G. Nigel. Probabilistic Counting Algorithms for Data Base Applications. Journal of Computer and System Sciences, v. 31, n. 2, p. 182-209, 1985.
GOLDREICH, Oded. Computational Complexity: A Conceptual Perspective. Cambridge: Cambridge University Press, 2008.
GOLDREICH, Oded; RON, Dana. Property Testing: A Learning Theory Perspective. Foundations and Trends in Machine Learning, v. 1, n. 3, p. 307-402, 2008.
GOODRICH, Michael T.; TAMASSIA, Roberto. Algorithm Design and Applications. Hoboken: Wiley, 2015.
GUHA, Sudipto; MCGREGOR, Andrew. Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams. SIAM Journal on Computing, v. 38, n. 5, p. 2044-2059, 2009.
HARVEY, Nicholas J. A.; NELSON, Jelani; ONAK, Krzysztof. Sketching and Streaming Entropy via Approximation Theory. Proceedings of FOCS, p. 489-498, 2008.
INDYK, Piotr. Stable Distributions, Pseudorandom Generators, Embeddings and Data Stream Computation. Journal of the ACM, v. 53, n. 3, p. 307-323, 2006.
INDYK, Piotr; MOTWANI, Rajeev. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. Proceedings of STOC, p. 604-613, 1998.
IOANNIDIS, Yannis. The History of Histograms (Abridged). Proceedings of VLDB, p. 19-30, 2003.
KANE, Daniel M.; NELSON, Jelani; WOODRUFF, David P. An Optimal Algorithm for the Distinct Elements Problem. Proceedings of PODS, p. 41-52, 2010.
KARGER, David et al. Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. Proceedings of STOC, p. 654-663, 1997.
KARP, Richard M.; RABIN, Michael O. Efficient Randomized Pattern-matching Algorithms. IBM Journal of Research and Development, v. 31, n. 2, p. 249-260, 1987.
KLEINBERG, Jon; TARDOS, Éva. Algorithm Design. Boston: Pearson, 2006.
LIBERTY, Edo. Simple and Deterministic Matrix Sketching. Proceedings of KDD, p. 581-588, 2013.
LI, Ping; KÖNIG, Arnd Christian. b-Bit Minwise Hashing. Proceedings of WWW, p. 671-680, 2010.
LESKOVEC, Jure; RAJARAMAN, Anand; ULLMAN, Jeffrey D. Mining of Massive Datasets. 3rd ed. Cambridge: Cambridge University Press, 2020.
MANKU, Gurmeet Singh; MOTWANI, Rajeev. Approximate Frequency Counts over Data Streams. Proceedings of VLDB, p. 346-357, 2002.
MCGREGOR, Andrew. Graph Stream Algorithms: A Survey. SIGMOD Record, v. 43, n. 1, p. 9-20, 2014.
METWALLY, Ahmed; AGRAWAL, Divyakant; ABBADI, Amr El. Efficient Computation of Frequent and Top-k Elements in Data Streams. Proceedings of ICDT, p. 398-412, 2005.
MITZENMACHER, Michael. A Brief History of Generative Models for Power Law and Lognormal Distributions. Internet Mathematics, v. 1, n. 2, p. 226-251, 2004.
MITZENMACHER, Michael; UPFAL, Eli. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. 2nd ed. Cambridge: Cambridge University Press, 2017.
MORRIS, Robert. Counting Large Numbers of Events in Small Registers. Communications of the ACM, v. 21, n. 10, p. 840-842, 1978.
MOTWANI, Rajeev; RAGHAVAN, Prabhakar. Randomized Algorithms. Cambridge: Cambridge University Press, 1995.
MUNRO, J. Ian; PATERSON, Mike S. Selection and Sorting with Limited Storage. Theoretical Computer Science, v. 12, n. 3, p. 315-323, 1980.
MUTHUKRISHNAN, S. Data Streams: Algorithms and Applications. Foundations and Trends in Theoretical Computer Science, v. 1, n. 2, p. 117-236, 2005.
NELSON, Jelani. Sketching and Streaming High-Dimensional Vectors. PhD Thesis, MIT, 2011.
PAGH, Rasmus; RODLER, Flemming Friche. Cuckoo Hashing. Journal of Algorithms, v. 51, n. 2, p. 122-144, 2004.
ROUGHGARDEN, Tim. Beyond Worst-Case Analysis. Communications of the ACM, v. 62, n. 3, p. 88-96, 2019.
RUBINFELD, Ronitt; SHAPIRA, Asaf. Sublinear Time Algorithms. SIAM Journal on Discrete Mathematics, v. 25, n. 4, p. 1562-1588, 2011.
SEDGEWICK, Robert; WAYNE, Kevin. Algorithms. 4th ed. Boston: Addison-Wesley, 2011.
SHRIVASTAVA, Anshumali; LI, Ping. Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search. Proceedings of NIPS, p. 2321-2329, 2014.
SILVA, Valmir C. Teoria da Complexidade Computacional. São Paulo: Cengage Learning, 2019.
THORUP, Mikkel. High Speed Hashing for Integers and Strings. arXiv:1504.06804, 2015.
VITTER, Jeffrey Scott. Random Sampling with a Reservoir. ACM Transactions on Mathematical Software, v. 11, n. 1, p. 37-57, 1985.
WEINBERGER, Kilian et al. Feature Hashing for Large Scale Multitask Learning. Proceedings of ICML, p. 1113-1120, 2009.
WOODRUFF, David P. Sketching as a Tool for Numerical Linear Algebra. Foundations and Trends in Theoretical Computer Science, v. 10, n. 1-2, p. 1-157, 2014.
YU, Minlan et al. Software Defined Traffic Measurement with OpenSketch. Proceedings of NSDI, p. 29-42, 2013.
ZHANG, Yin et al. Online Identification of Hierarchical Heavy Hitters: Algorithms, Evaluation, and Applications. Proceedings of IMC, p. 101-114, 2004.