001/*
002        AUTOMATICALLY GENERATED BY jTemp FROM
003        /Users/jsh2/Work/openimaj/target/checkout/machine-learning/nearest-neighbour/src/main/jtemp/org/openimaj/lsh/functions/#T#HyperplaneL1Factory.jtemp
004*/
005/**
006 * Copyright (c) 2011, The University of Southampton and the individual contributors.
007 * All rights reserved.
008 *
009 * Redistribution and use in source and binary forms, with or without modification,
010 * are permitted provided that the following conditions are met:
011 *
012 *   *  Redistributions of source code must retain the above copyright notice,
013 *      this list of conditions and the following disclaimer.
014 *
015 *   *  Redistributions in binary form must reproduce the above copyright notice,
016 *      this list of conditions and the following disclaimer in the documentation
017 *      and/or other materials provided with the distribution.
018 *
019 *   *  Neither the name of the University of Southampton nor the names of its
020 *      contributors may be used to endorse or promote products derived from this
021 *      software without specific prior written permission.
022 *
023 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
024 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
025 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
026 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
027 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
028 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
029 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
030 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
031 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
032 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
033 */
034package org.openimaj.lsh.functions;
035
036import org.openimaj.citation.annotation.Reference;
037import org.openimaj.citation.annotation.ReferenceType;
038import org.openimaj.feature.IntFVComparison;
039import org.openimaj.util.array.SparseIntArray;
040
041import cern.jet.random.Uniform;
042import cern.jet.random.engine.MersenneTwister;
043
044/**
045 * A hash function factory that produces hash functions that approximate L1
046 * (city-block) distance in closed spaces using random axis-aligned hyperplanes.
047 * <p>
048 * The hash function hashes the input vector into a binary value (i.e. 0 or 1). 
049 * It works by choosing a random dimension and a random threshold along that 
050 * dimension (between a given minimum and maximum which define the closed space).
051 * Input vectors whose element at the chosen dimension is greater than or equal
052 * to the threshold generate a 1; values less than the threshold generate a 0. 
053 * 
054 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
055 */
056 @Reference(
057        type = ReferenceType.Inproceedings,
058        author = { "Lv, Qin", "Charikar, Moses", "Li, Kai" },
059        title = "Image similarity search with compact data structures",
060        year = "2004",
061        booktitle = "Proceedings of the thirteenth ACM international conference on Information and knowledge management",
062        pages = { "208", "", "217" },
063        url = "http://doi.acm.org/10.1145/1031171.1031213",
064        publisher = "ACM",
065        series = "CIKM '04"
066)
067public class IntHyperplaneL1Factory extends IntHashFunctionFactory {
068        private class Function extends IntHashFunction {
069                int dimension;
070                double shift;
071
072                Function(int ndims, MersenneTwister rng) {
073                        super(rng);
074
075            Uniform uniform = new Uniform(rng);
076
077                        // choose a random dimension
078                        dimension = uniform.nextIntFromTo(0, ndims - 1);
079
080                        // random shift
081                        shift = uniform.nextDoubleFromTo(min, max);
082                }
083
084                @Override
085                public int computeHashCode(int[] point) {
086                        return (point[dimension] - shift) >= 0 ? 1 : 0;
087                }
088
089                @Override
090                public int computeHashCode(SparseIntArray array) {
091                        return (array.get(dimension) - shift) >= 0 ? 1 : 0;
092                }
093        }
094
095        int min = 0;
096        int max = 1;
097
098        /**
099         * Construct with the given arguments.
100         * 
101         * @param ndims
102         *            The number of dimensions
103         * @param rng
104         *            A random number generator
105         * @param min
106         *            The minimum bound of the space
107         * @param max
108         *            The maximum bound of the space
109         */
110        public IntHyperplaneL1Factory(int ndims, MersenneTwister rng, int min, int max) {
111                super(ndims, rng);
112
113                this.min = min;
114                this.max = max;
115        }
116
117        @Override
118        public Function create() {
119                return new Function(ndims, rng);
120        }
121
122        @Override
123        protected IntFVComparison fvDistanceFunction() {
124                return IntFVComparison.CITY_BLOCK;
125        }
126}