Index: trunk/src/org/openstreetmap/josm/actions/CreateCircleAction.java
===================================================================
--- trunk/src/org/openstreetmap/josm/actions/CreateCircleAction.java	(revision 2165)
+++ trunk/src/org/openstreetmap/josm/actions/CreateCircleAction.java	(revision 2166)
@@ -172,6 +172,7 @@
                 // if it is, delete it
                 CollectBackReferencesVisitor refs = new CollectBackReferencesVisitor(getCurrentDataSet());
+                refs.initialize();
                 refs.visit(n1);
-                if (refs.data.isEmpty() || ((refs.data.size() == 1) && (refs.data.contains(existingWay)))) {
+                if (refs.getData().isEmpty() || ((refs.getData().size() == 1) && (refs.getData().contains(existingWay)))) {
                     cmds.add(new DeleteCommand(n1));
                 }
Index: trunk/src/org/openstreetmap/josm/actions/search/SearchAction.java
===================================================================
--- trunk/src/org/openstreetmap/josm/actions/search/SearchAction.java	(revision 2165)
+++ trunk/src/org/openstreetmap/josm/actions/search/SearchAction.java	(revision 2166)
@@ -182,5 +182,5 @@
                searchText = (((Filter)s).inverted ? "-" : "") + "(" +  searchText + ")";
             }
-            System.out.println(searchText);
+            /*System.out.println(searchText);*/
             SearchCompiler.Match matcher = SearchCompiler.compile(searchText, s.caseSensitive, s.regexSearch);
             foundMatches = 0;
Index: trunk/src/org/openstreetmap/josm/actions/search/SearchCompiler.java
===================================================================
--- trunk/src/org/openstreetmap/josm/actions/search/SearchCompiler.java	(revision 2165)
+++ trunk/src/org/openstreetmap/josm/actions/search/SearchCompiler.java	(revision 2166)
@@ -33,4 +33,5 @@
     private String  rxErrorMsg = marktr("The regex \"{0}\" had a parse error at offset {1}, full error:\n\n{2}");
     private PushbackTokenizer tokenizer;
+    private static CollectBackReferencesVisitor childBackRefs;
 
     public SearchCompiler(boolean caseSensitive, boolean regexSearch, PushbackTokenizer tokenizer) {
@@ -38,4 +39,5 @@
         this.regexSearch = regexSearch;
         this.tokenizer = tokenizer;
+        childBackRefs = new CollectBackReferencesVisitor(Main.main.getCurrentDataSet());
     }
 
@@ -481,7 +483,7 @@
 
             boolean isChild = false;
