If you want to minimize memory usage, you will have to suffer in speed somewhere, somehow. There is a trade off that you have to make.

I think one of the easiest method is to use a proper database to record your files, like MySQL, Postgres, Oracle, etc. Create a table with an *index* on the filename to speed up SQL query. Let the database do the search optimization for you.

#!/usr/local/bin/perl -w
use strict;
use DBI;
use DBD::Sybase;
use File::Find;

my $dbh = ....;  # connect to database
my $sth = $dbh->prepare("select filename from bench where filename=?")
+;

# look for new files
my @new_files;
find( { follow => 1, no_chdir => 1,
        wanted =>
          sub {
            if (! /\.$/) {            # ignore unwanted . or ..
              $sth->execute($_);
              my $file_exists;
              while (my @res = $sth->fetchrow_array()) { $file_exists+
++ }
              push @new_files if !$file_exits;
            }
          }
      }, '/');
$sth->finish;

# insert new files into the database
$sth = $dbh->prepare("insert into bench (filename) values (?)");
$sth->execute($_) for @new_files;
$sth->finish;

# do stuff with @new_files ....
[download]

I can think of another solution, although the performance in speed is not great, that uses resonable amount of memory.

#!/usr/local/bin/perl -w
use strict;
use File::Find;

my $bench_file = 'bench.txt';

my @new_files;
find( { follow => 1,  no_chdir => 1,
        wanted => \&callback }, '/');

sub callback {
  if (! /\.$/) {            # ignore unwanted . or ..
    if ( ! `grep '$_' $bench_file` ) {
      push @new_files, $_;  # remember this file
    }
  }
}

# append unseen filenames to bench.txt file
open BENCH, ">>bench.txt"
     or die "Can not append to bench.txt";
print BENCH "$_\n" foreach (@new_files);
close BENCH;
[download]