Menu
▾
▴
[Pyxida-cvs-commits] Pyxida/src/edu/harvard/syrah/pyxida/knn HyperCubeZoneManager.java, 1.1, 1.2 KnnSim.java, 1.1, 1.2 ZoneManager.java, 1.1, 1.2
|
From: Jonathan L. <le...@us...> - 2007-03-14 02:43:02
|
Update of /cvsroot/pyxida/Pyxida/src/edu/harvard/syrah/pyxida/knn In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv28977 Modified Files: HyperCubeZoneManager.java KnnSim.java ZoneManager.java Log Message: hypercube division of space works with small set of test coords Index: HyperCubeZoneManager.java =================================================================== RCS file: /cvsroot/pyxida/Pyxida/src/edu/harvard/syrah/pyxida/knn/HyperCubeZoneManager.java,v retrieving revision 1.1 retrieving revision 1.2 diff -C2 -d -r1.1 -r1.2 *** HyperCubeZoneManager.java 13 Mar 2007 21:48:08 -0000 1.1 --- HyperCubeZoneManager.java 14 Mar 2007 02:42:57 -0000 1.2 *************** *** 9,22 **** import java.util.Map; import java.util.SortedMap; ! public class HyperCubeZoneManager implements ZoneManager { final int dimensions; final double zoneEdgeLength; final Map<Long,Zone> zoneMap; public HyperCubeZoneManager (int _dimensions, double _dimensionSideLength, int _zonesPerDimension) { dimensions = _dimensions; zoneEdgeLength = _dimensionSideLength / _zonesPerDimension; zoneMap = new HashMap<Long,Zone> (); --- 9,31 ---- import java.util.Map; import java.util.SortedMap; ! import java.util.HashSet; ! import java.util.Set; public class HyperCubeZoneManager implements ZoneManager { + protected static edu.harvard.syrah.prp.Log slog = + new edu.harvard.syrah.prp.Log(HyperCubeZoneManager.class); + + final int dimensions; final double zoneEdgeLength; + final double dimensionSideLength; + final int zonesPerDimension; final Map<Long,Zone> zoneMap; public HyperCubeZoneManager (int _dimensions, double _dimensionSideLength, int _zonesPerDimension) { dimensions = _dimensions; + dimensionSideLength = _dimensionSideLength; + zonesPerDimension = _zonesPerDimension; zoneEdgeLength = _dimensionSideLength / _zonesPerDimension; zoneMap = new HashMap<Long,Zone> (); *************** *** 26,39 **** public void add(long stamp, NodeDesc node) { - // TODO UNTESTED - // determine his zone ! long zoneId = 0; ! double vec[] = node.coord.asVectorFromZero(false).getComponents(); ! ! for (int i = 0; i < dimensions; i++) { ! int zoneIndex = (int)(Math.floor(vec[i] / zoneEdgeLength)); ! zoneId += Math.pow(zoneIndex, i+1); ! } Zone z = zoneMap.get(zoneId); --- 35,40 ---- public void add(long stamp, NodeDesc node) { // determine his zone ! long zoneId = findZone(node); Zone z = zoneMap.get(zoneId); *************** *** 45,55 **** // TODO also create Zone->nearby Zone mapping and add nearby zones during query? } ! public void query(NodeDesc node, SortedMap<Double, NodeDesc> distance2node) { ! } } --- 46,77 ---- // TODO also create Zone->nearby Zone mapping and add nearby zones during query? + slog.info ("added "+node.id+" to zone "+zoneId); } ! public void query(NodeDesc node, Set<NodeDesc> nearbyNodes, int maxReturnSize) { + // determine his zone + long zoneId = findZone(node); + + Zone z = zoneMap.get(zoneId); + if (z != null) { + z.probe(nearbyNodes,maxReturnSize); + } } + long findZone(NodeDesc node) { + long zoneId = 0; + double vec[] = node.coord.asVectorFromZero(false).getComponents(); + + for (int i = 0; i < dimensions; i++) { + final double halfDimensionSideLength = dimensionSideLength / 2.; + // normalize coordinate s.t. all coords are >0 + int zoneIndex = (int)(Math.floor((vec[i]+halfDimensionSideLength) / zoneEdgeLength)); + zoneId += Math.pow(zonesPerDimension, i) * zoneIndex; + //slog.info (i+" c"+vec[i]+" -> "+zoneIndex+ " id "+zoneId); + } + return zoneId; + } + } Index: ZoneManager.java =================================================================== RCS file: /cvsroot/pyxida/Pyxida/src/edu/harvard/syrah/pyxida/knn/ZoneManager.java,v retrieving revision 1.1 retrieving revision 1.2 diff -C2 -d -r1.1 -r1.2 *** ZoneManager.java 13 Mar 2007 21:48:08 -0000 1.1 --- ZoneManager.java 14 Mar 2007 02:42:57 -0000 1.2 *************** *** 7,11 **** import java.util.SortedMap; ! public interface ZoneManager { --- 7,12 ---- import java.util.SortedMap; ! import java.util.HashSet; ! import java.util.Set; public interface ZoneManager { *************** *** 13,17 **** void add(long stamp, NodeDesc node); ! void query(NodeDesc node, SortedMap<Double, NodeDesc> distance2node); } --- 14,18 ---- void add(long stamp, NodeDesc node); ! void query(NodeDesc node, Set<NodeDesc> nearbyNodes, int maxReturnSize); } Index: KnnSim.java =================================================================== RCS file: /cvsroot/pyxida/Pyxida/src/edu/harvard/syrah/pyxida/knn/KnnSim.java,v retrieving revision 1.1 retrieving revision 1.2 diff -C2 -d -r1.1 -r1.2 *** KnnSim.java 13 Mar 2007 21:48:08 -0000 1.1 --- KnnSim.java 14 Mar 2007 02:42:57 -0000 1.2 *************** *** 15,18 **** --- 15,19 ---- import java.util.Map; import java.util.Set; + import java.util.Iterator; import java.util.SortedMap; import java.util.StringTokenizer; *************** *** 21,32 **** import edu.harvard.syrah.pyxida.nc.lib.Coordinate; - public class KnnSim { protected static edu.harvard.syrah.prp.Log slog = new edu.harvard.syrah.prp.Log(KnnSim.class); - - /** - * @param args - */ Set<NodeDesc> nodes = new HashSet<NodeDesc>(); --- 22,28 ---- *************** *** 37,43 **** final boolean height = true; int dimsPlusHeight = height?dimensions:(dimensions+1); ! ZoneManager zm; public static void main(String[] args) { KnnSim sim = new KnnSim (args); } --- 33,50 ---- final boolean height = true; int dimsPlusHeight = height?dimensions:(dimensions+1); ! ZoneManager zm = null; ! ! // Number of guys we would be returning to client. ! // We will see how many of the true NN of the same size we find. ! int returnSetSize = 50; ! ! public static final String usage = ! "java KnnSim coord-file"; public static void main(String[] args) { + if (args.length <= 0) { + System.err.println (usage); + System.exit (-1); + } KnnSim sim = new KnnSim (args); } *************** *** 45,48 **** --- 52,57 ---- public KnnSim (String[] args) { String coordFilename = args[0]; + // TODO make into variables + returnSetSize = 50; slog.info ("reading coordinate file "+coordFilename); *************** *** 52,56 **** final double dimensionSideLength = 20000; ! final int zonesPerDimension = 1000; zm = new HyperCubeZoneManager (dimensions, dimensionSideLength, zonesPerDimension); --- 61,66 ---- final double dimensionSideLength = 20000; ! //final int zonesPerDimension = 1000; ! final int zonesPerDimension = 2; zm = new HyperCubeZoneManager (dimensions, dimensionSideLength, zonesPerDimension); *************** *** 85,103 **** public void evaluateZoneAssignment () { for (NodeDesc node : nodes) { ! SortedMap<Double,NodeDesc> distance2node = new TreeMap<Double,NodeDesc>(); ! zm.query(node,distance2node); ! ! /* ! * TODO Do something smart here to evaluate the mapping. ! * ! SortedMap<Double,NodeDesc> trueDistance2node = node2distance2node.get(node); ! StringBuffer sb = new StringBuffer ("truth "); ! for (Map.Entry<Double, NodeDesc>) entry : trueDistance2node) { ! ! } ! */ ! ! } ! } void readCoordFile (String coordFilename) { --- 95,133 ---- public void evaluateZoneAssignment () { for (NodeDesc node : nodes) { ! //SortedMap<Double,NodeDesc> distance2node = new TreeMap<Double,NodeDesc>(); ! Set<NodeDesc> foundSet = new HashSet<NodeDesc> (); ! zm.query(node,foundSet,returnSetSize); ! ! // foundSet is who we would be returning to the client ! //Set<NodeDesc> foundSet = getSetHead (distance2node, returnSetSize); ! Set<NodeDesc> tnnSet = getSetHead (node2distance2node.get(node), returnSetSize); ! ! int unionSize = 0; ! for (NodeDesc foundNode : foundSet) { ! if (tnnSet.contains(foundNode)) { ! unionSize++; ! } ! } ! ! // TODO want pct ! slog.info (node.id+" union "+unionSize); ! ! // TODO Could also eval mapping with abs(rank difference) ! // exponentially weighted by tnn rank ! ! // Or something that actually has to do with distance ! // as opposed to just rank ! ! } ! } ! ! Set<NodeDesc> getSetHead (SortedMap<Double,NodeDesc> theMap, int maxSize) { ! Set<NodeDesc> foundSet = new HashSet<NodeDesc>(); ! for (Map.Entry<Double,NodeDesc> entry : theMap.entrySet()) { ! foundSet.add (entry.getValue()); ! if (foundSet.size() == returnSetSize) break; ! } ! return foundSet; ! } void readCoordFile (String coordFilename) { |