-            CollectBackReferencesVisitor backRefs = new CollectBackReferencesVisitor(Main.main.getCurrentDataSet());
-            osm.visit(backRefs);
-            for (OsmPrimitive p : backRefs.data) {
+            childBackRefs.initialize();
+            osm.visit(childBackRefs);
+            for (OsmPrimitive p : childBackRefs.getData()) {
                 isChild |= parent.match(p);
             }
Index: trunk/src/org/openstreetmap/josm/command/DeleteCommand.java
===================================================================
--- trunk/src/org/openstreetmap/josm/command/DeleteCommand.java	(revision 2165)
+++ trunk/src/org/openstreetmap/josm/command/DeleteCommand.java	(revision 2166)
@@ -163,13 +163,14 @@
     public static Command deleteWithReferences(OsmDataLayer layer, Collection<? extends OsmPrimitive> selection, boolean simulate) {
         CollectBackReferencesVisitor v = new CollectBackReferencesVisitor(layer.data);
+        v.initialize();
         for (OsmPrimitive osm : selection) {
             osm.visit(v);
         }
-        v.data.addAll(selection);
-        if (v.data.isEmpty())
+        v.getData().addAll(selection);
+        if (v.getData().isEmpty())
             return null;
-        if (!checkAndConfirmOutlyingDeletes(layer,v.data) && !simulate)
+        if (!checkAndConfirmOutlyingDeletes(layer,v.getData()) && !simulate)
             return null;
-        return new DeleteCommand(layer,v.data);
+        return new DeleteCommand(layer,v.getData());
     }
 
@@ -239,4 +240,5 @@
     protected static Collection<Node> computeNodesToDelete(OsmDataLayer layer, Collection<OsmPrimitive> primitivesToDelete) {
         Collection<Node> nodesToDelete = new HashSet<Node>();
+        CollectBackReferencesVisitor v = new CollectBackReferencesVisitor(layer.data, false);
         for (OsmPrimitive osm : primitivesToDelete) {
             if (! (osm instanceof Way) ) {
@@ -247,8 +249,8 @@
                     continue;
                 }
-                CollectBackReferencesVisitor v = new CollectBackReferencesVisitor(layer.data, false);
+                v.initialize();
                 n.visit(v);
-                v.data.removeAll(primitivesToDelete);
-                if (v.data.isEmpty()) {
+                v.getData().removeAll(primitivesToDelete);
+                if (v.getData().isEmpty()) {
                     nodesToDelete.add(n);
                 }
@@ -297,8 +299,9 @@
             return null;
 
+        CollectBackReferencesVisitor v = new CollectBackReferencesVisitor(layer.data, false);
         for (OsmPrimitive osm : primitivesToDelete) {
-            CollectBackReferencesVisitor v = new CollectBackReferencesVisitor(layer.data, false);
+            v.initialize();
             osm.visit(v);
-            for (OsmPrimitive ref : v.data) {
+            for (OsmPrimitive ref : v.getData()) {
                 if (primitivesToDelete.contains(ref)) {
                     continue;
@@ -328,7 +331,7 @@
                 primitivesToDelete.add(w);
 
-                CollectBackReferencesVisitor v = new CollectBackReferencesVisitor(layer.data, false);
+                v.initialize();
                 w.visit(v);
-                for (OsmPrimitive ref : v.data) {
+                for (OsmPrimitive ref : v.getData()) {
                     if (primitivesToDelete.contains(ref)) {
                         continue;
Index: trunk/src/org/openstreetmap/josm/data/osm/visitor/CollectBackReferencesVisitor.java
===================================================================
--- trunk/src/org/openstreetmap/josm/data/osm/visitor/CollectBackReferencesVisitor.java	(revision 2165)
+++ trunk/src/org/openstreetmap/josm/data/osm/visitor/CollectBackReferencesVisitor.java	(revision 2166)
@@ -4,4 +4,6 @@
 import java.util.Collection;
 import java.util.HashSet;
+import java.util.HashMap;
+import java.util.Map;
 
 import org.openstreetmap.josm.data.osm.DataSet;
@@ -17,5 +19,5 @@
  * Deleted objects are not collected.
  *
- * @author imi
+ * @author imi, Petr Dlouhý
  */
 public class CollectBackReferencesVisitor extends AbstractVisitor {
@@ -24,71 +26,82 @@
     private final boolean indirectRefs;
 
-    /**
-     * The result list of primitives stored here.
-     */
-    public final Collection<OsmPrimitive> data = new HashSet<OsmPrimitive>();
+    private Collection<OsmPrimitive> data = new HashSet<OsmPrimitive>();
+    private Map<OsmPrimitive, Collection<OsmPrimitive>> lookupTable = new HashMap<OsmPrimitive, Collection<OsmPrimitive>>();
 
 
     /**
      * Construct a back reference counter.
+     * has time complexity O(n) - so it is appropriate not to call it in cycle
      * @param ds The dataset to operate on.
      */
     public CollectBackReferencesVisitor(DataSet ds) {
-        this.ds = ds;
-        this.indirectRefs = true;
+       this(ds, true);
     }
 
+    /**
+     * Construct a back reference counter.
+     * has time complexity O(n) - so it is appropriate not to call it in cycle
+     * @param ds The dataset to operate on.
+     * @param indirectRefs Make also indirect references?
+     */
     public CollectBackReferencesVisitor(DataSet ds, boolean indirectRefs) {
-        this.ds = ds;
-        this.indirectRefs = indirectRefs;
+       this.ds = ds;
+       this.indirectRefs = indirectRefs;
+       if(ds != null)
+          makeLookupTable();
+    }
+    
+    private void makeLookupTable(){
+       for (Way w : ds.ways) {
+          for (Node n : w.getNodes()) {
+             if(!lookupTable.containsKey(n)) lookupTable.put(n, new HashSet<OsmPrimitive>());
+             lookupTable.get(n).add(w);
+          }
+       }
+       for (Relation r : ds.relations) {
+          for (RelationMember m : r.getMembers()) {
+             OsmPrimitive o = m.getMember();
+             if(!lookupTable.containsKey(o)) lookupTable.put(o, new HashSet<OsmPrimitive>());
+             lookupTable.get(o).add(r);
+          }
+       }
     }
 
+    /**
+     * Get the result collection
+     */
+    public Collection<OsmPrimitive> getData(){
+       return data;
+    }
+
+    /**
+     * Initialize data before associated visit calls 
+     */
+    public void initialize(){
+       data = new HashSet<OsmPrimitive>();
+    }
+
+    public void visit(OsmPrimitive o) {
+       if(lookupTable.containsKey(o)){
+          Collection<OsmPrimitive> c = lookupTable.get(o);
+          Collection<OsmPrimitive> oldData = new HashSet<OsmPrimitive>(data);
+          data.addAll(c);
+          if(indirectRefs)
+             for(OsmPrimitive oo : c)
+                if(!oldData.contains(oo))
+                   visit(oo);
+       }
+    }
+    
     public void visit(Node n) {
-        for (Way w : ds.ways) {
-            if (w.isDeleted() || w.incomplete) {
-                continue;
-            }
-            for (Node n2 : w.getNodes()) {
-                if (n == n2) {
-                    data.add(w);
-                    if (indirectRefs) {
-                        visit(w);
-                    }
-                }
-            }
-        }
-        checkRelationMembership(n);
+       visit((OsmPrimitive)n);
     }
 
     public void visit(Way w) {
-        checkRelationMembership(w);
+       visit((OsmPrimitive)w);
     }
 
     public void visit(Relation r) {
-        checkRelationMembership(r);
-    }
-
-    private void checkRelationMembership(OsmPrimitive p) {
-        // FIXME - this might be a candidate for optimisation
-        // if OSM primitives are made to hold a list of back
-        // references.
-        for (Relation r : ds.relations) {
-            if (r.incomplete || r.isDeleted()) {
-                continue;
-            }
-            for (RelationMember m : r.getMembers()) {
-                if (m.getMember() == p) {
-                    if (!data.contains(r)) {
-                        data.add(r);
-                        if (indirectRefs) {
-                            // move up the tree (there might be relations
-                            // referring to this relation)
-                            checkRelationMembership(r);
-                        }
-                    }
-                    break;
-                }
-            }
-        }
+       visit((OsmPrimitive)r);
     }
 }